2のべき乗サイズの配列は危ないという話 via 行列積 - elkurin’s blog

こんにちは。労働者です。とあるプログラムで学生さんの課題を添削していたら面白い話に出会いました。 僕は今、主に学部生向けのインターン研修的なプログラムでメンターなるものをやっています。メンターとしての仕事は、学生さんの課題へフィードバックを返し、Office Hourというセッションを毎週設けて質問受けやCSに関するトークを行うといった内容になっています。今回話題に取り上げるのはその中の課題の1つ、「行列積のプログラムを書いて時間を計測せよ」という何気ない話で、続く課題たちのいわば前座のようなものです。こういったところに沼は隠されているものですね。 担当している学生さんたちが細かい実験を行ってくれて以下のような疑問が提示されました。 「行列積の計算が N = 1024のときだけ N = 1023, 1025のときに比べて3倍遅いのはなぜ？」 配列のサイズが2のべき乗になるのは避けるべきとい

[rryu]

キャッシュの説明が違っていて、1024sets×64 byte line size=64KB離れたデータはキャッシュのインデックスが同じになるのでwey数分の16個しかキャッシュできないので行数が16以上あると遅くなるという仕組み。

[catalog360]

N = 2^nのときだけアホになります。

[tattyu]

キレイなアドレスだとキャッシュタグが衝突しちゃうのか。ちょっとバッドノウハウっぽい。

[kotetsu306]

これループ順で最適化するやつだよね。一番内側のkループが縦アクセスになるのがよくないので、i→k→jループにすると、一番内側のループが横方向の連続したアドレスへのアクセスになる

[yorkfield]

おもしろいけど、そういうこともあるくらいの話で一般化は危険。

[igni3]

スパコンとかでは[1025][1024]で確保するとかの方法(パティングという)が基礎知識として知られております。が、こういうのはその道のプロだけ知っとればよくて一般PCでは気にせんでもええと思う。

[joseph150]

これをソフトで避けましょうっていうのは、なんかテクノロジーの敗北感ある

[eru01]

行ごとのメモリアライメントがズレるんだが？？？？？？？？？？？？？転置したりループ順入れ替えたら？？？？？？？？バッドノウハウ広げるのやめてくれます？？？？？？？？？？

[Nobkz]

普通に転置行列を作ればいいのでは？とふと。

[momonga_dash]

これGPUカーネルのチューニングではわりとよくあるヤツだ（バンクコンフリクト）

[natroun]

自分で使うことはまずないけど、面白い話。

[shidho]

思った以上に面白い話だった。古い人間なんで記憶領域はキリのいい2のべき乗サイズで設計したくなるけどそういうケチくさいことは逆に良くないことなんだな。

[quick_past]

“19 (”

[houyhnhm]

配列のメモリ確保のパターンの話。

[NOV1975]

コンパイラが最適化しろ

[digo]

むしろ2の冪乗でつけるクセついてた(´･ω･`) まぁ、それが問題になる様なプログラムは書いてなかった気がするけども。。

[FruitShop]

コンピュータアーキテクチャの講義で出てくるよ。

[sugyan]

たとえ現象に気付けても、この原因までは辿り着ける気がしないな…

[kazuhooku]

「学生さんたちが細かい実験を行ってくれて以下のような疑問が提示されました」現象自体は（比較的）知られてると思うけど、これに気づく学生はすごく優秀だと思う

[atoh]

『へ〜、そんな事あるんだ』も言えない。

[koogawa]

そういうこともあるのね

[mohno]

知らなかったが普通にある話なのか。/インターン、よく見つけたなというのと、こんなの言われても自分では調べきれない気がする。/コンパイラが最適化で対応するのも難しそうだなあ。

[a96neko]

見てる

[naari_3]

何でこんなにもOut of Scopeな話題をするブクマカが沢山いるんだ……

[daishi_n]

メモリアラインメントは2のべき乗がベストだけど、キャッシュラインは2のべき乗外とか面倒だな

[terazzo]

キャッシュライン衝突を避けるのにパディングするのは普通らしいっぽい→https://www.slideshare.net/RCCSRENKEI/20210408-katagiri/87 ／2冪相手だと奇数でさえあれば良いのか

[theta]

変なこともあるもんだ

[alt-native]

正方形の画像を扱いときは気をつけよう。積分はふつうにやるよな。OpenCVとかそのへんクリアしてんのかな？

[rck10]

面白いけど、これを意識してアプリ実装するのも違うような。アルゴリズムの良し悪しを処理系から判断するのは上級言語の敗北感が凄い。

[u_eichi]

「べき乘」というワードに触れたのは、高校を卒業して以来だ。｜ちゃんと意味を覚えてて、若いってすごいなと過去の俺を羨むなど。

[nmcli]

ほえー

[yosuke_furukawa]

ハッシュの衝突による Hash flooding DoS と非常によく似た話だけど、 L1, L2 cache の内容から理解できて非常に面白い記事だった。

[outalaw]

2^nで遅くなるの知らなかった。けど、その理由がここに書かれていることなのか自分では判別できない……。

[kamenoseiji]

FFTの都合で2^Nサイズの配列を使うことが多かったのに、こんな落とし穴があったとは。勉強になりました。

[dekasasaki]

ブコメ含めて面白い。

[tako-two]

その時代のアーキテクチャによってノウハウが出てくるのがおもしろい

[umai_bow]

おもろい

[hgot07]

詳しくは定番のヘネパタ本でもどうぞ。容量性ミスの影響も出る行列サイズなら、ブロッキングなどの対策も要るでしょう。あと、ベクトル計算・行列計算したいだけの人は、OpenBLASのような最適化されたBLASがお奨め。