Re: Good hash for pointers

On 25/05/2024 23:07, Malcolm McLean wrote:

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

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.

OK, parsing is a task I'm familiar with. Parsing a normal language into a syntax tree doesn't sound too different from parsing XML into a tree of nodes.
Such a task can be done at up to several million lines per second for source code. Are you getting throughput considerably below that?
It's not clear to me what the hashing is for on the nodes. What exactly is the input being looked up, and what is being compared? Because something sounds off: you don't normally look up a pointer to try and find it in a table; you already have the pointer pointing at the data!
 > 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.
If that's a bottleneck (you need to establish that; perhaps use a double call to malloc, and see if it slows down significantly), then the custom allocator is simple: just allocate from a pool. It's simpler still if you don't need to free that memory before the program ends