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

["Johannes Schindelin via GitGitGadget" <gitgitgadget@gmail.com>]

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, and 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.

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.
    
    Changes since v1:
    
     * Fixed a typo in the commit message
     * Dropped the claim that this patch fixes the CI clone perf regression
       that's still being root-caused.
     * Renamed the is_new parameter to the more informative skip_dup_check.

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

Range-diff vs v1:

 1:  3dfb305e58 ! 1:  b892964f7e packfile: fix perf regression with many packs
     @@ Commit message
          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
     +    _already_ in the list, and 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.
     +    0.4s to 4.5s.
      
          Let's fix this by establishing a fast path for known-new packfiles.
      
     @@ packfile-list.c: void packfile_list_prepend(struct packfile_list *list, struct p
       
      -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)
     ++			  int skip_dup_check)
       {
       	struct packfile_list_entry *entry;
       
      -	entry = packfile_list_remove_internal(list, pack);
     -+	entry = is_new ? NULL : packfile_list_remove_internal(list, pack);
     ++	entry = skip_dup_check ? NULL : packfile_list_remove_internal(list, pack);
       	if (!entry) {
       		entry = xmalloc(sizeof(*entry));
       		entry->pack = pack;
     @@ packfile-list.h: struct packfile_list_entry {
       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);
     ++			  int skip_dup_check);
       
       /*
        * Find the pack within the "packs" list whose index contains the object


 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..d6d411823c 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 skip_dup_check)
 {
 	struct packfile_list_entry *entry;
 
-	entry = packfile_list_remove_internal(list, pack);
+	entry = skip_dup_check ? 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..2b4b98b226 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 skip_dup_check);
 
 /*
  * 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