Re: fast-import's hash table is slow

[Jeff King <peff@peff.net>]

On Tue, Mar 31, 2020 at 09:14:58PM +0200, René Scharfe wrote:

> > nr_objects   master       patch
> > 2^20         0m04.317s    0m5.109s
> > 2^21         0m10.204s    0m9.702s
> > 2^22         0m27.159s    0m17.911s
> > 2^23         1m19.038s    0m35.080s
> > 2^24         4m18.766s    1m10.233s
> 
> I get similar numbers.
> 
> Pre-sizing by putting this near the top of cmd_main() gets the time
> for 1M down to 4 seconds:
> 
> 	kh_resize_object_entry_set(&object_table, 1 << 18);
> 
> The more fair 1 << 16 does not cut it, the totally unfair 1 << 20 gives
> a small extra boost.

Good call. I can reproduce those results, too ("1 << 20" gives me a 12%
overall speedup). I'm surprised the growth isn't aggressive enough for
this early expansion to get lost in the noise.

> > +	/*
> > +	 * this cast works because we only look at the oid part of the entry,
> > +	 * and it comes first in the struct
> > +	 */
> > +	khiter_t pos = kh_get_object_entry_set(&object_table,
> > +					       (struct object_entry *)oid);
> 
> Dirty, but I can believe the comment.

Our hashmap.c implementation gets around this by letting the equality
function take an extra parameter. It's annoying when you're writing
those functions, but it should allow this case without any casting (or
preemptively allocating a struct).

> > -	for (h = 0; h < ARRAY_SIZE(object_table); h++) {
> > -		struct object_entry *e;
> > -
> > -		for (e = object_table[h]; e; e = e->next)
> > +	for (iter = kh_begin(&object_table); iter != kh_end(&object_table); iter++) {
> > +		if (kh_exist(&object_table, iter)) {
> > +			struct object_entry *e = kh_key(&object_table, iter);
> >  			if (e->pack_id == id)
> >  				e->pack_id = MAX_PACK_ID;
> > +		}
> >  	}
> 
> Is this really the best way to handle that, independently of the hashmap
> that's used?  I wonder how an extra hashmap or set of valid pack_id
> values (or set of invalidated pack_id values?) would fare against having
> to touch all object entries here.

I think the invalidation is pretty infrequent. It only gets called by
end_packfile() when there are few enough objects to loosen them. So
usually that would only happen once per process. You can also trigger it
manually with a "checkpoint" command, but if you're checkpointing often
enough to dump loose objects, I suspect you have other performance
problems.

-Peff