Re: [PATCH 2/2] fsck: use oidset for skiplist

On Tue, Oct 02, 2018 at 09:05:32PM +0200, René Scharfe wrote:

quoted

The reason hashmap.c was added was to avoid open addressing. ;)

Because efficient removal of elements is easier to implement with
chaining, according to 6a364ced49 (add a hashtable implementation that
supports O(1) removal).  khash.h deletes using its flags bitmap.  We
didn't compare their performance when entries are removed so far.

I think it may depend on your workload. Open-addressing generally uses a
tombstone, so you're still dealing with the "deleted" entries until the
next table resize. I suspect that's fine in most cases, but I also am
sure you could find a benchmark that favors the chained approach (I
think in most cases we actually never delete at all -- we simply fill up
a table and then eventually clear it).

quoted

So yeah, I think it could perhaps be improved, but in my mind talking
about "hashmap.c" is fundamentally talking about chained buckets.

Admittedly I wouldn't touch hashmap.c, as I find its interface too
complex to wrap my head around.  But perhaps I just didn't try hard
enough, yet.

FWIW, it's not just you. ;)

quoted

Yeah. And if it really does perform better, I think we should stick with
it in the code base. I wonder if we could stand to clean up the
interfaces a little.  E.g., I had a hard time declaring a hash in one
place, and then defining it somewhere else.

You can't use KHASH_DECLARE and KHASH_INIT together, as both declare
the same structs.  So I guess the idea is to have a header file with
KHASH_DECLARE and a .c file with KHASH_INIT, the latter *not* including
the former, but both including khash.h.  I didn't actually try that,
though.

Yeah, that seems weird. You'd want to include one from the other to make
sure that they both match.

By the way, if you do want to pursue changes, I have no problem at all
hacking up khash into something that can't be merged with its upstream.
It's nice that it's a well-used and tested library, but I'd much rather
have something that we on this project understand (and that matches our
conventions and style).

quoted

This is kind of a layering violation, too. You're assuming that struct
assignment is sufficient to make one kh struct freeable from another
pointer. That's probably reasonable, since you're just destroying them
both (e.g., some of our FLEX structs point into their own struct memory,
making a hidden dependency; but they obviously would not need to free
such a field).

Fair enough.  How about this on top?  (The khash.h part would go in
first in a separate patch in a proper series.)

Yes, much nicer, and the khash change wasn't too painful.

-Peff