On my computer this is the same as:
block + (block >> 16) with average bucket size (ABS) = 1,
block + (block >> 15) with ABS = 2,
block + (block >> 14) with ABS = 4, ...
It seems lower shift values are better than higher ones. Shift values of
(16, 15, 14, 13, 12, 11, 10) are all about the same, then from (9) to (6)
it's constantly improving and (5, 4, 3) are all nearly as good as (6).
The results of (2) are a bit strange. Although the distribution looks quite
good it's slower in the benchmarks.
The problem with (block) + (block >> hash_bits) seems to be that often
consecutive blocks are stored in the buffer cache and (block >> hash_bits)
just shifts offending block runs by one, so they are still overlapping.
Maybe something like:
(block) + (block >> hash_bits-10)
would be the right thing, or even:
(block) + (block >> hash_bits) * shift_value.
where shift_value should be greater than most of the block runs (and maybe
it should be also an odd number). But this will be too slow anyway.
Peter
--
_ x ___
/ \_/_\_ /,--' p.steiner@t-online.de (Peter Steiner)
\/>'~~~~//
\_____/ signature V0.2 alpha
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/