Coding Man布尔语[]与比特斯特的性能比较
1. 概述
在本文中，我们将比较BitSet和 *boolean[]*在不同场景下的性能。
我们通常非常松散地使用术语性能，并考虑到不同的含义。因此，我们将首先查看术语“性能”的各种定义。
然后，我们将使用两种不同的性能指标进行基准测试：内存占用和吞吐量。为了对吞吐量进行基准测试，我们将比较一些常见的位向量操作。
2. 性能定义
性能是一个非常笼统的术语，指代广泛的“性能”相关概念！
**有时我们用这个术语来谈论特定应用程序的启动速度；**也就是说，应用程序在能够响应其第一个请求之前所花费的时间。
除了启动速度，我们在谈性能的时候可能还会想到内存使用。所以内存占用是这个术语的另一个方面。
可以将“性能”解释为我们的代码工作的“快”程度。所以延迟是另一个性能方面。
对于某些应用程序，以每秒操作数的形式了解系统容量非常重要。所以吞吐量可以是性能的另一个方面。
一些应用程序只有在响应了一些请求并在技术上“热身”之后，才能在其最高性能水平上运行。因此，达到峰值性能的时间是另一个方面。
可能的定义列表还在继续！然而，在整篇文章中，我们将只关注两个性能指标：内存占用和吞吐量。
3. 内存足迹
尽管我们可能期望boolean 只消耗一位，但boolean[]中的每个boolean值都消耗一个字节的内存 。这主要是为了避免单词撕裂和可访问性问题 。因此，如果我们需要一个位向量，则 *boolean[]*将占用大量内存。
为了使事情更具体，我们可以使用Java 对象布局 (JOL) 来检查具有 10,000 个元素的*boolean[]*的内存布局 ：
boolean[] ba = new boolean[10_000];
System.out.println(ClassLayout.parseInstance(ba).toPrintable());
这将打印内存布局：
[Z object internals:
OFFSET SIZE TYPE DESCRIPTION VALUE
0 4 (object header) 01 00 00 00 (1)
4 4 (object header) 00 00 00 00 (0)
8 4 (object header) 05 00 00 f8 (-134217723)
12 4 (object header) 10 27 00 00 (10000)
16 10000 boolean [Z. N/A
Instance size: 10016 bytes
如上所示，这个 *boolean[]*消耗大约 10 KB 的内存。
另一方面，BitSet使用原始数据类型（特别是long）和按位操作 的组合来实现每个标志占用一个位**。因此 ，与具有相同大小的boolean[] 相比，具有 10,000 位的BitSet将消耗更少的内存 ：
BitSet bitSet = new BitSet(10_000);
System.out.println(GraphLayout.parseInstance(bitSet).toPrintable());
同样，这将打印 BitSet的内存布局：
java.util.BitSet@5679c6c6d object externals:
ADDRESS SIZE TYPE PATH
76beb8190 24 java.util.BitSet
76beb81a8 1272 [J .words
正如预期的那样，具有相同位数的 BitSet消耗大约 1 KB，这远小于boolean[]。
我们还可以比较不同位数的内存占用：
Path path = Paths.get("footprint.csv");
try (BufferedWriter stream = Files.newBufferedWriter(path, StandardOpenOption.CREATE)) {
stream.write("bits,bool,bitset\n");
for (int i = 0; i <= 10_000_000; i += 500) {
System.out.println("Number of bits => " + i);
boolean[] ba = new boolean[i];
BitSet bitSet = new BitSet(i);
long baSize = ClassLayout.parseInstance(ba).instanceSize();
long bitSetSize = GraphLayout.parseInstance(bitSet).totalSize();
stream.write((i + "," + baSize + "," + bitSetSize + "\n"));
if (i % 10_000 == 0) {
stream.flush();
}
}
}
上面的代码将计算两种不同长度的位向量的对象大小。然后它将大小比较写入并刷新到 CSV 文件。
现在，如果我们绘制这个 CSV 文件，我们将看到 内存占用的绝对差异随着位数的增加而增长：
这里的关键点是，BitSet在内存占用方面优于 boolean[]，除了最少的位数。
4. 吞吐量
为了比较 BitSet和 *boolean[]*的吞吐量，我们将基于对位向量的三种不同但日常操作进行三个基准测试：
- 获取特定位的值
- 设置或清除特定位的值
- 计算设置的位数
这是我们将用于不同长度的位向量的吞吐量比较的常见设置：
@State(Scope.Benchmark)
@BenchmarkMode(Mode.Throughput)
public class VectorOfBitsBenchmark {
private boolean[] array;
private BitSet bitSet;
@Param({"100", "1000", "5000", "50000", "100000", "1000000", "2000000", "3000000",
"5000000", "7000000", "10000000", "20000000", "30000000", "50000000", "70000000", "1000000000"})
public int size;
@Setup(Level.Trial)
public void setUp() {
array = new boolean[size];
for (int i = 0; i < array.length; i++) {
array[i] = ThreadLocalRandom.current().nextBoolean();
}
bitSet = new BitSet(size);
for (int i = 0; i < size; i++) {
bitSet.set(i, ThreadLocalRandom.current().nextBoolean());
}
}
// omitted benchmarks
}
如上所示，我们正在创建 长度在 100-1,000,000,000 范围内的*boolean[]*和 BitSet 。此外，在设置过程中设置了一些位之后，我们将对 *boolean[]*和 BitSet执行不同的操作。
4.1. 得到一点
**乍一看，boolean[]中的直接内存访问似乎比在BitSet中每次get 执行两次按位操作左移加与操作更有效。**另一方面，BitSet的内存紧凑性可能允许它们在高速缓存行中容纳更多值。
让我们看看谁赢了！以下是 JMH 每次使用不同size状态值运行 的基准测试：
@Benchmark
public boolean getBoolArray() {
return array[ThreadLocalRandom.current().nextInt(size)];
}
@Benchmark
public boolean getBitSet() {
return bitSet.get(ThreadLocalRandom.current().nextInt(size));
}
4.2. 了解一下：吞吐量
我们将使用以下命令运行基准测试：
$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff get.csv getBitSet getBoolArray
这将使用四个线程和两个 fork 运行与 get 相关的基准测试，使用 Linux 上的 perf 工具分析它们的执行统计数据，并将结果输出到bench-get.csv文件中。“ -prof perfnorm”将使用 Linux 上的 perf 工具分析基准，并根据操作数规范化性能计数器。
由于命令结果非常冗长，我们将只在此处绘制它们。在此之前，让我们看一下每个基准测试结果的基本结构：
"Benchmark","Mode","Threads","Samples","Score","Score Error (99.9%)","Unit","Param: size"
"getBitSet","thrpt",4,40,184790139.562014,2667066.521846,"ops/s",100
"getBitSet:L1-dcache-load-misses","thrpt",4,2,0.002467,NaN,"#/op",100
"getBitSet:L1-dcache-loads","thrpt",4,2,19.050243,NaN,"#/op",100
"getBitSet:L1-dcache-stores","thrpt",4,2,6.042285,NaN,"#/op",100
"getBitSet:L1-icache-load-misses","thrpt",4,2,0.002206,NaN,"#/op",100
"getBitSet:branch-misses","thrpt",4,2,0.000451,NaN,"#/op",100
"getBitSet:branches","thrpt",4,2,12.985709,NaN,"#/op",100
"getBitSet:dTLB-load-misses","thrpt",4,2,0.000194,NaN,"#/op",100
"getBitSet:dTLB-loads","thrpt",4,2,19.132320,NaN,"#/op",100
"getBitSet:dTLB-store-misses","thrpt",4,2,0.000034,NaN,"#/op",100
"getBitSet:dTLB-stores","thrpt",4,2,6.035930,NaN,"#/op",100
"getBitSet:iTLB-load-misses","thrpt",4,2,0.000246,NaN,"#/op",100
"getBitSet:iTLB-loads","thrpt",4,2,0.000417,NaN,"#/op",100
"getBitSet:instructions","thrpt",4,2,90.781944,NaN,"#/op",100
如上所示，结果是一个以逗号分隔的字段列表，每个字段代表一个指标。例如， *“thrpt”*表示吞吐量， *“L1-dcache-load-misses”是一级数据缓存的缓存未命中数，“L1-icache-load-misses”是该级别的缓存未命中数1 个指令缓存，“op”*代表每个基准测试的 CPU 指令数。此外，最后一个字段表示位数，第一个字段表示基准方法名称。
这是使用 4 核 Intel(R) Xeon(R) CPU 2.20GHz 的典型 Digitial Ocean droplet 的吞吐量的基准测试结果：
如上所示，**boolean[]在较小的尺寸上具有更好的吞吐量。当位数增加时，BitSet在吞吐量方面优于 boolean[]。更具体地说，在 100,000 位之后，BitSet表现出优越的性能。
4.3. 了解一下：每次操作的说明
正如我们所料，**对 boolean[]的 get 操作每个操作的指令更少：
4.4. 了解一下：数据缓存未命中
现在，让我们看看数据缓存未命中是如何查找这些位向量的：
如上所示，*boolean[]*的数据缓存未命中 数随着位数的增加而增加。
所以缓存未命中比在这里执行更多指令要昂贵得多。因此， 在这种情况下， BitSet API 在大多数情况下都优于boolean[]。
4.5. 设置位
为了比较集合操作的吞吐量，我们将使用以下基准：
@Benchmark
public void setBoolArray() {
int index = ThreadLocalRandom.current().nextInt(size);
array[index] = true;
}
@Benchmark
public void setBitSet() {
int index = ThreadLocalRandom.current().nextInt(size);
bitSet.set(index);
}
基本上，我们选择一个随机位索引并将其设置为 true。同样，我们可以使用以下命令运行这些基准测试：
$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff set.csv setBitSet setBoolArray
让我们看看这些操作在吞吐量方面的基准测试结果如何：
**这次 boolean[]除了非常大的尺寸之外，大部分时间都优于 BitSet。由于我们可以 在缓存行中有更多的BitSet位，因此缓存未命中和错误共享的影响在
BitSet实例中可能更为显着 。
这是数据缓存未命中比较：
如上所示， 对于低到中等位数，*boolean[]*的数据缓存未命中率非常低。同样，当位数增加时，*boolean[]*会遇到更多的缓存未命中。
同样，boolean[]的每个操作的指令 都比BitSet少：
4.6. 基数
这种位向量中的其他常见操作之一是计算设置位的数量。这次我们将运行这些基准测试：
@Benchmark
public int cardinalityBoolArray() {
int sum = 0;
for (boolean b : array) {
if (b) sum++;
}
return sum;
}
@Benchmark
public int cardinalityBitSet() {
return bitSet.cardinality();
}
同样，我们可以使用以下命令运行这些基准测试：
$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff cardinal.csv cardinalityBitSet cardinalityBoolArray
以下是这些基准测试的吞吐量：
在基数吞吐量方面，BitSet API 几乎一直都优于boolean[]，因为它的迭代次数要少得多。更具体地说，BitSet只需迭代其内部 long[]，与相应的*boolean[]*相比，它的元素数量要少得多 。
此外，由于这条线和我们的位向量中设置位的随机分布：
if (b) {
sum++;
}
分支错误预测 的成本也可能是决定性的：
如上所示，随着位数的增加， *boolean[]*的错误预测数量显着增加。