Java JDK BitSet vs Lucene OpenBitSet

performance java lucene bitset

2022-09-03 12:59:52

我试图实现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实现在性能方面要好得多的原因是什么？导致速度提高的代码差异在哪里？

答案 1

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

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

在挥手解释为什么某些东西比其他东西更快之前，让我们写一个基准，看看它是否真的更快，然后再做出任何陈述。基准代码在这里：它只是测试填充因子为50%的大小为1024和1024 * 1024（~1kk）的集合的所有基本操作。测试在英特尔酷睿 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（包括快速版本）在性能方面是相等的。它们的结果位于相同的误差范围内，如果没有适当的纳米基准标记，很难分辨出任何差异，因此在典型应用程序实现中使用位集没有任何区别，如果分支无关紧要，则再有一个区别。因此，关于获取/设置更好的性能的陈述是错误的。UPD：获取方法的纳米基准也没有显示出任何差异，结果在这里。OpenBitSet
的基数可以计算得更快（对于 1k 和 1kk 大小，大约是 3 倍），因此关于“超快速基数”的陈述是错误的。但是，如果没有实际答案，为什么性能会有所不同，数字就毫无意义，所以让我们来挖掘一下。在单词中计算位使用是热点固有的。这意味着整个方法将被编译成单个指令（对于好奇的方法，它将是x86 ）。虽然使用黑客喜悦中的技巧手动滚动位计数（请参阅）。难怪为什么经典版本现在更快。BitSetBitSetLong#bitCountbitCountpopcntOpenBitSetorg.apache.lucene.util.BitUtil#pop_array

像和/或这样的组集方法都是相同的，所以这里没有性能优势。但有趣的是：实现跟踪单词的最大索引，其中至少设置了一个位，并且仅在[0，maxIndex]的范围内执行和/或/基数操作，因此我们可以比较特定情况，当set仅设置了第一个1/10/50%位而其余部分没有（给定部分的填充因子为50%）。然后性能应该有所不同，同时保持相同。让我们验证一下（基准代码）：BitSetBitSetOpenBitSet

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

集合的下半部分被填充，越快，当位均匀分布时，则性能和变得相等，理论证实。因此，对于特定的非均匀集位分布，经典对于组操作更快。关于非常快速的组操作的陈述是错误的。BitSetBitSetOpenBitSetBitSetOpenBitSet

总结

这个答案和基准并不打算表明这是坏事或作者是骗子。事实上，根据他们的基准机器（AMD皓龙和奔腾4）和Java版本（1.5），很容易相信早期的优化程度较低，Hotspot编译器不是很聪明，指令不存在，然后是一个好主意，性能要高得多。此外，不会公开其内部单词数组，因此不可能创建自定义的细粒度同步位集或灵活的序列化，而这正是Lucene所需要的。因此，对于Lucene来说，这仍然是一个合理的选择，而对于典型用户来说，最好使用标准，这更快（在某些情况下，不是一般情况下）并且属于标准库。时间变化，旧的性能结果变化，所以总是对特定案例进行基准测试和验证，也许对于其中一些案例（例如，没有基准测试迭代器或不同的设置填充因子）会更快。OpenBitSetBitSetpopcntOpenBitSetBitSetBitSetOpenBitSet

答案 2

免责声明：这个答案是在没有任何关于所讨论的比特集实现的效率的情况下完成的，这更像是关于算法设计的一般智慧。

如文档中所述，对于某些特定操作，实现速度更快。那么，使用它比标准Java更好吗？也许，是的，但不是因为速度，而是因为开放性。为什么？OpenBitSetBitSet

当你设计算法时，要做出的决策之一是：你是希望它在大多数情况下表现相同，还是在某些特定情况下表现更好，但在其他情况下可能会失败？

我猜想，作者走了第一条路。Lucene实现对于操作来说很可能更快，这对于它们的问题域更重要。但他们也使实现保持打开状态，以便您可以覆盖行为以针对对您重要的案例进行优化。java.util.BitSet

那么究竟什么是开放的呢？文档告诉和来源确认，该实现基本上将位的基础表示公开给子类。这既是好事，也是坏事：容易改变行为，也容易射出自己的脚。也许这就是为什么（只是一个疯狂的猜测！）在较新版本的Lucene中，他们采取了其他途径：删除有利于另一个尚未打开的实现，但不公开数据结构。实现（，）对自己的数据结构负全部责任。OpenBitSetOpenBitSetBitSetFixedBitSetSparseFixedBitSet

引用：

https://issues.apache.org/jira/browse/LUCENE-6010

http://lucene.apache.org/core/6_0_0/core/org/apache/lucene/util/BitSet.html