c - 缓冲增长战略

Question

我有一个通用的增长缓冲区，用于累积“随机”字符串片段，然后获取结果。 Code处理该缓冲区是用纯 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 wrote (引用 Andrew Koenig)最好的策略可能是因子 1.5 的指数增长(搜索“增长策略”)。这仍然是最佳选择吗？

有什么建议吗？您的经验说明了什么？

Answer 1

除非您有充分的理由不这样做，否则指数增长可能是最佳选择。使用 1.5 作为指数并不是真的神奇，事实上，这并不是 Andrew Koenig 最初所说的。他原来说的是增长因子应该小于(1+sqrt(5))/2 (~1.6)。

Pete Becker 在 Dinkumware 工作时说 Dinkumware 的老板 P.J. Plauger 说他们做了一些测试，发现 1.5 运行良好。当您分配一 block 内存时，分配器通常会分配一个至少比您请求的 block 稍大的 block ，以便为一些簿记信息留出空间。我的猜测(尽管未经任何测试证实)是稍微降低该系数可以使实际 block 大小仍然在限制范围内。

引用资料:我相信 Andrew 最初在一本杂志(面向对象编程杂志，IIRC)上发表了这篇文章，该杂志已经多年未出版了，因此重新打印可能会非常困难。

Andrew Koenig's Usenet post , 和 P.J. Plauger's Usenet post .