徐々に高度になるリングバッファの話、をRustで試した

## はじめに

kumagiさんが[徐々に高度になるリングバッファの話](https://kumagi.hatenablog.com/entry/ring-buffer)を書かれており、手元で挙動を確認してみたかったので試してみました。[kumagi実験のコードはC++だったので](https://gist.github.com/kumagi/519d48b0b22eba5b4b20c62d9f82b433)慣れているRustで実装しています。

## 実験

### 実行環境

手元に2つの環境があるのでそれぞれ試しました。
CPU周波数は固定していないので、機器間の比較はしません。

- AMD Ryzen 7735HS at 4.7GHz
- Intel i7-1165G7 at 4.7GHz (on WSL2)


### 実装について

[RustのコードはGitHubにあります](https://github.com/uzuna/demo-simple-ringbuf)

もともとの実装の概要については以下のとおりです。

|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`でビルドしました。

```text
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`でビルドしました。


```text
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の場合はそれぞれが別のスレッドで実行しています。
空回りしないように命令の成功カウント数が既定値になることを確認しています。

```rs
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();
```

```rs
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が多いのは空振りしている可能性があるのかもしれないですね。
これは元の記事にある通り、想定された動作ですね。

```text
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

```

```text
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を動かすのは手間なので、検証はここまでです。

```text
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
```

```text
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に特化せざるを得ないのかも