Java JDK BitSet 与 Lucene OpenBitSet

Question

我在尝试实现 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' 的数组来存储位。各个位映射到特定的数组索引和存储在索引处的 'long' 值中的位位置。

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

Answer 1

为什么 OpenBitSet 的性能优于 BitSet？举个相关的例子。

OpenBitSet 承诺 1.5x 到 3x cardinality 更快， iteration 和 get。它还可以处理更大基数的集合（最多 64 * 2**32-1）。
当 BitSet 在没有外部的情况下对于多线程使用不安全时同步，OpenBitSet 允许有效地实现备用序列化或交换格式。
对于 OpenBitSet，额外的安全和封装可能总是被构建在上面，但在 BitSet 中不是。
OpenBitSet 允许直接访问存储单词的数组位，但在 BitSet 中，它实现了一个位向量，它增长为需要。
IndexReader 和 SegmentMerger 更加自定义和可插入打开比特集。在 Lucene 3.0 中，整个 IndexReader class 树是重写为不乱用锁定、重新打开和引用数数。
在 Solr 中，如果您有一组那么小的文档，它最可能使用 HasDocSet 而不是 BitDocSet 建模。

举个例子，

您实际上是在测试大小为 5000 的集合与大小为 500,000 的集合。

BitSet 跟踪您设置的最大位（即 5000）和实际上并不计算交集或 populationCount 除此之外。 OpenBitSet 没有（它试图做最少的必要并使一切尽可能快。）

So if you changed the single bit you set from 5000 to 499,999, you
should see very different results.

无论如何，如果只设置一位，有很多计算交点大小的更快方法。

If you want to see the performance of OpenBitSet over BitSet, then go through this link: http://lucene.apache.org/core/3_0_3/api/core/org/apache/lucene/util/OpenBitSet.html

相关Link：Benchmarking results of mysql, lucene and sphinx

It seems to me that both these classes use an array of 'long' to store the bits. What is the reason, then that the OpenBitSet implementation is far better in terms of performance ?

实际上性能取决于 java.util.BitSet 和 OpenBitSet 设置的算法。 OpenBitSet 在大多数操作中比 java.util.BitSet 快，在计算集合的基数和集合操作的结果时 快得多 。它还可以处理更大基数的集合（最多 64 * 2**32-1） OpenBitSet 承诺在基数、迭代和获取方面快 1.5 到 3 倍。

资源Link：

The goals of OpenBitSet are the fastest implementation possible, and maximum code reuse. Extra safety and encapsulation may always be built on top, but if that's built in, the cost can never be removed (and hence people re-implement their own version in order to get better performance)

因此，如果您想要一个 "safe"、完全封装（并且速度较慢且受限）的 BitSet class，请使用 java.util.BitSet.

OpenBitSet 是如何工作的？

Constructs an OpenBitSet from an existing long[]. The first 64 bits are in long[0], with bit index 0 at the least significant bit, and bit index 63 at the most significant. Given a bit index, the word containing it is long[index/64], and it is at bit number index%64 within that word. numWords are the number of elements in the array that contain set bits (non-zero longs). numWords should be <= bits.length, and any existing words in the array at position >= numWords should be zero.

资源Link：

OpenBitSet 示例：http://www.massapi.com/class/op/OpenBitSet.html

资源Link：

Java BitSet Example
有一个案例研究显示了它们的有效性和方式改进 lucene 的 OpenBitSet?

Answer 2

DISCLAIMER: This answer is done without any research on how efficient are the bitset implementations in question, this is more of a general wisdom about algorithms design.

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

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

我想，java.util.BitSet 的作者采用了第一种方法。 Lucene 实现对于操作来说很可能更快，这对于他们的问题域来说更重要。但他们还保留了实现 open，以便您可以覆盖行为以针对对您重要的情况进行优化。

那么 OpenBitSet 中的 open 到底是什么？文档告诉我们，消息来源确认该实现基本上 向子类公开 位的底层表示。这既好又坏：容易改变行为，但也容易搬起石头砸自己的脚。也许这就是为什么（只是一个疯狂的猜测！）在较新版本的 Lucene 中他们采取了其他路径：删除 OpenBitSet 以支持另一个 BitSet 实现，该实现尚未公开，但不公开数据结构。实现（FixedBitSet、SparseFixedBitSet）完全负责自己的数据结构。

参考文献：

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

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

Answer 3

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

当有人声称他的实施速度比 "maximum code reuse"、"no extra safety" 等常用短语快 2-3 倍并且没有提供任何真正的基准时，您应该在你的头。事实上，他们邮件中的所有基准测试 lists/docs 都没有源代码，并且（根据结果）是手工编写的（因此可能违反 benchmarking rules）而不是使用 JMH。

在挥手说明为什么某些东西比其他东西更快之前，让我们先写一个基准测试，看看它是否真的更快，然后再发表任何声明。基准测试代码是 here：它只是测试大小为 1024 和 1024 * 1024 (~1kk) 且填充因子为 50% 的集合的所有基本操作。测试是在英特尔酷睿 i7-4870HQ CPU @ 2.50GHz 上运行。 score就是吞吐量，越高越好。

整个基准看起来像这样：

  @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（包括快速版本）在性能方面是平等的。他们的结果位于相同的误差范围内，如果没有适当的 nanobenchmarking 很难说出任何差异，因此在典型的应用程序实现中使用 bitset 没有任何区别，如果分支无关紧要，则多一个。所以关于 OpenBitSet get/set 更好性能的说法是 false。 UPD：get 方法的 nanobenchmark 也没有显示任何差异，结果是 here.
BitSet 的基数可以更快地计算出来（1k 和 1kk 大小都是约 3 倍），所以关于 "ultra fast cardinality" 的陈述是 false。但是，如果没有实际回答性能差异的原因，数字就毫无意义，所以让我们深入了解一下。要计算单词 BitSet 中的位数，请使用 Long#bitCount，即 Hotspot intrinsic。这意味着整个 bitCount 方法将被编译成 单指令 （对于好奇的人来说，它将是 x86 popcnt）。 OpenBitSet 使用来自 Hacker's Delight 的技巧进行手动位计数（参见 org.apache.lucene.util.BitUtil#pop_array）。难怪现在经典版速度更快了。

Group set 方法与 and/or 一样，所以这里没有性能优势。但有趣的是：BitSet 实现跟踪至少设置了一位的单词的最大索引，并仅在 [0, maxIndex] 的范围内执行 and/or/基数运算，因此我们可以比较具体情况，当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)，很容易相信 earlier BitSet 优化程度较低，Hotspot编译器不是很聪明，popcnt 指令不存在，然后 OpenBitSet 是个好主意，而且性能更高。此外，BitSet 不公开其内部字数组，因此无法创建自定义的细粒度同步位集或灵活的序列化，而这正是 Lucene 所需要的。所以对于 Lucene 来说它仍然是一个合理的选择，而对于典型用户来说最好使用标准 BitSet，它更快（在某些情况下，不是一般情况下）并且属于标准库。时间变化，旧的性能结果发生变化，因此始终对您的特定案例进行基准测试和验证，也许对于其中一些案例（例如，未进行基准测试的迭代器或不同的设置填充因子）OpenBitSet 会更快。

Java JDK BitSet 与 Lucene OpenBitSet

Java JDK BitSet vs Lucene OpenBitSet

java

lucene

performance

bitset

为什么 OpenBitSet 的性能优于 BitSet？举个相关的例子。

举个例子，

OpenBitSet 是如何工作的？

资源Link：

资源Link：

总结