为动态数据结构预分配内存空间

Question

5

我有一个问题/好奇心，假设我想实现一个列表，例如基本上可以使用Cormen书的方法。书中解释了如何实现、插入、删除、关键字搜索等操作。

然而，在内存使用方面却没有说什么。例如，如果我想在整数列表中插入一个整数。我可以首先创建一个节点（在那里分配内存），插入整数，然后将节点插入列表中。如果我想要删除一个整数，一旦我知道它存储在哪个节点中，就必须释放内存。

我现在在想，预分配内存以存储10个节点并保持指向可用节点的指针是否更方便。如果内存池已满，则为20个节点重新分配内存，如果池越大，则将其大小减半（依此类推）。当然，内存池更复杂，因为我需要处理可能的内存碎片等问题。

我所说的有任何意义吗？还是没有意义？我曾在游戏编程书中读到，内存预分配可以提高性能，但我想知道如何做到这一点。

- user8469759

2

这种方式没有按需分配/释放内存方便，但效率要高得多。是的，这很有道理。在算法全部固定后，几乎所有优化都归结为内存管理（不仅仅是内存来自哪里，还包括使用方式，例如缓存感知优化）。 - Cameron

1

如果有很多分配，内存池是一个好的选择。但如果只有很少的分配，则会增加负担。此外，现代的内存分配子系统都使用某种形式的内存池。 - GMichael

优化中常用的一种技术是不使用列表而使用数组。列表不是高效的数据结构。也可以使用节点数组而不是列表。另请参见B-Tree。 - Thomas Matthews

这将是一个侵入式的列表还是非侵入式的列表？ - kfsone

“Cormen书”是指这本书吗？ - chux - Reinstate Monica

显示剩余5条评论

2个回答

0

我现在在想，如果预先分配内存来存储10个节点，并保留一个指向可用节点的指针，是否更方便。

基本上，您正在描述池分配器通常所做的事情（我假设您正在谈论常量大小的节点）。因此，对于您的问题的简短答案是：使用带有列表容器的池分配器可以提高性能。

随着常见编译器附带的内存分配器非常适合一般目的的分配（即用于随机大小对象的分配）。但是，当您需要分配常量大小的对象时，应考虑使用自定义池分配器。您可以轻松理解为什么常量大小对象分配器比标准分配器执行得更快。

您可以编写自己的池分配器，但这不是一项易于完成的任务，最好考虑使用现有的池分配器，例如boost pool_allocator或fast_pool_allocator。

- shrike

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

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

- buld0zzr · Accepted Answer

这既是一个简单又是一个复杂的问题。如果您在标准问题范围内操作，就不需要担心内存分配。例如，为10个节点预分配内存在任何规模下都不会有效率，而您的性能问题可能出现在其他地方。然而，如果您的程序每秒不断地分配和释放数百或数千个小对象，可能会导致内存碎片，并且您可能需要编写自定义分配器。

几乎没有标准容器没有任何方法来预分配元素存储，除了std::vector::reserve函数。所有容器都允许在构造函数中使用自定义分配器。此外，还有placement new运算符。

您可以尝试进行此类实验，它们很有趣，但如果绝对不必要，请勿在生产中使用它们。