Tom Lane <[EMAIL PROTECTED]> writes: > Greg Stark <[EMAIL PROTECTED]> writes: > > If the hash tables were made a power of two then it would be possible to mix > > the bits of the 32 bit value and just mask off the unneeded bits. I've found > > one page via google that mentions mixing bits in a hash function, but I would > > look for a more serious treatment somewhere.
> Modding by a *non* power of 2 (esp. a prime) mixes the bits quite well, > and is likely faster than any multiple-instruction way to do the same. Well a) any number that has any factors of two fails to mix in some bits. That's a lot more common than non powers of two. b) The postgres code makes no attempt to make the number of buckets a prime and c) Even if the number of buckets were prime then it seems it would still be too easy to find real-world data where all the data have that prime as a factor. As it is they only need to have common factors to lose. > The quoted article seems to be by someone who has spent a lot of time > counting assembly cycles and none at all reading the last thirty years > worth of CS literature. Yes, well I did note that. -- greg ---------------------------(end of broadcast)--------------------------- TIP 6: Have you searched our list archives? http://archives.postgresql.org