9

我一直听说内存池在分配内存时可以显着提高性能。那么为什么传统的 malloc 实现不以某种方式使用它们呢？

我知道部分原因是内存池使用固定大小的内存块，但似乎有些没有，他们唯一需要的就是提前获取一些额外的内存。有没有一种方法可以将它们充分概括用于此类目的？

4

3 回答 3

6

内存池可能比通用内存分配更有效，但通常只是因为您有关于分配模式的额外信息。也许它们最重要的特性是它们的运行时间是确定性的，例如在实时操作系统中尤其重要。

例如，我曾经编写过一个嵌入式系统，我知道需要的最大分配是 128 字节（以下称为块）。为此，我维护了一组连续的块，并使用一个映射来决定一个块是否空闲。

它最初是一个位图，但我们最终只需将每个已使用/未使用的标志存储在一个单独的字节中即可获得更高的性能。地图的内存使用量是地图的八倍，但是，由于池大小是已知的并且合理有限（一千左右），这还不算太糟糕。它给了我们更快的速度，因为我们不必费力地进行池管理。

我们还添加了其他优化，例如存储第一个空闲块，以便我们可以快速找到它。它易于维护，因为：

  • 释放低于当前最低值的块只会更新最低值；和
  • 分配最低块只会增加最低块 - 虽然这并不能保证它指向一个空闲块，但它仍然会使搜索更快，并避免可能不必要的分配搜索（例如，如果你首先释放了一个块低于你刚刚分配的那个）。

然后，如果您要求超过块大小，它会返回 NULL（这在该系统中从未发生过，但出于偏执，我为它编写了代码以防万一）。如果您要求的东西可以放入一个块中，那么无论如何您都会得到一个完整的块（但是，当然，您仍然应该只使用您要求的内存，以防我以后想更改块大小或从单独的具有不同块大小的池）。

事实证明，这比当时的通用分配器要快得多，因为它们必须处理不同的请求大小并担心在释放内存时合并连续的空闲块等事情。

但它需要额外的知识，即没有分配会超过块大小的事实。

另一种模型是为低于特定大小的请求设置一个池，但如果出现以下任一情况，则恢复为一般分配：

  • 您请求的块超出了块大小；或者
  • 池目前已用尽。

在大多数情况下，这可以让您获得额外的效率（当然取决于您的分配模式），但允许分配超出此范围。它在每次分配中引入了一些额外的工作，因为您需要评估请求大小和池耗尽，但它仍然可能优于一般情况。

顺便说一句，我记得 Java 字符串中有类似的东西（不确定是否仍然如此，我已经有一段时间没有使用 Java）了。字符串对象分配内部有一个缓冲区用于存储小字符串，但也可以使用该空间来存储单独分配的字符块的指针（如果它大于内部缓冲区）。这减少了可能是大量小字符串的碎片（和取消引用），但如果需要，仍然允许使用更大的字符串。

有趣的是，我曾经在CPython源代码中尝试过一个实验，看看内存池是否可以提高性能，特别是考虑到那里进行的内存分配数量。它使用类似于上面给出的策略，优先从池中分配，但如果请求的大小超出块大小或池已用尽，则恢复为原始策略。

再一次，它有讨论的优化，然后是一些。例如，最后一个释放的块被缓存，因此它可以立即分发而无需对池进行任何搜索，以尝试加速many-times(single-free-then-allocate)模式。

然而，即使有各种优化、池和块大小，它似乎对我编写的一些测试代码的性能没有实质性的影响，这让我相信 CPython 中使用的实际分配器已经相当不错了。

而且，刚读完我几周前买的这本好书(a)，我现在知道为什么我没有取得任何进展。

事实证明，CPython已经进行了大量优化，包括内存池的使用。“内存管理”一章更详细，但它基本上只使用普通分配器（原始域）来获取大块（> 256K）或特定的非对象相关内存。

所有对象，而 Python 几乎就是所有对象 :-)，都来自对象域（除了一些遗留的东西）。

对于此域，它维护自己的堆并分配大小以匹配系统页面大小的区域，mmap如果支持则使用以减少碎片。所有使用过的 arena 都保存在一个双向链表中，空的 arena 保存在一个单链空闲列表中。

在每个 arena 中，创建 4K 个池（因此每个 arena 64 个），一个池只能提供一种大小的分配，当从该池请求第一个分配时锁定。例如，1-16 字节的请求将从服务 16 字节块的池中获得 16 字节的块，33-48 字节的请求将来自服务于 48 字节块的池。

请注意，这是针对块大小为{16, 32, 48, ..., 512}. 32 位系统的块大小集略有不同，{8, 16, 24, 32, ..., 512}.

对于竞技场内的游泳池，它们是：

  • 部分使用，在这种情况下，根据它们的块大小，它们存在于竞技场中的双向链表中。arena 维护池的空闲列表，每个块大小一个。
  • 未使用，在这种情况下，它们存在于池的空闲列表中，能够服务于任何请求大小（尽管一旦锁定，这就是它们被限制的块大小）。
  • 已满，在这种情况下，它们将无法访问，除非取消分配。

请记住，这三个状态之间的转换都会导致池从列表移动到列表。

我不会再详细介绍了，因为你的头可能会爆炸，就像我的几乎一样:-)

简而言之，CPython 对象分配总是针对特定的块大小，最小的一个大于或等于您需要的大小。这些来自提供单个块大小的池（一旦锁定）。这些池存在于为防止碎片化而进行了高度优化的领域中。并且可以根据需要创建竞技场。

可以说，这就是我的小实验没有改进 CPython 的原因：它已经以一种相当复杂但高效的方式进行内存池，而我的拦截尝试malloc根本没有用。

那本书的评论支持我的开场白，即池化内存可以更有效“但通常只是因为你有关于分配模式的额外信息”：

大多数内存分配请求都很小并且大小固定。因为PyObject是16字节，PyASCIIObject是42字节，PyCompactUnicodeObject是72字节，PyLongObject是32字节。

(a) CPython Internals如果您有兴趣，除了我喜欢关于事物如何工作的优秀技术书籍这一事实之外，我没有任何从属关系。

于 2021-05-21T01:55:07.943 回答
2

我编写了内存池，有多种方法和权衡。我相信malloc()不会在幕后使用它们（如果这是真的），因为：

  1. 内存池浪费了内存，因为它们可能（他们经常这样做）使用离散（固定）块大小来提高速度。
    1. 例如：如果您要求12字节，您可能会偷偷获取64字节（假设这是最近的块大小>= 12 字节，并且具有适当的对齐填充），具体取决于内存池的实现。但是， Maybemalloc()会给您16字节，这仅是最近的对齐要求，因此浪费的字节更少。
    2. 请注意，内存池将块分配给最接近的对齐块大小（意味着它必须是 A）对齐和B）您允许分配的有效块大小之一）>=n请求的字节数，而malloc()仅分配给最近的对齐要求（通常alignas(max_align_t)，通常是 8 或 16 字节对齐，具体取决于架构）> =n请求的字节数。
  2. 内存池浪费了内存，因为它们可能（取决于实现）有大的映射数组或哈希表（这里有多种方法和权衡）从n bytes你想要的映射到一个空闲列表链表（对于下一个块大小 >=n字节) 你可以从中提取。

换句话说，就像大多数事情一样，需要权衡取舍。我怀疑 malloc()选择更慢和不确定是为了：

  1. 充分利用您的 RAM，而不是通过给您一个 64 字节（例如）来浪费它，每次您要求 12 字节时阻塞，
  2. 并且没有大量（数十千字节大小）的映射数组，或者您可以分配的最大块大小的奇怪最大大小限制，内存池可能会强制执行。

内存池经常根据您的特定要求和手头的应用程序在速度、RAM 使用、块大小和最大块数方面进行定制。malloc()另一方面，对于给定大小的 RAM ，它必须对所有可能的字节数都通用且通用。它有很多不同的约束和要求。

说了这么多，我正在考虑编写一些称为fast_malloc()和fast_free()通用用途的替代品。他们要么通过使用巨大的映射数组从字节映射到块大小来获得O(1)n分配和释放时间复杂度，要么我可以选择一个使用较少程序空间和/或 RAM 但使用二进制搜索来映射的选项n字节到块大小，因此具有O(log m)时间复杂度，其中m是您可以分配的可能块大小的数量。我什至可以使用它malloc()在内存池用完时在运行时扩展内存池，如果需要的话——但这不应该在微控制器或实时、安全关键、确定性应用程序中完成，在这种情况下，我d 禁用该功能，仅在编译时静态分配，或在运行时初始化时分配一次。

速度说明：

  1. 一个O(log m)时间复杂度（分配是O(log m)，但免费是O(1)）算法可调块大小内存池我写的执行速度是系统的 1x~3xmalloc()（即：我的实现花费了大约 33% 到 100% 的时间），具体取决于允许的块大小和分配的字节数。有关详细信息，请参阅我在此答案下方的评论。
  2. 为了获得最大速度，可以写入一个大型 1:1 映射数组，以在O(1)时间内从n字节（调用 时fast_malloc(n)）直接index映射到包含 {block_size和ptr_to_free_list} 结构的映射数组。这个 1:1 O(N_MAX)大小的映射数组用于映射到另一个O(m)大小的映射数组会执行得更快，但代价是在程序空间/闪存和可能的 RAM 中使用更多的内存，取决于您运行的硬件：微控制器与 PC。

无论如何，确实有可能编写一个在底层使用内存池的fast_malloc()实现，并且具有O(1)分配和空闲时间复杂度，并且如果块大小太大而无法在O(1)中分配，它会在必要时恢复为常规time （即：用于在 where 分配字节），在这种情况下，它只会将调用传递给 regular 。malloc()nn > N_MAXmalloc()

补充阅读：

  1. *****对学习一些内存池分配策略的基础知识很有帮助：http: //dmitrysoshnikov.com/compilers/writing-a-pool-allocator/
  2. 另请参阅这些 Google 搜索：
    1. *****内存池
    2. 可调内存池
    3. 可调块大小内存池
于 2021-06-01T06:27:13.997 回答
2

像往常一样，这一切都取决于。
在这种情况下，它主要取决于您所说的性能。

正如其他人已经说过的，内存池通常比标准malloc和free实现更快，但速度并不是在一般情况下必须考虑的唯一因素。通用分配器不应该提前分配太多数据，直到必要（池通常这样做）并且它应该分配任意大小的块（池通常不这样做）。

内存池在分配大量小块时更有效，尤其是相同大小的块，因为它们可以作为数组分配，所以一堆块有一个公共头而不是每个块的单独头。
另一方面，通常不会全部用完，这可能被视为内存效率的损失。

malloc池在/中可以更快，new因为它们几乎可以立即从预先分配的合适大小的块数组中为您提供一个数据块，而不是搜索要从中切片的合适块。但是，您不能为每个可能的大小都设置一个池，因此通常您获得的块比需要的长一点，这又是一些内存损失。

free它们在/中也可以更快delete，因为它们只是将池中的块标记为已释放，并且不需要寻找相邻块以查看它们是否也空闲，并将新释放的块“粘合”到它们。

于 2021-06-01T06:58:13.207 回答