Messages in this thread | | | Date | Wed, 26 Aug 1998 08:26:49 -0700 | From | "David S. Miller" <> | Subject | Re: 2.1.xxx makes Electric Fence 22x slower |
| |
Date: Wed, 26 Aug 1998 09:17:55 -0600 (MDT) From: Colin Plumb <colin@nyx.net>
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
| |