优化：在多个对象使用之前预分配一块堆内存 - 收益？

Question

通过提前分配堆内存并增量填充它是否可以大幅提高性能？

考虑下面非常简单的例子：

byte * heapSpace = malloc (1 000 000);
int currentWriteSpot = 0;

struct A {
  int x;
  byte * extraSpace;
  int extraSpaceLength;
};

//a1 needs 10 bytes of extra storage space:
A a1;  
a1.x = 2;
a1.extraSpace = heapSpace + currentWriteSpot;
a1.extraSpaceLength = 10;

currentWriteSpot += 10;

//a2 needs 120 bytes of extra storage space:
A a2;
a2.x = 24;
a2.extraSpace = heapSpace + currentWriteSpot;
a2.extraSpaceLength = 120;

currentWriteSpot += 120;

// ... many more elements added

for ( ... ) {
   //loop contiguously over the allocated elements, manipulating contents stored at "extraSpace"
}

free (heapSpace);

对比：

...
a1.extraSpace = malloc ( 10 );
a2.extraSpace = malloc ( 120 );
a3...
a4...
...

//do stuff

free (a1.extraSpace);
free (a2.extraSpace);
free ...
free ...
free ...

或者这可能只是增加了复杂性而没有显着提高性能？

谢谢各位！

Answer 1

首先，这样做并不会增加复杂性；它减少了它。因为您在操作开始时就已经确定操作malloc是成功的，所以不需要任何进一步的失败检查，这至少需要free检查已经进行的分配，并且可能会逆转对各种对象状态的其他更改。

正如您所指出的，其他好处之一是性能。在多线程程序中，这将是一个更大的问题，其中调用malloc可能会导致锁争用。

也许更重要的好处是避免碎片化。如果整个数据对象是一起分配而不是分成小块，则释放它肯定会将整个大小的可用连续空间返回到空闲内存池，以供以后分配使用。另一方面，如果单独分配每个小块，它们很可能不会连续。

除了减少碎片之外，将所有数据分配为单个连续块还可以避免每次分配的开销（每次分配至少浪费 8-16 字节）并提高数据局部性以实现缓存目的。

顺便说一句，如果您发现这种分配策略过于复杂，您可以尝试创建一些函数来为您处理它，或者使用现有的库，例如 GNU obstack。