缓冲增长策略

我有一个通用的增长缓冲区，用于累积“随机”字符串片段，然后获取结果。 处理该缓冲区的代码用简单的C编写。

伪代码API：

void write(buffer_t * buf, const unsigned char * bytes, size_t len);/* appends */ const unsigned char * buffer(buffer_t * buf);/* returns accumulated data */ 

我正在考虑应该为缓冲区选择的增长策略。

我不知道我的用户是喜欢内存还是速度 – 或者用户数据的性质是什么。

我已经看到了两种策略：按固定大小增量增长缓冲区（这是我目前正在实现的）或以指数方式增长数据。 （还有一种策略来分配所需的确切内存量 – 但在我的情况下这并不是那么有趣。）

也许我应该让用户选择策略……但这会让代码变得更复杂……

曾几何时，Herb Sutter 写道 （引用Andrew Koenig），最好的策略可能是因子1.5指数增长（寻找“成长策略”）。 这还是最好的选择吗？

任何建议？ 你的经历说什么？

Answer 1

除非你有充分的理由不这样做，指数增长可能是最好的选择。 使用1.5作为指数并不是真正神奇，实际上这不是Andrew Koenig最初所说的。 他最初说的是增长因子应该小于（1 + sqrt（5））/ 2（~1.6）。

Pete Becker说，当他在Dinkumware时，Dinkumware的老板PJ Plauger说他们做了一些测试，发现1.5运行良好。 当你分配一块内存时，分配器通常会分配一个至少比你要求的块稍大的块，以便为一些小书保存信息提供空间。 我的猜测（虽然没有经过任何测试证实）是减少一点因素让真正的块大小仍然适合极限。

参考文献：我相信安德鲁最初是在一本杂志（IIRC 的面向对象编程期刊）上发表的，这本杂志多年来一直没有出版，所以重新打印可能会非常困难。

Andrew Koenig的Usenetpost和PJ Plauger的Usenetpost 。

Answer 2

在整个STL中使用指数增长策略，它似乎工作正常。 至少在你找到一个不起作用的明确案例之前，我会坚持这样做。

Answer 3

我通常使用一个小的固定量和乘以1.5的组合，因为它很有效，并且导致合理的步长，当缓冲区增长时，它们首先更大并且记忆更敏感。 作为固定偏移量，我通常使用缓冲区的初始大小，并从相当小的初始大小开始：

 new_size = old_size + ( old_size >> 1 ) + initial_size; 

作为initial_size，我将4用于集合类型，8,12或16用于字符串类型，128到4096用于输入/输出缓冲区，具体取决于上下文。

这是一个小图表，显示在早期步骤中增长得快得多（黄色+红色），而仅乘以1.5（红色）。

因此，如果您从100开始，则需要例如6个增加以容纳3000个元素，而单独乘以1.5则需要9个。

在较大的尺寸下，添加的影响可以忽略不计，这使得两种方法同样适用于1.5倍。 如果您使用初始大小作为添加的固定金额，这些是有效的增​​长因素：

 2.5 1.9 1.7 1.62 1.57 1.54 1.53 1.52 1.51 1.5 ... 

Answer 4

关键点在于指数增长策略允许您在达到某些浪费内存的成本时达到当前大小时避免使用昂贵的缓冲区内容副本 。 您链接的文章包含交易的数字。

Answer 5

答案一如既往地“依赖”。

指数增长背后的想法 – 即分配一个x当前大小的新缓冲区是因为你需要更多的缓冲区，你需要更多的缓冲区，你可能需要比一个小的固定增量更多的缓冲区提供。

所以，如果你有一个8字节的缓冲区，并且需要更多分配额外的8个字节就可以了，那么分配额外的16个字节可能是一个好主意 – 拥有16字节缓冲区的人不太可能需要额外的1个字节。 如果他们这样做，那么所发生的一切就是浪费一点点记忆。

我认为最好的增长因素是2 – 即你的缓冲区加倍，但如果Koenig / Sutter说1.5是最佳的，那么我同意他们的意见。 您可能希望在获得一些使用情况统计数据后调整您的增长率。

因此，指数增长是性能与保持低内存使用之间的良好折衷。

Answer 6

• 将尺寸加倍，直到达到阈值（~100MB？），然后将指数增长降低到1.5，…，1.3
• 另一种选择是使默认缓冲区大小在运行时可配置。

Answer 7

如果不了解分配，运行时环境，执行特性等等，任何人都无法提供好的建议。

有效的代码比高度优化的代码更重要……正在开发中。 选择一些算法 – 任何可行的算法 – 并尝试一下！ 如果它certificate不是最理想的，那么改变策略。 将其置于库用户的控制之下通常对他们没有好处。 但是如果你已经有一些选项方案，那么添加它可能很有用，除非你找到一个好的算法（并且n ^ 1.5是一个非常好的算法）。

---

此外，在C（而不是C ++）中使用名为write的函数与和冲突。 如果没有使用它们就没关系了，但是以后也很难添加它们。 最好使用更具描述性的名称。

Answer 8

使用指数增长（无论因子是1.5还是2）的关键是避免复制。 每次重新分配数组时，都可以触发项目的隐式副本，当然，它会越大，它就越大。 通过使用指数增长，您可以得到一个摊销的固定数量的重新复制 – 即您很少会最终复制。

只要您在某种类型的台式计算机上运行，​​您就可以获得基本上无限量的内存，因此时间可能是这种权衡的正确方面。 对于硬实时系统，您可能希望找到一种完全避免副本的方法 – 想到链接列表。

Answer 9

对于这种特殊情况，您可以更改API以要求调用者为每个块分配内存，然后记住块而不是复制数据。

然后，当实际生成结果时，您确切地知道需要多少内存并且可以准确分配。

这样做的好处是，调用者无论如何都需要为块分配内存，因此您也可以使用它。 这也避免了多次复制数据。

它的缺点是调用者必须动态分配每个块。 为了解决这个问题，您可以为每个块分配内存，并记住这些内存，而不是保留一个大缓冲区，当缓冲区变满时会resize。 这样，您将复制数据两次（一次进入您分配的块，另一次复制到结果字符串中），但不会再复制数据。 如果您需要多次resize，最终可能会有两个以上的副本。

此外，存储器分配器可能难以找到非常大的空闲存储器区域。 分配较小的块可能更容易。 一千兆字节的内存可能没有空间，但可能有一千兆字节的空间。