java - Java JDK BitSet与Lucene OpenBitSet

我试图实现一个BloomFilter，并遇到了一些有关BitSet的讨论。 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”数组来存储位。各个位映射到特定的数组索引，并将位的位置存储在索引的“长”值中。

那是什么原因，那么OpenBitSet实现的性能要好得多？导致速度提高的代码差异在哪里？

最佳答案

好的，这就是您处理此类问题的方式。

当有人声称使用“最大代码重用”，“没有额外的安全性”等常用词组的实现速度要快2-3倍，并且没有提供任何实际基准时，您应该提高警惕。实际上，他们的邮件列表/文档中的所有基准测试都没有源代码，而是手动编写(根据结果)(因此可能违反了benchmarking rules)，而不是使用JMH。

在挥手解释为什么某个事物比其他事物更快之前，让我们编写一个基准测试，看看在做任何语句之前是否真的更快。
基准代码为here:它仅对填充率为50％的大小为1024和1024 * 1024(〜1kk)的集合测试所有基本操作。测试在2.50GHz的Intel Core i7-4870HQ CPU上运行。分数就是吞吐量，越高越好。

整个基准看起来像这样:

  @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

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

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

可以更快地计算BitSet的基数(对于1k和1kk大小，约为3倍)，因此有关“超快速基数”的声明为 false 。但是，如果没有实际答案来说明性能为何不同，数字是没有意义的，因此让我们进行一些探讨。要计算单词BitSet中的位数，请使用Long#bitCount，它是Hotspot 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

理论上证实，集合的下部被填充，BitSet更快，并且当比特均匀分布时，BitSet和OpenBitSet的性能变得相等。因此，对于特定的非均匀集位分布，经典的BitSet对于组操作而言更快。关于OpenBitSet中非常快速的组操作的声明为 false 。

概要

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