Apple M1の参照カウントは本当に速いのか
Apple M1に関して以下のようなツイートが話題になった。
18/ Another "magic" trick is how their "Swift" programming language uses "reference counting" instead of the "garbage collection" in Android. They did something in their CPU to double the speed of reference counting.
— Robᵉʳᵗ Graham😷, provocateur (@ErrataRob) 2020年11月26日
fun fact: retaining and releasing an NSObject takes ~30 nanoseconds on current gen Intel, and ~6.5 nanoseconds on an M1
— David Smith (@Catfish_Man) 2020年11月10日
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言語での実装を日本語で解説した記事があるのでそちらを紹介しよう。
今回の話に関わる部分だけを要約すると以下のようになる。
- 参照カウントをインクリメントするときはRelaxedセマンティックで十分。
- 参照カウントをデクリメントするときはReleaseセマンティックが必要。
これは参照カウントというアルゴリズム自体の話であるので、他のプログラミング言語で実装する場合においても同じことが言える。例えば、Swift言語内部で使われている実装であればRefCount.hに同様の説明が書かれてある。
さて、このようにして必要最小限のセマンティクスを持つRMW操作を使った参照カウントの実装を書くことはできる。しかし、それをx86(_64)向けにコンパイルすると、全てSeqCstセマンティックのRMW操作を使った場合とほとんど同じバイナリが生成されてしまうのである。その理由は単純で、x86(_64)は全てのRMW命令がSeqCstセマンティックを持っており、それ以外のセマンティクスのRMW命令が存在しないからである。頑張って最適なセマンティクスを使用したコードを書いても、x86ではその利益をほとんど受けることができないのである。
命令セットの違いが参照カウントの性能に与える影響
さあ、これでもう種明かしはほとんどできたようなものだ。
fun fact: retaining and releasing an NSObject takes ~30 nanoseconds on current gen Intel, and ~6.5 nanoseconds on an M1
— David Smith (@Catfish_Man) 2020年11月10日
このツイートで述べているのは、参照カウントのインクリメントとデクリメントを繰り返すマイクロベンチマークの結果である。これは実質的に、以下の操作をシングルスレッド上で交互に何度も実行することに等しい。
- Relaxedセマンティックのアトミックインクリメント
- Releaseセマンティックのアトミックデクリメント
しかし、このベンチマークをx86_64上で実行させても「全てのRMW命令がSeqCstセマンティックを持つ」ために、実際にはSeqCstセマンティックのインクリメントとデクリメントを繰り返す分の実行コストがかかってしまう。一方で、 ARM(AArch64)の命令セットはRelaxedセマンティックとReleaseセマンティックのRMW操作を個別の命令として表現することができるので、このベンチマークも必要最小限のコストで実行することができるのである。
なお、これはx86とARMの命令セットの違いによるものなので、Apple M1に固有の話ではない。RMW命令の持つセマンティクスが参照カウントなどの性能に影響するという話は昔から言われてきたことであり、特に目新しいものではないのである。また、「参照カウントのインクリメント/デクリメントのマイクロベンチマーク」という題材がこのRMW命令の差を如実に見せるものであり、x86にとって非常に不利な土俵の上での話だという点は強調しておこう。より一般的なプログラムにおいては、参照カウントのインクリメント/デクリメント操作だけでなく、メモリのアロケーション/デアロケーションの速度なども考慮に入れないと総合的な性能を測ることはできない。
参照カウント自体の性能について
さて、AppleのエンジニアであるDavid Smith氏は以下のような興味深いツイートもしている。
Idle though: I wonder how much of the standard literature around e.g. memory management performance has an implicit dependency on x86-style strongly ordered memory models, and in particular slow uncontended atomic compare and swap.
— David Smith (@Catfish_Man) 2020年10月20日
As an example, uncontended ObjC reference counting is ~5x faster on modern Apple ARM than it is on modern Intel. Does that change the balance vs GC? Is GC also cmpxchg-bound? I actually don't know. Does it change the balance at low core count while leaving it at high concurrency?
— David Smith (@Catfish_Man) 2020年10月20日
This is one of the more depressing inverted performance profiles I’ve ever seen. Like… I know how to fix a lot of stuff here, but this absolutely guarantees it’s gonna be a massive slog of 1% at a time wins :( pic.twitter.com/119WudHxnC
— David Smith (@Catfish_Man) 2020年12月9日
参照カウントは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のメモリモデルの違いに関する話をしてきたが如何だっただろうか? これを機に、メモリモデルについて興味を持って頂けたなら幸いである。