Java JDK BitSet 与 Lucene OpenBitSet

Question

我试图实现一个 BloomFilter 并且遇到了一些关于 BitSets 的讨论。 Lucene OpenBitSet 声称它在几乎所有操作中都比 Java BitSet 实现更快。

http://grepcode.com/file/repo1.maven.org/maven2/org.apache.lucene/lucene-core/4.10.4/org/apache/lucene/util/OpenBitSet.java#OpenBitSet

我试图查看两种实现的代码。

Java 位集代码

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/BitSet.java#BitSet

在我看来，这两个类都使用一个“long”数组来存储这些位。单个位被映射到特定的数组索引和存储在索引处的“long”值中的位位置。

那么 OpenBitSet 实现在性能方面要好得多的原因是什么？导致这种速度提升的代码有何不同？

Answer 1

好的，这就是你处理这些事情的方式。

当有人用诸如“最大代码重用”、“没有额外的安全性”等常见短语声称他的实现速度提高了 2-3 倍并且没有提供任何真正的基准时，您应该在头脑中举起危险信号。实际上，他们的邮件列表/文档中的所有基准测试都没有源代码并且(根据结果)是手工编写的(因此可能违反了 benchmarking rules )而不是使用 JMH。

在挥手解释为什么某些东西比其他东西更快之前，让我们编写一个基准测试，看看它是否是 真的在发表任何声明之前更快。
基准代码为here :它只是测试大小为 1024 和 1024 * 1024 (~1kk) 的集合的所有基本操作，填充因子为 50%。测试在 Intel Core i7-4870HQ CPU @ 2.50GHz 上运行。分数是吞吐量，越高越好。

整个基准看起来像这样:

  @Benchmark
  public boolean getClassic(BitSetState state) {
      return state.bitSet.get(state.nextIndex);
  }

  @Benchmark
  public boolean getOpen(BitSetState state) {
      return state.openBitSet.get(state.nextIndex);
  }

  @Benchmark
  public boolean getOpenFast(BitSetState state) {
      return state.openBitSet.fastGet(state.nextIndex);
  }

好的，让我们看看结果:

Benchmark                           (setSize)   Mode  Cnt    Score    Error   Units
BitSetBenchmark.andClassic               1024  thrpt    5  109.541 ± 46.361  ops/us
BitSetBenchmark.andOpen                  1024  thrpt    5  111.039 ±  9.648  ops/us
BitSetBenchmark.cardinalityClassic       1024  thrpt    5   93.509 ± 10.943  ops/us
BitSetBenchmark.cardinalityOpen          1024  thrpt    5   29.216 ±  4.824  ops/us
BitSetBenchmark.getClassic               1024  thrpt    5  291.944 ± 46.907  ops/us
BitSetBenchmark.getOpen                  1024  thrpt    5  245.023 ± 75.144  ops/us
BitSetBenchmark.getOpenFast              1024  thrpt    5  228.563 ± 91.933  ops/us
BitSetBenchmark.orClassic                1024  thrpt    5  121.070 ± 12.220  ops/us
BitSetBenchmark.orOpen                   1024  thrpt    5  107.612 ± 16.579  ops/us
BitSetBenchmark.setClassic               1024  thrpt    5  527.291 ± 26.895  ops/us
BitSetBenchmark.setNextClassic           1024  thrpt    5  592.465 ± 34.926  ops/us
BitSetBenchmark.setNextOpen              1024  thrpt    5  575.186 ± 33.459  ops/us
BitSetBenchmark.setOpen                  1024  thrpt    5  527.568 ± 46.240  ops/us
BitSetBenchmark.setOpenFast              1024  thrpt    5  522.131 ± 54.856  ops/us



Benchmark                           (setSize)   Mode  Cnt    Score    Error   Units
BitSetBenchmark.andClassic            1232896  thrpt    5    0.111 ±  0.009  ops/us
BitSetBenchmark.andOpen               1232896  thrpt    5    0.131 ±  0.010  ops/us
BitSetBenchmark.cardinalityClassic    1232896  thrpt    5    0.174 ±  0.012  ops/us
BitSetBenchmark.cardinalityOpen       1232896  thrpt    5    0.049 ±  0.004  ops/us
BitSetBenchmark.getClassic            1232896  thrpt    5  298.027 ± 40.317  ops/us
BitSetBenchmark.getOpen               1232896  thrpt    5  243.472 ± 87.491  ops/us
BitSetBenchmark.getOpenFast           1232896  thrpt    5  248.743 ± 79.071  ops/us
BitSetBenchmark.orClassic             1232896  thrpt    5    0.135 ±  0.017  ops/us
BitSetBenchmark.orOpen                1232896  thrpt    5    0.131 ±  0.021  ops/us
BitSetBenchmark.setClassic            1232896  thrpt    5  525.137 ± 11.849  ops/us
BitSetBenchmark.setNextClassic        1232896  thrpt    5  597.890 ± 51.158  ops/us
BitSetBenchmark.setNextOpen           1232896  thrpt    5  485.154 ± 63.016  ops/us
BitSetBenchmark.setOpen               1232896  thrpt    5  524.989 ± 27.977  ops/us
BitSetBenchmark.setOpenFast           1232896  thrpt    5  532.943 ± 74.671  ops/us

令人惊讶，不是吗？我们可以从结果中学到什么？

Get 和 set(包括快速版本)在性能方面是相等的。他们的结果位于相同的错误范围内，如果没有适当的纳米基准测试，很难分辨出任何差异，因此在典型的应用程序实现中使用 bitset 没有任何区别，如果分支无关紧要，则更重要。所以关于OpenBitSet的声明获取/设置更好的性能是 假 . UPD:get 方法的 nanobenchmark 也没有显示任何差异，结果是 here .

BitSet的基数可以更快地计算(1k 和 1kk 大小的约 3 倍)，所以关于“超快基数”的声明是 假 .但是如果没有实际回答为什么性能不同，数字就毫无意义，所以让我们深入挖掘一下。计算字中的位数 BitSet用途 Long#bitCount这是热点intrinsic .这意味着整个bitCount方法将被编译成单个指令(对于奇怪的指令，它将是 x86 popcnt )。虽然 OpenBitSet使用来自 Hacker's Delight 的技巧手动滚动位计数(参见 org.apache.lucene.util.BitUtil#pop_array)。难怪为什么经典版现在更快了。

像和/或这样的组设置方法都是相同的，所以这里没有性能优势。但有趣的是:BitSet实现跟踪单词的最大索引，其中至少设置了一位，并且仅在 [0, maxIndex] 范围内执行和/或/基数运算，因此我们可以比较特定情况，当 set 只有前 1/10/50% 位时设置，其余的不是(给定部分的填充因子相同 50%)。然后BitSet性能应该有所不同，而 OpenBitSet保持原样。让我们验证( benchmark code ):

Benchmark                   (fillFactor)  (setSize)   Mode  Cnt   Score    Error   Units
BitSetBenchmark.andClassic          0.01    1232896  thrpt    5  32.036 ±  1.320  ops/us
BitSetBenchmark.andClassic           0.1    1232896  thrpt    5   3.824 ±  0.896  ops/us
BitSetBenchmark.andClassic           0.5    1232896  thrpt    5   0.330 ±  0.027  ops/us
BitSetBenchmark.andClassic             1    1232896  thrpt    5   0.140 ±  0.017  ops/us
BitSetBenchmark.andOpen             0.01    1232896  thrpt    5   0.142 ±  0.008  ops/us
BitSetBenchmark.andOpen              0.1    1232896  thrpt    5   0.128 ±  0.015  ops/us
BitSetBenchmark.andOpen              0.5    1232896  thrpt    5   0.112 ±  0.015  ops/us
BitSetBenchmark.andOpen                1    1232896  thrpt    5   0.132 ±  0.018  ops/us
BitSetBenchmark.orClassic           0.01    1232896  thrpt    5  27.826 ± 13.312  ops/us
BitSetBenchmark.orClassic            0.1    1232896  thrpt    5   3.727 ±  1.161  ops/us
BitSetBenchmark.orClassic            0.5    1232896  thrpt    5   0.342 ±  0.022  ops/us
BitSetBenchmark.orClassic              1    1232896  thrpt    5   0.133 ±  0.021  ops/us
BitSetBenchmark.orOpen              0.01    1232896  thrpt    5   0.133 ±  0.009  ops/us
BitSetBenchmark.orOpen               0.1    1232896  thrpt    5   0.118 ±  0.007  ops/us
BitSetBenchmark.orOpen               0.5    1232896  thrpt    5   0.127 ±  0.018  ops/us
BitSetBenchmark.orOpen                 1    1232896  thrpt    5   0.148 ±  0.023  ops/us

set 的下半部分被填满，速度越快 BitSet是并且当位均匀分布时，则 BitSet 的性能和 OpenBitSet变得相等，理论得到证实。所以对于特定的非均匀集合位分布经典 BitSet组操作更快。关于 OpenBitSet 中非常快速的组操作的声明是 假 .

概括

此答案和基准测试无意表明 OpenBitSet不好或者作者是骗子。事实上，根据他们的基准机器(AMD Opteron 和 Pentium 4)和 Java 版本 (1.5) 很容易相信 更早的 BitSet优化较少，Hotspot 编译器不是很智能， popcnt指令不存在，然后 OpenBitSet是个好主意，而且性能更高。此外， BitSet不公开其内部字数组，因此无法创建自定义的细粒度同步位集或灵活的序列化，而这正是 Lucene 所需要的。所以对于 Lucene 来说，它仍然是一个合理的选择，而对于典型用户来说，最好使用标准 BitSet ，它更快(在某些情况下，不普遍)并且属于标准库。时间变化，旧的性能结果发生变化，因此始终对您的特定情况进行基准测试和验证，可能针对其中一些(例如，未进行基准测试的迭代器或不同的设置填充因子) OpenBitSet会更快。