Deutsch English Français Italiano |
<86ttilg37o.fsf@linuxsc.com> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch <tr.17687@z991.linuxsc.com> Newsgroups: comp.lang.c Subject: Re: Good hash for pointers Date: Sat, 25 May 2024 11:23:55 -0700 Organization: A noiseless patient Spider Lines: 31 Message-ID: <86ttilg37o.fsf@linuxsc.com> References: <v2n88p$1nlcc$1@dont-email.me> <v2qm8m$2el55$1@raubtier-asyl.eternal-september.org> <v2qnue$2evlu$1@dont-email.me> <v2r9br$2hva2$1@dont-email.me> <86fru6gsqr.fsf@linuxsc.com> <v2sudq$2trh1$1@raubtier-asyl.eternal-september.org> <8634q5hjsp.fsf@linuxsc.com> <v2t8od$2vpp7$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Sat, 25 May 2024 20:23:55 +0200 (CEST) Injection-Info: dont-email.me; posting-host="8137c08e2aeaf8da9fb9d9b9c4e0a9a5"; logging-data="3145496"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19ANS13d+dsFFcJ+q7npSY2DD0MYT59u1U=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:8tlv3PqIRIXmsQ8/+qIUuCb/VB4= sha1:LByF/ZeJ7extj1l94/Kz+6G7y1Q= Bytes: 2358 Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > On 25/05/2024 18:40, Tim Rentsch wrote: > >> Bonita Montero <Bonita.Montero@gmail.com> writes: >> >>> Am 25.05.2024 um 11:12 schrieb Tim Rentsch: >>> >>>> Your hash function is expensive to compute, moreso even >>>> than the "FNV" function shown earlier. In a case like >>>> this one where the compares are cheap, it's better to >>>> have a dumb-but-fast hash function that might need a >>>> few more looks to find an open slot, because the cost >>>> of looking is so cheap compared to computing the hash >>>> function. >>> >>> A (size_t)pointer * LARGE_PRIME can be sufficient, >>> ignoring the overflow. >> >> Plenty fast but the output quality is poor. I tested >> this scheme against four other hash functions, and in >> four out of five workloads it was always dead last, by >> a noticeable margin. > > The lower bits of a pointer are often all zeroes. And mutlipying > by any integer will not set them. And that is catastrophic for a > hash. It can be but it doesn't have to be. It depends on how the hash value is used to determine a place or places to look in the table.