哪个更好？malloc一个指向结构体的指针数组，还是结构体数组？

Question

我一直对此很感兴趣，当在数组内使用结构体时，就内存分配而言，是为每个条目分配一个新的结构体更好，还是为 N 个结构体在数组中分配足够的空间更好。

//pointer based:
struct myStructure ** tmp = malloc(sizeof(struct myStructure *) * N);
tmp[0] = malloc(sizeof(struct myStructure));
tmp[0]->whatever = true;

//or structure in the array:
struct myStructure * tmp = malloc(sizeof(struct myStructure) * N);
tmp[0].whatever = true

这两种方法有哪些优势？我觉得使用第二种方法是更好的实践，因为你最终会减少较少的小型 malloc 调用，但也可能存在只能使用第一种方法的情况。

对此有什么见解吗？

谢谢！

- gngrwzrd

Answer 1

一般来说，我会使用第二种方法，因为如果您使用所有插槽，它会带来以下优点：

• 它使用稍微较少的内存（指针大小的N倍）；
• 堆碎片化较少；
• 避免了对malloc/free的N次调用（=>更快且更简单地分配/释放）；
• 访问每个结构时避免双重间接引用（非常小的改进）。

另一方面，如果您不会使用数组的所有插槽（但必须能够按需存储许多structs），并且您的struct非常大，那么使用第一种方法可能更加方便，因此保存该内存值得一试。此外，如果您需要便宜地更改struct的顺序（尽管您也可以使用指针的一个独立数组通过第二种方法完成此操作）。

- Matteo Italia

Answer 2

通常情况下，第二种方法更好 [在我看来] - 它可能会更便宜 [无论是内存还是时间]，并且维护起来肯定更容易。

然而，在某些情况下，第二种方法可能会失败 - 当第一种方法成功时。这可能是由于内存碎片 - 你的所有结构体都有足够的内存，只是它们不在内存的“一个位置”上。

- amit

Answer 3

目前已有三个很好的回答说明为什么应该使用第二种方法，所以我不会重复他们的回答。但我想说第一种方法有几个优点：

• 根据系统的实际需要，第一个数组要增长或缩小都容易得多。增加指针数组的大小非常容易——每个元素总共只有4或8个字节长，因此将数组大小加倍并不会花费太多空间。

  而第二个结构体数组可能要大得多（由于元素数量乘以struct foo的大小），即使略微增加数组大小也可能会耗尽内存，如果realloc(3)没有足够的空间来处理。

• 第一个数组使您能够通过“句柄”引用系统中的对象，并根据需要重新排列它们的内存。您可以在页面大小的slabs中分配基础对象，并向近乎满的slab重新压缩对象，从而允许您稍后将页面返回给操作系统供其他用途使用。系统中的其他对象必须通过另一层间接寻址才能访问引用的对象，但是当您移动对象时，这些客户端对象（“引用”？）不需要更新其指针。

• 第一个数组中对象的生命周期是“解耦”的，其中一些对象可能会存活很长时间，而其他对象可能只会存活几毫秒。在第二个数组中，整个数组的生命周期相同。您可以添加另一个数据结构来管理哪些对象是活动的，哪些对象是死亡的，或者在结构体中添加新字段以指示哪些对象是活动的和死亡的，但是这两种方法都需要更多的工作。对于第一个数组，如果指针非NULL，则该对象是活动的。

这两种方法各有优点。选择适合手头工作的方法。

- sarnold

Answer 4

在数组中使用结构通常更好；除非你有理由使用其他形式。

从代码正确性的角度来看，你应该处理malloc()失败的情况。如果你在循环中有1000个malloc()，你更有可能在错误处理代码中出现编程错误。同样，如果你的数据结构更复杂，你更有可能泄漏一些东西。因此，单个malloc()更容易。

从分配速度的角度来看，malloc()显然需要时间运行，所以单个malloc()通常会更快。

从内存大小的角度来看，malloc()通常在每个分配上都有一些开销。而且指针显然是额外的成本。因此，如果你分配了1000个16字节的结构体，你可能会在malloc开销和8字节指针中每个结构体占用16字节，总共40,016字节。进行单个分配只需要占用8,016字节。

从访问速度的角度来看，单个数组很可能更快，特别是如果结构较小或按顺序读取结构。如果结构较小，则多个结构将适合于单个缓存行，因此它们可以作为一组读取/写入。如果按顺序读取结构，则CPU很可能注意到对大数组的线性访问并将其预加载到缓存中。如果使用指针数组和单独的分配，则内存布局更随机，这些优化都不起作用。此外，由于要访问更多数据（指针），算法会更早地从数据缓存中掉出。

从内存碎片角度来看，情况因情况而异。如果您拥有足够大的结构（占用您总RAM的相当部分），则可能会出现这样的情况：没有足够的连续可用内存来分配一个大数组，但是有足够的内存来分配指针数组和单个结构。（例如，如果您在限制您使用2GB内存的操作系统上运行32位程序，并且您的内存分配器已经通过内存的一半分配了其他内容，那么您无法执行单个1.5GB分配，但您可以进行15个100MB的分配）。这种情况很少发生，因为人们通常不使用如此大的数据。

- user9876