19

我问这个问题是为了确定哪种内存分配算法可以为性能关键的应用程序（如游戏引擎或嵌入式应用程序）提供更好的结果。结果实际上取决于内存碎片的百分比和内存请求的时间确定性。

教科书中有几种算法（例如 Buddy 内存分配），但也有其他算法，例如 TLSF。因此，关于可用的内存分配算法，哪一种是最快的并且导致更少的碎片。顺便说一句，不应该包括垃圾收集器。

另请注意，这个问题不是关于分析，它只是为了找出给定要求的最佳算法。

4

5 回答 5

18

这完全取决于应用程序。例如，可以在定义的时刻清除与特定请求相关的所有内存的服务器应用程序将具有与视频游戏不同的内存访问模式。

如果有一种内存分配算法总是最适合性能和碎片，人们不会实现malloc并new总是选择那个算法吗？

如今，通常最好假设编写您的操作系统和运行时库的人并没有脑死亡。除非你有一些不寻常的内存访问模式，否则不要试图打败它们。

相反，请尝试减少您进行的分配（或重新分配）的数量。例如，我经常使用 a std::vector，但如果我提前知道它将有多少个元素，我可以一次性保留所有元素。这比通过多次调用让它“自然”增长要有效得多push_back()。

许多来自new仅仅意味着“给我一个对象”的语言的人会无缘无故地分配东西。如果您不必将其放在堆上，请不要调用new.

至于碎片：它仍然取决于。不幸的是，我现在找不到链接，但我记得 Microsoft 某人曾在 C++ 服务器应用程序上工作过的一篇博文，该应用程序遭受内存碎片的影响。该团队通过从两个区域分配内存解决了这个问题。所有请求的内存都来自区域 A，直到它被填满（请求将正常释放内存）。当区域 A 已满时，将从区域 B 分配所有内存。当区域 B 已满时，区域 A 再次完全为空。这解决了他们的碎片化问题。

它会解决你的问题吗？我不知道。您是否正在从事一个服务多个独立请求的项目？ 你在做游戏吗？

至于决定论：这仍然取决于。你的最后期限是什么时候？当你错过最后期限时会发生什么（宇航员迷失在太空中？正在播放的音乐开始听起来像垃圾？）？有实时分配器，但请记住：“实时”的意思是“承诺在最后期限前完成”，不一定是“快”。

我刚刚看到一篇文章，描述了 Facebook 为加快和减少 jemalloc 的碎片化所做的各种事情。你可能会觉得这个讨论很有趣。

于 2011-02-07T08:23:15.467 回答
6

巴里什：

您的问题非常笼统，但这是我的回答/指导：

我不了解游戏引擎，但对于嵌入式和实时应用程序，分配算法的一般目标是：

1- 有限的执行时间：您必须提前知道最坏情况的分配时间，以便您可以相应地计划您的实时任务。

2- 快速执行：嗯，越快越好，显然

3- 始终分配：特别是对于实时的、安全的关键应用程序，必须满足所有请求。如果你请求一些内存空间并得到一个空指针：麻烦！

4- 减少碎片：虽然这取决于所使用的算法，但由于多种原因，包括缓存效果，通常较少碎片的分配提供更好的性能。

在大多数关键系统中，您一开始就不允许动态分配任何内存。您分析您的需求并确定您的最大内存使用量，并在您的应用程序启动后立即分配大量内存。如果你不能，那么应用程序甚至不会启动，如果它启动了，则在执行期间不会分配新的内存块。

如果速度是一个问题，我建议采用类似的方法。您可以实现一个管理内存的内存池。该池可以在您的应用程序开始时初始化一个“足够”的内存块，并从该块中为您的内存请求提供服务。如果您需要更多内存，则池可以进行另一次 - 可能是大的 - 分配（预计会有更多内存请求），并且您的应用程序可以开始使用这个新分配的内存。周围还有各种内存池方案，管理这些池是另一个完整的主题。

至于一些例子：VxWorks RTOS 过去使用了一种首次拟合分配算法，该算法分析了一个链表以找到一个足够大的空闲块。在 VxWorks 6 中，他们使用了最佳拟合算法，其中空闲空间保存在树中，分配遍历树以获得足够大的空闲块。Memory Allocation in VxWorks 6.0有一份名为Zoltan Laszlo的白皮书，您可以通过 Google 搜索找到该白皮书，其中包含更多详细信息。

回到你关于速度/碎片的问题：这真的取决于你的应用程序。需要考虑的事情是：

  • 你会做很多非常小的分配，还是相对较大的分配？

  • 分配是突发的，还是均匀分布在整个应用程序中？

  • 分配的生命周期是多少？

如果您问这个问题是因为您要实现自己的分配器，那么您可能应该以可以更改底层分配/解除分配算法的方式设计它，因为如果速度/碎片在您的应用程序，您将要尝试使用不同的分配器。如果我在不了解您的任何要求的情况下推荐一些东西，我会从 TLSF 开始，因为它具有良好的整体特性。

于 2011-02-07T09:42:33.533 回答
4

最佳实践是 - 使用任何你可以使用的东西来及时完成事情（在你的情况下 - 默认分配器）。如果整个事情非常复杂 - 编写将模拟整个事情的一部分的测试和示例。然后，运行性能测试和基准以找到瓶颈（可能它们与内存分配无关：）。从这一点上，您将看到究竟是什么减慢了您的代码以及为什么。只有基于如此精确的知识，您才能优化某些东西并选择一种算法而不是另一种算法。没有测试只是浪费时间，因为你甚至无法衡量你的优化会在多大程度上加速你的应用程序（事实上，这种“过早的”优化真的会减慢它的速度）。

内存分配是一件非常复杂的事情，它实际上取决于许多因素。例如，这种分配器既简单又快，但只能在有限的情况下使用：

char pool[MAX_MEMORY_REQUIRED_TO_RENDER_FRAME];
char *poolHead = pool;

void *alloc(size_t sz) { char *p = poolHead; poolHead += sz; return p; }
void free() { poolHead  = pool; }

所以没有“有史以来最好的算法”。

于 2011-02-07T08:42:48.007 回答
4

正如其他人已经写的那样，每个可能的应用程序都没有“最佳算法”。已经证明，对于任何可能的算法，您都可以找到会导致碎片的分配顺序。

下面我写一些我的游戏开发经验的提示：

如果可以的话，避免分配

游戏开发领域的一个常见做法是（并且在某种程度上仍然是）通过避免像瘟疫一样的内存分配来解决动态内存分配性能问题。通常可以使用基于堆栈的内存来代替 - 即使对于动态数组，您通常也可以提供一个估计，该估计将为您涵盖 99% 的情况，并且您只需要在超出此边界时进行分配。另一种常用的方法是“预分配”：估计您在某个函数或某个对象中需要多少内存，创建一种您预先分配的小而简单的“本地堆”，并仅从该堆执行单独的分配。

内存分配器库

另一种选择是使用一些内存分配库 - 它们通常由该领域的专家创建以满足某些特殊要求，如果您有类似的要求，它们可能符合您的要求。

多线程

在一种特殊情况下，您会发现“默认” OS/CRT 分配器性能不佳，那就是多线程。如果您的目标是 Windows，请注意 Microsoft 提供的 OS 和 CRT 分配器（包括其他出色的低碎片堆）当前正在阻塞。如果要执行大量线程，则需要尽可能减少分配，或者使用一些替代方案。请参阅多线程可以加速内存分配吗？

于 2011-02-07T09:08:02.467 回答
0

一个值得一提但尚未提及的约束是多线程：必须实现标准分配器以支持多个线程，所有线程同时分配/解除分配，并将对象从一个线程传递到另一个线程，以便它被不同的线程解除分配线。

正如您可能从该描述中猜到的那样，实现一个能够很好地处理所有这些的分配器是一项棘手的任务。而且它确实具有成本性能，因为如果没有线程间通信（=使用原子变量和锁）就不可能满足所有这些约束，这是相当昂贵的。

因此，如果您可以避免分配中的并发性，那么您就有很好的机会实现自己的分配器，该分配器的性能明显优于标准分配器：我曾经自己做过一次，它使用相当简单的分配器为我每次分配节省了大约 250 个 CPU 周期这是基于一些用于小对象的固定大小的内存池，将空闲对象与侵入式链表堆叠在一起。

当然，避免并发对您来说可能是不可行的，但如果您无论如何都不使用它，那么利用这一事实可能是值得考虑的事情。

于 2017-10-09T19:46:13.523 回答