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

Question

这是出于历史原因吗？我经常看到像 char foo[256]; 或 #define BUF_SIZE 1024 这样的东西。即使我多数情况下只使用2ⁿ大小的缓冲区，主要是因为我认为它看起来更优雅，而且我不必考虑一个具体的数字。但我不确定这是否是大多数人使用它们的原因，希望能够得到更多信息。

- Hoffa

Answer 1

可能有许多原因，虽然很多人只是出于习惯。

在高效实现循环缓冲区时，特别是在没有硬件除法的架构上（主要是8位微控制器），使用2^n缓冲区非常有用。在这种情况下，模数运算就是简单地对上位比特进行位屏蔽，或者例如256字节缓冲区的情况下，仅使用一个8位索引并让其环绕即可。

在其他情况下，与页面边界、缓存等的对齐可能为某些架构提供了优化机会，但这将非常具体于架构。但可能只是这种缓冲区为编译器提供了优化可能性，所以其他条件相等，为什么不呢？

- Clifford

---

一些系统还能够在满足一定条件的情况下进行零拷贝 I/O 到用户空间，其中之一是读/写操作是系统页面大小的倍数。 - nos

Answer 2

缓存行通常是2的倍数（通常为32或64）。大小为该数字的整数倍的数据将能够适应（并充分利用）相应数量的缓存行。您可以将更多数据打包到缓存中，性能就越好...因此，我认为那些以这种方式设计结构的人正在优化性能。

- int3

Answer 3

除了其他人提到的原因之外，还有一个原因是SSE指令可以同时处理多个元素，而且输入的元素数量总是2的幂次方。将缓冲区设为2的幂次方可以确保不会读取未分配的内存。但只有在实际使用SSE指令时才适用。

我认为最终的原因在大多数情况下是程序员喜欢2的幂次方。

- Ray Hidayat

Answer 4

哈希表，分页分配

这对于哈希表非常有帮助，因为你需要对索引取模并将其与大小进行比较。如果大小是2的幂次方，则可以通过简单的按位与或&计算模数，而不是使用实现%操作符的缓慢除法类指令。

查看旧的Intel i386书籍，and指令需要2个时钟周期，而div指令需要40个时钟周期。即使1000倍更快的整体周期时间往往隐藏了最慢的机器操作的影响，但除法的基本复杂性要大得多，因此差距至今仍然存在。

曾经有一段时间，程序员们会尽力避免使用malloc来避免过多的开销。直接从操作系统中获取分配的内存将是（仍然是）特定数量的页面，因此幂次方可能会最大程度地利用分配的粒度。

正如其他人所指出的，程序员喜欢使用2的幂次方。

- DigitalRoss

---

值得注意的是，一些哈希算法建议使用哈希大小等于某个质数而不是2^n，以使其行为更可预测；这些算法通常在理论计算机科学方面具有强大的背景。 - liori

"分配粒度"可能会出现严重问题。如果您的内存分配器有任何每个项目的开销（例如存储分配大小），那么2的幂实际上会最糟糕地利用分配器的粒度。最好忽略这个问题，按照您首先说的选择最方便的大小，希望一切顺利，并在必要时进行特定于平台的优化。或者，如果您想依赖它，可以像许多游戏那样编写自己的分配器以消除所有疑虑。 - Steve Jessop

不仅哈希表使用“取模数组大小”操作 - 循环缓冲区也是另一个例子。 - caf

Answer 5

由于电子学中基于二进制算术的简单性（也可以理解为成本）：左移（乘以2），右移（除以2）。

在CPU领域，许多构造都围绕着基于二进制算术展开。用于访问内存结构的总线（控制和数据）通常按照2的幂对齐。电子学（例如CPU）中逻辑实现的成本使得基于二进制的算术变得引人注目。

当然，如果我们有模拟计算机，情况就会不同了。

---

顺便提一下：位于 X 层的系统属性直接受到其下方系统即第 x-1 层 服务器 层属性的影响。我之所以这样说是因为我发帖时收到了一些关于此问题的评论。

例如，“编译器”级别可以操纵的属性是从它下面的系统即 CPU 中电子器件的属性中继承和派生而来的。

- jldupont

Answer 6

我能想到一些原因：

1. 2^n是计算机尺寸中非常常见的值。这直接与计算机中比特的表示方式相关（有2个可能的值），这意味着变量往往具有范围为2^n的值。
2. 基于上述原因，您会经常发现缓冲区大小为256。这是因为它是可以存储在一个字节中的最大数字。如果您想将字符串与字符串大小一起存储，则最有效的方法是将其存储为：SIZE_BYTE+ARRAY，其中大小字节告诉您数组的大小。这意味着该数组的大小可以从1到256的任何大小。
3. 许多其他情况下，大小是基于物理事物选择的（例如，操作系统可以选择的内存大小与CPU寄存器的大小相关），这些也将是特定数量的位。这意味着您可以使用的内存量通常为2^n的某个值（对于32位系统为2^32）。
4. 这样的值可能会有性能优势/对齐问题。大多数处理器可以一次访问一定量的字节，因此，即使您有一个大小为20位的变量，32位处理器仍将读取32位，不管如何。因此，通常更有效的做法是将变量设置为32位。此外，一些处理器要求变量对齐到一定数量的字节（因为它们无法从内存中读取，例如，内存中地址是奇数的）。当然，有时不是奇怪的存储位置，而是4个、6个或8个等倍数的位置。因此，在这些情况下，更有效的做法是创建将始终对齐的缓冲区。

嗯，这些要点有点乱。如果需要进一步解释，请告诉我，尤其是第四点，我认为它最重要。

- Edan Maor

Answer 7

我本来想使用shift参数，但是无法想出一个好的理由来证明它的必要性。

一个大小为2的幂次方的缓冲区的好处之一是循环缓冲区处理可以使用简单的与运算而不是除法：

#define BUFSIZE 1024

++index;                // increment the index.
index &= BUFSIZE;       // Make sure it stays in the buffer.

如果它不是2的幂，那么就需要进行除法。在旧时代（以及目前在小芯片上）这很重要。

- Richard Pennington

---

我认为你想要的是 index &= BUFSIZE - 1。 - Yuliy

在追求效率的名义下，编写“聪明”的代码却得到错误的答案。 - Roger Pate

你是绝对正确的。它应该是 index %= BUFSIZE，这样在所有情况下都是正确的，并且可以在任何好的编译器中使用 AND 实现。 - Richard Pennington

Answer 8

页面大小通常是2的幂次方，这也很常见。

在Linux上，当像将缓冲区分块并将其写入套接字或文件描述符时，我喜欢使用getpagesize()。

- Sean A.O. Harney

---

常见的情况是你可能看到过不是2的次方的页面大小。我很难相信任何硬件会这样做（我看到的所有页表查找都基于虚拟地址的特定位。剩余的位数必然形成2的次方大小）。 - Bahbar

这取决于你如何计算。 :-) PDP-8有128个字的页面，但是每个字是12位，因此它在字上是2的幂，但不是在位上。 - Ken

我之所以说“通常情况”，是因为我知道肯定会有人找到某些例外的古老架构。因此PDP-8在那种情况下使用了12位CPU？我认为CPU位数始终与字长相同。 - Sean A.O. Harney

1970年代被称为“古老”？该死，我感觉自己老了。那么IBM AS/400呢？直到1995年他们转向PPC之前，它使用48位处理器。21世纪的x86单一文化令人沮丧。 - Ken

谁谈论过x86？powerpc，一些risc，68000...我们也有很多游乐场:D。说真的，我同意你的观点，这取决于你如何计算。我坚持我的评论，即硬件实现者将继续使用位子集来选择页面和/或位子集来选择单个页面内的元素。 - Bahbar

Answer 9

在二进制中它是一个不错的、圆满的数字，就像10、100或1000000在十进制中一样。

如果它不是2的幂（或者像96=64+32或192=128+64这样接近2的幂），那么你可能会想知道为什么要增加精度。非基于2的四舍五入大小可能来自外部限制或程序员的无知。你会想知道是哪个原因导致了这种情况。

其他答案也指出了一些特殊情况下有效的技术原因。我不会在这里重复任何一个。

- laalto

---

在任何进制下，10、100或1000000都是漂亮的圆数。 :) - aib

Answer 10

在哈希表中，2^n使得以某种方式处理关键冲突更容易。通常，在存在关键冲突时，您可以创建一个子结构（例如列表）来存储所有具有相同哈希值的条目；或者找到另一个空闲插槽。您可以将插槽索引加1，直到找到一个空闲插槽；但是，这种策略并不是最优的，因为它会创建一些被阻塞的位置集群。更好的策略是计算第二个哈希数h2，使得gcd(n,h2)=1；然后将h2添加到插槽索引，直到找到一个空闲插槽（带环绕）。如果n是2的幂，则很容易找到满足gcd(n,h2)=1的h2，每个奇数都可以做到。

- Erich Kitzmueller