哪种内存分配算法最适合于性能和时间关键的C++应用程序？

Question

哪种内存分配算法最适合于性能和时间关键的C++应用程序？

c++memory-managementperformancememory-fragmentation

19

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

教科书上有几种算法（例如伙伴内存分配），但也有其他算法，如TLSF。因此，就可用的内存分配算法而言，哪一种最快且导致的碎片最少。另外，垃圾收集器不应包括在内。

请注意，这个问题不涉及性能分析，只旨在找到满足给定要求的最佳算法。

- baris.aydinoz

还有其他要求吗，比如您将持有物品的时间有多长，您分配/释放的频率以及分配的大小？我对不同算法了解不够，但我可以想象出一些情况，在这些情况下，由于簿记结构的大小、分配/释放算法所涉及的时间开销等因素，这些因素可能是使用一种分配方法而不是另一种分配方法的决定性因素。 - Merlyn Morgan-Graham

@Merlyn Morgan-Graham 最小的执行时间和内存碎片化是最重要的要求。其他方面，在这一点上可以被舍弃。 - baris.aydinoz

3

不把这变成一个回答因为这是一个陈词滥调，但是：使用默认设置。如果（_如果_）性能成为问题，请进行性能分析。只有当证明内存分配成为瓶颈时，才会对内存分配进行调整。 - MSalters

2

需要记住的一件事是，虽然视频游戏具有实时交互性，但这并不意味着它们具有与实时应用程序相同的要求（根据整个行业的定义）。例如，在实际的实时程序中，如果可以保证分配将在最大处理器周期数下完成，则可以允许更高的平均执行时间。视频游戏优化往往涉及最小化或完全避免分配，或者仅仅减少平均运行时间，而不是试图给出一个周期计数保证。 - Merlyn Morgan-Graham

我提及这一点的原因是因为有些人在回答中提到了“实时”。但实际上，我并没有在你的问题中看到“实时”这个词。 - Merlyn Morgan-Graham

曾经有一个时期，人们关注实时性能和碎片化问题。 - Max Lybbert

5个回答

6

Barış:

你的问题很笼统，但这是我的答案/指导：

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

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

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

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

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

在大多数关键系统中，您不能开始动态分配任何内存。您分析您的要求并确定您的最大内存使用量，并在应用程序启动时分配一个大块内存。如果您不能，则应用程序甚至不会启动，如果它确实启动了，在执行过程中不会分配任何新的内存块。

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

至于一些例子：VxWorks RTOS曾经采用一种首次适配分配算法，其中算法分析链表以找到足够大的空闲块。在VxWorks 6中，他们使用最佳匹配算法，其中空闲空间保留在树中，分配遍历树以找到足够大的空闲块。有一篇名为“Memory Allocation in VxWorks 6.0”的白皮书，作者是Zoltan Laszlo，您可以通过谷歌搜索找到更多细节。

回到你关于速度/碎片化的问题：这实际上取决于你的应用程序。要考虑的事情包括：

您将进行许多非常小的分配，还是相对较大的分配？
分配会突然出现，还是在应用程序中平均分布？
分配的生命周期是多长？

如果您之所以提出这个问题是因为您将实现自己的分配器，那么您应该设计它的方式，以便您可以更改底层的分配/释放算法，因为如果速度/碎片化对您的应用程序真的很关键，您会想尝试不同的分配器。如果我不知道您的任何要求就要推荐一些东西，我会从TLSF开始，因为它具有良好的整体特性。

- SomethingBetter

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

因此，没有“最好的算法”。

- wonder.mice

谢谢回复，但这个问题与分析无关，而是关于给定要求的最佳内存分配算法。 - baris.aydinoz

1

好的，那么请将我的基于池的实现视为最快的，因为它符合您的要求 :) - wonder.mice

@baris_a：这个问题可能不是关于性能分析的。正如你从迄今为止的答案中推断出的那样，性能分析是必不可少的，因为并没有“一刀切”的最佳解决方案。这就像买衣服：如果你不测量，你注定会得到一些不适合你的东西。 - MSalters

1

@baris_a：游戏中的一个具体例子是，您希望为模型/图像数据和粒子系统中的单个粒子使用不同的分配策略。在粒子系统中，所有对象的大小都相同且微小。而模型/图像数据通常具有可变大小（也许不是纹理，但这取决于游戏），并且始终比单个粒子大得多。模型/图像数据倾向于加载一次，并保持一段时间，而粒子会不断出现和消失。您可能会为每个算法使用不同的子分配器。 - Merlyn Morgan-Graham

4

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

以下是我从游戏开发经验中提出的一些提示：

尽量避免分配

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

内存分配器库

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

多线程

有一种特殊情况，在这种情况下，您会发现“默认”操作系统/CRT分配器表现不佳，那就是多线程。如果您的目标是Windows，请注意Microsoft提供的操作系统和CRT分配器（包括否则出色的Low Fragmentation Heap）当前都是阻塞的。如果您想执行重要的线程操作，则需要尽可能减少分配或使用一些替代方案。请参见Can multithreading speed up memory allocation?

- Suma

1

值得一提的一个限制，尚未提及的是多线程：标准分配器必须实现以支持多个线程，所有线程都可以同时分配/释放，并将对象从一个线程传递到另一个线程，以便由不同的线程进行释放。

正如您从该描述中猜测的那样，实现处理所有这些的分配器是一项棘手的任务。而且，这会损失性能，因为不可能在没有线程间通信（=使用原子变量和锁）的情况下满足所有这些约束条件，这是相当昂贵的。

因此，如果您可以避免在分配中使用并发，那么您就有很大机会实现自己的分配器，其性能显着优于标准分配器：我曾经自己做过这件事，并且用基于许多固定大小内存池的相对简单的分配器为小对象堆栈化空闲对象，使用了一个侵入式链接列表，每次分配可节省大约250个CPU周期。

当然，避免并发可能对您来说不可行，但如果您不使用它，利用这一事实可能值得考虑。

- cmaster - reinstate monica

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Max Lybbert · Accepted Answer

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

如果有一种内存分配算法总是最佳性能和最小碎片化，那么实现malloc和new的人员难道不会选择这种算法吗？

现在，通常最好假设编写操作系统和运行时库的人员并非白痴；除非您具有某些异常的内存访问模式，否则请勿试图超越他们。

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

许多人来自那些new只表示“给我一个对象”的语言，就会毫无理由地分配东西。如果您不必将其放在堆上，请勿调用new。

至于碎片化：仍然取决于情况。不幸的是，我现在找不到链接，但我记得有一篇来自微软某个人员的博客文章，他曾经处理过一种C++服务器应用程序，该应用程序受到了内存碎片化的影响。该团队通过从两个区域分配内存来解决了这个问题。所有请求的内存都将来自区域A，直到它满为止（请求将像往常一样释放内存）。当区域A已满时，将从区域B分配所有内存。当区域B也满时，区域A再次完全为空。这解决了他们的碎片化问题。

这会解决你的问题吗？我不确定。你正在开展一个为多个独立请求提供服务的项目吗？是在开发游戏吗？

至于确定性：这仍然取决于情况。你的截止日期是什么时候？如果错过了截止日期会发生什么（宇航员在太空中迷失吗？播放的音乐开始听起来像垃圾？）？有实时分配器，但要记住：“实时”意味着“承诺满足截止日期”，不一定意味着“快速”。

我刚看到一篇文章，介绍了Facebook在jemalloc中加速和减少内存碎片的各种措施。您可能会发现该讨论很有趣。