当内存问题时，何时使用并行计数- MIT HAKMEM进行位计数？

Question

位计数可以通过几种方式来完成，例如。具有设置位迭代器、未设置位迭代器、具有查找表的预计算位或并行计数。正如我通过搜索网络发现的，未设置位迭代器在未设置位较少时速度较快，而设置位迭代器则相反。但是什么时候应该使用并行计数，尤其是麻省理工学院的HAKMEM (见下文)？它看起来相当快，虽然可能比查找表慢。就速度而言，它总是比设置/未设置位更好吗？除了速度和内存，还有没有其他的选择呢？

 int BitCount(unsigned int u) {
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
 }

Answer 1

为什么选择一种而不是另一种位计数方法？这取决于你的机器和你想要解决的问题。请注意，下面我给出的所有指令计数都是针对基本的RISC处理器的，可能不能很好地转换到像x86这样的更复杂的处理器上。

您引用的HAKMEM算法将在13条指令中执行，但由于模运算符的原因，执行速度不太可能很快。通过观察它，它看起来确实有一些非常好的指令级并行性，如果你的处理器能够利用这一点，这应该会有所帮助。

Bo Persson提出的算法非常快(2 + 5*pop(x)指令)，但只有在单词是稀疏填充的情况下。还可以对其进行修改，以处理人口密集的单词。它还包含分支，并且没有任何重要的指令级并行性。

EDIT:表查找方法也可以非常快，但确实会进行内存访问。如果整个表都在L1缓存中，那么它可能是最快的算法之一。如果表不在缓存中，那么它几乎肯定是最慢的表之一。

下面的算法是其中一个HAKMEM算法的变体，并在Hacker's Delight一书中介绍(如果你喜欢这类东西，我强烈推荐这本书)。它在19条指令中执行，并且是无分支的。它也不使用除法，但有乘法。它使用寄存器的方式也非常经济，通过尽可能多地使用相同的掩码。我在这里仍然看不到明显的指令级并行性。

int pop(unsigned x) {
  unsigned n;

  n = (x >> 1) & 0x77777777;
  x = x - n;
  n = (n >> 1) & 0x77777777;
  x = x - n;
  n = (n >> 1) & 0x77777777;
  x = x - n;
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x = x * 0x01010101;
  return x >> 24;
}

Hacker's Delight这本书还为9-8-7位宽的字段或使用浮点运算符提供了几个更专业的算法。请注意，我上面介绍的大部分分析也部分取自那本书。

事实是，有一大堆的方法，唯一的方法是确定哪种方法在你的特定情况下工作得最好，就是测量和比较。我确实意识到这是一个相当简单的答案，但另一种选择是彻底了解你的处理器和编译器。

Answer 2

这非常简单，但如果只设置了几个位，速度会令人惊讶：

int popCount (U64 x) {
   int count = 0;
   while (x) {
       count++;
       x &= x - 1; // reset LS1B
   }
   return count;
}

来自Chess programming wiki: Brian Kernighan's way

Answer 3

如果您有一个支持SSE4的x86CPU，那么您已经有了一条完成所有工作的指令: POPCNT。参见Intel® SSE4 Programming Reference。(PDF，698KB)

另一个备注:像HAKMEM 169这样的并行算法不包含条件分支。这是一个巨大的优势。现代处理器预测条件分支的方向，但在随机分支模式方面存在问题。错误预测的代价非常高(代价可能超过100条指令的等价物)。如果性能很重要，最好避免使用变量循环计数和/或条件语句的循环。有关详细信息，请参阅：

• Intel® 64 and IA-32 Architectures Optimization Reference Manual (PDF，4.5MB)
• Software Optimization Guide for AMD Family 15h Processors (PDF，1.9MB)

我也赞同Hackers Delight一书的建议。