基礎: メモリ階層

ほとんどのプログラマーは、自分たちの下にあるハードウェアとやり取りする際の生々しい詳細を意識していません。 それは意図された設計です。 これは、数十年にわたるソフトウェアとハードウェアの共進化の結果です。

素朴な print 文を考えてみましょう。 前回、フォーマット済みの出力をコンソールに出力したとき、おそらく次のことを考える必要はなかったはずです。

• 文字デバイス用のバッファをフラッシュすること（ベンダー固有のハードウェアに対する OS ソフトウェアの「接着剤」抽象化）。

• Universal Asynchronous Receiver/Transmitter（UART¹）プロトコルにおけるパリティビットの動作の複雑さ（物理伝送媒体向けのエンコーディング）。

これらは、日々の開発の大半で考慮する必要があるべきではない細部です。 メモリハードウェア技術も同様に、あなたから大部分が抽象化されているものです。 たいていの場合、コンピューターは、どのようなコンピューターであっても、2 つの異なる部分からなる複合体だと考えることができます。

1. コンパイル済みバイナリから命令をフェッチし、デコードし、実行する Central Processing Unit（CPU）。

2. CPU が読み取る命令と、CPU が処理するデータを保持する単一のメモリシステム。

この単純な 2 部構成の概念化では、メモリは個別にアドレス指定でき、定数時間でアクセスできるバイトの線形配列にすぎません。 しかし、それは現実ではありません。

ソフトウェアの観点から「メモリ」と考えているものは、実際には、異なる価格帯でさまざまな速度と容量を提供するハードウェア技術の異種混合です。 そして、それはシステムソフトウェアに影響を及ぼし得ます。

システムプログラマーとして下す判断によって、プログラムの実行中にどの特定の種類のストレージハードウェアが利用されるかが決まります。 そして、このハードウェアの特性は、プログラムの速度に重大な影響を与える可能性があります。 したがって、メモリについての議論は、その物理的な現実、すなわち現代のストレージ技術の性能階層に基づける必要があります。

正当に評価すべきところ

この章の内容は、Computer Systems: A Programmer’s Perspective² から大きな影響を受けています。

同書の著者である Carnegie Mellon University の教授たちは、学部向け CS 科目の教材としてこの本を使用しています。科目番号は 15-213 で、「CMU に zip を与える科目」と親しみを込めて呼ばれています。15213 は大学が所在する ZIP コードであり、またこの科目が同大学の中核的な CS カリキュラムにおいて非常に基礎的なものだからです。

CS:APP は評価の高いテキストであり、コンピューターアーキテクチャとオペレーティングシステムの両方に対する詳細な入門書です。 強くお勧めします。

メモリ性能階層

現代のメモリ技術は、明確な階層的ティアに整理できます。

• 上位ティアは信じられないほど高速ですが、同時にバイトあたりのコストが信じられないほど高価です。これらは希少なリソースです。その結果、格納できるデータ量は限られます。

• 下位ティアは相対的に低速ですが、同時にバイトあたりのコストが相対的に安価です。これらは豊富なリソースであり、大量のデータを自由に格納できます。

次の内訳を見てみましょう。

• CPU レジスター: 命令の実行時に直接アクセスされる（例: 0 CPU サイクル²）レジスターは、階層の最上位に位置します。

  • レジスター割り付けは、ターゲットマシンの Application Binary Interface（ABI）⁷ に従って、コンパイラーによって処理されます。インラインアセンブリ⁸（アーキテクチャ固有の命令を Rust ソースコードに混在させること）を書いていない限り、レジスターの使用を直接制御することはありません。

• SRAM キャッシュ: CPU に組み込まれた小さなメモリバンクで、レジスターの動作に物理的に近い位置にあります。4〜75 CPU サイクルでアクセスできます²。

  • コードが必要とするデータがどの程度頻繁にキャッシュ内に存在するか（別名「キャッシュヒット率」）は、コードの書き方の副作用ですが、API 呼び出しで明示的に制御できるものではありません。データ指向プログラミング⁹ は、CPU キャッシュを最適に利用するようにプログラムを構造化することを扱います。

• DRAM: メインメモリであり、ほとんどのシステムプログラミングにとって最適な位置にあります。数百サイクルでアクセスできます²。

  • 多くの場合、メインメモリのどの領域を使用するかを明示的に制御できます。具体的には、データがスタック、ヒープ、静的メモリ、あるいは「メモリマップト」ファイルに格納されるかどうか、といった場所です。各選択肢には性能上の含意があります。あなたはすでにスタックのみのプログラムを書いています。第 2 章の RC4 実装では #![no_std] 属性を指定しました。

• ローカルディスク: プログラムの実行間やマシンの再起動をまたいで永続する長期ストレージです。数千万サイクルでアクセスされるため²、上位レベルと比較して大きなペナルティがあります。

  • ローカルディスクストレージとのやり取りは、通常、ファイルを開く、読み取る、または書き込むために明示的な API を呼び出すことを意味します。ただし、利用可能なすべての DRAM が現在使用中の場合は例外です。その場合、OS は舞台裏でプログラムデータをローカルの二次ストレージへ、またはそこから ページング¹⁰ することを強いられます。

• リモートディスク: 物理的に別のマシン上にある長期ストレージで、プログラムを実行しているホストとはネットワーク経由で接続されています。アクセスレイテンシは CPU サイクルでは測定することすらできません。関与する予測不能な要因（プロトコル、物理的距離、ネットワーク輻輳など）が多すぎるためです。上の表では、便宜上ナノ秒単位の推定値³を使用しています。

  • リモートマシンから、またはリモートマシンへ暗黙的にデータをダウンロード/アップロードする方法はありません。ネットワーキング API を直接または間接的に呼び出す必要があります。

現代のオペレーティングシステムにおけるメモリ管理

ページング方式¹⁰は、仮想メモリ（OS によって管理される DRAM の抽象化）を実装する方法の一部です。 これは多くの含意を持つ複雑なトピックであり、徹底的に掘り下げるには CS:APP² の第9章をおすすめします。 要約すると、仮想メモリは次の3つの利点を提供すると考えられます。

• メモリの単純化された見方: 各プロセスには、物理メモリ上のどこに実際にマップされているか、またそれらのマッピングの一部が別のプロセスと共有されているかどうかに関係なく、実行用の一様な線形仮想アドレス空間が与えられます。

• アドレス空間の分離: OS は各プロセスのアドレス空間間の分離を強制でき、あるプロセスが別のプロセスを破壊することを防ぎます。同様に、ユーザー空間アプリケーション（例: あなたのプログラム）はカーネル空間（例: OS 内部）にアクセスできません。

• キャッシュによる効率化: メインメモリ（システム DRAM）がディスク上のファイルのキャッシュとして機能できるようにし、アクティブな項目へより高速にアクセスできるようにし、DRAM とディスク間の双方向の転送（ページング）を管理します。OS が移動できるデータの最小単位は 1 ページ（通常は 4 kB）です。

わかった、しかしこれらすべての実用上の含意は何か？

異なる種類のメモリハードウェアは、パフォーマンスに大きな影響を与えます。 場合によっては桁違いです。 したがって、既知の最速アルゴリズムを選んだと仮定すると、次の2つの事実を念頭に置くべきです。

• ディスクおよび/またはネットワーク I/O は高コストだが明示的です。 メモリ性能階層の下位2段ははるかに低速ですが、少なくともその使用は意識的に制御できます。

  • ファイル I/O とネットワーク I/O は低速であることに加え、失敗する可能性があります。ファイルは移動されていたり、権限が変更されていたりするかもしれません。リモートサーバーは一時的または恒久的にアクセス不能になる可能性があります。これらのケースを処理するためのロジックは、エラーを伝播するにせよ、代替パス/ホストを再試行するにせよ、パフォーマンスコストをさらに悪化させます。

• キャッシュ最適化は差別化要因になり得ます。 Rust の BTreeSet¹¹ と BTreeMap¹²、つまり私たちが代替を構築する標準ライブラリのコレクションは、SRAM キャッシュ効率を最大化するように特別に設計されています。どちらも非常に高性能です。

  • 余談ですが、C++ と Java の標準ライブラリはいずれも Red-Black Tree を使用しています。B-tree は、ファイルシステムやデータベースのユースケースでより一般的です。

  • 私たちのライブラリの最適化は、階層の別のレベルである DRAM を対象とします。インデックスベースのアロケータパターン（第6章で導入）を使用して、コードが stack DRAM のみを使用することを保証します。その結果として、組み込み環境での移植性が得られます。

なぜ「既知の最速アルゴリズム」という但し書きがあるのか？

アルゴリズムは通常、実行を支える物理メモリの種類よりもはるかに大きなパフォーマンスへの影響を持ちます。

線形時間で解ける問題に対して二次時間の解法を実装してしまうと、どれほど SRAM の局所性があっても補うことはできません。 後者の解法の方が、いずれにせよはるかに優れたスケーラビリティを持ちます。

アルゴリズム計算量の基礎については第7章で説明します。

要点

私たちはメモリを単なるバイトの線形配列だと信じたいところですが、現実にはそれはコストとパフォーマンスのトレードオフを行うハードウェアの階層です。 このメモリの物理的な見方は基礎的なものです。

しかし、日々のシステムプログラミングでより関心があるのは、メモリの論理的な見方、すなわちスタックフレームとヒープバッファの管理です。 それらは DRAM に格納されます。 本書のすべてのコードを私たちが見る際の抽象化はこれです。

1. UART 通信の基礎。Scott Campbell（2022年アクセス）。 ↩

2. [個人的なお気に入り] Computer Systems: A Programmer’s Perspective。Randal Bryant、David O’Hallaron（2015）。 ↩ ↩2 ↩3 ↩4 ↩5 ↩6

3. ORIE 6125: 第8週 - コンピューターアーキテクチャ。Cornell University（2022年アクセス）。 ↩ ↩2

4. マルチレベルキャッシュ。Wikipedia（2022年アクセス）。 ↩

5. ソリッドステートドライブ（SSD）とハードディスクドライブ（HDD）は、2つの二次ストレージ技術です。前者はより高速な読み取り速度と書き込み速度を提供します。 ↩

6. この文脈における Round Trip Time（RTT）は、パケットが宛先に到達し、確認応答が戻ってくるまでにかかる時間です。 ↩

7. アプリケーションバイナリインターフェイス。Wikipedia（2022年アクセス）。 ↩

8. nightly で利用可能になった新しいインラインアセンブリ構文。Josh Triplett（2020）。 ↩

9. Rust によるデータ指向設計の入門。James McMurray（2020）。 ↩

10. ページング。OSDev Wiki（2022年アクセス）。 ↩ ↩2

11. 構造体 std::collections::BTreeSet。The Rust Team（2022年アクセス）。 ↩

12. 構造体 std::collections::BTreeMap。The Rust Team（2022年アクセス）。 ↩