『並列プログラミングは難しいのか？もしそうなら、どうすればよいか？』レビュー

パウル・E・マッケニィ氏（Linux カーネルの RCU 同期機構 の著者）による無料オンラインテキストブック『Is Parallel Programming Hard, And, If So, What Can You Do About It?』に関するレビューです。 この教科書を読み終え、満足感を味わい、近い将来にはおそらくこれ以上の読書をしないだろうと判断したため、内容をまだ鮮明に覚えているうちにレビューを書きます。

背景と環境

本書を読み始めた際のメンタリティ、人生のフェーズ、および物理的な環境についてです。

• キャリアの変化
  • プロフェッショナルなキャリア（過去 10 年）は TLA⁺ と分散システムを中心に進めていましたが、変化の時を迎えていました。
  • 2022 年に Lean（証明支援系）へ移行し、量子情報処理の形式化を目指しましたが失敗。その結果、燃え尽きてしまいました。
• Software Should Work カンファレンス (2026)
  • ミズーリ州コロンビアで開催されたカンファレンスに参加。フィリップ・ピズロ氏による Fil-C セッションが特にお気に入りでした。
  • TLA⁺ と分散システムの知見から、コンカレンシーについて理解していると思っていましたが、フィル氏の指摘により以下を学びました：
    • 実際にはロックフリーなガーベッジコレクタを書くことがどれほど難しいか。
    • 「自分はほとんど何も知らない」という自覚こそが、優れたカンファレンスへの参加資格。
  • TLA⁺ の限界: TLA⁺ は文字通り同時に起こるイベントの推論（マルチコア CPU のケース）には有用でない（少なくとも使い勝手が悪い）。
  • 線形化可能性: 分散システム文脈における「線形化可能性」の重要性を再認識しました。
• 書籍選定
  • ロックフリーな側面、Mutex ベース、メッセージパッシングに焦点を当てた教科書を探していましたが、本書は一般的な並列プログラミングと CPU キャッシュの効果 を主題としており、目的に適していました。
  • 多くの HN スレッド（2011 年〜2023 年）を見て分析パライシスに陥るのを避けたため、この選択は有益でした。
• 読書環境 (2026)
  • カナダの森のある地域での家族訪問（約 1 週半）。悪名高いモスシーズンでしたが、涼しいスクリーン付きパティオで没頭しました。
  • 衛星と携帯電話局によるインターネット接続がありましたが、物理的な場所として最適でした。

テキストブックの形式

本書は少なくとも 3 つの異なる PDF 形式で入手可能です：

1. 科学的論文のような二欄形式。
2. 余白を大きく取った単一欄形式。
3. 余白なしの単一欄形式（Pine64 PineNote で読むのに最適）。

ナビゲーションの問題点

• 内部リンクの多さ: 膨大な数のリンクがあり、クリックすると質問への答えや図・注釈へ移動します。
  • 誤ってリンクをタップすると意図せずページが飛び、「ナビゲート自体が混乱を招く」という悪循環に陥ります。
• タッチスクリーンの精度: 隣り合った位置にリンクが 2 つ並んでいる場合、一方だけを選択できず、解決策がない状態です。

テキストブックの内容 - 導入編

資料提示方法としてほぼ完璧でした。第三章「ハードウェアとその癖」に入る前に、ユーモア溢れるイラスト付きで現代 CPU の仕組みを高レベルで学びます。

ハードウェアシステムアーキテクチャ

• CPU コアがキャッシュに存在しないメモリアドレスへ書き込むプロセスを追跡しました。
• MESI プロトコルについて基本的な説明 lacked しており、直感的な理解に役立ちませんでした（後で補足編で学習）。
• 重要な知見:
  • x86 CPU は直接メモリではなくキャッシュへしか書き込みません（最終的にメモリアップロードされます）。
  • キャッシュラインに対する独占的所有権がない限り、特定のアドレスへの書き込みはできません。
  • 別のコアが同時に同じアドレスへの書き込もうとすれば、待たなければなりません。文字通りの並列な書き込みは実際には発生しません。
  • 例外：書き込まれるデータが複数のキャッシュラインに跨る場合のみ、書き込みが中断（torn）される可能性があります。

並列プログラミングの落とし穴

• 第 4 章「Tools of the Trade」: コンパイラによる想像を絶する最適化により、完全におかしい振る舞いを引き起こす可能性があります。
  • 対象となるミスハプ：ロードテアリング、ストアテアリング、ロード融合、コードの再配置、架空の読み書きなど。
• Linux カーネルへの依存:
  • 不満足点として、内容が Linux カーネル文脈に特化しすぎていること。
  • C++11 および C11 の

    std::memory_order

    や、

    ACCESS_ONCE()

    /

    WRITE_ONCE()

    マクロの解説は短く、興味深い歴史的発展（善意のデータレースなど）がスキップされていました。

テキストブックの内容 - 主要編

第 5 章以降、興味のあるトピックを探しながらざっと読みました。

カウント（Counting）

• 第 5 章: 複数のスレッドがカウンターを増分するプログラムへの約 10 のアプローチをカバー。
  • 明らかなバグのない実装でも、ひどくパフォーマンスが悪いものが早期に却下されます。
  • MESI に関する知識が本当に役立ちました。
• シグナル強盗限界カウンター: 完全な理解には至っていませんが、配列ベースのスレッドごとの統計的カウンターはコンフリクトフリーリプリケードデータタイプとの類似性から気に入りました。
  • スレッド固有のカウンターを単一配列に詰め込むのはパフォーマンスへの悪影響を理解するための教材としても優秀でした。

分散システムと形式検証

• 所有権、パーティショニング、デフェード処理など、分散システムからの概念的な話題を含む章もありました。
• ハインゼンベルグバグの狩り: 「Hunting Heisenbugs」に関するセクション（11.6.4）は良いものでした。
• 形式検証: Promela と Spin が使用されましたが、TLA⁺ ユーザーとしては学習意欲が湧きませんでした。

ロックフリープログラミングへの移行点

• 第 14 章までロックフリープログラミングについて真正面から扱われません。この時点で、データ構造に特化した教科書への移行を準備していました。
• 第 15 章でようやくメモリ順序が取り上げられますが、混乱を解消するために余計な情報源へ移動してしまっていました。

総合評価

最初の 5 章のみを詳細に読みましたが、この教科書は非常に優れていると思います。並列プログラミングについてさらに学ぶ欲求を本当に満たしたからです！

職場の昼食で coworkers に学んだ無茶苦茶なことを情報ダンプとして押しつけようとするのを自分自身で制御するのが困難になりました：

• リリース・コンスーム順序の形式化が失敗したことは知っていましたか？

• mov

  を使用した基本的な整列されたロードとストアが x86 上で原子操作になること。
• **アウト・オブ・ザ・エア（out-of-thin-air）**値について。
• DEC Alphaの極めて弱いメモリモデルについて。
• リリース・アキュアセマンティクスがどのように機能するかについて。
• 決定論的シミュレーションテストでまだ有意義にロックフリーアルゴリズムをテストできない理由。
• **ARM（v8 以前）**上の原子操作がプリエンプト可能であること。

ここにあり得ないほど不自然なコミカルな nonsense の宝庫があります。次に高性能ガーベッジコレクションについて学びたいと思っています。

推奨先！

• lobste.rs
• Mastodon
• Hacker News
• LinkedIn