Double Arrayの非常に効率的な圧縮

　「ダブル配列におけるキャッシュの効率化」という論文を見付けた。FIT2006というフォーラムで発表されたものらしい。これはすごい。目から鱗が落ちた。なんかリンク張って良いものか迷うので、とりあえずはリンクしない。
　この論文に書いてあることは2つあって、ひとつは配列サイズの削減で、もうひとつはできるだけキャッシュミスを減らすための方法である。配列サイズを削減するための方法がすごい。これまで誰も考え付かなかったのか、それとも考え付いたけどやらなかったのか？
　まず、checkの要素サイズは1byteで十分である。なぜなら、遷移元のインデックスがわからなくても、遷移に使ったキーの値がわかれば十分なので。これでDoubleArray全体のサイズを5/8に減らせる。また、普通、1GBのDouble Arrayを作成したりすることは無い（せいぜい100MB程度だろう）ので、Baseにも4byteも割り当てる必要はない。3byteで十分である。これで、baseとcheckの要素を4byteに納める事ができ、めでたくDouble Arrayは半分のサイズになる。 Double ArrayとHashの比較によるとDouble Arrayのメモリ消費量は約4877KB、Hashのメモリ消費量は約2827KBとなっているので、Double Arrayが半分のサイズになるならハッシュよりもメモリ消費量が少なくて済むことになる。ちなみに、リンク先のエントリのページ分割に関するサイズ計算はたぶん間違っている。
　Double Arrayのサイズ自体はページ分割した方が小さくなるみたいだけど、ページ分割のアルゴリズムはややこしいので、この単純なアルゴリズムは魅力的だと思う。ただ、2^24ではちょっと要素数が足りない場合も出てくるかもなぁ、という気もする。（1エントリに15要素使うとして112万単語程度。問題になる場合の方が少なそうではあるが。）
　（追記）：この記述は嘘。上の「サイズ」には圧縮できない値配列が含まれているので、DoubleArrayを半分のサイズに減らしたとして、結果は3251KB程度になるので、やっぱりハッシュには負ける。これ以上の圧縮をしようとすると、簡潔データ構造的な方向に行かねばならないのかな…。