> However this pattern induces stronger cache effects which are maybe not too realistic,
> because neighboring keys in the middle are more likely to be chosen.
I think that your opinion is right. However, in effect, it is a paseudo-benchmark, so that I think that such a simple mechanism is also necessary.
> Have you considered adding a "randomization" layer, that is once you have a key in [1 .. > n] centered around n/2, then you perform a pseudo-random transformation into the same > domain so that key values are scattered over the whole domain?
Yes. I also consider this patch. It can realize by adding linear mapping array which is created by random generator. However, current erand48 algorithm is not high accuracy and fossil algorithm, I do not know whether it works well. If we realize it, we may need more accurate random generator algorithm which is like Mersenne Twister.
Regards,
--
Mitsumasa KONDO