我正在尝试实现一个堆（带有页眉/页脚的隐式空闲列表）并决定是否应该向它添加填充。添加焊盘的实际好处是什么？我读到它以某种方式减少了碎片，但我真的不明白为什么会这样。此外，我感兴趣的是我可以在时间方面获得什么样的性能优势。
这是否也有助于我的程序中的本地化，它有什么帮助？
我应该将整个块填充为 4 或 8 字节倍数的格式，还是应该填充我的块，不包括页眉和页脚。
忘了提到这是在 linux 中使用 unistd 的 C 实现。
问问题
410 次
2 回答
1
我读到它以某种方式减少了碎片，但我真的不明白为什么会这样。
这是对的。它之所以有效，是因为它设置了分配的最小大小。假设您添加了填充，以便每个块至少为 1kB。这意味着永远不会出现这样的情况：您释放了一块内存，之后进行的分配将不适合新释放的内存，只要新分配的内存最多为 1kB。
通过在一张纸上进行一些简单的实验，您可以很容易地看到这种效果。首先有一个块大小等于你的总内存。当然不会有碎片，但是会浪费很多内存。如果块大小是大小的一半，则基本上是相同的场景，但浪费更少。当我们的块大小是总内存的三分之一时，我们首先会遇到碎片。这将在分配中间块时发生。
简而言之，填充减少了碎片，但需要更多的内存。
我应该将整个块填充为 4 或 8 字节倍数的格式，还是应该填充我的块，不包括页眉和页脚。
如果您以巧妙的方式实现它，那么您将能够通过简单地更改变量来更改填充大小。因此，请找到一种方法来衡量问题并根据您的需要调整填充。
这是否也有助于我的程序中的本地化，它有什么帮助？
这更棘手。它可以双向使用，并且取决于使用堆的程序。但我的直觉表明填充可能会降低局部性。如果是这种情况，这可能会因为缓存未命中而影响性能。
于 2019-11-09T16:33:18.727 回答
1
klutt 的回答给出了你可能需要一些（重要的）填充的原因。但是，您需要一定的最小填充量还有一个原因：对齐。
分配器分配的内存块需要可用于任何数据类型，并且许多数据类型具有某种对齐要求。通常，只是未对齐的数据项会使访问像蛞蝓一样爬行，但某些数据类型可能有硬对齐要求。例如，PPC CPU 根本无法从不能被 16 整除的地址加载向量（16 字节）。这些对齐要求是高度特定于平台的。
因此，您的分配器必须将它返回的任何内存地址对齐到 CPU 所需的最大对齐（在 PPC 的情况下为 16 个字节），并因此将所有内存块填充到这个最小内存量。
将内存分配填充到完整的缓存行（X86-64 上的 64 字节，如果我没记错的话）甚至可能是一个明智的主意，但这不是必需的。
从最小块大小开始，分配器通常将分配填充到 2 或类似的下一个幂，以减少它们需要处理的不同内存块大小的数量。
于 2019-11-09T17:18:22.457 回答