Re: fast-import's hash table is slow
- From
Jeff King <peff@peff.net>
- Date
- Apr 3, 2020, 19:01 UTC
- 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:
Show 17 quoted lines
> 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