From: Jeff King <peff@peff.net>
Date: Fri, 03 Apr 2020 19:01:38 GMT
Subject: Re: fast-import's hash table is slow
Message-ID: <20200403190138.GA660829@coredump.intra.peff.net>
In-Reply-To: <0279dc99-871c-8fb4-f1b0-3ae4ae7d94d8@web.de>

On Fri, Apr 03, 2020 at 08:53:23PM +0200, René Scharfe wrote:

> Am 03.04.20 um 14:12 schrieb Jeff King:
> > On Thu, Apr 02, 2020 at 08:40:35PM +0200, René Scharfe wrote:
> >
> >>>  struct object_entry {
> >>>  	struct pack_idx_entry idx;
> >>> -	struct object_entry *next;
> >>> +	struct hashmap_entry ent;
> >>
> >> That uses 16 bytes more memory per entry on x64 than khash would.
> >> That's 256MB for 2^24 objects -- not ideal, but bearable, I guess.
> >
> > Isn't it 8? We're dropping the old pointer and replacing it with the
> > "next" pointer in hashmap_entry, plus our 4-byte hash code (which likely
> > gets padded to 8).
> 
> That's right, so the difference to your khash version is 16, as the
> latter removes the pointer without any replacement.

Ah, OK. We are on the same page, then.

The khash version removes the pointer, but it presumably it would use a
larger number of buckets to keep the load factor down. I doubt it's
worth spending time running real-world heap-profiling experiments
(especially not on the silly synthetic test I showed).

-Peff