java - 优化 Long.bitCount

Question

我有一个程序正在对 Long.bitCount() 进行大量调用，如此之多以至于它在一个 CPU 内核上占用了 33% 的周期。有没有比 Sun JDK 版本更快的方法来实现它？

我试过了：

这个算法（我认为这正是JDK的实现方式）
^{2 8}到 2 ²²之间的各种大小的查找表（一次查看几位并添加结果）

但是我没有比使用手动展开循环（大约 27% 的 CPU）的 2 ¹⁶条目查找表做得更好的了。
这还能如何针对 Java 进行优化？

注意：这个问题是关于特定于 Java 的优化，但是这个类似的（与语言无关的）问题还有许多其他算法。

score 12 · Accepted Answer

如果您使用的是最新的 x86 CPU，则有一条指令 popcnt。

在最新版本的 Java 中，Long.bitCount() 使用此指令。只需使用 -XX:+UsePopCountInstruction （这是最近版本中的默认值）

但是，在 JRE 6.0_u18 到 7.0_u5 中存在一些错误： https ://bugs.java.com/bugdatabase/view_bug.do?bug_id=7063674

score 4 · Accepted Answer

这似乎是 GPU 可以解决的完美问题之一。它应该能够将您的时间减少几个数量级。

否则我认为你可能不得不在更高的层次上处理它。让多个线程同时处理不同的数据段（我相信你已经这样做了），在收集数据的同时处理数据，围绕多个系统共享工作——类似的事情。

score 4 · Accepted Answer

如果您的机器有一个整数 ALU 可以处理比 64 位的某些倍数更宽的数据（也称为 SIMD，例如 SSE2 或 VMX），您可以一次计算多个 64 位元素的位数。

不幸的是，这将要求您以比 Java 更低级别的语言提供特定于机器的实现。

score 2 · Accepted Answer

我怀疑您的应用程序受内存限制而不是 CPU 限制，即它花费更多时间从内存中获取值而不是计算它们的位。在这种情况下，您应该尝试减小工作集的大小或改进访问局部性以减少缓存未命中（如果算法允许的话）。

score 1 · Accepted Answer

我不是该主题的专家，但如果您没有看过这些页面，它们可能会有所帮助：

http://www.reddit.com/r/programming/comments/84sht/fast_bit_couting_algorithms/

http://www-graphics.stanford.edu/~seander/bithacks.html

您可能还想探索那里的许多图形库，尤其是那些较低级别和/或直接与硬件对话的图形库。

编辑：看起来你可以使用相对较新引入的 POPCNT 指令（在一些最近的 AMD 和 Intel 处理器上可用）来提高潜在的速度，如果你可以选择编写特定于平台的低级代码，并且可以针对该特定架构. http://kent-vandervelden.blogspot.com/2009/10/counting-bits-population-count-and.html和另一篇带有基准的文章：http: //www.strchr.com/crc32_popcnt

score 1 · Accepted Answer

据我了解：

我只会使用 33% 作为指标，因为小方法的分析可以真正改变整体性能。所以我会在一些大数据集上运行算法并查看总时间。我会根据总时间的变化来考虑我的优化效率。我还将包括一个警告阶段，以便 JIT 可以进行优化。

实际上，无论如何，位计数似乎是您算法的关键部分之一……如果您优化所有内容，并设法将所有关键部分的速度提高 10 倍，那么您仍然可以为这部分配置接近 33% 的数据。从本质上讲，这并不坏。

从此链接http://bmagic.sourceforge.net/bmsse2opt.html受到启发，如果我没记错的话，您现在可以尝试使用所有 intel/AMD 处理器中存在的 SSE 指令（否则您总是可以故障回复到 JAVA）。关于这篇文章的一个有趣的部分是……在大多数情况下，无论如何，它是受内存限制的。但我仍然会尝试看看这对你有用。

GPU 将非常适合快速处理（CPU 核心的数百倍）和带宽。主要问题是将数据推送到 CPU 专用内存并返回结果。但是如果你不只是进行位计数而是更多的操作，这可能会带来巨大的收益。

反正没有捷径可走，你必须尝试几种方法，看看什么能带来最大的收益。不要计算百分比，而是花费的总时间。

score 1 · Accepted Answer

我现在正在使用这种方法，它一次交错四个 popcnt 操作。它基于这个 C 实现。

private static final long M0=0x5555555555555555L,
                          M1=0x3333333333333333L,
                          M2=0x0f0f0f0f0f0f0f0fL;
public void store4Tags(long tag0, long tag1, long tag2, long tag3) {
    long count0 = tag0,
         count1 = tag1,
         count2 = tag2,
         count3 = tag3;
    count0 = (count0 & M0) + ((count0 >>> 1) & M0);
    count1 = (count1 & M0) + ((count1 >>> 1) & M0);
    count2 = (count2 & M0) + ((count2 >>> 1) & M0);
    count3 = (count3 & M0) + ((count3 >>> 1) & M0);

    count0 = (count0 & M1) + ((count0 >>> 2) & M1);
    count1 = (count1 & M1) + ((count1 >>> 2) & M1);
    count2 = (count2 & M1) + ((count2 >>> 2) & M1);
    count3 = (count3 & M1) + ((count3 >>> 2) & M1);

    count0 = (count0 + (count0 >>> 4)) & M2;
    count1 = (count1 + (count1 >>> 4)) & M2;
    count2 = (count2 + (count2 >>> 4)) & M2;
    count3 = (count3 + (count3 >>> 4)) & M2;

    count0 += count0 >>> 8;
    count1 += count1 >>> 8;
    count2 += count2 >>> 8;
    count3 += count3 >>> 8;

    count0 += count0 >>> 16;
    count1 += count1 >>> 16;
    count2 += count2 >>> 16;
    count3 += count3 >>> 16;

    count0 += count0 >>> 32;
    count1 += count1 >>> 32;
    count2 += count2 >>> 32;
    count3 += count3 >>> 32;

    storeWithPopCnt(tag0, 0x3f & (int) count0);
    storeWithPopCnt(tag1, 0x3f & (int) count1);
    storeWithPopCnt(tag2, 0x3f & (int) count2);
    storeWithPopCnt(tag3, 0x3f & (int) count3);
}

这稍微优于查找表版本，并且不消耗缓存。

score 0 · Accepted Answer

与其优化此功能，不如优化此功能的使用。例如，您可以保留一个柜台。

public void set(int n) {
   if(!get(n)) bitCount++;
   // set the bit
}
public void clear(int n) {
   if(get(n)) bitCount--;
   // clear the bit
}
public int bitCount() {
   return bitCount;
}

这通过跟踪设置的位数来避免扫描数据。这将开销转移到位和设置或清除的频率上，并使设置位的数量变得微不足道。它出现在您的用例中，后者更常见。

java - 优化 Long.bitCount

8 回答 8

Related

Reference