Programming先日、北陸twitterオフで、2次元配列をx,yの順でアクセスするのと、y,xの順でアクセスするのでは、実行速度が違うんだよ、という話をしていたのだが、正直このネタは4、5年前にMIPSを使っていたときの事なので、今でも有効なのか?と思いベンチマークプログラムを作成して検証してみた。内容Integer型二次元配列の内容を処理する時に、アドレス順に行う(キャッシュにヒットしやすい)場合と、そうでない(キャッシュにヒットしにくい)場合を比較してみた。今でも有効な手法という事が判明。Core2Duoの2次キャッシュも十分大きいので、そんな大差がつかないだろうと思っていたのだが、思ったより差がついたので、自分でもビックリ。遅いと言っても、それでも十分早いが。コードは下にある通り。プログラム自体の差は、見た目ほどんど分からないが、実行時間となると結構差が出てくる。BeHardwareの資料を元に話を進める。2次キャッシュは、コードを格納するコードキャッシュとデータを格納するデータキャッシュの2種類がある。今回のプログラム程度ではコードは全部キャッシュに載るので、あとはデータキャッシュをいかにヒットさせるかが焦点となってくる。2次キャッシュはページ単位で管理されており、Core2Duoは1ページ32KBでキャッシュを管理している。データは32KB以内の領域を連続してアクセスする場合は2次キャッシュにヒットするのでCPUと同等の速度でデータを取得し計算を行う事ができる。32KBより外側のデータを取得する必要がある場合は、キャッシュミスとなるので、いったんメインメモリから2次キャッシュにデータを格納した後、CPUが計算を行うのである。通常CPUのクロック速度に比べ、メインメモリへのアクセス速度が遅いのが一般的。今回の場合も、アドレスを飛び飛びでアクセスする事でキャッシュミスが頻発し、CPUは結構ストール(待たされる)が発生していたのではないかと思われる。これが、今回速度の差が出た原因である。Core2Duoのキャッシュを正しく把握した上でループを最適化してやれば、もっと速くなる可能性もあるが、今回はここまで。2次キャッシュを意識せよプログラムを高速に動作させるのは、データ構造&アルゴリズムが一番大切だが、その次に「いかに2次キャッシュにヒットさせるか」を意識したコーディングを行う事で、処理速度が速くなる事が立証された。今回のように、可読性を損わずに最適化を行う事も十分可能なのである。クヌース)と言えばTeXで有名な方。広告スターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。