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

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);

VS：

...
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。

Answer 2

你想这样做的原因是如果你需要保证一致的分配时间(其中' consistent‘!=’want‘)。最大的例子是游戏或其他绘画操作的绘制循环--对于它来说，不“打呃”比以牺牲一致性为代价获得额外的2FPS要重要得多。

如果您想要的是尽可能快地完成一个操作，Win7 LFH是相当快的，并且已经在为您做这种优化(这篇技巧来自于堆管理器通常很糟糕并且非常慢的日子)。话虽如此，我可能完全错了--总是分析你的工作负载，看看哪些有效，哪些无效。

Answer 3

一般来说，最好是让内存管理器来做这类事情，但在一些极端情况下(例如：许多小的分配和取消分配)可以使用您自己的实现更好地处理。即。您可以抓取一大块内存，并根据需要进行分配/释放。一般来说，这样的情况将是非常简单的情况(例如，您自己的稀疏矩阵实现)，其中您可以应用特定于域的优化，这是标准内存管理器无法做到的。例如：在稀疏矩阵示例中，每个内存块的大小都相同。这使得垃圾收集相对简单--释放的内存块不需要连接--只需要一个简单的“使用中”标志，等等。