Re: Good hash for pointers

On 25/05/2024 22:13, Janis Papanagnou wrote:

On 25.05.2024 19:56, Malcolm McLean wrote:

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.

 I haven't read all the thread, but if I'd be going to tackle that
I'd first try to map the pointer onto a fitting integral type (if
that's possible; sizeof()), or first "fold" (XOR) the upper/lower
parts of the pointer (so that zero-sequences, if they appear, also
won't affect the outcome too badly as a side effect) to reduce the
size of the data, and finally use any established hash algorithm
on the (folded/reduced) integral type.
 Shall the created hash codes also be portable across platforms?
 

Yes, the Baby X resource compiler should be portable to any hosted platform with a reasonable up to date C compiler.
But we also need portablity in another sense. The hash table is hashing nodes of a XML document model created by the functions in the file xmlparser2.c. These make repeated calls to malloc() for small allocations of nodes. But I have no control, over either pointer representation or the platform's implemetation of malloc(). So the pointers could be at seemingly rsndom loctions in. memory, or they could be evenly spaced at increments of 64 bytes, and thus differing in only a few bits. Then if someone wants to help out with this project, an obvious thing to do would be to speed up the xml parser by replacing the calls to malloc() with a custom allocator. All the XPath functions are in the file xpath.c. They shouldn't suddenly hit the treacle because someone has changed the memory allocation system in xmlparser2.c.
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm