我有一个通用的增长缓冲区,用于累积“随机”字符串片段,然后获取结果。 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 的指数增长(搜索“增长策略”)。这仍然是最佳选择吗?
有什么建议吗?您的经验说明了什么?
最佳答案
除非您有充分的理由不这样做,否则指数增长可能是最佳选择。使用 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 .
关于c - 缓冲增长战略,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2269063/