██████████ のブログ

なんか技術的なメモ & ブクマ (no affiliate ads)

「プログラミングの常識」を時々見直す必要性について

一方でDRAMはCPUに比べればすごく遅くなった。CPUが恐ろしく速くなったとも言えるのだが、メインメモリにアクセスするには数百クロックを必要とするようになり、そのレイテンシを隠蔽するためにL1, L2, L3キャッシュがCPUの近くに加わった。

現代のプロセッサはメモリの局所性が悪いプログラムに対しては本来の性能が全然発揮できない。この変化によって、配列など局所性のよいデータ構造を使うアルゴリズムが、ランダムアクセスを必要とするアルゴリズムよりかなり有利になった。たとえばJavaArrayListを使うほうがLinkedListを使うより大抵ずっと速いのはこのためだ。多くの場合、凝ったアルゴリズムは局所性が悪いので、理論的には速い凝ったアルゴリズムを考案してみても、配列などを使った単純だが効率の悪そうなアルゴリズムに勝つことは結構難しい。大規模なデータを扱うのならこういうこともある程度頭に入れてデータ構造を設計しないといけない。

「プログラミングの常識」を時々見直す必要性について @rui314 (lld開発者)

 

コンピュータの構成と設計 第5版 上

コンピュータの構成と設計 第5版 上