職場で視聴をお勧めされて見たのだけれど、学びがあったので雑多にメモしておく。
- 横持ちでデータを読むのと縦持ちでデータを読む。読む量、使用するメモリは同じ。
- でもパフォーマンスとしては2つの異なるコンパイラーでも縦持ちで読みに行った方が遅い。
- 読みに行く時に今読んだ内容を元にPrefetchして速く読もうとする挙動が組まれていることが多い。横で読んでいけばそれに対応できるが、縦で読むとそうはいかず、結果として遅くなる。
- 奇数と偶数のように分けて計算をするマルチスレッドで実施したところ、
- 期待に反し2倍のコアを使って-40%、
- そして、16倍のコアを使ってようやく10%速くなった。
- そこでローカルカウンターを置いた。一見メモリ量の資料が増え、パフォーマンス的には悪く見える。
- しかし、実際はスレッドの数だけスケールするようになった。
- 理由はスレッドを跨いだメモリへのアクセスの問題。
- パフォーマンスを考えるならData cache, instruction cacheのことを考えるのが重要
- CPUが100%となっていても、実際には99%はデータ待ちになっていて本当は99% Idleかもしれない。
Time space trade off
Small = fast
L3cacheでも8MB
- Cache missが連続で発生してしまうから縦持ちで見に行くくと遅い
- Prefetchにハードウェアが対応していることが多い。その場合、予測可能な動きをすることでprefetchできるようになる。2つ飛ばしごと、3つ飛ばしごと、など。
- マルチスレッドでプログラムを組むときはdata racesを避ける、ということが言われる
- プログラマーとして、同時アクセスのことを気にする必要はない、それはハードウェア開発者の問題。ただし、data racesは避けなければいけない
- Data racesを避けるという観点で例えば
- 隣り合ったデータを取りに行ってもたしかにdata racesは起きない、がそこに書き込みをするとキャッシュラインがmark as dirtyとなってしまう=false sharing issue
気にしなければいけないのは下記すべてが満たされたとき
- 独立したデータが同じキャッシュラインに落ちている
- 異なるコアが同時にアクセスをしている
- それが頻繁に行われている
- 同時アクセスのうちの1つは少なくとも書き込みをしている
Data oriented design
- CPUがキャッシュラインを全て読めるようにデータを構成しプログラムを作る
- Sortをtype A, B, Cでやるより
- Type A、その後Type B、その後Type Cとした方がCPUにとっては都合がいい
- メトリクスを測るとき、sizeとshape(I.e. カラムの多さ)が重要になる
- リーダビリティやコードの品質とCache friendlyなコードは共存可能？アルゴリズムやデザインパターンなどあるか？
- Cache Oblivious Algorithmで探すとCache Friendlyなアルゴリズムについては見つかる。
正直言って、これまでパフォーマンスがシビアに求められるプログラムを書くことがあまりなかった。
振り返って唯一あったのはビッグデータ周りでのデータ処理で、その時初めて行指向と列指向という（今回の縦横とは当たらずも遠からずの話）、データの指向性について考える機会になったということ。
今回の、Data oriented designという考え方は結構面白くて、扱うデータや処理について真剣に考えれば考えるほど重要になるのだろうと思う。
今後の学習テーマの一つになる、かも。