ソートあれこれ - その５。

Bucket-Sort を in-place ではなくしたところ、予想通りの性能が出てくれてほっとしている。

なぜ in-place では性能が出なかったのかを考えてみると、やはり配列の要素を使って辿るという操作が良くないということになるだろう。要素データがメインメモリから来なければ、次の要素を参照する事ができないため、完全にメインメモリのバンド幅に依存する。にしてもあまりにも遅いが。

それでは in-place ではなぜ性能が出るのか。
まず移動元は連続に並んでおり、データは塊（64byte）でロードされるためキャッシュヒット率は高いと思われる。移動先に関してはかなり不連続だが、１度書き出されればその後はその要素にアクセスしないため、書き込みに対しての待ちもない。

data: USA-road-d.USA.gr (n=24M, m=58M)
Quick-Sort   6.7 [sec]
Bucket-Sort   17 [sec](in-place)
Bucket-Sort  1.5 [sec]