植山類さん講演会 (並行プログラミング)

先週に引き続き、リンカlldのオリジナル作者かつ現メンテナで、Cコンパイラ8ccの作者である植村類さんの講演会に参加しました。

今回は並行プログラミングを主題として、効率化の仕組みや類さんが自作されているリンカmoldについても教えていただきました。

特にlldとmoldの速度の違いに関してはとても興味深かったです。

ここから、学んだことをまとめています。

マルチコアマシン

• 昔はシングルコアだけだった。

• 今は PC やスマホもマルチコア

  • チップの微細化が進んでいるから。

• 10 万円以下だと 4 ~ 6 コア

• ハイエンドだと 16 ~ 64コア

  • 今の技術的には 64 コアくらいが上限。

  • 微細化が進めばもっと多くなるかも。

• スパコンだともっと多かったりする。

性能向上

• マルチコア構成により、複数のプログラムを同時に実行できる。

• make -jN のように make を実行するとサブプロセスを N 個同時に実行できる。

  • 複数プロセスで実行するため素早く make できる。

マルチスレッドと共有資源

• 1 つのプログラムをマルチコアマシンで速く動かすには、複数のスレッドを使う。

• ローカル変数はスレッドごとに別。

  • スレッドごとに別々実行スタックを持つ。

• マルチスレッドの例として Web サーバやレイトレーシング、GUI アプリなどが挙げられる。

• スレッドもあまり細かくしすぎるとオーバーヘッドが大きくなる。

  • そのため効率が良くならないこともある。

• 既存のプログラムをマルチスレッド化する万能の方法はない。

• 個別に良い感じのタスク分割をする。

Web サーバでのマルチスレッド

• コネクションが多すぎるとスケールしない。

• 少ないスレッドでイベント駆動型のほうが良いのか？

  • どっちも派閥がある。

  • 一概にどちらが良いとは言えない。

• google だとマルチスレッド。

• 1スレッド1コネクションの方がプログラミングは楽。

タスク分割のガイドライン

• スレッド間で共有するデータは少ないほうが良い。

  • データの整合性を保つための排他制御が必要になる。

• タスクの粒度は大きい方が良い。

  • 小さい処理を分割してもオーバーヘッドの方が大きい。

• タスクは多い方が良い。

• スレッド間の関係は単純な方が良い。

共有データの古典的な問題

• 銀行で同時に振り込みを行う。

  • 正しく制御しないと残高が合わないってことが起こり得る。

• そのためロックを使って排他制御を行う。

• 上手くロックしないとデッドロックが起こる。

  • 互いに相手の終了待ちとなり、いつまでも処理が進まなくなってしまう状態。

排他制御の責任はプログラマーにある？

• もう少し低いレイヤーでいい感じに制御できないのか。

• あることはあるが基本的にはプログラムで上手く排他制御するのがベター。

• トランザクショナル･メモリ を用いて CPU によって排他制御が行うことも可能ではある。

  • 各実行スレッドがそのコピーをローカルに持ち、処理終了時点で参照数値が変更されていないことの確認と、結果の書き込みを一気に行う。

  • 失敗した場合、処理そのものを廃棄してやり直す。

高水準スレッドライブラリ

並行コンテナ

• 別のスレッドからアクセスしても大丈夫な配列。

• ベクタやハッシュテーブルなどのデータ構造と同じ API を提供している。

• 中身の具体的な実装を気にすることなく使える。

Future

• データの受け渡しとスレッドの同期を一体化したもの。

• データを生成する側はデータを Future にセットする。

• 受け取り側は、必要となった時に Future から読み取る。

Wait group

• カウントダウン･ラッチともいう。

• 全員の処理を完了するまでの待ち合わせポイントとして使うことができる。

  • メインのルーチンがサブルーチンが全て終わるまで待つ。

• プロセスの wait みたいなイメージ。

アムダールの法則

• 並列化されたプログラムの性能を決める要因

  1. 並列化されていない箇所が全体のどれくらいか。

  2. 何個のコアが利用可能か。

(例) シングルコアで30分かかる処理

• 20分の処理は並列化されている。

• コアがいくつあっても10分より短くすることができない。

• 並列化された処理を増やすことが重要となる。

mold と lld の比較

• lld は並列化されていない処理が多い。

  • 全体の処理時間の大半を占めている。

• mold はほぼすべての処理が並列化されていないされている。

  • 短時間で処理可能。

mold の速度

• 手元のマシンでcd出力ファイル 1GB あたり約 1 秒

• cp で出力ファイルを別ファイルにコピーするのと比較して 2 倍遅い程度

• かなり速いらしい。

• 秘訣はたくさんのコアを有効に活用すること。

mold リンカの並列化手法

mold の目標

• 利用可能なコアを使い切る。

• 複雑のなことは行わない。

採用した手法

• データパラレリズム

• 同じ型のデータがたくさんあり、並列 for ループで同時に処理する。

• リンカ全体としてはシングルスレッドの場合と同じ複雑さ。

• 高水準スレッドライブラリはそこまでたくさん使っていない。

無理なく並列化できるデータ構造を考えることが大切。

Intel TBB

• C++ライブラリ

• 並列コンテナや 並列 for ループなど、マルチスレッドプログラミングのベースとなる機能

• mold でも使っている。

並列forループ

• 異なる繰り返しが同時に走るかもしれない for ループ。

tbb::parallel_for(0, 10000, [&](int i) {
    len[i] = strings[i].size();
});

• 最大で10000 並列で実行してくれる。

• 要素が少ないときに呼ぶとオーバーヘッドの方が無駄となる。

並列での名前解決

• 基本的にはハッシュテーブル。

• 並列化されたハッシュテーブルに並列 for ループで入れていく。

ファイルオフセットの決定

文字列をファイルに出力する場合

• 各文字列ごとにファイル上での位置を決める必要がある。

• 並列に足し算を行って、オフセットを求める。

入力文字
hello xxxx world

hello 文字列長 5 オフセット 5
xxxx  文字列長 4 オフセット 9
world 文字列長 5 オフセット　14

並行ハッシュマップ

• mold では自作の並行ハッシュテーブルを利用している。

• ハッシュテーブルのサイズを拡張する操作が遅い。

  • そのためリサイズしたくない。

  • あらかじめ大きなハッシュテーブルを用意する。

• すべての要素数を数えればちょうどよい大きさのハッシュテーブルができる。

  • しかしそれだと時間がかかるので本末転倒。

• ユニークな要素数を推定できるアルゴリズムを用いる。

  • HyperLogLog アルゴリズム。

HyperLogLog アルゴリズム

1. 文字列ごとにハッシュ値計算する。

2. ハッシュ値の最後に連続している 0 の数を数える。

(例) 最大で 0 が 5個連続しているものがあった場合

• そのような要素が出現する確率は [tex: \frac {1} {2⁸} = \frac {1} {256} ]

• おそらく元の要素は 256 種類程度あったと推測できる。

• 実際は複数の数をハッシュ値を使って複数の予測値を出して、それをすべて合わせることで、よりよい精度で推測を行う。

MapReduce パターン

• 共有ライブラリのシンボルを参照している未定義シンボルがあり、PLT/GOTを作る場合などに用いられる。

• ベクタを小さいブロックに分けて、並列に処理する。(Map フェーズ)

• ブロックを処理した結果として、少量のデータを出力する。

• 少量のデータをシングルスレッドで処理する。(Reduce フェーズ)

速いプログラムを書くために

• 推測せず、計測する。

• 凝ったコードより自然と速くなるようなデータ構造を考える。

• 複数実装して、一番速いものを選ぶ。

• 何度か同じプログラムを書く。

  • 再び作ることでより学べる。

  • 最初からいい感じに作るのは無理。

  • 同じ実装で改善できる範囲にも限界がある。

  • lldb で実装すると書き直しになるので mold を作った。

感想

並列処理を学ぶことの重要性を理解することができました。

工夫次第で劇的に性能向上が期待できるということが学べて良かったです。

また lld と mold の実行速度の違いを例として見ることができたのでよりイメージが湧きました。

最後に教えて頂いた効率的なコードの書き方を今後意識していこうと思います。