From: Jeff King Date: Wed, 27 May 2026 09:45:35 GMT Subject: Re: [PATCH 5/8] pack-bitmap: cache object positions during fill Message-ID: <20260527094535.GF981444@coredump.intra.peff.net> In-Reply-To: On Tue, May 19, 2026 at 12:12:47PM -0400, Taylor Blau wrote: > The previous commits removed some redundant work from bitmap generation > by avoiding unnecessary tree recursion and by reusing selected bitmaps > that have already been computed. > > Even with those changes in place, there is still an extremely hot path > from `fill_bitmap_commit()` and `fill_bitmap_tree()` to translate object > IDs into their corresponding bit positions in order to generate their > bitmaps. > > In a small repository, this overhead is not significant. However, in a > very large repository (e.g., the one that we have been using as a > benchmark over the past several commits with ~57M total objects), the > overhead of locating object bit positions (often repeatedly) adds up > significantly. > > Combat this by adding a small, direct-mapped cache to the bitmap writer > which maps object IDs to their corresponding bit positions. Size the > cache according to the number of objects being written, with fixed lower > and upper bounds so small repositories do not pay for a large table and > large repositories can avoid most repeated packlist and MIDX lookups. Introducing another layer of data structure feels so dirty, but it's hard to argue with the numbers. We are looking up oids in the packlist, so it's already O(lg n). Your cache here is essentially a hash lookup, which is O(1)-ish (with collisions causing eviction rather than growth). And it presumably works because there's a lot of locality in lookups (between commits X and X^1, their top-level trees will be almost identical but we have to resolve the bits to find out which entries are new). It does make me wonder if we'd see similar improvements if we just turned the packlist into a regular hash table. Or maybe not, because then we'd have to do actual probing. It also makes me wonder if we could use this trick elsewhere, but I guess we usually are using "struct object" itself to find repeats in most graph traversals. And there we're using a hash table already. So this might save us a tiny bit of probing, but not much else. Likewise when comparing two trees directly, we can just walk them in parallel to find the changed parts (which doesn't work here, because we're comparing one tree to the bitmap of all ancestors, not just X^1). So this really is a somewhat unique situation. It _might_ be applicable for the reading side of bitmaps, though. When we do fill-in traversal we end up with this same "read a tree, find the bit for each entry, and 99% of the time find that it is already in the bitmap". > On my machine with (a somewhat outdated) GCC 15.2.0, each entry in the > cache is 40 bytes wide: > > $ pahole -C bitmap_pos_cache_entry pack-bitmap-write.o > struct bitmap_pos_cache_entry { > struct object_id oid; /* 0 36 */ > uint32_t pos; /* 36 4 */ > > /* size: 40, cachelines: 1, members: 2 */ > /* last cacheline: 40 bytes */ > }; I wondered about storing a pointer to an oid here, which would be smaller but require an extra level of pointer chasing. The ones from object structs are stable, but I guess the ones from trees are not (they point to an entry field which will be reused). So we have to store the oid whole. > In our example repository from above and in earlier commits, this > results in a ~9.4% reduction in runtime relative to the previous commit: > > +------------------+-------------+-------------+---------------------+ > | | HEAD^ | HEAD | Delta | > +------------------+-------------+-------------+---------------------+ > | elapsed | 324.8 s | 294.1 s | -30.7 s (-9.4%) | > | cycles | 1,508.6 B | 1,365.5 B | -143.0 B (-9.5%) | > | instructions | 1,436.6 B | 1,389.8 B | -46.9 B (-3.3%) | > | CPI | 1.050 | 0.983 | -0.068 (-6.4%) | > +------------------+-------------+-------------+---------------------+ I show a 26% speed up on linux.git (1m37 down to 1m12). Very cool. > +static uint32_t store_cached_object_pos(struct bitmap_writer *writer, > + const struct object_id *oid, > + uint32_t pos) > +{ > + size_t slot; > + > + if (pos & BITMAP_POS_CACHE_VALID) > + return pos; /* too large to cache */ Cute, I wondered what would happen if we went past 2^31. I suspect there are other parts of the code that do not behave that well around that size, but it is good that we are not introducing any new surprises. The whole patch looked pretty cleanly done. -Peff