为什么数据结构的大小通常为2 ^ n？

Question

有历史原因还是什么？我已经看过很多次喜欢char foo[256];或者#define BUF_SIZE 1024.即使我大多只使用2 ⁿ大小的缓冲区,主要是因为我觉得它看起来更优雅,这样我就不必考虑具体的数字了.但我不太确定这是否是大多数人使用它们的原因,更多信息将受到赞赏.

Answer 1

可能有很多原因,尽管很多人会像你说的那样只是出于习惯.

一个非常有用的地方是循环缓冲区的有效实现,特别是在%运算符昂贵的架构上(没有硬件鸿沟的架构 - 主要是8位微控制器).在这种情况下,通过使用2 ^ n缓冲区,模数只是对高位进行位掩码的情况,或者在例如256字节缓冲区的情况下,仅使用8位索引并让它环绕.

在其他情况下,与页面边界,高速缓存等的对齐可能为某些体系结构提供优化机会 - 但这将是非常特定于体系结构的.但可能只是这样的缓冲区为编译器提供了优化的可能性,所以其他所有东西都是相同的,为什么不呢？

Answer 2

缓存行通常是2的倍数(通常为32或64).作为该数字的整数倍的数据将能够适合(并充分利用)相应数量的高速缓存行.您可以将更多数据打包到缓存中,性能越好.所以我认为以这种方式设计其结构的人正在优化.