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 BitSet代码

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倍,并且没有提供任何真正的基准时,你应该提出头脑中的红旗.实际上,他们的邮件列表/文档中的所有基准都没有源代码并且手工编写(根据结果)(因此可能违反基准测试规则)而不是使用JMH.

在挥手为什么比某些东西更快的东西之前让我们写一个基准,看看它在发表任何陈述之前是否真的更快.基准代码在这里:它只测试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

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

• 获取和设置(包括快速版本)在性能方面是相同的.它们的结果存在于相同的误差界限中,如果没有适当的纳米标记,很难说出任何差异,因此在典型应用程序实现中使用bitset方面没有任何区别,如果分支无关紧要,则不会产生任何差异.所以关于OpenBitSet获取/设置更好性能的陈述是错误的.UPD:get方法的nanobenchmark也没有显示任何差异,结果在这里.
• BitSet可以更快地计算基数(对于1k和1kk大小都可以计算~3倍),因此关于"超快基数"的陈述是错误的.但是如果没有实际的答案,为什么性能不同,数字就没有意义了,所以让我们稍微挖掘一下 计算单词BitSet使用Long#bitCount中的位数是Hotspot 内在的.这意味着整个bitCount方法将被编译成单个指令(对于奇怪的指令,它将是x86 popcnt).虽然OpenBitSet使用来自Hacker's Delight的技巧进行手动滚动计数(参见参考资料org.apache.lucene.util.BitUtil#pop_array).难怪为什么经典版本现在更快.

• 组合方法和/或两者都是相同的,所以这里没有表现胜利.但有趣的是:BitSet实现跟踪字的最大索引,其中至少有一个位被设置并且仅在[0,maxIndex]的边界内执行和/或/基数操作,因此我们可以比较特定情况,当设置仅有前1/10时/ 50%位设置,其余不是(给定部分的填充因子相同50%).然后BitSet表现应该不同,同时OpenBitSet保持不变.让我们验证(基准代码):

  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
  

组的下部填充越快BitSet是和当比特均匀地分布,则性能的BitSet和OpenBitSet变成等于,理论证实.因此,对于特定的非均匀设置比特分布,经典BitSet对于组操作更快.关于非常快速的集团运营的声明OpenBitSet是错误的.

摘要

这个答案和基准并不打算表明这OpenBitSet是坏的或作者是骗子.实际上,根据他们的基准测试机器(AMD Opteron和Pentium 4)和Java版本(1.5),很容易相信早期的 BitSet优化程度较低,Hotspot编译器不是很聪明,popcnt指令不存在然后OpenBitSet是一个好主意,性能更高.此外,BitSet不会暴露其内部字数组,因此无法创建自定义的细粒度同步bitset或灵活的序列化,这就是Lucene所需要的.因此对于Lucene而言,它仍然是一个合理的选择,而对于典型的用户来说,使用标准更好BitSet(更快(在某些情况下,通常不是))并且属于标准库.时间变化,旧的性能结果发生变化,所以总是基准测试和验证您的特定情况,可能对其中一些情况(例如,没有基准测试的迭代器或不同的设置填充因子)OpenBitSet会更快.