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

From: Jeff King <peff@peff.net>
Date: Oct 2, 2018, 19:19 UTC
Message-ID: <20181002191900.GA2014@sigill.intra.peff.net>
In-Reply-To: <d2421f36-563c-92ac-3fc9-29306d94b6fd@web.de>

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

Show 5 quoted lines

> > 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).

Show 6 quoted lines

> > 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. ;)

Show 10 quoted lines

> > 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).

Show 9 quoted lines

> > 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