24日目のエントリです。Rustのゼロコスト抽象化が期待どおりに働いていることを、コンパイラが出力した機械語(アセンブリコード)で確認します。abstraction)とは、Rustが持つ抽象化のしくみが実行時の追加コストなしに動作することです。ここでいう追加コストとは、メモリ使用量の増加や実行速度の低下などの、いわゆるオーバーヘッドを指します。プログラミングにおける抽象化とは、共通な部分を抽出し、その詳細をブラックボックス化することです。これにより仕様変更に強く、再利用性の高いソフトウェアを開発できます。Rustが提供する抽象化のしくみには、たとえば以下のようなものがあります。ポリモーフィズム:いくつかの型に共通する振る舞い(メソッド)を抽出し、トレイトとして定義する。その振る舞いをどう実現するかは個々の型の実装に委ねられ、メソッドを呼ぶ側では意識しなくてよい高階関数:高階関数とはクロージャを引数にとったり、戻り値として返したりする関数やメソッドのこと。イテレータやOption<T>では、それらが包んでいる値を操作するためにmapやfilterなどのメソッドが定義されている。具体的な操作の内容はこれらのメソッドでは定義されておらず、引数にとるクロージャによって実現されるこれらのしくみはRustでプログラミングするうえで欠かせないものです。一般的なプログラミング言語では抽象化のしくみを使うと実行時のオーバーヘッドがかかることがよくあります。ポリモーフィズムを実現するために使われる動的ディスパッチなどがそうです。(動的ディスパッチについては後ほど説明します)一方、Rustではこれらをできる限りコンパイル時に解決し、実行時にはゼロコストになるよう、言語自体や標準ライブラリが設計されています。システム資源の効率的な使用と制御が求められる、システムプログラミング言語ならではの特徴といえるでしょう。机上で最適化の動作を理解するRustのゼロコスト抽象化と呼ばれる機能は、主に以下のものがあります。トレイトメソッドとクロージャFutureこの記事では前者について見ていきます。以下のコードについて調べます。456);このコードはκeenさんが2016年に書かれた以下の記事で紹介されていたものをベースにしています。Blog短いコードですがTとして参照型を持つOption<T>型と、ジェネリックな高階関数のmap()メソッドを使用しています。これらがコンパイル時にどう最適化されて、実行時のオーバーヘッドがなくなるのか調べます。κeenさんの記事とかぶりますが、まずはコンパイラの最適化の内容を机上で確認しましょう。列挙型とnullableポインタ最適化Option<T>型から見ていきます。今回のコードですが、変数o1はOption<&i64>型、o2はOption<i64>型です。標準ライブラリのOption<T>型は列挙型として定義されており、NoneとSomeの2つの列挙子(バリアント)を持ちます。Some(T),}Rustの列挙型は実行時にバリアントを識別できるよう、ほとんどの場合でタグと呼ばれる通し番号が付与されます。タグの分だけ余分にメモリを使うわけですから、ゼロコストではありません。例としてo2の型であるOption<i64>のメモリ上の表現を見てみましょう。Some(100)のときは以下のようになります。Noneのときは以下のようになります。タグを見ればバリアントがわかるわけです。(1ならSome(i64)、0ならNone)タグが付与されていることは次のコードで確認できます。}Option<i64>のデータサイズは16バイトだそうです。i64型のデータサイズは8バイトですが、タグのためにさらに8バイト使っていることがわかります。この列挙型ですがタグが不要になることもあります。それは以下のすべての条件を満たすときです。バリアントを2つだけ持つ一方のバリアントはデータフィールドを持たないもう一方のバリアントはデータフィールドを持つが、そのデータの全ビットが0になることはないこれを「nullableポインタ最適化」と呼びます。o2の型のOption<i64>は1.と2.の条件は満たしますが、3.は満たしません。i64型は0になることがあるからです。nullableポインタ最適化は適用できません。o1の型のOption<&i64>は3.も満たします。&i64は必ず有効なアドレスを指しているので、その値は決して0(nullポインタ)にならないからです。nullableポインタ最適化を適用できます。Option<&i64>型のデータサイズを確認すると、期待どおりタグがなくなって、全体で8バイトになっていることが確認できます。}メモリ上の表現はSome(&100)ならこうなります。Noneならこうです。0(nullポインタ)のときはNoneで、そうではなく、有効なアドレスが入っているときは、Someということになります。このように列挙型では、特定の条件を満たす場合はメモリ上のオーバーヘッドなしにバリアントの識別が可能になっています。Option<T>のmap()メソッド次にOption<T>のmap()メソッドを見てみましょう。以下のように定義されています。}}map()メソッドはF型のクロージャを引数にとります。このクロージャはFnOnceトレイトを実装し、T型の値をU型の値へマッピング(変換)します。map()メソッドには#[inline]アトリビュートがついていますので、コンパイル時の最適化により、呼び出し側のコードにこのコードが埋め込まれるはずです。456)(x)),}コンパイル時にこれと等価なコード(コンパイラの内部表現)が生成されることが期待できます。o1にnullableポインタ最適化を適用します。Rustでo1の値をnullポインタに設定することは許されないので、上のコードはコンパイルできません。最適化の過程では、これと等価な内部表現が作られていると考えられます。トレイトとして実現されるクロージャo1がシンプルな型になり、map()メソッドもインライン化されました。次はクロージャのところがどうなるか見てみましょう。456)(o1)クロージャは「無名関数」と自由変数を捕捉した「環境」で構成されます。コンパイラはクロージャの定義に出会うたびに、クロージャの環境を表現するための匿名型を生成します。AnonymousType;このクロージャはなにも捕捉しないので環境は空になっています。(データフィールドがありません)そしてクロージャの無名関数の部分はトレイトメソッドとして実装されます。}}これを呼び出すと以下のようになります。Some(f.call_once(o1))}変数fの値は単なる構造体なので、o1などのローカル変数と一緒にスタック領域にアロケートされます。Rustでは動的にアロケートするメモリ領域としてスタック領域とヒープ領域を使いますが、一般的な話として、スタック領域へのアロケートのほうがヒープ領域のアロケートよりも高速です。今回のAnonymousTypeはフィールドを持たないので、実行時にはなにもアロケートしません。トレイトメソッドのディスパッチ次はトレイトメソッドの呼び出しf.call_once(o1)の実行時コストについて調べましょう。トレイトメソッドの呼び出しは、普通の関数の呼び出しと比べると複雑になります。そのトレイトメソッドを実装している型がいくつも存在している可能性があり、そのなかから正しいものを選ばないといけないからです。このような同種のものからひとつを選ぶ出すことを「ディスパッチ」と呼びます。Rustでは2種類のメソッドディスパッチ方式をサポートしています。動的ディスパッチ:実行時にわかる情報から呼び指すメソッドの実体を選ぶ。柔軟だが実行時コストがかかる静的ディスパッチ:コンパイル時に決まる型で呼び指すメソッドの実体を選ぶ。使える場面がやや限定されるが実行時コストはかからない結論から言うと、Option<T>のmap()メソッドはクロージャのメソッドを静的ディスパッチします。ゼロコストになるのですが、そのありがたみは動的ディスパッチがわからないと実感できません。動的ディスパッチについて詳しく説明しましょう。動的ディスパッチ動的ディスパッチは実行時にわかる情報から呼び指すメソッドの実体を選びます。柔軟ですが実行時コストがかかる方法です。オブジェクト指向言語の多くはメソッドの呼び出しに動的ディスパッチを使用し、静的ディスパッチは行なえません。Rustでは前述のとおり動的ディスパッチと静的ディスパッチの両方に対応しており、状況に応じて使い分けられます。Rustで動的ディスパッチを行うときはトレイトオブジェクトを作成します。トレイトオブジェクトは同じトレイトを実装してる複数の型を統一的にあつかえるしくみです。ひとつのベクタに複数の型の値を混ぜて格納したり、関数の戻り値型を条件に応じて変えたりしたいときに便利です。トレイト名>のようになります。&やBoxといったポインタ経由でしか使えないことに注意が必要です。このポインタはfatポインタと呼ばれ、値を指す通常のポインタに加えて、vtableという内部データ構造へのポインタを持っています。vtableはメソッドの名前と実装コードのアドレスが対になった辞書で、vtableを検索することで呼び出そうとしているメソッドの実装を見つけられます。f.call_once(o1)を動的ディスパッチで実行するときは、以下のような手順になるでしょう。o1);動的ディスパッチではvtableのためにメモリを少し多く使用しますし、実行時間もfind_method()の分だけ余分にかかることになります。静的ディスパッチ静的ディスパッチは、コンパイル時に決まる型で、呼び出すメソッドの実体を選びます。使える場面がやや限定されますが実行時の追加コストはかかりません。Rustで静的ディスパッチを行うときはジェネリクスを使います。トレイト名を指定したときも静的ディスパッチになります。トレイトはジェネリクスの糖衣構文です)先ほどOption<T>のmap()がクロージャに対してジェネリックなメソッドとして実装されていることを見ました。このことからmap()は静的ディスパッチを行うことがわかります。静的ディスパッチではコンパイル時にジェネリックな型を解決し、その型を当てはめた専用のメソッドを作ります。}}fの具体的な型が分かったので、どのトレイトメソッドを呼ぶのか自然に特定されます。}}静的ディスパッチを私たちのコードに適用します。456)}コンパイル時の最適化は以上になります。Rustの抽象化のしくみを使ったコードが、ゼロコスト抽象化に関連する最適化によって、実行時のオーバーヘッドが最小のコードへと変換されました。アセンブリコードで確認するそれではRustコンパイラが生成したアセンブリコードの内容を確認しましょう。Rustのバージョンなど今回は以下のRustバージョンとターゲットを使用しました。9.0試してはいませんが他のターゲット(macOS、Windows、ARM上のLinuxなど)でも同様の効果が得られるはずです。確認に使ったコード元のコードそのままですと、入出力がないためコンパイラの最適化によって全体のコードが削除されてしまいます。(なにも仕事をしないアセンブリコードが生成される)そこで以下のような修正を施しました。o2);}コマンドライン引数として整数をひとつ取りnを束縛。nが123ならo1はNoneに、それ以外ならSome(&n)に束縛します。コードが少し長くなりましたが本質は変わっていません。Some(556)アセンブリコードを生成するこのコードをコンパイルして、最適化後のアセンブリコードを生成しましょう。rustcコマンドを実行します。'llvm-args=...'フラグでx86アセンブリコードの文法としてIntel形式を指定する。(デフォルトはAT&T形式)x86アセンブリコードの文法にはIntel形式を指定しました。Intel形式は一般的なプログラム言語に慣れた人には、ポインタによるメモリアドレス指定などが直感的でわかりやすいと思います。デフォルトの文法であるAT&T形式は、コンパクトなコードになるので読み慣れた人にはいいかもしれませんが、少し癖があります。アセンブリファイルはtarget/release/depsディレクトリ配下に出力されます。target/release/deps/optmap-4ee5145a2c1fa529.stokeiというRust製のCLOCツール(コード行数を数えるツール)でアセンブリコードの行数を数えてみました。34------------------------------------------------------------------入出力があるのでCode部分が850行と長くなっていますが、今回はその中の20行くらいを見るだけですみます。レジスタとスタック領域の使われかたRustではローカル変数はスタック領域に置かれます。o2がスタック領域のどこに置かれるか調べておきました。図の右側がスタック領域です。図の左側にはCPU内にあるレジスタのなかから、今回に関係するものだけを描きました。レジスタはメモリよりもはるかに高速に動作する一時記憶域で、CPUが持つ多くの命令はレジスタに入ったデータを対象にしています。RAXとRCXは汎用レジスタで、いずれも64ビットです。RAX(アキュムレータ)は四則演算の第1引数などに暗黙的に使われたりするRCX(カウントレジスタ)はループのカウントなどにも暗黙的に使われるが、今回は単なるデータの一時置き場になっているRAXとRCXは32ビットのレジスタとして使うこともできて、そのときは順にEAX、ECXと呼ばれます。これから見るアセンブリコードにも、RAX(64ビット)とEAX(32ビット)の両方が出てきますが、同じレジスタを指しています。ちなみにRAXとRCXは16ビットや8ビットのレジスタとしても使えるのですが、今回読む部分には出てこないため、図では省略しています。RBPとRSPはポインタレジスタです。いずれも64ビットで、値としてメモリ上のアドレスを保持します。RBPは汎用ポインタのひとつで、今回は変数o1(ポインタ型の&i64)として使われている。32ビットのEBPとして使うことも可能RSP(スタックポインタ)はスタック領域の先頭アドレスを保持するRustで関数を呼び出したり関数からリターンしたりするとRSPの値が増減します。64]など)で示されます。x86アセンブラのごく基本的なことごく簡単にですがアセンブリコードの読み方を説明します。以下のアセンブリコードはポインタであるo1に、&nをセットするためのものです。o1にも同じ番地を格納する左端のleaやmovはCPUに対する命令です。そのあとにカンマで区切られて操作対象のレジスタなどが与えられます。これらの操作対象をオペランドと呼び、左から順に第1オペランド、第2オペランドと呼びます。leaは実行アドレスロード命令で、第1オペランドで指定したレジスタに、第2オペランドのアドレッシングで生成された値(アドレス)をセットします。movは転送命令で第2オペランドの値を第1オペランドにコピーします。ptrは転送するサイズの指定で、x86系CPUの4ワードポインタである64ビットポインタを表します。セミコロンから行末まではコメントです。これ以降は命令の説明を省略しますので、筆者が書いたコメントを読んでください。列挙型のnullableポインタ最適化が働いていることを確認しましょう。以下のコードのコンパイル結果を調べます。Some(&n)};o1はOption<&i64>型ですので、nullableポインタ最適化によってi64へのポインタになり、NoneやSomeを識別するためのタグがなくなるはずです。最適化後の擬似的なコード。&n};アセンブリコード内を123で探すと、以下のコード片が見つかります。o1にも同じ番地を格納する.LBB12_26:nとして100を与えたときについて考えます。123のときはラベル.LBB12_19以降の命令が実行されます。そこではRBPレジスタにnが置かれている番地をセットし、さらにo1にも同じ番地をセットしています。nとして123を与えたときはそれよりも前の命令が実行されます。o1にnullポインタを意味する0をセットし、RBPレジスタも0にクリアしています。この部分は期待どおりにコンパイルされたことが確認できました。map()メソッドのインライン化とクロージャの静的ディスパッチOption<T>のmap()メソッドに関連する部分を確認しましょう。元のコードはこうなっていました。456);クロージャは匿名型とトレイト実装へと展開されますので、最適化前は以下のコードに等しい内部表現になるはずです。o1))}インライン化によってAnonymousType自体が消滅し、最終的にはこうなるはずです。456)}アセンブリコード内を456で探すと、以下のコード片が見つかります。AXレジスタの値をo2の値の部分にセットするo1がSome(&100)のときについて考えます。Someのときは前半の命令が実行されます。そこではRAXレジスタを456にして、RBPレジスタが指すnの値をRAXに加算しています。結果はRAXレジスタに入ります。RCXレジスタにはSomeを表すタグとして1をセットしています。(o2はOption<i64>型なのでタグを持ちます)そのあと、ラベル.LBB12_29以降が実行され、RCXレジスタの値がo2のタグへ、RAXレジスタの値がo2のSomeの値部分へコピーされます。o1がNoneのときはラベル.LBB12_27以降が実行されます。そこではまずRCXレジスタをクリアしてNoneを表す0にしています。そのあとはSomeのときと同様に、ラベル.LBB12_29以降が実行され、RCXレジスタの値がo2のタグへ、RAXレジスタの値がo2のSomeの値部分へコピーされます。o2")を実行するための値がセットされているので、o2のSomeの値は無意味なものになってしまいます。いえNoneのときは、そこにどんな値が入っていても読み出されることはないので問題ありません。この部分も期待どおりにコンパイルされたことが確認できました。まとめ高階関数とトレイトによるポリモーフィズムを使ったRustコードをコンパイルすると、手書きしたのと同じくらいシンプルで無駄のないアセンブリコードが生成されました。Rustでは抽象化のしくみがゼロコストになるよう、言語自体や標準ライブラリが注意深く設計されているここで言うゼロコストはオーバーヘッドがないという意味。(tatsuya6502)Erlang/OTPやRustで分散DBを開発してます。最近、Rustの本を書きました。(tatsuya6502)。