boolean[]とBitSetのパフォーマンス比較
1. 概要
この記事では、さまざまなシナリオでのパフォーマンスの観点から、BitSetsとboolean[]を比較します。
私たちは通常、パフォーマンスという用語を非常に大まかに使用し、さまざまな意味を念頭に置いています。 したがって、「パフォーマンス」という用語のさまざまな定義を確認することから始めます。
次に、ベンチマークに2つの異なるパフォーマンスメトリックを使用します。メモリフットプリントとスループットです。 スループットをベンチマークするために、ビットベクトルに対するいくつかの一般的な操作を比較します。
2. パフォーマンスの定義
パフォーマンスは、さまざまな「パフォーマンス」関連の概念を指す非常に一般的な用語です。
この用語を使用して、特定のアプリケーションの起動速度について話すことがあります。 つまり、アプリケーションが最初の要求に応答できるようになるまでにかかる時間。
起動速度に加えて、パフォーマンスについて話すとき、メモリ使用量について考えるかもしれません。 したがって、メモリフットプリントはこの用語のもう1つの側面です。
「パフォーマンス」を、コードがどれだけ「高速」に機能するかとして解釈することができます。 したがって、レイテンシーはさらに別のパフォーマンスの側面です。
一部のアプリケーションでは、1秒あたりの操作数でシステム容量を知ることが非常に重要です。 したがって、スループットはパフォーマンスの別の側面になる可能性があります。
一部のアプリケーションは、いくつかの要求に応答し、技術的に言えば「ウォームアップ」された後にのみ、ピークパフォーマンスレベルで動作できます。 したがって、 t imeからピークまでのパフォーマンスは別の側面です。
可能な定義のリストはどんどん増えていきます！ ただし、この記事では、 mエモリーフットプリントとスループットの2つのパフォーマンスメトリックのみに焦点を当てます。
3. メモリーフットプリント
booleans は1ビットしか消費しないと予想されるかもしれませんが、boolean[]内の各ブール値は1バイトのメモリを消費します。 これは主に、単語のティアリングとアクセシビリティの問題を回避するためです。 したがって、ビットのベクトルが必要な場合、 boolean[]のメモリフットプリントはかなり大きくなります。
さらに具体的に言うと、 Java Object Layout（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[]は約10KBのメモリを消費します。
一方、 BitSetは、プリミティブデータ型（特に長い）とビット単位の演算の組み合わせを使用して、フラグフットプリントごとに1ビットを実現しています。 したがって、10,000ビットの BitSet は、同じサイズの boolean [] と比較して、はるかに少ないメモリを消費します。
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は約1KBを消費します。これは、 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[] のスループットを相互に比較するために、ビットベクトルに対する3つの異なる、しかし日常的な操作に基づいて3つのベンチマークを実行します。
- 特定のビットの値を取得する
- 特定のビットの値を設定またはクリアする
- セットビット数をカウントする
これは、さまざまな長さのビットベクトルのスループット比較に使用する一般的な設定です。
@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. ビットを取得する
どちらが勝つか見てみましょう！ JMHがサイズ状態の異なる値で毎回実行されるベンチマークは次のとおりです。
@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これにより、4つのスレッドと2つのフォークを使用してget関連のベンチマークが実行され、Linuxのperfツールを使用して実行統計がプロファイルされ、結果がbench-get.csvファイルに出力されます。 「-profperfnorm」は、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」はレベル1データキャッシュのキャッシュミスの数です。「L1- 「icache-load-misses」はレベル1命令キャッシュのキャッシュミスの数であり、「instructions」は各ベンチマークのCPU命令の数を表します。 また、最後のフィールドはビット数を表し、最初のフィールドはベンチマークメソッド名を表します。
これは、4コアのIntel（R）Xeon（R）CPU2.20GHzを使用した典型的なDigitialOceanドロップレットのスループットのベンチマーク結果がどのように見えるかを示しています。
上に示したように、
4.3. ビットの取得：操作ごとの指示
予想どおり、ブール値[]でのget操作では、操作ごとの命令が少なくなります：
4.4. ビットの取得：データキャッシュの欠落
次に、データキャッシュミスがこれらのビットベクトルをどのように探しているかを見てみましょう。
上に示したように、 boolean [] のデータキャッシュミスの数は、ビット数が増えるにつれて増加します。
したがって、キャッシュミスは、ここでより多くの命令を実行するよりもはるかにコストがかかります。 したがって、このシナリオでは、ほとんどの場合、 BitSetAPIが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. カーディナリティ
このようなビットベクトルでの他の一般的な操作の1つは、セットビットの数をカウントすることです。 今回は、次のベンチマークを実行します。
@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は反復回数がはるかに少ないため、ほぼ常にブール値[]を上回っています。 より具体的には、 BitSet は、対応する boolean[]と比較して要素数がはるかに少ない内部long[]を反復するだけで済みます。
また、この線とビットベクトル内のセットビットのランダムな分布のために：
if (b) {
sum++;
}ブランチの誤予測のコストも決定的なものになる可能性があります。
上に示したように、ビット数が増えると、 boolean[]の誤予測の数が大幅に増えます。
5. 結論
この記事では、BitSetとboolean[] のスループットを、ビットの取得、ビットの設定、カーディナリティの計算という3つの一般的な操作の観点から比較しました。 スループットに加えて、 BitSet は、同じサイズの boolean[]と比較してはるかに少ないメモリを使用することがわかりました。
要約すると、シングルビットの読み取りが多いシナリオでは、 boolean[]はBitSetよりも小さいサイズで優れています。 ただし、ビット数が増えると、BitSetのスループットが向上します。
さらに、シングルビットの書き込みが多いシナリオでは、 boolean [] は、非常に多くのビットを除いて、ほぼ常に優れたスループットを示します。 また、バッチ読み取りシナリオでは、 BitSetAPIがboolean[]アプローチを完全に支配します。
JMH-perf統合を使用して、L1データキャッシュの欠落や分岐予測の欠落などの低レベルのCPUメトリックをキャプチャしました。 Linux 2.6.31の時点で、 パフォーマンス有用なものを公開できる標準のLinuxプロファイラーですパフォーマンス監視カウンターまた
いつものように、すべての例はGitHubでから入手できます。 さらに、実施されたすべてのベンチマークのCSV結果は、GitHubからにアクセスすることもできます。
