问2的乘法效率

EN

Andrew Koenig在1998年出版的Journal of Object Orient Programming上发表了一篇关于缓冲区增长策略的文章。不幸的是，我找不到这篇文章的在线副本。

一般来说，指数增长比固定增长更受欢迎。在指数增长中，1.6 (或1.5)的因子是首选的。Koenig在usenet的帖子中谈到了原因

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

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

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

P J Plauger的vector的STL实现(由MSVC使用)基于上面的1.5。

很多C++大人物都在讨论它的完整线索-- http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/6ac1ff5688d6289c/ba558b4924758e2e#ba558b4924758e2e

在JOOP上也有几篇文章谈到了Koenig的文章。

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

有关更多信息，请参阅1998年9月刊

(面向对象编程杂志)上Andrew Koenig的专栏。Koenig还说明了为什么，通常情况下，最佳增长因子不是2，而可能是1.5左右。

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

增长策略使用户能够指定指针向量在需要更多元素的情况下如何增长。尽管在大多数情况下，Andrew Koenig Koe98建议的最佳增长策略，Sut07应该为大多数情况下提供最佳性能，但在某些情况下，不同的方法仍然可以发挥作用。

我不认为这与我使用的系统和优化的代码有关。但是，它将非常依赖于您使用的操作系统和编译器。按照NPE的建议，最好的方法是使用一个简单的基准测试代码。

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

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

您还将使用大量不同的分配来运行更长的会话，以查看块大小是否会影响内存的碎片。

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