この記事は、Techouse Advent Calendar 2024 17日目です。
昨日は harashunnn さんによる こんにちは。わたしはDocker build --secrets。あなたのクレデンシャルを守ります。 でした。
はじめに
こんにちは、株式会社 Techouse のクラウドハウス採用でエンジニアインターンをしている ReLU と申します。
Techouse では技術責任者の山崎による任意参加の社内勉強会を隔週で行っており、そこでは OS・ネットワーク・データベース・ハードウェア・セキュリティ・システムアーキテクチャなど、エンジニアとして基礎的な知識が学べます。
ここで先日、メカニカルシンパシー(2) 命令レベル並列性というタイトルの勉強会が開催されました。
「メカニカルシンパシー」という言葉に聞き馴染みがない方もいるかもしれません。私もこの勉強会が開催されるまでは聞いたことがない単語でした。
簡単に「メカニカルシンパシー」について説明します。
...とは言っても、メカニカルシンパシーについて検索しても明確な意味が得られなかったので、ChatGPT に聞いてみることにしました。
質問
「メカニカルシンパシー」とはどういう意味ですか？ソフトウェアエンジニアの視点から答えてください。
回答
「メカニカルシンパシー」（mechanical sympathy）とは、ソフトウェアエンジニアリングにおいて、システムやハードウェアの動作を深く理解し、それに合ったソフトウェアを設計・実装するための概念です。具体的には、ハードウェアの特性や制約、たとえば CPU のキャッシュやメモリアクセスの速度、マルチコアプロセッサの並列性といった要素を理解し、その特性を活かしたソフトウェアを書くことを意味します。
この考え方は、レーシングドライバーが車のエンジンやサスペンションの動きを理解し、それに合わせて運転技術を最適化するのと同じようなもので、「機械的な共鳴」というニュアンスを持っています。この用語は、元 F1 エンジニアのアドリアン・ニューウェイ（Adrian Newey）によって広められました。
私の理解では、IT 分野だけでなく全ての技術者が一般人では持ち得ない理解の範疇を超えた感覚として物事を捉えることができる能力のことだと思っています。
前置きはここまでにしておき、メカニカルシンパシー(2) 命令レベル並列性の勉強会でメモリのキャッシュラインへのヒット率による実行時間の違いを学んだ時に気になることがあり、調べてみたら面白いことがわかったので紹介させていただきます。
勉強会の内容
この日の勉強会では、コンピュータのメインメモリの歴史を学びました。
詳細は省略しますが、「水銀遅延線」から始まり「磁気ドラム装置」が作られ、現代の「SRAM」や「DRAM」があるということを学びました。
ふむふむ面白いな、と思って聞いていたのですが、いきなりこんなことを山崎が言いました。
「メインメモリってめっちゃ遅いんですよ〜」
……!?
正直、「メモリはすごく早い」っていうイメージだったのでとてもびっくりしました。
しかし、ここで比べる対象は HDD や SSD ではなく CPU の処理速度でした。
なるほど……!?
例えば、CPU のクロック周波数が 3.2GHz の場合、1 CPU クロックサイクルは約 0.3125 ナノ秒になります。
CPU 内部のレジスタへのアクセスはほぼこの 1 クロックサイクル で完了します。
一方、メインメモリへのアクセス時間は約 50〜100 ナノ秒かかります。
これは CPU クロックサイクルに換算すると約 160〜320 サイクル に相当します。
つまり、CPU がメインメモリからデータを読みとる間に、CPU は数百もの命令を実行できる時間を待機していることになります。
これではせっかくの高速な CPU の性能を十分に活かせません。
このようにメモリ速度と CPU 速度のギャップのことを「ノイマンボトルネック」と言います。
メインメモリで使用されている DRAM が遅いんであれば、より高度な SRAM をキャッシュに使えばいいじゃないかという考えになります。
そこで CPU 内部には L1 、L2 、L3 の複数段からなるキャッシュ階層が設けられています。
本記事の本筋からは外れてしまうので、ここでの説明は省略します。
メモリのキャッシュライン
CPU は、メモリからデータを取得する際に、データを単体で取得するのではなく、そのデータに加えて隣接するデータも一緒に取得します。
隣接するデータがキャッシュに保存されるというわけです。
この、「隣接データをまとめて取得する単位」のことをキャッシュラインと呼びます。
データの再利用と効率性
全てのプログラムは局所性の法則に従って動作するとされています。
局所性には下記の 2 つの側面が存在します。
時間的局所性
ある項目が参照された場合、その項目が再び参照される確率が高いという性質
この性質を活かすために、メモリから取得したデータは、CPU 内の全階層のキャッシュ（L1 キャッシュ、L2 キャッシュ、L3 キャッシュなど）に書き込まれる空間的局所性
ある項目が参照された場合、その項目の近くにある項目が再び参照される確率が高いという性質
この性質を活かすために、CPU は隣接する要素を一緒にキャッシュに格納する
図を使って説明していきます。
CPU とメモリが以下のようになっているとします。
ここからデータ 4 を取得することを表したのが以下の図です。
この処理が文字列や配列の処理であれば、空間的局所性に従ってデータ 4 の次にデータ 5 にアクセスする可能性が高いです。
というわけで、隣接するデータもまとめてキャッシュに保存しておくことで、次にデータ 5 を参照するときにはわざわざ遅いメインメモリまで取りにいかなくても、キャッシュから取得するだけでよくなります。
キャッシュラインのサイズ
キャッシュラインのサイズは CPU によって異なります。
試しに私の MacBook Pro（Apple M3）で調べてみたところ、キャッシュラインは 128 バイトでした。
$ sysctl hw.cachelinesize > hw.cachelinesize: 128
というわけで、私の Mac では 1 回のメモリ読み込み操作で、隣接する 128 バイトのデータを一度に取得していることになります。
このキャッシュラインの効果を意図的に利用することで、メモリ待ちの無駄な時間を減らし、処理速度を向上させることが可能です。
そこで、勉強会では弊社が主に使用しているプログラミング言語である Ruby を用いて、簡単な配列操作を通じてキャッシュラインの有用性を実際に確認しました。
require 'benchmark' def setup a = [] 10240.times do a << ([0] * 10240) end a end Benchmark.benchmark(Benchmark::CAPTION, 7, Benchmark::FORMAT, ">total:", ">avg:" ) do |x| a = setup x.report("row-col") { for i in (0...10240) for j in (0...10240) a[i][j] += 1 end end } a = setup x.report("col-row") { for i in (0...10240) for j in (0...10240) a[j][i] += 1 end end } end
以下は row-col と col-row のメモリアクセスの違いを図示したものです。
図の青矢印がデータを取得する順序を表しています。
row-col のメモリアクセス
col-row のメモリアクセス
row-col というベンチマークでは行方向のアクセスが主、col-row というベンチマークでは列方向のアクセスが主となっています。
Ruby の内部実装において Array は以下のように len, capa, shared, ptr から成る RArray 構造体として扱われています。
ここでは Ruby 3.3.5 を対象としています。
// Ruby 3.3.5 // 見やすさのために中略してます struct RArray { struct RBasic basic; // クラスの情報などを保持する構造体 union { struct { long len; // 配列のサイズ union { long capa; // メモリ領域の容量 const VALUE shared_root; // 配列が共有状態の時に親配列を指す } aux; const VALUE *ptr; // 配列の要素を格納する C の配列指すポインタ } heap; const VALUE ary[1]; // 配列のサイズが小さい場合はここに直接埋め込む } as; }
2 次元配列は「配列の配列」として保存されるため、内部的には図で表すと以下のように格納されています。
この図から、[0][0] の要素を取得しようとすると、(0) VALUE が参照されます。
空間的局所性から、(0) VALUE の周辺のデータをキャッシュに書き込むので、行方向のアクセスはキャッシュに当たる可能性が高いですが、列方向のアクセスではキャッシュに当たる可能性が低いです。
そのため Ruby でもキャッシュラインを意識したプログラミングが理論上可能で、このベンチマークでもパフォーマンスに大きな差が出るはずです。
行方向アクセスと列方向アクセスで、データの取得方法をよりわかりやすくした図が以下です。
行先行のメモリアクセスイメージ
列先行のメモリアクセスイメージ
測定結果は以下のとおりです。
user の列ではユーザーランドでの実行時間、system の列ではカーネルランドでの実行時間、real は全体の実行時間です。
| user | system | real | |
|---|---|---|---|
| 行方向 | 3.848 | 0.014 | 3.897 |
| 列方向 | 9.045 | 0.023 | 9.180 |
この結果から、行方向アクセスによりデータを処理した場合と列方向アクセスにより処理した場合で、実行時間に 2 倍強の大きな差が生じることを確認しました。
このように、データの配置やアクセスパターンを意識することで、処理の効率を大幅に向上させることができることを確認できました。
疑問
ふと、こんな疑問を抱きました。
「Ruby ってインタプリタ型言語なのにメモリのキャッシュラインとか意識してプログラミングできるのか。他の言語でも同じように意識してできるのかな……?」
というわけで、いくつかの言語で同じようにベンチマークを取ってみることにしました。
実験
以下の環境で実験します。
- OS: macOS Sequoia 15.0.1
- アーキテクチャ: Arm64（Apple M3 Pro）
- メモリ: 24 GB
本実験では、インタプリタ型言語およびコンパイル型言語を含む 5 つのプログラミング言語（Python、Ruby、C、Go、Rust）を対象に、キャッシュラインの効果を検証しました。
以下に各言語のバージョンを示します。
| 言語 | バージョン |
|---|---|
| Python | Python 3.12.7 |
| Ruby | Ruby 3.3.5 |
| C | Apple Clang 16.0.0 |
| Go | Go 1.23.2 |
| Rust | rustc 1.81.0 |
各言語での実装詳細は、こちらのリポジトリをご参照ください。
なるべく全ての言語が平等に実行されるよう、Go や Rust の関数はコンパイル時にインライン展開されないようにオプションをつけ、C ではインライン展開されないように inline 演算子を意図的にオミットしています。
実験条件
- 配列サイズ：50,000
- 繰り返し回数：5 回（平均値を算出）
- 配列の中身は 64bit 符号付き整数
実験結果
各言語における行方向アクセスと列方向アクセスの処理時間平均（秒）は以下の通りです。
| 言語 | 行方向[s] | 列方向[s] |
|---|---|---|
| Python | 64.39385 | 478.37587 |
| Ruby | 81.88193 | 481.23455 |
| C | 2.43678 | 11.88624 |
| Go | 5.72752 | 25.05058 |
| Rust | 4.15397 | 27.12902 |
グラフの縦軸は対数スケールで表示しており、各言語のパフォーマンス差を視覚的に理解しやすくしています。
期待通り、どの言語でも列方向アクセスより行方向アクセスの方が高速に処理されることがわかりました。
考察
上記の結果だけではわかりづらいので、行方向アクセスと列方向アクセスの処理時間の倍率とC 言語を基準とした他言語の処理時間の 2 つの観点から詳細に考察していきます。
1. 行方向アクセスと列方向アクセスの処理時間の倍率
行方向アクセスと列方向アクセスの処理時間の倍率を示すグラフを以下に示します。
このグラフから、言語ごとの倍率が以下のようになっていることが分かります。
- Python: 約 7.4 倍
- Ruby: 約 5.9 倍
- C: 約 4.9 倍
- Go: 約 4.4 倍
- Rust: 約 6.5 倍
どの言語でもアクセス方向を変えたときの処理時間の向上率は比較的同じで、5 ~ 7 倍改善されることがわかりました。
2. C 言語を基準とした他言語の処理時間の比較
C の処理時間を基準（100%）として、他言語の処理時間を比較したグラフを以下に示します。
グラフの縦軸は対数スケールで表示しており、各言語のパフォーマンス差を視覚的に理解しやすくしています。
また、単純な C との比較なのでパフォーマンス比は高いとパフォーマンスが悪く、低いとパフォーマンスが優れていることを表しています。
Rust と Go は、C と比較して行方向アクセス・列方向アクセスどちらも 200% ほど処理時間を要していることがわかります。
これらの言語が C よりも劣っている主な要因として、メモリ安全性を保証するための境界チェックが挙げられます。
境界チェックは、配列やスライスへのアクセス時にインデックスが有効な範囲内であることを確認する処理です。
Rust と Go では、このチェックが各アクセスごとに行われてオーバーヘッドが発生するため、パフォーマンスに影響を与えていることが考えられます。
C は境界チェックを行わないため、各配列アクセスに追加のオーバーヘッドがありません。これにより、高速なメモリアクセスが可能になりますが、メモリ安全性はプログラマの責任となります。
Python・Ruby は、C・Go・Rust に比べて大幅に時間がかかっています。
Python や Ruby では実行方式が異なり、メソッド呼び出しやオブジェクトの取り出しなどのオーバーヘッドが行列アクセスにかかわらず支配的となります。
しかし、アクセス方向による処理時間の倍率は C・Go・Rust と比較しても大きな違いはないことから、コンパイル型言語と同様にキャッシュを考慮した設計によってパフォーマンスを向上可能であることを確認できました。
さいごに
今回の内容は、メモリのキャッシュラインという非常に低いレイヤーに踏み込んだものでしたが、実際にコードを書き、結果を自分で確認することで、プログラムが内部でどのように動作しているかを垣間見ることができました。こうして裏側を理解しながらコードを書く経験を通して、コードがメモリやハードウェアとどのように「共鳴」しているのか、少しずつ「メカニカルシンパシー」を感じられるようになってきた気がします。
その感覚をさらに深めるには、基礎力を固め、実務で応用し、また基礎に立ち返るというプロセスを何度も繰り返していくことが必要だと感じました。道は長いですが、少しずつ精進していきたいです。
おまけ
インタプリタ型言語とコンパイル型言語の性能を比較できたところで、ここからはコンパイル型言語のより深いところまで考察していきます。
要素の型と最適化について見ていきます。
要素の型
実験では、Python や Ruby の型と合わせるために、コンパイル型言語の型を 64bit 符号付き整数にしていました。
では、型指定が可能な言語でこれを32bit 符号付き整数にすると処理時間はどうなるのでしょうか。
32bit、64bit で計測した結果が以下です。
64bit 符号付き整数の結果（再掲）
| 言語 | 行方向[s] | 列方向[s] |
|---|---|---|
| C | 2.43678 | 11.88624 |
| Go | 5.72752 | 25.05058 |
| Rust | 4.15397 | 27.12902 |
32bit 符号付き整数の結果
| 言語 | 行方向[s] | 列方向[s] |
|---|---|---|
| C | 1.43815 | 8.20754 |
| Go | 3.32073 | 21.01973 |
| Rust | 2.70564 | 24.67822 |
行方向アクセスだと 32bit/64bit で 2 倍ほどの処理速度の差がありますが、列方向アクセスだと 1.1 ~ 1.3 倍ほどにとどまっています。
これは、例えば 32bit だと 10 個のデータをキャッシュに乗せることができるとしたとき、32bit だと 5 個しかキャッシュに乗せることができません。
行方向アクセスではキャッシュの恩恵を強く受けているため、64bit にしたときに処理速度の低下率が列方向アクセスと比較して高いことが考えられます。
最適化
今回は、C・Go・Rust の比較の際にマシン語レベルでの差がなるべく小さくなるよう、C の最適化を低いレベル-O1レベルでとどめたり、Rust や Go のインライン展開を無効にしたりしていました。
では、そんなことは無視して C・Go・Rust の最適化オプション群を最大限に効かせたときの処理時間はどうなるのでしょうか。
以下は追加した最適化オプションとその説明です。
これらの最適化を入れた状態で同じベンチマークを行った結果が以下です。
32bit の結果を表示しています。
最適化前の結果（再掲）
| 言語 | 行方向[s] | 列方向[s] |
|---|---|---|
| C | 1.43815 | 8.20754 |
| Go | 3.32073 | 21.01973 |
| Rust | 2.70564 | 24.67822 |
最適化後の結果
| 言語 | 行方向[s] | 列方向[s] |
|---|---|---|
| C | 0.88874 | 7.59235 |
| Go | 2.00809 | 19.63388 |
| Rust | 2.11314 | 24.41771 |
最適化前後で比較すると、C・Go・Rust のすべての言語でパフォーマンスの向上が見られました。
特に C で行方向アクセスした際の処理時間が約 2 倍改善されており、最適化の効果が顕著に現れています。
これは、-O3レベルの最適化により自動的に SIMD 命令とループアンローリングが適用されたためです。
さらに、SIMD 命令とループアンローリングのどちらが処理時間の短縮により大きく寄与したかを調査した結果、SIMD 命令による高速化がより支配的であることがわかりました。
SIMD 命令が適用されることによって以下の恩恵を受けることができます。
- 1 つの命令で複数のデータ（今回は 4 つの 32 ビット整数）に対して同じ操作をする
ldpやstp命令を使用することでメモリから一度に複数のデータを読み書きできる- メモリアクセスの回数が削減される
以下の row_col 関数の最適化前と最適化後の逆アセンブリ結果から確認できます。
なお、ここでは SIMD が適用されている命令列に着目して抜粋しています。
C の最適化前の命令列
... 100003c54: f868782a ldr x10, [x1, x8, lsl #3] ; データのアドレスをロード 100003c5c: b940014c ldr w12, [x10] ; メモリから1つのデータをロード 100003c60: 1100058c add w12, w12, #0x1 ; データに1を加算 100003c64: b800454c str w12, [x10], #0x4 ; 加算結果をメモリにストア ...
C の最適化後の命令列
... 100003af8: 4f000420 movi.4s v0, #0x1 ; ベクトルレジスタv0の4スロットに1を設定 100003b08: ad7f0961 ldp q1, q2, [x11, #-0x20] ; メモリから2つの128ビットデータをロードしてレジスタq1とq2に格納 100003b0c: ad401163 ldp q3, q4, [x11] ; 同様にレジスタq1とq2に格納 100003b10: 4ea08421 add.4s v1, v1, v0 ; ベクトルレジスタv1の各スロットに対してv0の値を加算 100003b14: 4ea08442 add.4s v2, v2, v0 ; ベクトルレジスタv2に同様の処理 100003b18: 4ea08463 add.4s v3, v3, v0 ; ベクトルレジスタv3に同様の処理 100003b1c: 4ea08484 add.4s v4, v4, v0 ; ベクトルレジスタv4に同様の処理 100003b20: ad3f0961 stp q1, q2, [x11, #-0x20] ; レジスタq1とq2のデータをメモリに書き込む 100003b24: ac821163 stp q3, q4, [x11], #0x40 ; レジスタq3とq4のデータをメモリに書き込む ...
SIMD 命令の恩恵や命令列の違いを比較することで、プログラムの高速化の仕組みを具体的に理解できました。
明日のTechouse Advent Calendar 2024は k-hiraoka さんによる プロダクトデザインを前進させるために参考になった本（サイト）たちの話 です。
Techouseでは、社会課題の解決に一緒に取り組むエンジニアを募集しております。 ご応募お待ちしております。
