On Wed, Feb 01, 2023 at 10:09:29PM +0000, Eric Wong wrote: > Eric Wong <e@xxxxxxxxx> 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
