c++ - 乘以 2 的效率

Question

我应该以几何方式分配内存并将初始大小设置为 1000。当它被填充时，它将扩展到 2000、4000 等等。

我的问题是：如果我将初始大小设置为 2 的乘积，即 1024，在效率或任何其他方面会有什么不同吗？

请不要谈论向量和分配的替代方法，这只是理论上的。

Answer 1

Andrew Koenig 在 1998 年的面向对象编程杂志上发表了一篇关于缓冲区增长策略的文章。不幸的是，我无法找到该文章的在线副本。

一般来说，指数增长优于固定增长。在指数增长中，1.6（或 1.5）的因子是优选的。Koenig 在一篇 usenet 帖子中谈到了原因

http://groups.google.com/group/comp.lang.c++.moderated/msg/ba558b4924758e2e？

偏爱 1.5 到 2 是有技术原因的——更具体地说，偏爱小于 (1+sqrt(5))/2 的值。

假设您使用的是首次拟合内存分配器，并且您正在逐步附加到向量。然后每次重新分配时，分配新内存，复制元素，然后释放旧内存。这留下了一个空白，最终能够使用该内存会很好。如果向量增长太快，对于可用内存来说总是太大。事实证明，如果增长因子 >= (1+sqrt(5))/2，那么新的内存对于到目前为止已经留下的空洞来说总是太大了；如果它是 <(1+sqrt(5))/2，那么新的内存最终会适合。所以 1.5 足够小，可以让内存被回收。

PJ Plauger 的 STL 实现（由 MSVC 使用）vector基于上述使用 1.5。

The full thread where a lot of big C++ guys discuss it - http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/6ac1ff5688d6289c/ba558b4924758e2e#ba558b4924758e2e

Also there are a couple of articles which talk about Koenig's article in JOOP.

1) http://www.gotw.ca/gotw/043.htm

For more information, see Andrew Koenig's column in the September 1998 issue of JOOP (Journal of Object-Oriented Programming). Koenig also shows why, again in general, the best growth factor is not 2 but probably about 1.5.

2) http://www10.informatik.uni-erlangen.de/Publications/TechnicalReports/TechRep09-11.pdf

The growth policy enables the user to specify how a pointer vector grows in case it needs more elements. Although in most cases the optimal growth strategy suggested by Andrew Koenig [Koe98,Sut07] should provide the best performance for most scenarios, in some scenarios a dierent approach can still make a difference.

Answer 2

我认为这与我使用和优化代码的系统无关。但是，这将非常依赖于您使用的操作系统和编译器。正如 NPE 建议的那样，最好的了解方法是一个简单的基准代码。

Answer 3

问题是：为什么你认为使用 2 的幂会有所不同？根据操作系统、使用的内存分配器和其他一些因素，存在差异，唯一合理的方法是针对您的用例对其进行基准测试。

您想要测试的是：计算出您的系统每次分配有多少开销。在某些情况下，当您保留 2 的幂减去开销时，它可能对内存分配器有所帮助。例如，如果开销为 24 字节，则从 1024-24=1000 字节开始。如果需要增加，使用2048-24=2024字节等。

您还将运行具有许多不同分配的更长会话，以查看块大小是否会影响内存碎片。

当然，我不知道这是否（仍然）适用于您的系统。