[PATCH] packfile: fix perf regression with many packs

[PATCH] packfile: fix perf regression with many packs

[Johannes Schindelin via GitGitGadget]

From: Johannes Schindelin <johannes.schindelin@gmx.de>

Since 589127caa730 (packfile: move list of packs into the packfile
store, 2025-10-30), there is a performance regression when many
packfiles need to be loaded: `packfile_store_add_pack()` now calls
`packfile_list_remove_internal()` to detect whether the packfile was
_already_ in the list, if if so, move it to the end of the list. This
function linearly scans the existing list before every insertion. Newly
loading N packs therefore has complexity O(N²).

In one reported use case (https://github.com/microsoft/git/issues/970),
N equals 37,815 and caused a slow-down of a simple `git rev-parse
--short HEAD` (which is regularly executed as part of `GIT_PS1`) from
0.4s to 4.5s. In another, heavily exercised CI scenario, clone times
increased from under 2 minutes to over half an hour.

Let's fix this by establishing a fast path for known-new packfiles.

The keen reader will note that there is currently only a single,
"known-new" caller of the `packfile_list_append()` function, and wonder
why not simply remove this check whether the packfile already exists in
the list? Originally, when above-mentioned commit introduced that logic,
there was a second caller in `prepare_midx()`, which would have required
that check, but that caller was removed in 6aff1f25a046 (packfile:
always add packfiles to MRU when adding a pack, 2025-10-30). Still, the
function is declared in a header file, and to avoid any problems with
in-flight or downstream callers, it is safer to extend the signature to
be explicit whether or not to skip that check.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
    packfile: fix perf regression with many packs
    
    This issue was spotted by a Microsoft Git user with the massive amount
    of packfiles typical of an average, long-running monorepo checkout.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2202%2Fdscho%2Ffix-perf-regression-in-v2.53-with-many-packfiles-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2202/dscho/fix-perf-regression-in-v2.53-with-many-packfiles-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2202

 packfile-list.c            | 5 +++--
 packfile-list.h            | 3 ++-
 packfile.c                 | 2 +-
 t/perf/p5303-many-packs.sh | 4 ++++
 4 files changed, 10 insertions(+), 4 deletions(-)

diff --git a/packfile-list.c b/packfile-list.c
index 01fb913abf..1379ab3a4f 100644
--- a/packfile-list.c
+++ b/packfile-list.c
@@ -57,11 +57,12 @@ void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack)
 		list->tail = entry;
 }
 
-void packfile_list_append(struct packfile_list *list, struct packed_git *pack)
+void packfile_list_append(struct packfile_list *list, struct packed_git *pack,
+			  int is_new)
 {
 	struct packfile_list_entry *entry;
 
-	entry = packfile_list_remove_internal(list, pack);
+	entry = is_new ? NULL : packfile_list_remove_internal(list, pack);
 	if (!entry) {
 		entry = xmalloc(sizeof(*entry));
 		entry->pack = pack;
diff --git a/packfile-list.h b/packfile-list.h
index 1b05e2aa36..01f9fb4cc5 100644
--- a/packfile-list.h
+++ b/packfile-list.h
@@ -15,7 +15,8 @@ struct packfile_list_entry {
 void packfile_list_clear(struct packfile_list *list);
 void packfile_list_remove(struct packfile_list *list, struct packed_git *pack);
 void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack);
-void packfile_list_append(struct packfile_list *list, struct packed_git *pack);
+void packfile_list_append(struct packfile_list *list, struct packed_git *pack,
+			  int is_new);
 
 /*
  * Find the pack within the "packs" list whose index contains the object
diff --git a/packfile.c b/packfile.c
index 0eee45055f..f80f05a1fe 100644
--- a/packfile.c
+++ b/packfile.c
@@ -781,7 +781,7 @@ void packfile_store_add_pack(struct odb_source_packed *store,
 	if (pack->pack_fd != -1)
 		pack_open_fds++;
 
-	packfile_list_append(&store->packs, pack);
+	packfile_list_append(&store->packs, pack, 1);
 	strmap_put(&store->packs_by_path, pack->pack_name, pack);
 }
 
diff --git a/t/perf/p5303-many-packs.sh b/t/perf/p5303-many-packs.sh
index af173a7b73..4221f9dd70 100755
--- a/t/perf/p5303-many-packs.sh
+++ b/t/perf/p5303-many-packs.sh
@@ -141,4 +141,8 @@ test_perf "load 10,000 packs" '
 	git rev-parse --verify "HEAD^{commit}"
 '
 
+test_perf "abbreviate with 10,000 packs" '
+	git rev-parse --short HEAD
+'
+
 test_done

base-commit: 11c6700f10234578d10523faf35656ca491425c9
-- 
gitgitgadget

Re: [PATCH] packfile: fix perf regression with many packs

[Junio C Hamano]

"Johannes Schindelin via GitGitGadget" <gitgitgadget@gmail.com>
writes:

> In one reported use case (https://github.com/microsoft/git/issues/970),
> N equals 37,815 and caused a slow-down of a simple `git rev-parse
> --short HEAD` (which is regularly executed as part of `GIT_PS1`) from
> 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times
> increased from under 2 minutes to over half an hour.

Face with Rolling Eyes (1f644) 🙄

As we grow older, more and more extreme use cases that we initially
thought were simply crazy become reality.

> Let's fix this by establishing a fast path for known-new packfiles.

As long as the caller reliably knows that the pack it has is new and
cannot be on the list, there is no reason to cycle through all the
packs in the ring to attempt removing it in vain.

Clever and clean.

> diff --git a/packfile.c b/packfile.c
> index 0eee45055f..f80f05a1fe 100644
> --- a/packfile.c
> +++ b/packfile.c
> @@ -781,7 +781,7 @@ void packfile_store_add_pack(struct odb_source_packed *store,
>  	if (pack->pack_fd != -1)
>  		pack_open_fds++;
>  
> -	packfile_list_append(&store->packs, pack);
> +	packfile_list_append(&store->packs, pack, 1);
>  	strmap_put(&store->packs_by_path, pack->pack_name, pack);
>  }
>  
> diff --git a/t/perf/p5303-many-packs.sh b/t/perf/p5303-many-packs.sh
> index af173a7b73..4221f9dd70 100755
> --- a/t/perf/p5303-many-packs.sh
> +++ b/t/perf/p5303-many-packs.sh
> @@ -141,4 +141,8 @@ test_perf "load 10,000 packs" '
>  	git rev-parse --verify "HEAD^{commit}"
>  '
>  
> +test_perf "abbreviate with 10,000 packs" '
> +	git rev-parse --short HEAD
> +'
> +
>  test_done
>
> base-commit: 11c6700f10234578d10523faf35656ca491425c9

Re: [PATCH] packfile: fix perf regression with many packs

[Jeff King]

On Wed, Aug 12, 2026 at 12:51:30PM -0700, Junio C Hamano wrote:

> "Johannes Schindelin via GitGitGadget" <gitgitgadget@gmail.com>
> writes:
> 
> > In one reported use case (https://github.com/microsoft/git/issues/970),
> > N equals 37,815 and caused a slow-down of a simple `git rev-parse
> > --short HEAD` (which is regularly executed as part of `GIT_PS1`) from
> > 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times
> > increased from under 2 minutes to over half an hour.
> 
> Face with Rolling Eyes (1f644) 🙄
> 
> As we grow older, more and more extreme use cases that we initially
> thought were simply crazy become reality.

Sort of. The quadratic adding became a problem long ago, hence
ec48540fe8 (packfile.c: speed up loading lots of packfiles, 2019-11-27).

So this was something we already dealt with that regressed. We can even
see the regression in our perf suite:

  $ GIT_SKIP_TESTS='p5303.[1-9] p5303.1[0-9]' ./run 589127caa730^ 589127caa730 p5303-many-packs.sh
  Test                         589127caa730^     589127caa730
  ----------------------------------------------------------------------
  5303.21: load 10,000 packs   0.13(0.11+0.02)   0.45(0.42+0.02) +246.2%

Unfortunately I don't think anybody pays close attention to the perf
suite (partially because it's clunky and expensive to run, but also
because it often requires human judgement to decide when something is a
real change and not just a blip).

None of that has any bearing on the fix, which seems reasonable to me,
but...

> > --- a/t/perf/p5303-many-packs.sh
> > +++ b/t/perf/p5303-many-packs.sh
> > @@ -141,4 +141,8 @@ test_perf "load 10,000 packs" '
> >  	git rev-parse --verify "HEAD^{commit}"
> >  '
> >  
> > +test_perf "abbreviate with 10,000 packs" '
> > +	git rev-parse --short HEAD
> > +'

...I wonder what value this is adding. It shows the same slowdown as the
existing test you can see in the context (and whose results I showed
above).

-Peff

Re: [PATCH] packfile: fix perf regression with many packs

[Ben Knoble]

> Le 12 août 2026 à 15:15, Johannes Schindelin via GitGitGadget <gitgitgadget@gmail.com> a écrit :
> 
> From: Johannes Schindelin <johannes.schindelin@gmx.de>
> 
> Since 589127caa730 (packfile: move list of packs into the packfile
> store, 2025-10-30), there is a performance regression when many
> packfiles need to be loaded: `packfile_store_add_pack()` now calls
> `packfile_list_remove_internal()` to detect whether the packfile was
> _already_ in the list, if if so, move it to the end of the list. This
> function linearly scans the existing list before every insertion. Newly
> loading N packs therefore has complexity O(N²).
> 
> In one reported use case (https://github.com/microsoft/git/issues/970),
> N equals 37,815 and caused a slow-down of a simple `git rev-parse
> --short HEAD` (which is regularly executed as part of `GIT_PS1`) from
> 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times
> increased from under 2 minutes to over half an hour.
> 
> Let's fix this by establishing a fast path for known-new packfiles.
> 
> The keen reader will note that there is currently only a single,
> "known-new" caller of the `packfile_list_append()` function, and wonder
> why not simply remove this check whether the packfile already exists in
> the list? Originally, when above-mentioned commit introduced that logic,
> there was a second caller in `prepare_midx()`, which would have required
> that check, but that caller was removed in 6aff1f25a046 (packfile:
> always add packfiles to MRU when adding a pack, 2025-10-30). Still, the
> function is declared in a header file, and to avoid any problems with
> in-flight or downstream callers, it is safer to extend the signature to
> be explicit whether or not to skip that check.
> 
> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
> ---
>    packfile: fix perf regression with many packs
> 
>    This issue was spotted by a Microsoft Git user with the massive amount
>    of packfiles typical of an average, long-running monorepo checkout.

As a different kind of intermediate solution, would turning on maintenance for that user’s checkout help? (Not sure that would help CI clone times unless the server repacks, of course.)