The fuzzy hash code may make the point moot, but generating
pseudo-random numbers can be done quite quickly (say, < 10 cycles) for
the fairly low quality requirements of a skip list. Precomputing a
bunch into a table and fetching from the table until empty helps a
great deal.
Certainly it is as fast as most good hash functions. (After all, I could
just keep a counter and hash that if I had a good hash function, couldn't I?)
What is important for skip lists is the distribution qualities, it
must be mostly evenly spread out. A bad distribution leads to unduly
long search paths.
the Mersenne Twister (Can you say "perfect score on the spectral
test with up to 600 dimensions", boys and girls?), is quite fast.
Indeed it does kick ass.
As I wrote before, I think it's the variable node size that makes
skip lists a pain to work with, not the random numbers.
I agree, but I also believe that the quality of the layout is strongly
connected to the distribution characteristics of the random number
input stream.
Later,
David S. Miller
davem@dm.cobaltmicro.com
-
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.altern.org/andrebalsa/doc/lkml-faq.html