From: Jeff King <peff@peff•net>
To: Taylor Blau <me@ttaylorr•com>
Cc: git@vger•kernel.org, Junio C Hamano <gitster@pobox•com>,
Elijah Newren <newren@gmail•com>,
Derrick Stolee <stolee@gmail•com>
Subject: Re: [PATCH 5/8] pack-bitmap: cache object positions during fill
Date: Wed, 27 May 2026 05:45:35 -0400 [thread overview]
Message-ID: <20260527094535.GF981444@coredump.intra.peff.net> (raw)
In-Reply-To: <e43ef6a42d13578a6b7a4a346f491e51a6edfd14.1779207127.git.me@ttaylorr.com>
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
next prev parent reply other threads:[~2026-05-27 9:45 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-05-19 16:12 [PATCH 0/8] pack-bitmap-write: speed up bitmap generation Taylor Blau
2026-05-19 16:12 ` [PATCH 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()` Taylor Blau
2026-05-27 8:57 ` Jeff King
2026-05-27 14:36 ` Taylor Blau
2026-05-19 16:12 ` [PATCH 2/8] pack-bitmap: check subtree bits before recursing Taylor Blau
2026-05-27 9:03 ` Jeff King
2026-05-27 14:36 ` Taylor Blau
2026-05-19 16:12 ` [PATCH 3/8] pack-bitmap: reuse stored selected bitmaps Taylor Blau
2026-05-27 9:24 ` Jeff King
2026-05-27 14:40 ` Taylor Blau
2026-05-29 6:00 ` Jeff King
2026-05-19 16:12 ` [PATCH 4/8] pack-bitmap: consolidate `find_object_pos()` success path Taylor Blau
2026-05-20 14:42 ` SZEDER Gábor
2026-05-20 17:12 ` Taylor Blau
2026-05-27 9:27 ` Jeff King
2026-05-19 16:12 ` [PATCH 5/8] pack-bitmap: cache object positions during fill Taylor Blau
2026-05-27 9:45 ` Jeff King [this message]
2026-05-27 14:46 ` Taylor Blau
2026-05-19 16:12 ` [PATCH 6/8] pack-bitmap: sort bitmaps before XORing Taylor Blau
2026-05-27 10:04 ` Jeff King
2026-05-27 16:56 ` Taylor Blau
2026-05-29 8:26 ` Jeff King
2026-05-19 16:12 ` [PATCH 7/8] pack-bitmap: remember pseudo-merge parents Taylor Blau
2026-05-19 16:12 ` [PATCH 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps Taylor Blau
2026-05-27 10:25 ` Jeff King
2026-05-27 19:24 ` Taylor Blau
2026-05-29 8:33 ` Jeff King
2026-05-27 10:27 ` [PATCH 0/8] pack-bitmap-write: speed up bitmap generation Jeff King
2026-05-27 19:55 ` [PATCH v2 " Taylor Blau
2026-05-27 19:55 ` [PATCH v2 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()` Taylor Blau
2026-05-27 19:55 ` [PATCH v2 2/8] pack-bitmap: check subtree bits before recursing Taylor Blau
2026-05-27 19:55 ` [PATCH v2 3/8] pack-bitmap: reuse stored selected bitmaps Taylor Blau
2026-05-27 19:55 ` [PATCH v2 4/8] pack-bitmap: consolidate `find_object_pos()` success path Taylor Blau
2026-05-27 19:56 ` [PATCH v2 5/8] pack-bitmap: cache object positions during fill Taylor Blau
2026-05-27 19:56 ` [PATCH v2 6/8] pack-bitmap: sort bitmaps before XORing Taylor Blau
2026-05-27 19:56 ` [PATCH v2 7/8] pack-bitmap: remember pseudo-merge parents Taylor Blau
2026-05-27 19:56 ` [PATCH v2 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps Taylor Blau
2026-05-29 8:34 ` [PATCH v2 0/8] pack-bitmap-write: speed up bitmap generation Jeff King
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20260527094535.GF981444@coredump.intra.peff.net \
--to=peff@peff$(echo .)net \
--cc=git@vger$(echo .)kernel.org \
--cc=gitster@pobox$(echo .)com \
--cc=me@ttaylorr$(echo .)com \
--cc=newren@gmail$(echo .)com \
--cc=stolee@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox