> actually, this was my first implementation choice. i found that the hash
> function didn't work very well with 3 8-bit tables -- it had poor
> bucket size distribution characteristics. how does one combine 3 8-bit
> values appropriately to get, say, a 14-bit table index?
[...]
> however, i think we're making different assumptions about what goes in the
> random table. i assumed they were random numbers from 0 to table_size,
> whereas some of your comments indicate you assume that the random table is
> filled with random numbers from 0 to 2^16.
Whoa! The size of the *random* tables is not related
to the size of the *hash* table. Why should it be?
The sizes of the random tables depend on the number of
bits in each of the key fragments.
As I said in the original message, the values stored
in the random tables are in the range 0..PAGE_HASH_SIZE-1.
If you've been picking only smaller values, no wonder the
hash has been performing poorly!
You were earlier perfectly correct that this kind of scheme
has a large cache footprint. On a modern processor with
a fast multiply, it would not be competitive.
Paul
-
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/