メモリプールやめました

少し前の話だが、Rekisa version 0.21.008 で差分の計算速度が大幅に向上した。
このとき、変えたのはアルゴリズムではない、メモリの管理方法だ。

以前は大きな配列を確保し、その中で使用する領域の確保と開放を繰り返していた。
その様子はこんな感じだ。

大きな配列を確保。
□□□□□□

５つの領域を確保。
■■■■■□

２番目と４番目を開放。
■□■□■□

１つの領域を確保。すぐ前に開放した２番目が使用される。
■■■□■□

空き領域は空き領域のリンクリストとなっている。その為、確保も開放も定数時間で可能だ。

それを変更し.NETのGCに任せることにした。
GCの動作は以下のようになる。

５つの領域を確保。
■■■■■

２つの領域が使われなくなった。
■□■□■

１つの領域を確保。領域は常に最後尾に確保される。
■□■□■■

ＧＣにより、空き領域が詰められる。
■■■■

こちらでも、領域の確保は定数時間で可能。一方、開放はGCに任せるので時間がかかる。

これだけ見るとGCの方が遅そうだが、実際には以前の方法で2分かかっていた処理が、新しい方法では1分に短縮された。それは何故か？

これは、おそらくキャッシュミスの発生率が下がったからだと思われる。

以前の方法では、あちこちに点在する開放済み領域から確保が行われる為、メモリの位置がバラバラになる。その為、確保時にも、解放時にも、アクセス時にもキャッシュミスが発生する。
一方、GCを使用した場合、メモリは確保された順に並んでいる。その為、確保したばかりのメモリしかアクセスしないアルゴリズムならば、ほとんどキャッシュミスは発生しない。

そして、差分計算のアルゴリズムは確保したばかりのメモリしかアクセスしないのだ。

その効果はGCによるオーバーヘッドを上回り、1分の差となって現れたのだろう。