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
Taylor Blau <me@ttaylorr.com>
Date
May 27, 2026, 14:46 UTC
Message-ID
<ahcDsgYTJurWO7X3@nand.local>
In-Reply-To
<20260527094535.GF981444@coredump.intra.peff.net>
On Wed, May 27, 2026 at 05:45:35AM -0400, Jeff King wrote:
Show 18 quoted lines
> > 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.

I haven't run that experiment directly, but I share your suspicion. I wrote a 2- and 4-way associative cache implementation as alternatives before settling on the direct-mapped approach in this patch. I found that associative caches regardless of cache lines nearly nuked any of the performance gains that we got as a result of this patch.

> 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".

I think it's certainly likely. In my experience, many object to bit-position queries are extremely cache-friendly. And in practice, many large repositories have MIDXs with many tens of millions of objects. So even on a O(log n) lookup, caching seems to help a lot.

Show 13 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.
Glad it reproduces ;-).
Show 12 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.

Yeah, I suspect that there are many breakages past the 32-bit unsigned maximum number of objects. I figure the easiest thing to do in this patch is to avoid making that situation worse by simply not caching objects that are near that limit.

Thanks, Taylor

Previous: Jeff KingNext: Taylor Blau
Message 18 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.