git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 5/8] pack-bitmap: cache object positions during fill

From
Jeff King <peff@peff.net>
Date
May 27, 2026, 09:45 UTC
Message-ID
<20260527094535.GF981444@coredump.intra.peff.net>
In-Reply-To
<e43ef6a42d13578a6b7a4a346f491e51a6edfd14.1779207127.git.me@ttaylorr.com>
On Tue, May 19, 2026 at 12:12:47PM -0400, Taylor Blau wrote:
Show 20 quoted lines
> 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".

Show 11 quoted lines
> 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.

Show 11 quoted lines
> 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.
Show 8 quoted lines
> +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
Previous: Taylor BlauNext: Taylor Blau
Message 17 of 38 in “pack-bitmap-write: speed up bitmap generation”
  1. 0/8 pack-bitmap-write: speed up bitmap generationTaylor Blau, May 19, 2026
  2. 1/8 pack-bitmap: pass object position to `fill_bitmap_tree()`Taylor Blau, May 19, 2026
  3. Jeff KingMay 27, 2026
  4. Taylor BlauMay 27, 2026
  5. 2/8 pack-bitmap: check subtree bits before recursingTaylor Blau, May 19, 2026
  6. Jeff KingMay 27, 2026
  7. Taylor BlauMay 27, 2026
  8. 3/8 pack-bitmap: reuse stored selected bitmapsTaylor Blau, May 19, 2026
  9. Jeff KingMay 27, 2026
  10. Taylor BlauMay 27, 2026
  11. Jeff KingMay 29, 2026
  12. 4/8 pack-bitmap: consolidate `find_object_pos()` success pathTaylor Blau, May 19, 2026
  13. SZEDER GáborMay 20, 2026
  14. Taylor BlauMay 20, 2026
  15. Jeff KingMay 27, 2026
  16. 5/8 pack-bitmap: cache object positions during fillTaylor Blau, May 19, 2026
  17. Jeff KingMay 27, 2026
  18. Taylor BlauMay 27, 2026
  19. 6/8 pack-bitmap: sort bitmaps before XORingTaylor Blau, May 19, 2026
  20. Jeff KingMay 27, 2026
  21. Taylor BlauMay 27, 2026
  22. Jeff KingMay 29, 2026
  23. 7/8 pack-bitmap: remember pseudo-merge parentsTaylor Blau, May 19, 2026
  24. 8/8 pack-bitmap: build pseudo-merge bitmaps after regular bitmapsTaylor Blau, May 19, 2026
  25. Jeff KingMay 27, 2026
  26. Taylor BlauMay 27, 2026
  27. Jeff KingMay 29, 2026
  28. Jeff KingMay 27, 2026
  29. 0/8 pack-bitmap-write: speed up bitmap generationTaylor Blau, May 27, 2026
  30. 1/8 pack-bitmap: pass object position to `fill_bitmap_tree()`Taylor Blau, May 27, 2026
  31. 2/8 pack-bitmap: check subtree bits before recursingTaylor Blau, May 27, 2026
  32. 3/8 pack-bitmap: reuse stored selected bitmapsTaylor Blau, May 27, 2026
  33. 4/8 pack-bitmap: consolidate `find_object_pos()` success pathTaylor Blau, May 27, 2026
  34. 5/8 pack-bitmap: cache object positions during fillTaylor Blau, May 27, 2026
  35. 6/8 pack-bitmap: sort bitmaps before XORingTaylor Blau, May 27, 2026
  36. 7/8 pack-bitmap: remember pseudo-merge parentsTaylor Blau, May 27, 2026
  37. 8/8 pack-bitmap: build pseudo-merge bitmaps after regular bitmapsTaylor Blau, May 27, 2026
  38. Jeff KingMay 29, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.