置換表と衝突と再利用性

少し、置換表の性能の話題があったので調べました。っていうほど詳しく調べてませんが。
昨年のいくつかの実験で、置換表の効果はそこまで大きくないという見解がありましたが*1。あまり詳しく調べてないので、適当にパラメタいじって出力。
対象はFFO#40（終盤解析20手完全読み）で、終盤7手置換表無しなので、node数に比べてヒット数も衝突数も異常に少ないです（私の場合の最善はこの辺のライン）。衝突時の挙動はいわゆるdirect map（衝突したら上書き）。

エントリ数	時間	node数	ヒット数	衝突	非衝突
2^18=256K	12.4sec	17.6M	39K	400K	230K
2^19=512K	10.5sec	14.8M	27K	200K	340K
2^20=1M	9.6sec	13.4M	26K	100K	400K
2^21=2M	9.9sec	13.6M	26K	58K	450K
2^22=4M	9.9sec	13.5M	26K	30K	480K

2^20エントリで速いのは、偶然かキャッシュの問題か。キャッシュはないか。あと、カウントするために++入れただけで0.7secくらい遅くなりました。マジカヨ。それから、こないだコンパイルし直してから、また遅くなりました。マジカヨ。
上から伺えることは、必要なサイズはおそらく500Kくらい（上の場合は）。その2倍程度のサイズの置換表以上ではたいした性能差はでない。エントリが足りないときの速度低下が大きい。
そういえば、#41以上は手数が増えるからキャッシュミス率あがってるのかもしれない。すると、やはりset associativeにした方がいいか。しかし、検索が遅くなるし、しかしミス率上昇の方が問題か…。ブツブツ。

*1:小さな置換表でもせいぜい性能比2倍程度