Zenn
🚀

Juliaでキャッシュチューニング

2022/03/27に公開
Julia
高速化
ベンチマーク
チューニング
ベンチマークテスト
tech

Juliaは特に工夫しなくても速いコードが書けますが, より速いコードを書くコツがいくつかあります. 今回はキャッシュチューニングについて解説していきます. BenchmarkTools.jlを用いて, JuliaでもFortranと同じ方法でのキャッシュチューニングが有効か検討しました.

動作環境

versioninfo()

Julia Version 1.7.1
Commit ac5cc99908 (2021-12-22 19:35 UTC)
Platform Info:
OS: Windows (x86_64-w64-mingw32)
CPU: Intel(R) Core(TM) i7-4650U CPU @ 1.70GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-12.0.1 (ORCJIT, haswell)

パッケージ

# using Pkg
# Pkg.add("BenchmarkTools")
using BenchmarkTools

キャッシュチューニング

雑に説明すると, コンピュータはメモリ⇄キャッシュ⇄CPU(レジスタ)へとデータを受け渡します. メモリ-キャッシュ間の通信は遅いので, できるだけキャッシュ-CPU(レジスタ)間の通信だけで済むように工夫して（正確にはキャッシュミスを減らすように）プログラムを書くことをキャッシュチューニングといいます.

青山幸也『チューニング技法虎の巻』 p.4-4 より

【重要】多次元配列(多重ループ)の場合、キャッシュミスを少なくするためには、

　　　　Fortranでは、図4-2-3(1)に示すように、内側のループを配列の左側の添字で反復させること。

図4-2-3(1)　良い例
DIMENSION A(4,9)
DO J=1,9
  DO I=1,4
    A(I,J) = A(I,J) + 1.0
  ENDDO
ENDDO
図4-2-4(1)　悪い例
DIMENSION A(4,9)
DO I=1,4
  DO J=1,9
    A(I,J) = A(I,J) + 1.0
  ENDDO
ENDDO

メモリ上の多次元配列の格納方向は, JuliaとFortranでは同じであるため, Juliaでも上記のFortranと同じ方法でのキャッシュチューニングが有効であろうと予想できます.

ベンチマーク

2次元配列の総和を計算します. 比較する関数は以下のbad()とgood()に加えて標準ライブラリのsum()の3つです.

遅い
function bad(arr)
    sum = 0
    for i in 1:size(arr)[1]
        for j in 1:size(arr)[2]
           sum += arr[i,j]
        end
    end
    return sum
end
速い
function good(arr)
    sum = 0
    for j in 1:size(arr)[2]
        for i in 1:size(arr)[1]
           sum += arr[i,j]
        end
    end
    return sum
end

次の配列Aの総和を計算する. 配列Aは倍精度浮動小数点数(Float64)の1000×1000配列です.

A = rand(1000,1000)

各要素は[0,1)の一様分布に従う疑似乱数であるので, 総和は概ね500000になるはずです.

println("bad(A)  = ", bad(A))
println("good(A) = ", good(A))
println("sum(A)  = ", sum(A))

bad(A) = 500432.86382117023
good(A) = 500432.8638211867
sum(A) = 500432.86382120027

浮動小数点の計算であるため, 和の順序によって僅かに結果が異なりますが, 概ね500000になっています.

結果

ベンチマークテストの結果は以下の通りです.

@benchmark bad(A)

BenchmarkTools.Trial: 1479 samples with 1 evaluation.
Range (min … max): 3.153 ms … 11.431 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 3.327 ms ┊ GC (median): 0.00%
Time (mean ± σ): 3.363 ms ± 419.905 μs ┊ GC (mean ± σ): 0.00% ± 0.00%
Memory estimate: 16 bytes, allocs estimate: 1.

@benchmark good(A)

BenchmarkTools.Trial: 4180 samples with 1 evaluation.
Range (min … max): 979.800 μs … 11.564 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 1.151 ms ┊ GC (median): 0.00%
Time (mean ± σ): 1.179 ms ± 307.241 μs ┊ GC (mean ± σ): 0.00% ± 0.00%
Memory estimate: 16 bytes, allocs estimate: 1.

@benchmark sum(A)

BenchmarkTools.Trial: 9209 samples with 1 evaluation.
Range (min … max): 478.700 μs … 5.138 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 509.500 μs ┊ GC (median): 0.00%
Time (mean ± σ): 525.046 μs ± 104.547 μs ┊ GC (mean ± σ): 0.00% ± 0.00%
Memory estimate: 16 bytes, allocs estimate: 1.

表にまとめると以下のような計算時間でした.

関数 Time(mean)
bad() 3327µs
good() 1151µs
sum() 509µs

まとめ

JuliaでもFortranと同じ方法でキャッシュチューニングが可能であることがわかりました. しかし, sum(A)が圧倒的に速かったので, できるだけ既存のライブラリの関数を利用することをお勧めします.

参考文献

この記事の元になったJupyter Notebookのデータは下記のリンクにあります.

https://gist.github.com/ohno/86f1ba4c9a237b17a10cb88904e283e6

追記

コメントを頂きました. この記事ではキャッシュチューニングの有効性の一例を挙げたのみで終わりにしてしまいましたが, せっかくなのでこれを参考にして後で追記したいと思います.

Discussion