Rust Atomics and Locks を読んだ

TVアニメ『ぼっち・ざ・ろっく！』はとても面白かったですね。年末年始は『結束バンド』のアルバムをひたすら聴いていました。ロック最高!!

anxmusic.lnk.to

さて、"Rock"も良いのですが、"Lock"についても最近面白い話題がありました。 "Rust Atomics and Locks" という、Rust言語を使ってLockなどの低レベル並行ライブラリを実装してみることで、CPUアーキテクチャにまで踏み込んだ並行プログラミングについて学ぶことができる本が出版されます(電子版は既に入手可能)。

marabos.nl

この著者は実際にRustのMutexやCondvarなどの改良に携わっており、それらを実装するために使われた知識がこの本には満載されています。

この本ではコードは基本的にRustで書かれていますが、最初の第1章でRust言語の並行性に関わる機能が解説されているので、Rustにそれほど詳しくない人でも読むことができると思います。

低レベル並行ライブラリを実装するために必須となるAtomic変数とメモリモデルについては、それぞれ一章ずつ使って詳しく説明されています(2章および 3章)。また、これらが実際のCPU上でどのように動作しているかについて、x86-64とARM64を例にして具体的なサンプルコードやベンチマークなどを用いた説明がまるまる一章あります(7章)。この辺りは、私のブログの過去記事で触れた内容をより深く解説しているものになります。

yamasa.hatenablog.jp
yamasa.hatenablog.jp
yamasa.hatenablog.jp

4, 5, 6章では、実際にAtomic変数を用いてSpin Lock、Channels、Arc(並行参照カウント)を実装してみています。ここでは、ライフタイムなどを意識したよりRustらしいコードにするための方法についても詳しく説明されています。
Spin Lockではない普通のLockでは、ロックが競合したときにスレッドの実行を止めたり再開させたりしなければなりません。これはAtomic変数だけでは実現できないので、カーネルが提供する機能が必要になります。8章では、このスレッドの待機に関わる機能が、LinuxやMacOS、Windowsでどのように提供されているかを解説しています。
そして9章でいよいよ、MutexやCondition Variable(条件変数)、Reader-Writer Lockなどを実装していきます。ここまで読めば、Atomic変数を使った複雑なコードも理解できるようになるでしょう。

最後の第10章では、より発展的な話題としてLock-Freeアルゴリズムなどが紹介されています。

Rust Atomics and Locksは私がこのブログでいずれ書きたいなと思っていたことをほとんど全て網羅した上で詳細かつわかりやすく解説している素晴らしい本ですので、私のブログの過去記事を読んで興味を持った人は是非この本も読んでみてください。ロック最高!!

追記(1/7):
この本の内容がWeb上で無料で読めるようになったそうです!

Apple M1の参照カウントは本当に速いのか

Apple M1に関して以下のようなツイートが話題になった。

Apple M1では参照カウント(reference counting)がIntelプロセッサの何倍も速いらしい。これは本当だろうか?

参照カウントとは

まず、参照カウントについて簡単に説明しておこう。参照カウントとはインスタンスのライフサイクルを管理するための手法の一つで、文字通りそのインスタンスへの参照の数を常にカウントし、参照数が0になったときにインスタンスを破棄するというものである。Swift言語での利用例は以下のようになる。

// MyClassのインスタンスを生成し、それを変数aが参照するようにする。
// 参照カウントは1。
var a: MyClass? = MyClass()

// 変数bも変数aと同じインスタンスを参照するようにする。
// 参照カウントは2。
var b: MyClass? = a

// 変数aの参照をクリアする。
// 参照カウントは1。
a = nil

// 変数bの参照をクリアする。
// 参照カウントが0になったのでMyClassのインスタンスは破棄される。
b = nil

Swift言語では Automatic Reference Counting (ARC) という仕組みによって参照カウントの扱いがプログラムコードからは見えなくなっているが、内部的には上記のように各インスタンスに紐付いた参照カウントが頻繁にインクリメント/デクリメントされている。このインクリメント/デクリメント操作のコストが今回の話の主題である。

Atomic Read-Modify-Write (RMW) 操作とは

参照カウントをマルチスレッドプログラムで使用する場合、参照カウントのインクリメント/デクリメント操作はアトミック(atomic, 不可分)に行わなければならない。さもないと、複数のスレッド間で共有されるインスタンスの参照を正確にカウントすることができなくなってしまう。

このアトミックなインクリメントやデクリメントのような操作を総称して Atomic Read-Modify-Write 操作(以下RMW操作と省略)と呼ぶが、マルチプロセッサのシステムでは必須となる操作であるため、各CPUの命令セットにもRMW操作を行うための機械語命令が用意されている。(単一の命令でRMW操作を実現できるのか、それとも複数の命令を組み合わせてRMW操作を実現するようになっているのかの違いはあるが。)

では、このRMW操作の実行コストはどのくらいあるのだろうか? 「バスロック」という言葉を覚えている人にとっては、RMW操作は非常に実行コストの高いものだという印象があるかもしれない。実際、初期Pentium辺りの大昔のプロセッサにおいてはRMW操作は非常に遅いものだった。x86におけるRMW操作は "LOCK" プレフィックス付きのニーモニックで表されるが、当時のプロセッサにおいてこのLOCKプレフィックスはシステムバスをロックするという意味を持っていた。つまり、CPUがシステムバスを専有状態にして、その間にメインメモリに対する読み書きを連続して行うことでアトミックな操作を実現していたのである。当然、このような方法では実行コストが非常に高くなってしまうし、多数のCPUコアを持つシステムでは全くスケールしない。

そのため、現代のマルチプロセッサシステムでは「バスロック」のような仕組みは用いられていない。そもそも、HyperTransportやQPIの登場によって、現在のx86システムにおいてはロックするような「バス」がもはや存在しないのである。代わりに、現在はキャッシュコヒーレンシの仕組みの上でRMW操作が実現されている。RMW操作の対象となるアドレスのキャッシュラインを専有状態(MESIプロトコルで言えばModifiedまたはExclusive状態)にして、それが維持されている間に読み書きのμOPsを連続して実行することでアトミックな操作を実現しているのである。

このようにして実現されたRMW操作は単一のキャッシュライン上での読み書きだけで完結するため、他のCPUの実行を妨げるようなこともなく、非常に低いコストで実行できるようになる。原理的には、非アトミックに読み書きを行う場合とほとんど変わらない性能を達成することができるはずである。

RMW操作のセマンティクス

ただしここで問題になってくるのは、前回の記事で挙げたメモリアクセスの「セマンティクス」をRMW操作に対しても考えなければならない点である。RMW操作はメモリ読み書きの複合操作であるため、これに適用可能なセマンティクスは以下の5種類が考えられる。

  • Relaxedセマンティック
  • Acquireセマンティック
  • Releaseセマンティック
  • AcquireかつReleaseセマンティック
  • SeqCstセマンティック

これらは上にあるものほどメモリアクセスの順序保証が弱い一方で実行コストが小さくなる。そして、最も弱いRelaxedセマンティックのRMW操作は、実際に非アトミックな読み書きとほとんど変わらない性能を実現することが可能である。しかし、より強いセマンティクスのRMW操作を使う場合は、そのセマンティクスを実現するためのコストが追加でかかってしまうことに注意しなければならない。

参照カウントに必要なセマンティクス

ここまで述べてきたように、現代のCPUにおけるRMW操作の実行コストは非常に小さくなってきている。しかし、その性能を最大限に発揮するには、メモリアクセスのセマンティクスによる追加の実行コストをできる限り小さくするように心がける必要がある。

では、参照カウントを実装するために必要なRMW操作のセマンティクスとはどのようなものだろうか? これについてはRust言語での実装を日本語で解説した記事があるのでそちらを紹介しよう。

qiita.com

今回の話に関わる部分だけを要約すると以下のようになる。

  • 参照カウントをインクリメントするときはRelaxedセマンティックで十分。
  • 参照カウントをデクリメントするときはReleaseセマンティックが必要。

これは参照カウントというアルゴリズム自体の話であるので、他のプログラミング言語で実装する場合においても同じことが言える。例えば、Swift言語内部で使われている実装であればRefCount.hに同様の説明が書かれてある。

さて、このようにして必要最小限のセマンティクスを持つRMW操作を使った参照カウントの実装を書くことはできる。しかし、それをx86(_64)向けにコンパイルすると、全てSeqCstセマンティックのRMW操作を使った場合とほとんど同じバイナリが生成されてしまうのである。その理由は単純で、x86(_64)は全てのRMW命令がSeqCstセマンティックを持っており、それ以外のセマンティクスのRMW命令が存在しないからである。頑張って最適なセマンティクスを使用したコードを書いても、x86ではその利益をほとんど受けることができないのである。

命令セットの違いが参照カウントの性能に与える影響

さあ、これでもう種明かしはほとんどできたようなものだ。

このツイートで述べているのは、参照カウントのインクリメントとデクリメントを繰り返すマイクロベンチマークの結果である。これは実質的に、以下の操作をシングルスレッド上で交互に何度も実行することに等しい。

  • Relaxedセマンティックのアトミックインクリメント
  • Releaseセマンティックのアトミックデクリメント

しかし、このベンチマークをx86_64上で実行させても「全てのRMW命令がSeqCstセマンティックを持つ」ために、実際にはSeqCstセマンティックのインクリメントとデクリメントを繰り返す分の実行コストがかかってしまう。一方で、 ARM(AArch64)の命令セットはRelaxedセマンティックとReleaseセマンティックのRMW操作を個別の命令として表現することができるので、このベンチマークも必要最小限のコストで実行することができるのである。

なお、これはx86とARMの命令セットの違いによるものなので、Apple M1に固有の話ではない。RMW命令の持つセマンティクスが参照カウントなどの性能に影響するという話は昔から言われてきたことであり、特に目新しいものではないのである。また、「参照カウントのインクリメント/デクリメントのマイクロベンチマーク」という題材がこのRMW命令の差を如実に見せるものであり、x86にとって非常に不利な土俵の上での話だという点は強調しておこう。より一般的なプログラムにおいては、参照カウントのインクリメント/デクリメント操作だけでなく、メモリのアロケーション/デアロケーションの速度なども考慮に入れないと総合的な性能を測ることはできない。

参照カウント自体の性能について

さて、AppleのエンジニアであるDavid Smith氏は以下のような興味深いツイートもしている。

参照カウントはTracing GC(単に"GC"と呼ばれることも多い、参照をトレースすることでオブジェクトの生死を判断するタイプのGC)よりもスループットが劣ると言われている。これは、参照カウントのインクリメント/デクリメント操作が非常に多く発生するために、トータルでのオーバーヘッドがかなり大きくなってしまうことによる。

これに対しSmith氏は、ARMのような弱いセマンティクスのRMW命令を持つアーキテクチャではこの評価を覆すことができるのではなかろうか、という問いを投げかけている。Smith氏自身は "I actually don't know." と言っているし、実際にそれを検証するのは困難だろう。参照カウントとTracing GCでは、スループット以外にも多くの特性が異なっているために単純比較するのは難しい。

ただひとつ明らかなのは、弱いセマンティクスによる性能向上が見込まれるのは "uncontended" な場合に限るという点である。"uncontended"とは同時に複数のCPU/スレッドからアクセスされないという意味なので、これは「低い並列度の場合に限る」ということになる。

高い並列度のプログラムでの参照カウントの使用は、キャッシュコヒーレンシの仕組みと致命的に相性が悪い。あるCPUがメモリに書き込みを行う際は、他のCPUに対してそのキャッシュラインをinvalidateさせる処理が行われる。つまり、同じメモリアドレスに対して複数のCPUが頻繁に書き込みを行うとキャッシュのinvalidate処理が頻繁に発生することになるので非常に大きなオーバーヘッドとなってしまう。参照カウントはこの「同じメモリアドレスに対する書き込み」が頻繁に発生するアルゴリズムなので、並列度に対するスケーラビリティが非常に悪いのである。これは原理的な問題であり、弱いセマンティクスの使用などでは解決できない。

そのため、lock-freeアルゴリズムのような高い並列度でスケールすることを目標とするアルゴリズムはTracing GCの存在に依存していることが多い。また、Tracing GCが存在しないLinuxカーネルのような環境においても、RCUやハザードポインタといった参照カウントに代わるアルゴリズムが使用されたりしている。

まとめ

さて、話題が発散してしまいそうなのでまとめに入ろう。今回の話を箇条書きにまとめると以下のようになる。

  • Atomic Read-Modify-Write (RMW) 操作は、現代のCPUアーキテクチャにおいては非アトミックな読み書き操作とほとんど変わらない性能を達成することができるようになった。
  • ただしそれはRelaxedセマンティックのような「弱いセマンティクス」の場合であり、SeqCstセマンティックのような「強いセマンティクス」ではその影響によるオーバーヘッドが大きくなる。
  • x86の命令セットではRMW操作に対するセマンティクスを指定することはできず、全てSeqCstセマンティックとして扱われる。一方、ARMの命令セットでは異なるセマンティクスのRMW操作を記述することができる。
  • 参照カウントのマイクロベンチマークのようなケースでは、このRMW操作のセマンティクスの違いが如実に現れる。ARM上の参照カウントがx86と比べて速いと言われるのもこのためである。
  • そもそも、参照カウントというアルゴリズム自体はそれほどスループットが高くない。特にCPUの並列度に対するスケーラビリティが悪いので、Tracing GCやRCU、ハザードポインタといったアルゴリズムのほうが優れている場合も多い。

これまで3回にわたってx86とARMのメモリモデルの違いに関する話をしてきたが如何だっただろうか? これを機に、メモリモデルについて興味を持って頂けたなら幸いである。

メモリアクセスのセマンティクスとApple siliconの裏技(?)について

アウト・オブ・オーダー実行について補足

前回の記事で「アウト・オブ・オーダー実行」について特に説明せずに話を進めてしまったことに気づいたので、まずはそれについて簡単に補足しておこう。

コンピューターの性能向上の歴史はレイテンシーとの戦いの歴史でもある。

colin-scott.github.io

上のサイトは年代毎にコンピューターシステムでの各種レイテンシーがどのように変化していったかを紹介している。1990年代前半はキャッシュメモリとメインメモリとの間のレイテンシー差はそれほど大きくなかったが、その後の技術革新によって現在はL1キャッシュとメインメモリとの間に100倍くらいのレイテンシー差があるようになってしまった。これはつまり、プログラム実行中にメインメモリへのアクセスが発生してしまうと、それだけ長いレイテンシーの間CPUの処理を進めることができなくなってしまうことを意味する。そのため、このメインメモリへのアクセスの遅さをいかにカバーするかというのがCPUの性能向上における大きなテーマとなっている。

アウト・オブ・オーダー実行もそのための技術の一つで、プログラムコード上の命令列の順序に依らずメモリアクセスの準備が整った命令から実行することで、メインメモリへのアクセス待ちのためにCPUが遊んでしまうような状況を減らす、というものである。

ただし「プログラム上の順序に依らない実行」といっても、意味が変わってしまうようなものはもちろん認められない。例えば以下のようなコードを考えてみよう。

int a = 0;
int b = 0;
int c = 0;

CPU1:
  a = 1;
  b = 2;
  c = a + b;

ここで b = 2; の書き込みだけ後回しにして最終的に c == 1 になってしまうようでは当然ダメである。しかし一方で、最終的に a == 1 && b == 2 && c == 3 になるのであれば、変数a, b, cそれぞれへの書き込みはどのような順序で行われても構わない、という点が重要である。 c = a + b; の右辺が3になることは変数a, bのメモリアドレスへ実際にアクセスしなくてもわかる(このような技術をBypassあるいはForwardingと呼ぶ)ので、例えば変数bへのアクセスが大幅に遅れてしまったとしても変数cへの書き込みは先に完了させられる、といったことができるようになる。

メモリアクセスの「セマンティクス」

さて、メモリモデルの話に戻ろう。前回の記事で

デフォルトでは「強いメモリモデル」を提供せずにもっと緩い条件を認める一方、一部のマルチスレッドプログラム用にメモリアクセスの順序を明示的に指定するための機械語命令を用意したアーキテクチャ

という話をしたが、ここで言う「もっと緩い条件」や「メモリアクセスの順序を明示的に指定する」とは具体的にどんなことだろうか? 同じ「弱いメモリモデル」のアーキテクチャだとされるARMとPowerPCとの間でもメモリアクセスの仕様については大きく差があるし、「どの命令を使用するとメモリアクセスの順序をどう指定できるか」というのはそれこそ各CPUの詳細なドキュメントを個別に読み解かなければならないような話である。

だからといって、メモリアクセスの挙動を理解してプログラムコードを書くには各CPUアーキテクチャの細かな仕様を把握する必要があるというのでは無理がある。そこで、「プログラムコードを書く側が期待する挙動」に着目して、メモリアクセスの順序についてCPU(やコンパイラ)が満たすべき抽象的なルールを何種類かに分類して定義するということが行われた。分類されたメモリアクセスの挙動は、それぞれが満たすべきルールを持つ「セマンティクス」として表される。大きく3つに分けることができるこの「メモリアクセスのセマンティクス」とは以下のようなものである。

  • Relaxedセマンティック
  • Release/Acquireセマンティック
  • Sequentially consistent (SeqCst)セマンティック

それぞれについて説明していこう。

Relaxedセマンティック

Relaxedセマンティックが満たすべきルールは以下の2つである。

  • あるCPU(スレッド)が行うメモリアクセスは、同じCPU(スレッド)からはプログラム上の順序と矛盾しないように見えなければならない。
  • 同じメモリアドレスに対するアクセスは全てのCPU(スレッド)間で同一の順序として観測される。

1つめのルールは先程アウト・オブ・オーダー実行について述べたことと同じである。つまり、同一CPU(スレッド)から見た結果が変わらない限りにおいては、実際のメモリアクセスの順序を変えてもよいことを意味している。

2つめのルールはキャッシュコヒーレンシに関するものである。現代のマルチプロセッサシステムではキャッシュコヒーレンシという仕組みにより、同じメモリアドレスに対するアクセスが一貫性を持つように制御されている。CPUがあるアドレスに書き込みを行う場合、同じアドレスに対する他のCPU上のキャッシュをinvalidateする、といった制御が自動的に行われているのである。Relaxedセマンティックもそのような仕組みが存在することを想定しているので、同一アドレスに対するアクセス順序は常に一貫性を持つと決められている。

ただしこのルールは裏を返すと、「異なるCPU(スレッド)間において異なるメモリアドレスに対するアクセスが観測される順序は基本的に不定であり、またその順序はCPU(スレッド)間で一貫性が保たれていなくてもよい」ということを意味している。すなわち、異なるメモリアドレスに対するアウト・オブ・オーダー実行については特に制限しない、ということになる。

このように、Relaxedセマンティックでは現代のマルチプロセッサシステムが持つべき最低限のルールだけを定義しており、そのルールを満たす限りにおいて、アウト・オブ・オーダー実行などの最適化を最大限に認めている。その点では、Relaxedセマンティックは最もオーバーヘッドの少ないセマンティックと言うことができる。

Release/Acquireセマンティック

Release/Acquireセマンティックとは、メモリへの書き込み(ストア)アクセスに付随するReleaseセマンティックと読み込み(ロード)アクセスに付随するAcquireセマンティックの総称である。Release/Acquireセマンティックが満たすべきルールは、Relaxedセマンティックが持つ2つのルールに以下を加えたものになる。

  • あるCPU(スレッド)がReleaseセマンティックで書き込んだ値を別のCPU(スレッド)がAcquireセマンティックで読み込んだ場合、「Releaseセマンティックの書き込みよりもプログラム順で前にある全てのメモリアクセス(セマンティクスは問わない)」と「Acquireセマンティックの読み込みよりもプログラム順で後にある全てのメモリアクセス(セマンティクスは問わない)」の間で前後関係が強制される。

文章だとわかりにくいので具体的な例を挙げよう。

int a = 0;
int b = 0;

CPU1:
  a = 1;  // Relaxedセマンティック
  b = 1;  // Releaseセマンティック

CPU2:
  int r1 = b;  // Acquireセマンティック
  int r2 = a;  // Relaxedセマンティック

// 変数aへのアクセスはRelaxedセマンティック、
// 変数bへのアクセスはRelease/Acquireセマンティックで行われるとする。
// このとき、 "r1 == 1 && r2 == 0" という結果は起こり得ない。

r1 == 1 だと仮定したときに変数bへの読み書きに注目すると、これはCPU1が b = 1; で書き込んだ値をCPU2が int r1 = b; で読み込んだことを意味する。ここでRelease/Acquireセマンティックのルールを適用すると、「b = 1; よりもプログラム順で前にある a = 1;」と「int r1 = b; よりもプログラム順で後にある int r2 = a;」の間で前後関係が強制される、すなわち「a = 1; は int r2 = a; よりも前である」ことが決まる。故にこの場合は r2 == 1 でなければならないと結論づけられるのである。

別の例を挙げよう。

int a = 0;
int b = 0;

CPU1:
  int r2 = a;  // Relaxedセマンティック
  b = 1;  // Releaseセマンティック

CPU2:
  int r1 = b;  // Acquireセマンティック
  a = 1;  // Relaxedセマンティック

// 変数aへのアクセスはRelaxedセマンティック、
// 変数bへのアクセスはRelease/Acquireセマンティックで行われるとする。
// このとき、 "r1 == 1 && r2 == 1" という結果は起こり得ない。

先程と同様に r1 == 1 と仮定して変数bへの読み書きに注目すると、CPU1が b = 1; で書き込んだ値をCPU2が int r1 = b; で読み込んでいることになる。ここでRelease/Acquireセマンティックのルールを適用すると、「b = 1; よりもプログラム順で前にある int r2 = a;」と「int r1 = b; よりもプログラム順で後にある a = 1;」の間で前後関係が強制される、すなわち「int r2 = a; は a = 1; よりも前である」ことが決まる。故にこの場合は r2 == 0 でなければならないと結論づけられるのである。

Release/Acquireセマンティックを用いることで、異なるCPU間で観測されるメモリアクセスの順序について制限をかけることができる。Mutexのような排他制御を行うライブラリは、異なるCPU(スレッド)がそれぞれのクリティカルセクション内で行った操作の順序付けを保証するためにRelease/Acquireセマンティックを内部で使用している。また、Channelのようなスレッド間でデータをやり取りするためのライブラリも、送信側が書き込んだ内容が確実に受信側から見えることを保証するためにRelease/Acquireセマンティックを内部で使用している。

このようにRelease/Acquireセマンティックは特にスレッドライブラリにおいて重要な仕組みとなるが、一方でこのセマンティックの使用によりアウト・オブ・オーダー実行などの最適化にはある程度の制限がかかることになる。この点で、Release/AcquireセマンティックはRelaxedセマンティックよりもオーバーヘッドが大きいと考えることができる。

Sequentially consistent (SeqCst)セマンティック

Sequentially consistent (SeqCst)セマンティックとは、Release/Acquireセマンティックまでの全てのルールに加えて以下のルールを持つものである。

  • Sequentially consistent (SeqCst)セマンティックを持つ全てのメモリアクセスは、全てのCPU(スレッド)の間で逐次一貫性(sequential consistency)を持たなければならない。

これも具体的な例を挙げよう。

int a = 0;
int b = 0;

CPU1:
  a = 1;  // SeqCstセマンティック
  int r1 = b;  // SeqCstセマンティック

CPU2:
  b = 1;  // SeqCstセマンティック
  int r2 = a;  // SeqCstセマンティック

// 変数a, bへのアクセスは全てSeqCstセマンティックで行われるとする。
// このとき、 "r1 == 0 && r2 == 0" という結果は起こり得ない。

もしこのコードで "r1 == 0 && r2 == 0" という結果が得られたとすると、実際に変数a, bへの読み書きが行われた順序としてプログラムコードと矛盾しない一貫性のある順序を示すことができないことがわかるだろうか。このように、異なるCPU(スレッド)間の異なるメモリアドレスに対するアクセスの順序も一貫性を持つことを要求するのがSeqCstセマンティックである。

一方で、このサンプルコードにおいてSeqCstセマンティックの代わりにRelease/Acquireセマンティックを用いた場合は、 "r1 == 0 && r2 == 0" が起こり得ないことを保証できない点にも注意してもらいたい。Release/Acquireセマンティックのルールは「あるCPUが書き込んだ値を別のCPUが読み込んだとき」に適用可能であって、この例のようにどちらのCPUも他方のCPUが書き込んだ値を読み込んでいない場合には適用できないのである。

SeqCstセマンティックの持つ強い一貫性はプログラムを書く側からするとわかりやすいルールではあるが、CPU側からすると「先行する書き込みの内容が確実に他CPUから見えるようになる(globally visible)まで後続の処理を進めることができない」という制限になる。これはパイプライン処理の観点からすると非常に大きなペナルティとなるため、実行コストはRelease/Acquireセマンティックよりも更に大きくなる。すなわち、SeqCstセマンティックはRelease/Acquireセマンティックよりも更にオーバーヘッドが大きいと言うことができる。

x86-64メモリモデルの分析

さて、これまで述べてきた3つのセマンティクスをそれぞれのオーバーヘッドとともに再掲しよう。

  • Relaxedセマンティック (オーバーヘッド無)
  • Release/Acquireセマンティック (オーバーヘッド小〜中)
  • Sequentially consistent (SeqCst)セマンティック (オーバーヘッド大)

これらのセマンティクスを持つメモリアクセスを実際にx86-64アーキテクチャ上で行うにはどうすればよいか考えてみよう。

前回の記事で述べたように、x86-64アーキテクチャで複数のメモリアドレスに対する書き込みと読み込みの順序はそれぞれ「他のCPUから変更が見えるようになる(globally visible)順序」と矛盾しないようになっている。これは、x86-64のメモリアクセスがデフォルトでRelease/Acquireセマンティックを持っていることを意味する。つまり、Release/Acquireセマンティックを必要とするメモリアクセスをx86-64の機械語命令にコンパイルする際は、x86-64の通常のストア・ロード命令である MOV 命令を使用すればよい、ということになる。

この MOV 命令は、Relaxedセマンティックのメモリアクセスに対しても使用することができる。これはRelaxedセマンティックとRelease/Acquireセマンティックの関係から明らかである。

一方で、この MOV 命令はそれ単体ではSeqCstセマンティックを満たさない。x86-64でSeqCstセマンティックを満たすためには、ストア命令として XCHG 命令を使用するか MOV と MFENCE の2命令を続けて使用する必要がある。

といったことが以下のサイトに書かれてある。

www.cl.cam.ac.uk

このように、CPUのストア・ロード命令がどのようなセマンティクスを持つか調べることにより、プログラムコードに必要とされるセマンティクスを満たすにはどの命令を使用すれば良いのかがわかるのである。

ARM(AArch64)メモリモデルの分析

同様にしてARMの64bitアーキテクチャ(AArch64)についてもメモリモデルのセマンティクスを調べてみよう。といっても先程の "C/C++11 mappings" のページを下にスクロールすれば答えは書いてある。

AArch64の通常のストア・ロード命令 STR/LDR はRelaxedセマンティックを持っている。

Release/Acquireセマンティックが必要なところは STR/LDR 命令では不十分なので、代わりに STLR/LDAR 命令を使用する。

興味深いのはSeqCstセマンティックについてで、それに対しても単体の STLR/LDAR 命令だけで十分だとされている。つまり、AArch64の STLR/LDAR 命令は実際はSeqCstセマンティックを持っているということになる。

AArch64がRelease/AcquireセマンティックとSeqCstセマンティックのために別々の命令を用意しなかった理由については良くわからない。しかし、先程の "C/C++11 mappings" のページはARMのエンジニアのレビューも受けているようなので、書いてある内容が間違っているわけではなさそうである。

Rosetta2によるストア・ロード命令の変換

さて、これでようやくRosetta2の話をする準備が整った。

Rosetta2とはx86-64のバイナリをAArch64のバイナリに変換して実行してくれるツールである。この変換において、プログラムコードの多くの部分で使われるストア・ロード命令をどのようにマッピングするかが、変換後のバイナリの動作に大きく影響することは容易に想像がつくだろう。

仮にx86-64の MOV 命令をAArch64の STR/LDR 命令にマッピングするように変換したとしよう。元のプログラムコードが MOV 命令をRelaxedセマンティックのつもりで使用していたなら、変換後のバイナリも正しく動作する。しかし、元のコードが MOV 命令をRelease/Acquireセマンティックが必要な場所で使用していたとすると、STR/LDR 命令はそのセマンティックを満たさないために誤動作する可能性がある。具体的には、マルチスレッドのコードで他スレッドの予期せぬ値を読み取ってしまってクラッシュするなどの不具合が考えられる。

つまり、x86-64のバイナリを見るだけでは MOV 命令がRelaxedとRelease/Acquireのどちらのセマンティックで用いられているかは判断できないので、安全側に倒して全てRelease/Acquireセマンティックだと仮定して変換する必要がある、ということになる。そうすると、x86-64バイナリの MOV 命令は全てAArch64の STLR/LDAR 命令に変換しなければならなくなるが、これだと今度はパフォーマンス上の問題が出てくる。

前節で述べたように、AArch64の STLR/LDAR 命令は実際にはSeqCstセマンティックを持っている。よってこれを MOV 命令の変換先として用いてしまうと、SeqCstセマンティックのオーバーヘッドの大きさのために、変換後のバイナリの実行速度はかなり遅くなってしまうだろう。

Apple silicon のTSOモード(?)

さて、このx86-64とAArch64との間のセマンティクスのギャップによる問題に対して、Appleのエンジニアはとんでもない裏技を使ったようである。

github.com

TSO (Total Store Ordering) とは、デフォルトのストア・ロード命令がRelease/Acquireセマンティックを持つようになるメモリモデル、つまりx86-64と同等のメモリモデルのことである。Apple siliconにはメモリモデルをこのTSOに変更するモードが搭載されており、Rosetta2はこれを使用しているとのことである。

つまり、Rosetta2はx86-64の MOV 命令をAArch64の STR/LDR 命令に変換し、その変換後のバイナリを上記のTSOモードを有効にしたプロセスとして実行しているということである。このTSOモードにおいては STR/LDR 命令もRelease/Acquireセマンティックで動作するので、Relaxedセマンティックによる不具合も発生せず、またSeqCstセマンティックによるパフォーマンス劣化も起こさないということになる。

このTSOモード(?)というのは少なくとも現時点ではARMの正式な仕様として定義されているものではないようなので、AppleがM1プロセッサだけに搭載した特別なカスタマイズということになる。まさに裏技というしかない。

さて、また長くなってしまったので今回はここまで。次回は参照カウントについての話をしよう。

「強いメモリモデル」と「弱いメモリモデル」

Apple M1についての面白い記事を見かけて、久しぶりにメモリモデル屋(?)の血が騒いだのでブログを書く。

note.com

強いメモリモデル

現代のCPUアーキテクチャでは、x86(64bit, 32bitどちらも)が「強いメモリモデル」を採用しており、それ以外のメジャーなCPUが「弱いメモリモデル」を採用している。この「強いメモリモデル」「弱いメモリモデル」について、まずおさらいしておこう。

以下のように、2つの変数a, bに対して異なるCPUコアが同時にアクセスしたとする。

int a = 0;
int b = 0;

CPU1:
  a = 1;
  b = 1;

CPU2:
  int r1 = b;
  int r2 = a;

(上記はC言語に似た疑似コードを用いているが、実際は機械語命令になっていると考えてほしい。つまり、CPU1は変数a, bの示すメモリアドレスに対するストア命令を実行しており、CPU2は同じメモリアドレスに対するロード命令を実行しているということである。)

このようなコードが実行されたとき、 r1 == 1 && r2 == 0 という結果は起こり得るだろうか? 「強いメモリモデル」を採用するx86では、そのような結果が起こり得ないことが保証されている。 r1 == 1 は変数bに対してCPU1が書き込みをした後にCPU2が読み込みをしたことを示している。よってその場合、CPU2が変数aから読みだした値 r2 も、CPU1が書き込んだ 1 でなければおかしい、ということである。

しかしこの「強いメモリモデル」はCPUの内部動作に重大な制約を強いることになる。近年のCPUでは当たり前のようにアウト・オブ・オーダー実行が行われているが、先程のコードで素朴に変数a, bへのアクセスをリオーダーしてしまうと、もはや「r1 == 1 && r2 == 0 という結果が起こり得ない」ということを保証できなくなってしまう。そのため、x86アーキテクチャでは以下のようなルールを守った範囲でだけアウト・オブ・オーダー実行などの最適化を行っている。

  • あるCPUが複数のメモリアドレスに対して行った書き込みの結果が「他のCPUから見えるようになる(globally visible)」順序は、機械語命令の順序と矛盾してはならない。
    • つまり上の例で言うと、CPU1が変数bへ書き込んだ値は変数aよりも先にCPU2から見えるようになってはならない、ということである。
  • あるCPUが複数のメモリアドレスに対して行った読み込みの結果は、それらがglobally visibleになった順序と矛盾してはならない。
    • つまり上の例で言うと、CPU2がある時点の変数bの値を読みだした場合、その時点での変数aの値(=その時点でglobally visibleになっている値)よりも古い値を読み出してはならない、ということである。
    • 変数aのメモリアドレスだけがキャッシュメモリに乗っている場合などは、変数bの読み込みよりも先に変数aの読み込みを投機的に実行するのは認められている。しかしその場合でも、上記のルールに矛盾する可能性を検知したときは投機的実行をキャンセルして変数aの読み込みをやり直さなければならない。

かなり複雑ではあるが、このルールをほぼ全てのメモリアクセスに対して適用することでx86アーキテクチャは「強いメモリモデル」を実現しているのである。

弱いメモリモデル

さて、ここまでの解説を読んだら当然浮かぶ疑問は「もしこの強いメモリモデルのルールを捨てることができれば、CPUはより高速に動作できるようになるのではないか」というものであろう。

実際、強いメモリモデルはほとんどのプログラムコードでは不要である。メモリモデルとは上で述べたように「同じメモリアドレスに対して複数のCPUコアが同時にアクセスした」場合の挙動を定義するものであるので、mutexなどによって排他制御を正しく行っていれば考える必要のないものである。しかし一方で、このmutexのようなマルチスレッドライブラリ自身の内部実装では、メモリモデルに関する考慮が非常に重要になってくる。

そのため、デフォルトでは「強いメモリモデル」を提供せずにもっと緩い条件を認める一方、一部のマルチスレッドプログラム用にメモリアクセスの順序を明示的に指定するための機械語命令を用意したアーキテクチャ、というものを考えることができる。これがx86以外の現代の多くのCPUアーキテクチャで用いられている「弱いメモリモデル」である。

「弱いメモリモデル」は「強いメモリモデル」よりも制約が緩い分、CPU内部実装の最適化・高速化の面で有利なはずである。しかし何故x86は現在もまだ強いメモリモデルを採用しているのかというと、互換性の問題があるからである。デフォルトのメモリモデルを変えてしまうと、強いメモリモデルを前提として実装されている既存のマルチスレッドライブラリが誤動作してしまうのである。そのため、デフォルトのメモリモデルを変更することは、命令セットの切り替えのような大幅な刷新が行われるタイミングでないと難しい。

インテルもItanium(IA-64)プロセッサでは弱いメモリモデルを採用したのだが、御存知の通りItaniumは終了してしまっている。対抗のx86-64(AMD64)アーキテクチャは既存の32bitコードとの互換性を重視したために以前と同じ強いメモリモデルを採用したので、x86アーキテクチャはメモリモデルの切り替えを行う最大のチャンスを逃してしまったということになる。

だいぶ長くなってしまったので、続きは別記事で。

ふと思いついて書いた。後悔はしていない。

ネタ

昨日、マルチスレッドなプログラムのコードを読んでたんです。マルチスレッド。
そしたらなんかロックがめちゃくちゃ競合しててパフォーマンスが出ないんです。
で、変更履歴よく見たらなんか全メソッドを一つのmutexでロックして、マルチスレッドに対応した、とか書いてあるんです。
もうね、アホかと。馬鹿かと。
お前らな、単一mutexで囲うだけの対応如きでマルチスレッド対応とか言ってんじゃねーよ、ボケが。
単一mutexだよ、単一mutex。
なんかthreadを作りまくってる箇所もあるし。多重ループの内側でthread生成か。おめでてーな。
よーしデータを細分化してガンガン別スレッドで処理しちゃうぞー、とかやってるの。もう見てらんない。
お前らな、Fork/Joinフレームワークのスレッドプール実装やるからそれ使えと。
マルチスレッドってのはな、もっと殺伐としてるべきなんだよ。
Work-stealing dequeを持ったスレッド同士がいつタスクをstealしてもおかしくない、
盗むか盗まれるか、そんな雰囲気がいいんじゃねーか。Lock-freeじゃない奴は、すっこんでろ。
で、ようやくdata raceの箇所を見つけたかと思ったら、コメントに、gccの最適化でバグるのでvolatileを付ける、とか書いてるんです。
そこでまたぶち切れですよ。
あのな、volatileなんてC++のマルチスレッドプログラムじゃ意味ねーんだよ。ボケが。
得意げな顔して何が、最適化でバグる、だ。
お前は本当にメモリモデルを理解してるのかと問いたい。問い詰めたい。小1時間問い詰めたい。
バグってるのはお前のコードのほうちゃうんかと。
マルチスレッド通の俺から言わせてもらえば今、マルチスレッドプログラミングでの最新流行はやっぱり、
non seq_cst atomics、これだね。
非seq_cstなatomic変数 + seq_cst fence。これが通の作り方。
non seq_cst atomicsってのはatomic変数へのアクセスにmemory_order_seq_cstを指定しない。そん代わりオーバーヘッドが少なめ。これ。
で、それを補完する明示的なmemory_order_seq_cstメモリフェンス。これ最強。
しかしこれをやると次からHans Boehm先生にマークされる*1という危険も伴う、諸刃の剣。
素人でなくてもお薦め出来ない。
まあお前らド素人は、毎日 Good morning all! とでもつぶやいてなさいってこった。

*1:Boehm先生はdata raceによる絶望からプログラマを救うため、seq_cst以外のatomic変数を全て消し去りたいと願っているのです。

私立C++女学園 マルチスレッド科

ネタ

ここは私立C++女学園。
由緒あるこの学園も、時代の流れに押され大きな変革の時を迎えていた。新たに学園に設けられることとなった「マルチスレッド科」。物語はここから始まる……

登場人物

memory_order_seq_cstさん
学級委員長。どんなことも完璧にこなす優等生であり、先生や他の生徒からの信頼も厚い。ただ、あまりの完璧主義者ゆえに、何でも全て順番どおりにやらないと気が済まないところが、ある意味欠点でもある。
memory_order_releaseさんとmemory_order_acquireさん
シンクロナイズドスイミング部に所属する双子の姉妹。二人の息の合ったシンクロ演技には、部内に限らずファンが多い。学園内では、memory_order_seq_cstさんと人気を二分していると言ってよいだろう。
memory_order_acq_relさん
あまり目立たない生徒だが、実はmemory_order_releaseさんやmemory_order_acquireさんの姉である。才能に恵まれているにも関わらず、その存在感の薄さ故にC(ry先生からも忘れ去られてしまったこともある不遇の生徒。
memory_order_relaxedさん
一見すると普通の平凡な生徒。しかし彼女は、魔法の杖(fence)によって変身する魔法少女なのである。魔法の力で何でもできるはずなのだが、実際はよく変身に失敗してしまうドジっ娘属性の持ち主である。
memory_order_consumeさん
学園一の不良生徒。彼女のために校則すらも書き変えられたという逸話がある。夜な夜な公道レースに参加しているという噂もあり、彼女のスピードに魅了された者たちが死のレース(data race)によって次々と命を落としているらしい……
Java女学院のvolatileさん
C++女学園から少し離れたところにあるJava女学院のマルチスレッド科に所属する生徒。昔、とある問題に躓いたことをきっかけに猛勉強した結果、他の学校からも一目置かれるほどの才女となった。memory_order_seq_cstさんが慕い、目標としている相手が彼女である。そのせいか、二人の仕草はとてもよく似ている。
C++女学園のvolatileさん
よく間違われるのだが、彼女はマルチスレッド科の生徒ではない。勘違いで彼女宛に送られてくる手紙の多さに、いつも辟易としている毎日である。

メモリバリアを理解するために必要な3つのこと

programming multithreading

Togetter - 「メモリバリアとガチャピン先生」
上の話において、「メモリバリア」の意味するところをもう少し明確にすべきかなあと思ったので、簡単にまとめてみます。
「メモリバリア」が満たすべき性質は、以下の3つに分類することができます。

  1. atomicity
  2. release/acquire fence
  3. sequential consistency

これらの性質は、C++0xのmemory_orderと以下のように対応しています。

C++0x memory_order 持っている性質
memory_order_relaxed atomicity
memory_order_acquire, memory_order_release, memory_order_acq_rel atomicity + release/acquire fence
memory_order_seq_cst atomicity + release/acquire fence + sequential consistency

atomicity とは文字通り「不可分な」操作を保証するものですが、その影響は操作対象のオブジェクトに限定されます。つまり、あるatomic変数に対する memory_order_relaxed でのアクセスは、他の変数に対するアクセスの順序付けには何も影響しません。
一方 release/acquire fence では、release操作とacquire操作の対によってアクセスの順序付けを行ないます。この順序付けの効果は、releaseより前とacquireより後にある全ての変数に対して影響します。
そして、この release/acquire fence を用いても実装できない、「複数のatomic変数に対する書き込みの見た目の順序に依存するようなアルゴリズム」を実装するために必要なのが sequential consistency になります。
これら3つの性質について、x86アーキテクチャでの実現方法は以下のようになります。

単純なread, write read-modify-write
atomicity 対象の変数が正しくalignされていればよい lock-prefix付き命令を用いる
release/acquire fence 自動的に保証される 自動的に保証される
sequential consistency writeを XCHG または MOV+MFENCE にする lock-prefix付き命令を用いる

このように、CMPXCHGやXADDなどのread-modify-write命令では atomicity の実現のためだけでも lock-prefix が必要となりますが、その結果 sequential consistency までもオマケに付いてくることになるわけです。