On Tue, Oct 02, 2018 at 09:05:32PM +0200, René Scharfe wrote: > > 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). > > 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. ;) > > 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). > > 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
