はじめに
kumagiさんが徐々に高度になるリングバッファの話を書かれており、手元で挙動を確認してみたかったので試してみました。kumagi実験のコードはC++だったので慣れているRustで実装しています。
実験
実行環境
手元に2つの環境があるのでそれぞれ試しました。
CPU周波数は固定していないので、機器間の比較はしません。
- AMD Ryzen 7735HS at 4.7GHz
- Intel i7-1165G7 at 4.7GHz (on WSL2)
実装について
もともとの実装の概要については以下のとおりです。
| name | 実装概要 |
|---|---|
| RingBuffer0 | 読み書き位置をモジュロで計算 |
| RingBuffer1 | 0の読み書き位置をAndで計算 |
| RingBufferMutex | 1からマルチスレッド対応MutexLockを追加 |
| RingBuffer2 | 1からマルチスレッド対応のためそれぞれIndexをAtomicUintに変更 |
| RingBuffer3 | 2からキャッシュライン分離のためにアライン調整と同期処理を追加 |
| RingBuffer4 | Bufferをmmapに変更? |
上記のうちRingBuffer0,1,2,3の実装をしました。
RingBuffer0,1は特に実装の違いはありません。
RingBuffer2はマルチスレッド化のためProducerとConsumerの構造体を追加しています。
RingBuffer3はアライン調整のために_paddingフィールドを追加しました。
MultiThreadはもとのコードはcpuset(0,1)決め打ちだったので、それに合わせたものとcore idが違う(0,2)も実施しました。
実行結果
リファレンス(AMD Ryzen 7735HS)
リファレンスとなるkumagiさんのコードをg++ -O2でビルドしました。
RingBuffer0_single: 1000000000 ops in 939 ms 1064962.726 ops/ms
RingBuffer1_single: 1000000000 ops in 338 ms 2958579.882 ops/ms
RingBuffer2_single: 1000000000 ops in 552 ms 1811594.203 ops/ms
RingBuffer3_single: 1000000000 ops in 541 ms 1848428.835 ops/ms
RingBuffer2: 1000000000 ops in 3360 ms 297619.0476 ops/ms
RingBuffer3: 1000000000 ops in 2377 ms 420698.3593 ops/ms
RingBuffer1が最も高速です。一方、記事では高度化したRingBuffer3はRingBuffer2に比べればいくらか改善はしていますが、記事ではRingBuffer1に肉薄するほどであったのに比べるとまるで遅いです。
Rust実装(AMD Ryzen 7735HS)
次にRust 1.71.0 opt-level = 2でビルドしました。
Run R0S : 1000000000 ops in 840 ms 1190476 ops/ms
Run R1S : 1000000000 ops in 503 ms 1988071 ops/ms
Run R2S : 1000000000 ops in 704 ms 1420454 ops/ms
Run R2M (0,1): 1000000000 ops in 2604 ms 384024 ops/ms
Run R2M (0,2): 1000000000 ops in 3953 ms 252972 ops/ms
Run R3S : 1000000000 ops in 637 ms 1569858 ops/ms
Run R3M (0,1): 1000000000 ops in 1927 ms 518941 ops/ms
Run R3M (0,2): 1000000000 ops in 2308 ms 433275 ops/ms
リファレンスと傾向としてはほとんど変わらず、やはりシングルコアでの処理が早いです。and計算の効果もそこまで劇的ということはなく、マルチスレッド化した場合に性能が劣化する傾向は代わりはありません。CPU Core IDが異なる組み合わせになると更に遅くなっています。
Intel i7-1165G7
こちらもRust 1.71.0 opt-level = 2でビルドしました。GCCが9系でサンプルコードがビルドが通らなかったのでリファレンスのデータはありません。
Run R0S : 1000000000 ops in 1026 ms 974658 ops/ms
Run R1S : 1000000000 ops in 679 ms 1472754 ops/ms
Run R2S : 1000000000 ops in 780 ms 1282051 ops/ms
Run R2M (0,1): 1000000000 ops in 4043 ms 247341 ops/ms
Run R2M (0,2): 1000000000 ops in 3990 ms 250626 ops/ms
Run R3S : 1000000000 ops in 694 ms 1440922 ops/ms
Run R3M (0,1): 1000000000 ops in 672 ms 1488095 ops/ms
Run R3M (0,2): 1000000000 ops in 628 ms 1592356 ops/ms
こちらも概ね傾向は一緒ですが、R3M(0,1 or 2)のスループットが高いです。異なるコアの場合でも性能は劣化しないどころかむしろ高速なようです。リファレンスでの高速化が再現しなかったのは、RyzenCPUとIntelCPUの実装違いの可能性がありそうです。
考察
R2SとR2M (0,1)の違い
ベンチマークのコードの違いは以下です。
Sの場合は直列にenqueue dequeueするのに対して、Mの場合はそれぞれが別のスレッドで実行しています。
空回りしないように命令の成功カウント数が既定値になることを確認しています。
let start = std::time::Instant::now();
for _ in 0..opt.loop_count {
for i in 0..opt.enqueue_count {
p.enqueue(i as i32);
}
for _ in 0..opt.enqueue_count {
c.dequeue();
}
}
let end = std::time::Instant::now();
let start = std::time::Instant::now();
let loop_count = opt.loop_count;
let enqueue_count = opt.enqueue_count;
let h_p = spawn(move || {
if !core_affinity::set_for_current(core_p) {
println!("set_for_current failed");
}
for _ in 0..loop_count {
let mut count = enqueue_count;
while 0 < count {
if p.enqueue(count as i32) {
count -= 1;
}
}
}
});
let loop_count = opt.loop_count;
let enqueue_count = opt.enqueue_count;
let h_c = spawn(move || {
if !core_affinity::set_for_current(core_c) {
println!("set_for_current failed");
}
for _ in 0..loop_count {
let mut count = enqueue_count;
while 0 < count {
if c.dequeue().is_some() {
count -= 1;
}
}
}
});
h_p.join().unwrap();
h_c.join().unwrap();
let end = std::time::Instant::now();
Pref R2S, R2M(7735HS)
ざっくりPerfを取ってみました。
キャッシュアクセス回数が非常に多くです。IPCが低いので待ち時間が長そうなのと、instructionsが多いのは空振りしている可能性があるのかもしれないですね。
これは元の記事にある通り、想定された動作ですね。
Run R2S : 1000000000 ops in 672 ms 1488095 ops/ms
Performance counter stats for 'target/release/simple-ringbuf -r r2s':
63,911,067 cache-references
853,880 cache-misses # 1.336 % of all cache refs
3,218,827,611 cycles
13,267,848,530 instructions # 4.12 insn per cycle
1,027,019 branch-misses
2,136 faults
2 migrations
0.673736458 seconds time elapsed
Run R2M (0,1): 1000000000 ops in 2601 ms 384467 ops/ms
Performance counter stats for 'target/release/simple-ringbuf -r r2m -c 0,1':
437,763,912 cache-references
1,375,689 cache-misses # 0.314 % of all cache refs
24,898,212,181 cycles
16,160,841,677 instructions # 0.65 insn per cycle
8,688,538 branch-misses
2,148 faults
2 migrations
2.602918788 seconds time elapsed
Pref R3S, R3M(7735HS)
同様にキャッシュアクセス回数が多いですがR2ほどではありません。IPCもわずかに改善がしていますしｍInstructionも少ないので空振りが減っているようです。一方でR2よりもbranch-missesが多く、インデックスが追いついたときにだけに行われるべき更新の分岐が、頻繁に実行されている可能性がありそうです。
Intelでは性能低下が見られなかったのは、このケースでの分岐予測がAMDよりも適切なのかもしれません。
Intelの方はWSLでperfを動かすのは手間なので、検証はここまでです。
Run R3S : 1000000000 ops in 634 ms 1577287 ops/ms
Performance counter stats for 'target/release/simple-ringbuf -r r3s':
63,771,790 cache-references
785,122 cache-misses # 1.231 % of all cache refs
3,043,132,770 cycles
12,018,050,266 instructions # 3.95 insn per cycle
1,049,131 branch-misses
2,139 faults
0 migrations
0.635995627 seconds time elapsed
Run R3M (0,1): 1000000000 ops in 1892 ms 528541 ops/ms
Performance counter stats for 'target/release/simple-ringbuf -r r3m -c 0,1':
324,043,366 cache-references
1,248,718 cache-misses # 0.385 % of all cache refs
18,060,932,634 cycles
13,922,493,296 instructions # 0.77 insn per cycle
136,154,577 branch-misses
2,149 faults
2 migrations
1.894017234 seconds time elapsed
まとめ
- シンプルな操作はマルチコア化すると、シングルコアよりも遅くなる要因が多数ある
- マルチコアの場合にはキャッシュラインを意識して実装するのは効果はある
- 最速を目指すなら使うCPUに特化せざるを得ないのかも