Re: [PATCH] packfile: fix perf regression with many packs
- From
Jeff King <peff@peff.net>
- Date
- Aug 17, 2026, 07:21 UTC
- Message-ID
- <20260817072113.GA690018@coredump.intra.peff.net>
- In-Reply-To
- <aoKZvxE8oP5B6O_4@pks.im>
On Mon, Aug 17, 2026 at 07:18:55AM +0200, Patrick Steinhardt wrote:
Show 12 quoted lines
> > The map protects more than just adding to the list; it avoids all of > > add_packed_git(), which allocates and does a bunch of stat() calls. So > > it couldn't just be a check in packfile_list_append(), but would have to > > be a separate existence check well before that. > > > > That's not impossible, but it would be a lot easier to see what > > generalized pattern would be most useful if there were more than one > > caller of packfile_list_append(). ;) > > We only have a single caller that appends, but we have some more that > use `packfile_list_prepend()`. And there we basically have the same > problem.
Ah, indeed. I see prepend calls sprinkled in some rather hot code paths, including the MRU adjustment from find_pack_entry(). That is a possible candidate for Dscho's clone slowdown[1].
But I don't think would not want to pay the cost for a hash de-dup there. We are not adding a new pack at all, but just adjusting the placement, and that should be a quick O(1) if we are using a doubly-linked list.
It's harder to construct a synthetic test for prepending because of pack locality. If two subsequent requests both try to move pack A to the front of the list, the second prepend()'s removal operation will find the pack at the front in essentially constant time.
But we can spread the history across packs like this (I recommend running on a ram disk, otherwise the checkpoint sync() makes it take forever):
git init
for i in $(seq 10000); do
echo "commit refs/heads/foo"
echo "committer <none@example.com> $i +0000"
echo "data <<EOF"
echo "commit message $i"
echo "EOF"
echo
echo checkpoint
done |
git -c fastimport.unpackLimit=0 fast-importAnd then timing "git rev-list --count foo" is interesting as the number of packs grows:
- 500: 18ms - 1000: 34ms - 2000: 103ms - 4000: 374ms - 8000: 1648ms - 16000: 6351ms
You can see the quadratic growth taking over around 2000 packs. But I'm not sure that is proving anything about list management. Lookup across packs is linear, so this situation is inherently quadratic. I think you could probably make an argument that the list management follows exactly the same quadratic patterns, and thus the MRU optimizes the removal from the prepend, too.
Still, it seems prudent for these MRU updates to use a constant-time movement within the list, rather than an explicit duplicate check and removal.
-Peff