Zenn
Closed14

CPU cache line の動作確認

hmatui66hmatui66

概要

CPU cache line を考慮したデータ構造を採用すると速い、とよく聞くものの実際に試したことないのでやってみる

動作環境

  • Apple M1 Max
$ sysctl -a | grep -e "hw.*cache"
...略
hw.cachelinesize: 128
hw.l1icachesize: 131072
hw.l1dcachesize: 65536
hw.l2cachesize: 4194304

cacheline のサイズは 128 バイト。
てっきり 64 バイトだと思っていた。

hmatui66hmatui66

動作確認用コード全体

use std::time::Instant;
use rand::{random, Rng};

const LINE_SIZE: usize = 128;
const ARRAY_SIZE: usize = 8192;
const REPEAT: usize = 1024;

fn main() {
    let mut rng = rand::thread_rng();
    let arr: [[u8; LINE_SIZE]; ARRAY_SIZE] = array_init::array_init(|_| array_init::array_init(|_| rng.gen()));

    let mut match_count = 0;
    let b = random();

    let start = Instant::now();
    for _ in 0..REPEAT {
        for line in 0..ARRAY_SIZE {
            for i in 0..LINE_SIZE {
                if arr[line][i] == b {
                    match_count += 1;
                }
            }
        }
    }
    let duration = start.elapsed();

    println!(
        "duration: {:?}, compare/ms: {:?}, match_count: {:?}",
        duration,
        LINE_SIZE * ARRAY_SIZE * REPEAT / (duration.as_millis() as usize),
        match_count,
    );
}
  • 2次元の配列を用意: let arr: [[u8; LINE_SIZE]; ARRAY_SIZE]
    • [u8; LINE_SIZE] を cache line に載せきれるかどうか、でパフォーマンスが変わる...はず
  • どういう最適化がされるか掴めてないので、u8 にはランダム値を入れる
  • match_count についても最適化による loop の省略を回避するために入れている
    • 単に loop するだけだと REPEAT に巨大な数値を指定しても 100 ns 強で処理が完了してしまう
hmatui66hmatui66

検証方法

  • LINE_SIZE を振って実行
  • ビルドは cargo build --release で実施

結果

※ compare/ms は ms 辺りの if 実行回数という意味合いで命名。適切な呼び方別にある可能性高い。

LINE_SIZE に対する処理数について、

  • 4 - 32 は同レベル
  • 32 → 64, 64 → 128 はきれいに伸びている
  • 128 で頭打ち
hmatui66hmatui66

LINE_SIZE を 48 から 128 まで1ずつ増やしつつ確認

  • 49->50 で跳ねる
  • 50->100前後までほぼリニアに増える
  • 100前後で頭打ち
hmatui66hmatui66

コード変更①

use std::time::Instant;
use rand::{random, Rng};

const LINE_SIZE: usize = 128;
const ARRAY_SIZE: usize = 8192;
const REPEAT: usize = 1024;

fn main() {
    let mut rng = rand::thread_rng();
    let arr: [[u8; LINE_SIZE]; ARRAY_SIZE] = array_init::array_init(|_| array_init::array_init(|_| rng.gen()));

    let mut match_count = 0;
    let b = random();

    let start = Instant::now();
    for _ in 0..REPEAT {
        for i in 0..ARRAY_SIZE {
            let line = &arr[i];
            for j in 0..LINE_SIZE {
                if line[j] == b {
                    match_count += 1;
                }
            }
        }
    }
    let duration = start.elapsed();

    println!(
        "{:?}, match_count: {:?}",
        LINE_SIZE * ARRAY_SIZE * REPEAT / (duration.as_millis() as usize),
        match_count,
    );
}
  • let line = &arr[i]; で一旦 line を保持する形に変えた

結果

  • 最初のコードとあまり変わらず
hmatui66hmatui66

49 → 50 の跳ねはなぜ起こる？

https://tomoyuki-nakabayashi.github.io/embedded-rust-techniques/04-tools/rustc.html#速度最適化

を読むと、

rustcは、3つの最適化レベルを提供しています。opt-level = 1, 2, 3です。cargo build --releaseを実行した場合、デフォルトでは、opt-level = 3です。

opt-level = 2, 3では、バイナリサイズを犠牲にする (大きくする) ことで、速度を向上します。例えば、opt-level = 2以上では、ループ展開が行われます。ループ展開は、Flash/ROMの容量をより多く使用します。

とあり、最適化によってループ展開(loop unrolling)が行われるとのこと。

loop unrolling 関連情報

以下の issue は aarch64 ではうまく loop unrolling されないというもので、上記の動作確認結果と関係するかはわからないが、https://github.com/pacak/cargo-show-asm で asm が良い感じで asm が見れるとあるので試してみる。

https://github.com/rust-lang/rust/issues/105857

LINE_SIZE=49 の asm

https://gist.github.com/hmarui66/248c8740ae5f0e8c8ecb85a47b67a22d

if line[j] == b で検索すると 50 箇所ヒットするが、まず初期値セットした上で

mov rdx, rcx
or rdx, 1
mov rsi, rcx
or rsi, 2
mov rdi, rcx
or rdi, 3
mov r9, rcx
or r9, 4
mov rbx, rcx
or rbx, 5
mov r15, rcx
or r15, 6
mov r12, rcx
or r12, 7
    // /Users/hirotsugu-marui/dev/hm/cacheline/src/main.rs : 20
    if line[j] == b {
imul r14, rcx, 49
imul r11, rdx, 49
imul r10, rsi, 49
imul r8, rdi, 49
imul r9, r9, 49
imul rdi, rbx, 49
imul rsi, r15, 49
imul rdx, r12, 49

以下のような処理が 49 回繰り返される。

movzx ebx, byte ptr [rbp + r14 - 401544]
movd xmm2, ebx
pinsrb xmm2, byte ptr [rbp + r11 - 401544], 1
pinsrb xmm2, byte ptr [rbp + r10 - 401544], 2
pinsrb xmm2, byte ptr [rbp + r8 - 401544], 3
    // /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library/core/src/iter/range.rs : 753
    if self.start < self.end {
movzx ebx, byte ptr [rbp + r9 - 401544]
movd xmm6, ebx
pinsrb xmm6, byte ptr [rbp + rdi - 401544], 1
pinsrb xmm6, byte ptr [rbp + rsi - 401544], 2
pinsrb xmm6, byte ptr [rbp + rdx - 401544], 3
    // /Users/hirotsugu-marui/dev/hm/cacheline/src/main.rs : 20
    if line[j] == b {
pcmpeqb xmm2, xmm0
pmovzxbd xmm5, xmm2
pand xmm5, xmm1
paddd xmm5, xmm3
pcmpeqb xmm6, xmm0
pmovzxbd xmm3, xmm6
pand xmm3, xmm1
paddd xmm3, xmm4
  • byte ptrを8回、合計8バイト分を xmm レジスタに移動し xmm0 と比較している
    • xmm2, xmm6 はそれぞれ 4バイト分を担当
  • これを 49 回繰り返すことで arr の 8 要素([u8; 49] * 8)分の比較がされる

LINE_SIZE=50 の asm

https://gist.github.com/hmarui66/6dbe4bc6176e8e04c620fe40bd4e9a71

if line[j] == b で検索すると 2 箇所ヒットする
そこを見てみると、

movd xmm3, dword ptr [rbp + rcx - 409785]
pcmpeqb xmm3, xmm0
pmovzxbd xmm3, xmm3
pand xmm3, xmm1
paddd xmm3, xmm2

という感じで 32 bit 分をレジスタに移動して xmm0 と比較するというのを12回繰り返した後に、

cmp byte ptr [rbp + rcx - 409737], r15b
sete dil
xor edx, edx
cmp byte ptr [rbp + rcx - 409736], r15b
sete dl
add edx, edi

2バイト分を比較していて、結果 50バイト(=4バイト*12 + 2 バイト) の比較をしている。

→ 49 とは異なる方法で loop unrolling されている

まとめ

  • 96, 128 の asm を見てみたが、50と同様の方針で 1 line ごとに 4 バイトの xmm レジスタを使った比較をしていた
    • 49 は同時に 8 line を比較
  • 結果からすると 1 line ごとの比較をしていったほうが効率が良いといえる？
    • 仮説: cacheline が効く
      • 50 以降は 100 前後までスケールするので cacheline が効いている可能性ある
        • cacheline に載る分は処理量を増やしても単純にスケールする
  • なぜ 49 までは 8 line 同時に比較しているのか
    • 仮説: 小さいサイズであればむしろこの方式の方がよいケースも多いのかも
      • 49 前後がちょうど切り替えポイントとしては適切なのかも
hmatui66hmatui66

--target aarch64-apple-darwin を指定

デフォルトでは X86_64 用のバイナリが生成されていたので cargo build --release --target aarch64-apple-darwin でビルドして試す。

結果

  • X86_64 よりもがたつき多くなった
  • スループットは向上
hmatui66hmatui66

X86_64 と aarch64 のバイナリの比較

  • macOS だから aarch64 の方が速い、とはいえそこまで大きく変わらない
このスクラップは1ヶ月前にクローズされました