CPUアーキテクチャとソートなど

スカラ型CPUはL1キャッシュのヒット率に処理速度が大きく依存する。
それを意識した仕様・アルゴリズムを書けるかどうかが、プログラムの性能を決める。
もちろん大きな設計レベルで無駄がないことは前提だ。

L1キャッシュは、キャッシュの追い出しアルゴリズムがCPUごとにマチマチではあるが、基本的には古いほうや使われていないほうから捨てられる。
バブルソートなんかで、L1データキャッシュのサイズを超える配列をソートしようとすると、ほぼ確実にキャッシュミスを連発する。
スカラ型CPUとバブルソートは相性が悪い。
マージソートはアルゴリズム的な性能も高いが、それ以上にスカラ型CPUと相性がいい。
データを2分割しながら再帰で処理するから、配列のサイズがいくつであろうが、原理的にL1データキャッシュに入る量の単位で確実にソートされていく。

現在のPCではメモリが多いから、構造体のサイズを小さくする努力などすることは、すでにあまりないだろう。
でも、キャッシュのことを考えると、なんとかして32Byteに縮めたいところだ。
それから、データを作るたびにmallocしてメモリを確保すると、メモリ上に分散してしまうから、キャッシュ的には効率が悪い。
ループの中で集中して参照するデータであればなおさら、まとめて確保するようにすればキャッシュ効率は上がる。
最近の言語やシステムでは普通に贅沢なことをしてるが、根本的な部分を見るとそのやりかたはすさまじく効率が悪いのだ。
Rubyのような高級言語の世界ではあまり考えないことかもしれないが、そういう細かい差が、最近のDXRubyの実行速度として表面に出てきていると思う。

DXRubyのアーキテクチャは、Rubyの拡張ライブラリであるという制限、DirectXを扱うという制限の中で、最大の効率が出せるように一応考えてあるつもりだ。
もともと最適化はしていなかったが、それができるようにしていたし、すれば速くなる。
実行速度だけがアピールポイントなわけではないが、用途が用途なのと、特にRubyが遅いだけに、強調して恥ずかしくないレベルになってくれれば、これは結構価値として大きいんじゃないかと思う。