On Thu, 1 Jul 2021 at 13:00, Thomas Munro <thomas.munro@gmail.com> wrote:
>
> On Wed, Jun 30, 2021 at 11:14 PM David Rowley <dgrowleyml@gmail.com> wrote:
> > 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.
>
> +1 for doing customisable "is in use" checks on day anyway, as a
> separate project. Not sure if any current users could shrink their
> structs in practice because, at a glance, the same amount of space
> might be used by padding anyway, but when a case like that shows up...
Yeah, I did look at that when messing with simplehash when working on
Result Cache a few months ago. I found all current usages have at
least a free byte, so I wasn't motivated to allow custom statuses to
be defined.
There's probably a small tidy up to do in simplehash maybe along with
that patch. If you look at SH_GROW, for example, you'll see various
formations of:
if (oldentry->status != SH_STATUS_IN_USE)
if (oldentry->status == SH_STATUS_IN_USE)
if (newentry->status == SH_STATUS_EMPTY)
I'm not all that sure why there's a need to distinguish !=
SH_STATUS_IN_USE from == SH_STATUS_EMPTY. I can only imagine that
Andres was messing around with tombstoning and at one point had a 3rd
status in a development version. There are some minor inefficiencies
as a result of this, e.g in SH_DELETE, the code does:
if (entry->status == SH_STATUS_EMPTY)
return false;
if (entry->status == SH_STATUS_IN_USE &&
SH_COMPARE_KEYS(tb, hash, key, entry))
That SH_STATUS_IN_USE check is always true.
David