Re: Use simplehash.h instead of dynahash in SMgr

On Wed, 23 Jun 2021 at 12:17, Thomas Munro <thomas.munro@gmail.com> wrote:
>
> David and I discussed this a bit off-list, and I just wanted to share
> how I understand the idea so far in case it helps someone else.  There
> are essentially three subcomponents working together:

Thanks for taking an interest in this. I started looking at your idea
and I've now changed my mind from just not liking it to thinking that
the whole idea is just completely horrible :-(

It gets really messy with all the nested pre-processor stuff around
fetching the element from the segmented array inside simplehash.  One
problem is that simplehash needs the address of the segments despite
simplehash not knowing anything about segments. I've tried to make
that work by passing in the generic hash struct as simplehash's
private_data. This ends up with deeply nested macros all defined in
different files. I pitty the future person debugging that.

There is also a problem of how to reference simplehash functions
inside the generichash code.  It's not possible to do things like
SH_CREATE() because all those macros are undefined at the end of
simplehash.h. It's no good to hardcode the names either as GH_PREFIX
must be used, else it wouldn't be possible to use more than 1
differenrly defined hash table per .c file.  Fixing this means either
modifying simplehash.h to not undefine all the name macros at the end
maybe with SH_NOUNDEF or creating another set of macros to build the
names for the simplehash functions inside the generic hash code. I
don't like either of those ideas.

There are also a bunch of changes / API breakages that need to be done
to make this work with simplehash.h.

1) Since I really need 8-byte buckets in the hash table to make this
as fast as possible, I want to use the array index for the hash status
and that means changing the simplehash API to allow that to work.
This requires something like SH_IS_BUCKET_INUSE, SH_SET_BUCKET_INUSE,
SH_SET_BUCKET_EMPTY.
2) I need to add a new memory allocation function to not zero the
memory.  At the moment all hash buckets are emptied when creating a
table by zeroing the bucket memory. If someone defines
SH_SET_BUCKET_EMPTY to do something that says 0 memory is not empty,
then that won't work. So I need to allocate the bucket memory then
call SH_SET_BUCKET_EMPTY on each bucket.
3) I'll need to replace SH_KEY with something more complex.  Since the
simplehash bucket will just have a uint32 hashvalue and uint32 index,
the hash key is not stored in the bucket, it's stored over in the
segment. I'll need to replace SH_KEY with SH_GETKEY and SH_SETKEY.
These will need to consult the simplehash's private_data so that the
element can be found in the segmented array.

Also, simplehash internally manages when the hash table needs to grow.
I'll need to perform separate checks to see if the segmented array
also must grow.  It's a bit annoying to double up those checks as
they're in a very hot path as they're done everytime someone inserts
into the table.

> 2.  A bitmapset that tracks unused elements in 1, making it easy to
> find the lowest-index hole when looking for a place to put a new one
> by linear search for a 1 bit, so that we tend towards maximum density
> despite having random frees from time to time (seems good, the same
> idea is used in  kernels to allocate the lowest unused file descriptor
> number).

I didn't use Bitmapsets. I wanted the bitmaps to be allocated in the
same chunk of memory as the segments of the array.  Also, because
bitmapset's nwords is variable, then they can't really do any loop
unrolling.  Since in my implementation the number of bitmap words are
known at compile-time, the compiler has the flexibility to do loop
unrolling.  The bitmap manipulation is one of the biggest overheads in
generichash.h. I'd prefer to keep that as fast as possible.

> 3. A hash table that has as elements indexes into 1.  It somehow hides
> the difference between keys (what callers look things up with) and
> keys reachable by following an index into 1 (where elements' keys
> live).

I think that can be done, but it would require looking up the
segmented array twice instead of once.  The first time would be when
we compare the keys after seeing the hash values match. The final time
would be in the calling code to translate the index to the pointer.
Hopefully the compiler would be able to optimize that to a single
lookup.

> One thought is that you could do 1 as a separate component as the
> "primary" data structure, and use a plain old simplehash for 3 as a
> kind of index into it, but use pointers (rather than indexes) to
> objects in 1 as elements.  I don't know if it's better.

Using pointers would double the bucket width on a 64 bit machine. I
don't want to do that. Also, to be able to determine the segment from
the pointer it would require looping over each segment to check if the
pointer belongs there. With the index we can determine the segment
directly with bit-shifting the index.

So, with all that. I really don't think it's a great idea to try and
have this use simplehash.h code. I plan to pursue the idea I proposed
with having seperate hash table code that is coded properly to have
stable pointers into the data rather than trying to contort
simplehash's code into working that way.

David