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

教科書レビュー：並列プログラミングは難しいか、そして、もしそうなら、どうすればよいか？

Paul E. McKenney氏（LinuxカーネルのRCU同期メカニズムの著者）による無料オンライン教科書『Is Parallel Programming Hard, And, If So, What Can You Do About It?』についての私の考えを述べます。この教科書の大部分を読み、十分な知識を得ましたが、おそらく近い将来さらに読み進めることはないでしょう。そのため、まだ記憶が新しいうちにこのレビューを書きたいと思いました。

設定と環境

ここでは、この教科書を読み始めた際の私の考え方／人生の段階と、物理的な環境について話します。レシピサイトにあるような、退屈な個人的な前置きのようになるかもしれませんが、興味がなければ飛ばしてください。

過去10年間、私の専門的なキャリアはTLA⁺と分散システムを中心に展開してきましたが、変化の時期が来たと感じていました。それは過渡期であり、感情的にも激動の時期でした！2022年には、研究者の量子情報処理の結果を形式化する、非常にニッチで存在しないような仕事に就こうとして（そして失敗して）Leanへの移行を試みました。その試みで燃え尽きてしまいましたが、最近の自動定理証明の進歩を考えると、一時的に先見の明があった私の神経系が私を危険から遠ざけてくれたのかもしれません。このようにして、2026年にミズーリ州コロンビアで開催されたSoftware Should Workカンファレンスに参加した経緯と背景がありました。

カンファレンスでは多くの良い講演がありましたが、特にFilip Pizlo氏によるFil-Cについての講演が気に入りました。

Fil氏とは、インタプリタ、そしてその後は並列処理についてもかなり話す機会がありました。TLA⁺と分散システムのおかげで並列処理についてはかなり知識があると思っていましたが、Fil氏はロックフリーのガベージコレクタを書くことの難しさについて語り、私は実際には並列処理についてほとんど何も知らないことに気づきました（何も知らないと感じるのは、良いカンファレンスの証です）。Fil氏はまた、TLA⁺は文字通り並列に（マルチコアCPUで実際に起こりうる！）発生するイベントの推論には役立たない（少なくとも人間にとって使いやすい形ではない）可能性があり、線形化可能性（distributed systemsの文脈でなんとなく理解していた概念）について並列アルゴリズムを分析することの重要性についても言及しました。

これらすべてが非常に魅力的だったので、ミューテックスベースやメッセージパッシングのパターンよりも、ロックフリーの側面に焦点を当てた並列処理の教科書を探しました。『Is Parallel Programming Hard, And, If So, What Can You Do About It?』は、より具体的なロックフリーデータ構造の書き方に関する教科書ではなく、一般的な並列プログラミングとCPUキャッシュの効果に焦点を当てているため、まさにうってつけだと思いました。また、過去にも（2023年、2021年、2020年、2015年、2014年、2011年）いくつか興味深いHNのスレッドがありました。私は、正確な「正しい」教科書を見つけようとして分析麻痺に陥ることに時間を費やすのは無駄だと思っています（これは本当に先延大好きな巧妙な方法です）、なので、これは十分良いと思えました。

この教科書を読んだ物理的な環境は、カナダの静かで緑豊かな地域に住む家族を訪ねる1.5週間の休暇でした。2026年は特に蚊の多い季節でもありました。そのため、涼しい網戸付きのパティオに座って過ごす時間が多く、何百もの見張り番に厳重に監視され、持ち場を離れないようにしていました。

［画像: 網戸付きのパティオでノートパソコンを開いて座っている著者］

衛星や携帯電話の基地局のおかげで、国のより遠隔地でも気を散らすインターネット接続は迷惑なほど良好ですが、それ以外はこの教科書を読むのに最適な場所でした。

教科書の形式

教科書の実際の構造について簡単に触れておきます。この教科書は、少なくとも3つの異なる形式で提供されており、すべてPDFです。

1. 科学論文のような、2段組形式
2. 広い余白を持つ、1段組形式
3. 余白のない、1段組形式

最後の形式は、私のPine64 PineNoteで読むのに最適です。

教科書には非常に多くの内部リンクが含まれています。これらのリンクの一部は、簡単な知識チェックの質問ボックスで使用されており、リンクをクリックすると質問の答えに移動します。他のリンクは、図やセクションが言及されるたびに、または大量の脚注や引用に使用されます。残念ながら、後者のリンクは非常に煩わしく、おそらく少なくとも80％は削減されるべきです。もしあなたの電子書籍リーダーに物理的なページめくりボタンがない場合、この本を読む体験は、ページをめくろうとしたときに誤ってこれらのリンクのいずれかをクリックしてしまい、どこに飛ばされるかわからないという状況の連続になります。電子書籍は、ナビゲーションがすでに混乱しやすいのに、これがあることでさらに混乱し、繰り返しページめくりをタップして2つのセクション間を素早く行き来することがほぼ不可能になりました。リンクをクリックしたい場合でも、場所によっては隣接して2つのリンクがあり、タッチスクリーンでは一方のリンクをクリックする代わりに他方をクリックする精度がありません。リンクをすべて無効にするという解決策も考えられますが、そうすると非常に優れた知識チェックの質問へのアクセスを失ってしまいます。そのため、私はただ我慢しました。

教科書の内容 - 導入章

教科書は、私のレベルにとってほぼ完璧な教材の提示方法でした。本は、 niceで軽い導入と動機付けの章から始まり、第3章のHardware and its Habits（ハードウェアとその習慣）で本格的に進みます。ここでは、最新のCPUがどのように機能するかを、何がそれらを高速にし、何がそれらを低速にするのかを、大まかに学びます。たくさんのユーモラスなイラスト付きです！セクション3.2.1のHardware System Architecture（ハードウェアシステムアーキテクチャ）は、私にとって特に興味深いものでした。CPUコアがキャッシュに存在しないメモリ位置に書き込むという、単純化された説明をたどります。

ここで一つの機会を逃しています。私はMESIプロトコルの基本的な説明から非常に恩恵を受けたでしょう。CPUキャッシュが並列な読み書きをどのように仲介するのかについて、ほとんど直感を持っていませんでした。このセクションをよりよく理解するためにオンラインで検索しているときにMESIについて知りました。MESIはこの本の付録にしか言及されていません。しかし、それについて知ることで、本の残りの部分の理解が大幅に向上しました。

MESIを学ぶことで、複数のCPUコアが同じデータ位置に文字通り同時に書き込むことはできないということも学びました！x86 CPUは実際にはメモリに直接書き込むのではなく、キャッシュに書き込みます（キャッシュの値は最終的にメモリにフラッシュされます）。x86 CPUコアは、そのアドレスを含むキャッシュラインの排他的な所有権を持っている場合にのみ、特定のアドレスに書き込むことができます。他のコアが同時にそのアドレスに書き込もうとすると、キャッシュラインの所有権が移動されるのを待たなければなりません。したがって、文字通りの同時書き込みは実際には発生しません。ただし、書き込まれるデータが複数のキャッシュラインにまたがる場合は、書き込みが破損する可能性があります。

第4章、Tools of the Trade（ツールの紹介）と題された章は、まさに驚異的でした。ここでは、注意深く並列プログラムを書かないと、コンパイラが完全に無意味な動作を引き起こすような、信じられないほど創造的な最適化を試みることが学べます！セクション4.3.4.1のShared-Variable Shenanigans（共有変数のおかしな挙動）は、ロードの引き裂き（load tearing）、ストアの引き裂き（store tearing）、ロードの融合（load fusing）、ストアの融合（store fusing）、コードの並べ替え（code reordering）、発明されたロード（invented loads）、発明されたストア（invented stores）（特に悪質）、ストア・トゥ・ロード変換（store-to-load transformations）、デッドコード削除（dead-code elimination）といった恐ろしい失敗を扱っています。その後、コードがコンパイルを無事に通過したと仮定すると、章ではCPUがプログラムを実行しているときに起こりうるおかしな挙動について説明します！この二重の困難さにより、ミューテックスやメッセージパッシングのような馴染みのあるもの以外で、並列プログラムについてまともに考えることが難しくなりました。

この章で私が抱いた唯一の問題は、それがLinuxカーネルのコンテキストに非常に特化していることです。C++11やC11がstd::memory_orderのようなもので並列プログラミングを形式化するために行ったことについて学びたかったのです。これらは、セクション4.2.6と4.2.7のAtomic Operations (C11)（アトミック操作（C11））とAtomic Operations (Modern GCC)（アトミック操作（モダンGCC））で短い段落が与えられただけでした。ACCESS_ONCE()とWRITE_ONCE()マクロが単にvolatile*にキャストするだけで、それがコンパイラを怖がらせるのに十分だったという漠かな考えを持ってこの章を終えました。アトミック操作（C11）とアトミック操作（モダンGCC）は、無害なデータ競合はエラーだったのかという議論のような、非常に興味深い歴史的な発展は完全に省略されていました。

教科書の内容 - 本編

第5章のCounting（カウント）は、おそらくこの本の目玉となる章です。また、私が最も深く読んだ最後の章でもあります。この章では、複数のスレッドがカウンターをインクリメントするプログラムを書くための、10種類ほどの異なる方法を扱っています。各スレッドがアトミックインクリメント命令を使用する、明白で壊れていない実装は、そのパフォーマンスがどれほどひどいかを示すことで、早い段階で却下されます。ここで、MESIに関する私の追加学習が本当に役立ちました。

この章は、シグナル盗難リミットカウンター（signal-theft limit counter）と呼ばれるもので締めくくられますが、正直に言って、私はそれを完全に理解していません。もし自分でカウンターを書くなら、そこまでしないだろうと思います。私は、分散システムの世界の競合フリーレプリケートデータ型（conflict-free replicated datatypes）に似た、配列ベースの各スレッド統計カウンターが非常に気に入りました。それらは、偽共有（false sharing）のパフォーマンスへの影響を学ぶための優れた手段でもありました。すべてのスレッド固有のカウンターを単一の連続した配列に詰め込んで、それで良いと呼ぶことはできません！

第5章以降は、興味のあるトピックを探して、ほとんど内容を skimmingしました。いくつかの章はかなり概念的で、所有権、パーティショニング、遅延処理など、分散システムから容易に移行できるものでした。Formal Verification（形式検証）の章では、TLA⁺ユーザーである私には学習意欲が湧かなかったPromelaとSpinが使用されていました。Validation（検証）の章には、11.6.4のHunting Heisenbugs（ハイゼンバグの狩猟）という良いセクションがありました。ロックフリープログラミングは、第14章のAdvanced Synchronization（高度な同期）まで実際にはカバーされず、その時点では、ロックフリープログラミングとデータ構造に特化した教科書に移る準備ができていました。第15章でついにメモリ順序付けがカバーされますが、私はすでにそれについての混乱を解消しようと追加の資料に移っていました。

全体的なレビュー

最初の5章を深く読んだだけですが、この教科書は素晴らしいと思います。なぜなら、並列プログラミングについてもっと学びたいという渇望を本当に与えてくれたからです！仕事中のほとんどの昼食時間、同僚に学んだくだらないことを延々と話したくなるのを抑えるのに苦労しています。例えば、リリース・コンシューマー順序付けの形式化の失敗について知っていますか？あるいは、x86では基本的なアラインされたロードとストアがmovを使用してアトミックであること？あるいは空中からの値？あるいはDEC Alphaの信じられないほど弱いメモリモデル？あるいはリリース・アキューズ順序がどのように機能するか？あるいは、決定論的なシミュレーションテストは、ロックフリーアルゴリズムを（まだ）意味のあるテストができないこと？あるいは、ARM（v8以前）のアトミック操作はプリエンプトされる可能性があること？ここには、滑稽なほど直感に反するくだらないことの金脈があります。次に、高性能なガベージコレクションについて学びたいです。おすすめを募集しています！

ディスカッション

• lobste.rs
• Mastodon
• Hacker News
• LinkedIn