日々の破片

_ 低レベルプログラミング

翔泳社の野村さんから低レベルプログラミングをいただいたのでレビュー（完全に読んだわけではなく、自分および少数の購買予定者のためのアジェンダ用にレビューしたというところ）。

著者はレニングラードの（こんなところで懐古趣味をひけらかしてもしょうがないが、そういう性格だからしょうがない、つまり聖ピョートルの都市のことだ）ITMO（と書いて国立情報技術機械光学研究大学、らしいのだが光学って本当なのか工学の誤記なのか謎）の先生で、多分、この本は副読本なのではなかろうか。どういう先生かというと、この先生のチームは、ACM-ICPCの国際大学対抗プログラミングコンテンストで6回優勝しているそうだ（少なくとも2017年の優勝は間違いない。というか3位は京城、7位が北京で、東京が12位なのか。韓国もすごいな）。

本書の目的がまえがきにある。7つの目標だ。

・アセンブリ言語で自由自在に書くことができる

・Intel 64のプログラミングモデルを理解する

・C11で、保守が容易で堅牢なコードを書ける

・コンパイルのプロセスを理解し、アセンブリリストを解読できる

・コンパイルされたアセンブリコードのエラーをデバッグできる

・適切な計算モデルを使うことで、プログラムの複雑さを大きく減らせる

・性能が重視されるコードを書ける

おお。少なくとも3は自信がないし、7と8は知りたい。

というわけで、なるほどACM-ICPCで優勝しそうな内容だ。

問題ががんがん入っていて、解答はGitHubにある（英語ですと書いてあるが、Apressの本だからロシア語というわけはないよなぁ）。

レポジトリには、すぐに使えるDebianのVMXへのリンクがあるので、すぐに実習ができるとのことだ（VMWareがあれば）。というか、これはうまい仕組みかも知れないと思った。

目次を見ると全体は4部構成。

1部はアセンブリ言語とコンピュータアーキテクチャ。

レジスタ、プロテクションリング、ハードウウェアスタック。なぜか10ページを使ってレガシーとしてリアルモードとプロテクトモードなどを説明、仮想メモリについていろいろ（効率とかメモリマップトファイルとか）、コンパイル処理、割り込みとシステムコール、計算モデルとしては、有限状態マシン、Forthマシン（スタックマシンのことだよな？）で、課題としてForthコンパイラとインタープリタ。はて、なぜこれが計算モデルの章なのだろう。

2部はプログラミング言語C。

基礎、型システム、コードの構造、構文のセマンティクスとプラグマティクス（意味と実際、なのだが、実際？ 実態ではないのかなぁとか思う）。唐突にアラインメントの話。

そして良いコードを書くにはとして、選択、カプセル化、不変性、アサート、エラー処理、メモリー割当、柔軟性など。C11で。課題として画像の回転と、カスタムメモリアロケータ（これは面白そう）。

3部はCとアセンブラの間。

変換処理の詳細。つまり関数コールのシーケンス、volatile、非局所ジャンプとsetjmp、inline関数、restrictポインタ……（最適化の変換処理のことか）

共有オブジェクトとコードモデル。この章は再配置とPIC、GOTとPLT、プリローディング。どうでも良いけど、章題と実態がおれの感覚とはずいぶん違うな（これまでのところもそうだ）。

性能。最適化、キャッシング、SIMD、SSE/AVX。

マルチスレッド。難しいのはなぜか？ 実行順序。強弱メモリモデル。volatile、メモリバリア、pthreadsの紹介（？）、セマフォ、Intel64の強さについて。ロックフリー。C11のメモリモデル。

付録。gdbの使い方。makeの使い方。システムコール（read、write、open、close、mmap、munmap、exit。性能テストの情報。参考文献。

520ページほど。

1部はどちらかというとトピックの紹介。アセンブリのリストはある。

たとえば有限状態マシンでは、最後に正規表現のNFAによる説明が2ページほどあって、問題117「よく知っている言語を使ってgrepに似たプログラムをNFAの構築によって実装してみよう。参考情報：Russ Cox. Regular expression matching can be simple and fast (2007)」

という感じ。

一方、Forthはそれなりの長さのサンプル実装（アセンブリ）を示してForthマシンを説明している。課題はForthインタプリタの実装（当然、アセンブリ。sete、setl、setz、cpo。呼び出し先の退避にはr13,r14,r15を使え。ということからx64の話とわかる。自信がなければGforthでしばらく遊べ。

1部が150ページくらい。

2部がC11。セマンティクスのところは後でちゃんと読む（ぱっと眺めたところ、おれはちゃんと理解していない（知識として言語化されていないという意味）ことがわかった）。プラグマティクスの意味（言語仕様外だが、プログラムの振る舞いに影響するもの）。アラインメント、パディング。

13章の良いコードを書くには、は、ソフトウェア工学の話になるようだ。

3部。

変換処理：calling conventionの概念を再考して理解を深め、コンパイラがソスコードをどのように変換するかを詳述。

保護機構として、スタックに埋め込むセキュリティクッキー。アドレス空間のランダム化（なるほど）。DEPはわかる。

共有オブジェクト：ELFを思い出そう。から始まる。ffiの世界だ。

性能：高速化の神話。性能テストは特殊化されているし。プロファイルをしろ。コンパイラ作者はばかではないというか鬼のように賢いから、みんながよく書くコードパターンが恐ろしく最適化されている。手作業で最適化するのは不健全（コードが読みにくくなるし、保守は難しくなる）

まず、アルゴリズムの選択が重要。

具体的なコンパイラの戦略：スタックフレームポインタ省略。末尾再帰。共通式の除去。定数伝播。戻り値の最適化。分岐予測の影響（お、おう）。このへんまではわかる。実行ユニットの影響。リード・ライトのグループ化、わからん。後で読む。キャッシング、プリフェッチ。なんでプリフェッチのところでバイナリーサーチが出てくるんだ？ メモリアクセスパターンが予測困難だから。valgrindのcachegrindモジュールを使って調べる。プリフェッチによってLast Levelキャッシュのミスが改善されている。なぜだ？後で読む。

キャッシュバイパス。巨大行列のアクセスでいかにシーケンシャルにアクセスするようにするか。ここでもvalgrind。

この章はおもしろい（しろそう）。

マルチスレッドがどう難しいか。

C11のメモリモデル。弱い。アトミックのサポート。メモリオーダリング。問題407：ミューテックスがあるとき、なぜ条件変数が必要なのか。問題408：メモリオーダリングでIntel64が保証するのは何か。といった問題が並ぶ。

付録。gdbってemacsで実行するのだと思っていたら（というか、そうやって実行しているのだが）、自分のXのGUIを持っているのか。知らんかった。

makeの説明はなんで？ というレベル。

システムコール。

システムコールをアセンブリで発行するのは簡単だ。対応するレジスタを正しいパラメータ値に初期化して、syscall命令を実行するだけである。

そりゃそうだ。

低レベルプログラミング(Igor Zhirkov)

というわけで、すごくまっとうな本でした。

追記：本書の内容例

あ、そうか。これは怖いな。setjmp前後でアクセスする変数はvolatile必須じゃん。 pic.twitter.com/FhDgku6F93

— arton (@arton) 2018年1月20日