Re: pack-objects memory use observations [was: [PATCH] delta-islands: free island-related data after use]

From: Jeff King <peff@peff.net>
Date: Feb 2, 2023, 00:11 UTC
Message-ID: <Y9r/rLhB1L9EnTKR@coredump.intra.peff.net>
In-Reply-To: <20230201220929.M549554@dcvr>

On Wed, Feb 01, 2023 at 10:09:29PM +0000, Eric Wong wrote:

> Eric Wong <e@80x24.org> wrote:
> > [1] WIP oidtree map, but I feel like I forgot C, again :<
> 
> Well, it hasn't crashed.  It's just much slower compared to khash.

I experimented a bit with critbit trees several years ago, mostly for the main obj_hash. I could never make them faster than hashing. I think part of it is that "hashing" an oid is basically free, since we just pull off the first 4 bytes. And we keep our table factors quite low. Whereas for trie structures, even though the big-O behavior is good, there's a lot of branching that ends up being slow.

> I'm thinking `struct object_id' should be pooled+deduplicated
> like hash keys in the Perl/Ruby interpreters and we'd pass
> 4/8-byte pointers instead of 36-byte structs.

I think that could work, but it feels like it would be pretty major surgery, given how often object_ids appear in the code.

-Peff