{"thread":{"id":"66166","subject":"[PATCH] packfile: fix perf regression with many packs","startedAt":"2026-08-12T19:11:13Z","lastAt":"2026-08-17T07:21:21Z","messageCount":24,"participants":["Johannes Schindelin via GitGitGadget","Junio C Hamano","Jeff King","Ben Knoble","Patrick Steinhardt","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"550441","messageId":"pull.2202.git.1786561870638.gitgitgadget@gmail.com","threadId":"66166","inReplyTo":null,"subject":"[PATCH] packfile: fix perf regression with many packs","fromName":"Johannes Schindelin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-08-12T19:11:09Z","receivedAt":"2026-08-12T19:11:13Z","isPatch":true,"body":"From: Johannes Schindelin \n\nSince 589127caa730 (packfile: move list of packs into the packfile\nstore, 2025-10-30), there is a performance regression when many\npackfiles need to be loaded: `packfile_store_add_pack()` now calls\n`packfile_list_remove_internal()` to detect whether the packfile was\n_already_ in the list, if if so, move it to the end of the list. This\nfunction linearly scans the existing list before every insertion. Newly\nloading N packs therefore has complexity O(N²).\n\nIn one reported use case (https://github.com/microsoft/git/issues/970),\nN equals 37,815 and caused a slow-down of a simple `git rev-parse\n--short HEAD` (which is regularly executed as part of `GIT_PS1`) from\n0.4s to 4.5s. In another, heavily exercised CI scenario, clone times\nincreased from under 2 minutes to over half an hour.\n\nLet's fix this by establishing a fast path for known-new packfiles.\n\nThe keen reader will note that there is currently only a single,\n\"known-new\" caller of the `packfile_list_append()` function, and wonder\nwhy not simply remove this check whether the packfile already exists in\nthe list? Originally, when above-mentioned commit introduced that logic,\nthere was a second caller in `prepare_midx()`, which would have required\nthat check, but that caller was removed in 6aff1f25a046 (packfile:\nalways add packfiles to MRU when adding a pack, 2025-10-30). Still, the\nfunction is declared in a header file, and to avoid any problems with\nin-flight or downstream callers, it is safer to extend the signature to\nbe explicit whether or not to skip that check.\n\nSigned-off-by: Johannes Schindelin \n---\n packfile: fix perf regression with many packs\n \n This issue was spotted by a Microsoft Git user with the massive amount\n of packfiles typical of an average, long-running monorepo checkout.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2202%2Fdscho%2Ffix-perf-regression-in-v2.53-with-many-packfiles-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2202/dscho/fix-perf-regression-in-v2.53-with-many-packfiles-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2202\n\n packfile-list.c | 5 +++--\n packfile-list.h | 3 ++-\n packfile.c | 2 +-\n t/perf/p5303-many-packs.sh | 4 ++++\n 4 files changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/packfile-list.c b/packfile-list.c\nindex 01fb913abf..1379ab3a4f 100644\n--- a/packfile-list.c\n+++ b/packfile-list.c\n@@ -57,11 +57,12 @@ void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack)\n \t\tlist->tail = entry;\n }\n \n-void packfile_list_append(struct packfile_list *list, struct packed_git *pack)\n+void packfile_list_append(struct packfile_list *list, struct packed_git *pack,\n+\t\t\t int is_new)\n {\n \tstruct packfile_list_entry *entry;\n \n-\tentry = packfile_list_remove_internal(list, pack);\n+\tentry = is_new ? NULL : packfile_list_remove_internal(list, pack);\n \tif (!entry) {\n \t\tentry = xmalloc(sizeof(*entry));\n \t\tentry->pack = pack;\ndiff --git a/packfile-list.h b/packfile-list.h\nindex 1b05e2aa36..01f9fb4cc5 100644\n--- a/packfile-list.h\n+++ b/packfile-list.h\n@@ -15,7 +15,8 @@ struct packfile_list_entry {\n void packfile_list_clear(struct packfile_list *list);\n void packfile_list_remove(struct packfile_list *list, struct packed_git *pack);\n void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack);\n-void packfile_list_append(struct packfile_list *list, struct packed_git *pack);\n+void packfile_list_append(struct packfile_list *list, struct packed_git *pack,\n+\t\t\t int is_new);\n \n /*\n * Find the pack within the \"packs\" list whose index contains the object\ndiff --git a/packfile.c b/packfile.c\nindex 0eee45055f..f80f05a1fe 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -781,7 +781,7 @@ void packfile_store_add_pack(struct odb_source_packed *store,\n \tif (pack->pack_fd != -1)\n \t\tpack_open_fds++;\n \n-\tpackfile_list_append(&store->packs, pack);\n+\tpackfile_list_append(&store->packs, pack, 1);\n \tstrmap_put(&store->packs_by_path, pack->pack_name, pack);\n }\n \ndiff --git a/t/perf/p5303-many-packs.sh b/t/perf/p5303-many-packs.sh\nindex af173a7b73..4221f9dd70 100755\n--- a/t/perf/p5303-many-packs.sh\n+++ b/t/perf/p5303-many-packs.sh\n@@ -141,4 +141,8 @@ test_perf \"load 10,000 packs\" '\n \tgit rev-parse --verify \"HEAD^{commit}\"\n '\n \n+test_perf \"abbreviate with 10,000 packs\" '\n+\tgit rev-parse --short HEAD\n+'\n+\n test_done\n\nbase-commit: 11c6700f10234578d10523faf35656ca491425c9\n-- \ngitgitgadget\n"},{"id":"550447","messageId":"xmqqfr0jw20t.fsf@gitster.g","threadId":"66166","inReplyTo":"pull.2202.git.1786561870638.gitgitgadget@gmail.com","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-08-12T19:51:30Z","receivedAt":"2026-08-12T19:51:33Z","isPatch":true,"body":"\"Johannes Schindelin via GitGitGadget\" \nwrites:\n\n> In one reported use case (https://github.com/microsoft/git/issues/970),\n> N equals 37,815 and caused a slow-down of a simple `git rev-parse\n> --short HEAD` (which is regularly executed as part of `GIT_PS1`) from\n> 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times\n> increased from under 2 minutes to over half an hour.\n\nFace with Rolling Eyes (1f644) 🙄\n\nAs we grow older, more and more extreme use cases that we initially\nthought were simply crazy become reality.\n\n> Let's fix this by establishing a fast path for known-new packfiles.\n\nAs long as the caller reliably knows that the pack it has is new and\ncannot be on the list, there is no reason to cycle through all the\npacks in the ring to attempt removing it in vain.\n\nClever and clean.\n\n> diff --git a/packfile.c b/packfile.c\n> index 0eee45055f..f80f05a1fe 100644\n> --- a/packfile.c\n> +++ b/packfile.c\n> @@ -781,7 +781,7 @@ void packfile_store_add_pack(struct odb_source_packed *store,\n> \tif (pack->pack_fd != -1)\n> \t\tpack_open_fds++;\n> \n> -\tpackfile_list_append(&store->packs, pack);\n> +\tpackfile_list_append(&store->packs, pack, 1);\n> \tstrmap_put(&store->packs_by_path, pack->pack_name, pack);\n> }\n> \n> diff --git a/t/perf/p5303-many-packs.sh b/t/perf/p5303-many-packs.sh\n> index af173a7b73..4221f9dd70 100755\n> --- a/t/perf/p5303-many-packs.sh\n> +++ b/t/perf/p5303-many-packs.sh\n> @@ -141,4 +141,8 @@ test_perf \"load 10,000 packs\" '\n> \tgit rev-parse --verify \"HEAD^{commit}\"\n> '\n> \n> +test_perf \"abbreviate with 10,000 packs\" '\n> +\tgit rev-parse --short HEAD\n> +'\n> +\n> test_done\n>\n> base-commit: 11c6700f10234578d10523faf35656ca491425c9\n"},{"id":"550453","messageId":"20260812212955.GA152730@coredump.intra.peff.net","threadId":"66166","inReplyTo":"xmqqfr0jw20t.fsf@gitster.g","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-08-12T21:29:55Z","receivedAt":"2026-08-12T21:30:03Z","isPatch":true,"body":"On Wed, Aug 12, 2026 at 12:51:30PM -0700, Junio C Hamano wrote:\n\n> \"Johannes Schindelin via GitGitGadget\" \n> writes:\n> \n> > In one reported use case (https://github.com/microsoft/git/issues/970),\n> > N equals 37,815 and caused a slow-down of a simple `git rev-parse\n> > --short HEAD` (which is regularly executed as part of `GIT_PS1`) from\n> > 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times\n> > increased from under 2 minutes to over half an hour.\n> \n> Face with Rolling Eyes (1f644) 🙄\n> \n> As we grow older, more and more extreme use cases that we initially\n> thought were simply crazy become reality.\n\nSort of. The quadratic adding became a problem long ago, hence\nec48540fe8 (packfile.c: speed up loading lots of packfiles, 2019-11-27).\n\nSo this was something we already dealt with that regressed. We can even\nsee the regression in our perf suite:\n\n $ GIT_SKIP_TESTS='p5303.[1-9] p5303.1[0-9]' ./run 589127caa730^ 589127caa730 p5303-many-packs.sh\n Test 589127caa730^ 589127caa730\n ----------------------------------------------------------------------\n 5303.21: load 10,000 packs 0.13(0.11+0.02) 0.45(0.42+0.02) +246.2%\n\nUnfortunately I don't think anybody pays close attention to the perf\nsuite (partially because it's clunky and expensive to run, but also\nbecause it often requires human judgement to decide when something is a\nreal change and not just a blip).\n\nNone of that has any bearing on the fix, which seems reasonable to me,\nbut...\n\n> > --- a/t/perf/p5303-many-packs.sh\n> > +++ b/t/perf/p5303-many-packs.sh\n> > @@ -141,4 +141,8 @@ test_perf \"load 10,000 packs\" '\n> > \tgit rev-parse --verify \"HEAD^{commit}\"\n> > '\n> > \n> > +test_perf \"abbreviate with 10,000 packs\" '\n> > +\tgit rev-parse --short HEAD\n> > +'\n\n...I wonder what value this is adding. It shows the same slowdown as the\nexisting test you can see in the context (and whose results I showed\nabove).\n\n-Peff\n"},{"id":"550458","messageId":"6EA76E66-E80C-4F19-8806-FAE8294ACFB7@gmail.com","threadId":"66166","inReplyTo":"pull.2202.git.1786561870638.gitgitgadget@gmail.com","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Ben Knoble","fromEmail":"ben.knoble@gmail.com","sentAt":"2026-08-12T22:29:47Z","receivedAt":"2026-08-12T22:30:00Z","isPatch":true,"body":"> Le 12 août 2026 à 15:15, Johannes Schindelin via GitGitGadget a écrit :\n> \n> From: Johannes Schindelin \n> \n> Since 589127caa730 (packfile: move list of packs into the packfile\n> store, 2025-10-30), there is a performance regression when many\n> packfiles need to be loaded: `packfile_store_add_pack()` now calls\n> `packfile_list_remove_internal()` to detect whether the packfile was\n> _already_ in the list, if if so, move it to the end of the list. This\n> function linearly scans the existing list before every insertion. Newly\n> loading N packs therefore has complexity O(N²).\n> \n> In one reported use case (https://github.com/microsoft/git/issues/970),\n> N equals 37,815 and caused a slow-down of a simple `git rev-parse\n> --short HEAD` (which is regularly executed as part of `GIT_PS1`) from\n> 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times\n> increased from under 2 minutes to over half an hour.\n> \n> Let's fix this by establishing a fast path for known-new packfiles.\n> \n> The keen reader will note that there is currently only a single,\n> \"known-new\" caller of the `packfile_list_append()` function, and wonder\n> why not simply remove this check whether the packfile already exists in\n> the list? Originally, when above-mentioned commit introduced that logic,\n> there was a second caller in `prepare_midx()`, which would have required\n> that check, but that caller was removed in 6aff1f25a046 (packfile:\n> always add packfiles to MRU when adding a pack, 2025-10-30). Still, the\n> function is declared in a header file, and to avoid any problems with\n> in-flight or downstream callers, it is safer to extend the signature to\n> be explicit whether or not to skip that check.\n> \n> Signed-off-by: Johannes Schindelin \n> ---\n> packfile: fix perf regression with many packs\n> \n> This issue was spotted by a Microsoft Git user with the massive amount\n> of packfiles typical of an average, long-running monorepo checkout.\n\nAs 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.)"},{"id":"550474","messageId":"an1zz02GNqDu-0Oz@pks.im","threadId":"66166","inReplyTo":"pull.2202.git.1786561870638.gitgitgadget@gmail.com","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-08-13T07:35:49Z","receivedAt":"2026-08-13T07:36:01Z","isPatch":true,"body":"On Wed, Aug 12, 2026 at 07:11:09PM +0000, Johannes Schindelin via GitGitGadget wrote:\n> From: Johannes Schindelin \n> \n> Since 589127caa730 (packfile: move list of packs into the packfile\n> store, 2025-10-30), there is a performance regression when many\n> packfiles need to be loaded: `packfile_store_add_pack()` now calls\n> `packfile_list_remove_internal()` to detect whether the packfile was\n> _already_ in the list, if if so, move it to the end of the list. This\n\nNit: s/if if/and if/\n\n> function linearly scans the existing list before every insertion. Newly\n> loading N packs therefore has complexity O(N²).\n> \n> In one reported use case (https://github.com/microsoft/git/issues/970),\n> N equals 37,815 and caused a slow-down of a simple `git rev-parse\n> --short HEAD` (which is regularly executed as part of `GIT_PS1`) from\n> 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times\n> increased from under 2 minutes to over half an hour.\n\nWow, 38k packfiles is a lot.\n\n> Let's fix this by establishing a fast path for known-new packfiles.\n> \n> The keen reader will note that there is currently only a single,\n> \"known-new\" caller of the `packfile_list_append()` function, and wonder\n> why not simply remove this check whether the packfile already exists in\n> the list? Originally, when above-mentioned commit introduced that logic,\n> there was a second caller in `prepare_midx()`, which would have required\n> that check, but that caller was removed in 6aff1f25a046 (packfile:\n> always add packfiles to MRU when adding a pack, 2025-10-30). Still, the\n> function is declared in a header file, and to avoid any problems with\n> in-flight or downstream callers, it is safer to extend the signature to\n> be explicit whether or not to skip that check.\n\nQuite conservative, but fair enough.\n\n> diff --git a/packfile-list.c b/packfile-list.c\n> index 01fb913abf..1379ab3a4f 100644\n> --- a/packfile-list.c\n> +++ b/packfile-list.c\n> @@ -57,11 +57,12 @@ void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack)\n> \t\tlist->tail = entry;\n> }\n> \n> -void packfile_list_append(struct packfile_list *list, struct packed_git *pack)\n> +void packfile_list_append(struct packfile_list *list, struct packed_git *pack,\n> +\t\t\t int is_new)\n> {\n> \tstruct packfile_list_entry *entry;\n> \n> -\tentry = packfile_list_remove_internal(list, pack);\n> +\tentry = is_new ? NULL : packfile_list_remove_internal(list, pack);\n> \tif (!entry) {\n> \t\tentry = xmalloc(sizeof(*entry));\n> \t\tentry->pack = pack;\n\nI wonder whether we should slightly reformulate this and rename `is_new`\nto `accept_duplicates`. Because ultimately, that is what we're doing\nnow: instead of ensuring that the packfile is unique in the list, we\njust don't care and just append the entry to the list.\n\nAn alternative would be to use a hashmap here that tracks the packs that\nhave already been added. It has the advantage that it also covers the\n`prepend()` operation and that callers don't have to be aware of this\nmechanism at all. Furthermore, moving preexisting entries to the back or\nfront could become O(logn) if the list was doubly-linked. We do this\noperation quite often to re-sort entries in the list when looking up\nobjects.\n\nOverall though I'm not quite sure whether the added complexity would be\nworth it, see below patch.\n\nThanks!\n\nPatrick\n\ndiff --git a/http-push.c b/http-push.c\nindex 94a1fac9ab..52b00e7c95 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1729,6 +1729,7 @@ int cmd_main(int argc, const char **argv)\n \tconst char *gitdir;\n \n \tCALLOC_ARRAY(repo, 1);\n+\tpackfile_list_init(&repo->packs);\n \n \targv++;\n \tfor (i = 1; i < argc; i++, argv++) {\n@@ -1992,6 +1993,7 @@ int cmd_main(int argc, const char **argv)\n cleanup:\n \tif (info_ref_lock)\n \t\tunlock_remote(info_ref_lock);\n+\tpackfile_list_clear(&repo->packs);\n \tfree(repo->url);\n \tfree(repo);\n \ndiff --git a/http-walker.c b/http-walker.c\nindex b58a3b2a92..541437e52d 100644\n--- a/http-walker.c\n+++ b/http-walker.c\n@@ -325,6 +325,7 @@ static void process_alternates_response(void *callback_data)\n \t\t\t\t\twarning(\"adding alternate object store: %s\",\n \t\t\t\t\t\ttarget.buf);\n \t\t\t\t\tCALLOC_ARRAY(newalt, 1);\n+\t\t\t\t\tpackfile_list_init(&newalt->packs);\n \t\t\t\t\tnewalt->base = strbuf_detach(&target, NULL);\n \n \t\t\t\t\twhile (tail->next != NULL)\n@@ -609,6 +610,7 @@ struct walker *get_http_walker(const char *url)\n \tstruct walker *walker = xmalloc(sizeof(struct walker));\n \n \tCALLOC_ARRAY(data->alt, 1);\n+\tpackfile_list_init(&data->alt->packs);\n \tdata->alt->base = xstrdup(url);\n \tfor (s = data->alt->base + strlen(data->alt->base) - 1; *s == '/'; --s)\n \t\t*s = 0;\ndiff --git a/odb/source-packed.c b/odb/source-packed.c\nindex 0890704e76..082c2494cb 100644\n--- a/odb/source-packed.c\n+++ b/odb/source-packed.c\n@@ -835,6 +835,7 @@ struct odb_source_packed *odb_source_packed_new(struct object_database *odb,\n \n \tCALLOC_ARRAY(packed, 1);\n \todb_source_init(&packed->base, odb, ODB_SOURCE_PACKED, path, local);\n+\tpackfile_list_init(&packed->packs);\n \tstrmap_init(&packed->packs_by_path);\n \n \tpacked->base.free = odb_source_packed_free;\ndiff --git a/packfile-list.c b/packfile-list.c\nindex 01fb913abf..d3c4843d8d 100644\n--- a/packfile-list.c\n+++ b/packfile-list.c\n@@ -2,6 +2,28 @@\n #include \"packfile.h\"\n #include \"packfile-list.h\"\n \n+static unsigned int packfile_list_entry_hash(struct packfile_list_entry *e)\n+{\n+\treturn memhash(&e->pack, sizeof(e->pack));\n+}\n+\n+static int packfile_list_entry_cmp(const void *data UNUSED,\n+\t\t\t\t const struct hashmap_entry *h1,\n+\t\t\t\t const struct hashmap_entry *h2,\n+\t\t\t\t const void *keydata UNUSED)\n+{\n+\tconst struct packfile_list_entry *e1, *e2;\n+\te1 = container_of(h1, const struct packfile_list_entry, ent);\n+\te2 = container_of(h2, const struct packfile_list_entry, ent);\n+\treturn e1->pack != e2->pack;\n+}\n+\n+void packfile_list_init(struct packfile_list *list)\n+{\n+\tmemset(list, 0, sizeof(*list));\n+\thashmap_init(&list->seen, packfile_list_entry_cmp, NULL, 0);\n+}\n+\n void packfile_list_clear(struct packfile_list *list)\n {\n \tstruct packfile_list_entry *e, *next;\n@@ -12,6 +34,20 @@ void packfile_list_clear(struct packfile_list *list)\n \t}\n \n \tlist->head = list->tail = NULL;\n+\n+\thashmap_clear(&list->seen);\n+}\n+\n+static struct packfile_list_entry *packfile_list_lookup(struct packfile_list *list,\n+\t\t\t\t\t\t\tstruct packed_git *pack)\n+{\n+\tstruct packfile_list_entry key = { .pack = pack };\n+\tstruct hashmap_entry *ent;\n+\n+\thashmap_entry_init(&key.ent, packfile_list_entry_hash(&key));\n+\tent = hashmap_get(&list->seen, &key.ent, NULL);\n+\n+\treturn ent ? container_of(ent, struct packfile_list_entry, ent) : NULL;\n }\n \n static struct packfile_list_entry *packfile_list_remove_internal(struct packfile_list *list,\n@@ -38,20 +74,33 @@ static struct packfile_list_entry *packfile_list_remove_internal(struct packfile\n \n void packfile_list_remove(struct packfile_list *list, struct packed_git *pack)\n {\n-\tfree(packfile_list_remove_internal(list, pack));\n+\tstruct packfile_list_entry key = { .pack = pack };\n+\n+\thashmap_entry_init(&key.ent, packfile_list_entry_hash(&key));\n+\tif (hashmap_remove(&list->seen, &key.ent, NULL)) {\n+\t\tstruct packfile_list_entry *e = packfile_list_remove_internal(list, pack);\n+\t\tif (!e)\n+\t\t\tBUG(\"corrupt packfile list\");\n+\t\tfree(e);\n+\t}\n }\n \n void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack)\n {\n \tstruct packfile_list_entry *entry;\n \n-\tentry = packfile_list_remove_internal(list, pack);\n-\tif (!entry) {\n+\tif (packfile_list_lookup(list, pack)) {\n+\t\tentry = packfile_list_remove_internal(list, pack);\n+\t\tif (!entry)\n+\t\t\tBUG(\"corrupt packfile list\");\n+\t} else {\n \t\tentry = xmalloc(sizeof(*entry));\n \t\tentry->pack = pack;\n+\t\thashmap_entry_init(&entry->ent, packfile_list_entry_hash(entry));\n+\t\thashmap_add(&list->seen, &entry->ent);\n \t}\n-\tentry->next = list->head;\n \n+\tentry->next = list->head;\n \tlist->head = entry;\n \tif (!list->tail)\n \t\tlist->tail = entry;\n@@ -61,13 +110,18 @@ void packfile_list_append(struct packfile_list *list, struct packed_git *pack)\n {\n \tstruct packfile_list_entry *entry;\n \n-\tentry = packfile_list_remove_internal(list, pack);\n-\tif (!entry) {\n+\tif (packfile_list_lookup(list, pack)) {\n+\t\tentry = packfile_list_remove_internal(list, pack);\n+\t\tif (!entry)\n+\t\t\tBUG(\"corrupt packfile list\");\n+\t} else {\n \t\tentry = xmalloc(sizeof(*entry));\n \t\tentry->pack = pack;\n+\t\thashmap_entry_init(&entry->ent, packfile_list_entry_hash(entry));\n+\t\thashmap_add(&list->seen, &entry->ent);\n \t}\n-\tentry->next = NULL;\n \n+\tentry->next = NULL;\n \tif (list->tail) {\n \t\tlist->tail->next = entry;\n \t\tlist->tail = entry;\ndiff --git a/packfile-list.h b/packfile-list.h\nindex 1b05e2aa36..bfb7017852 100644\n--- a/packfile-list.h\n+++ b/packfile-list.h\n@@ -1,17 +1,22 @@\n #ifndef PACKFILE_LIST_H\n #define PACKFILE_LIST_H\n \n+#include \"hashmap.h\"\n+\n struct object_id;\n \n struct packfile_list {\n \tstruct packfile_list_entry *head, *tail;\n+\tstruct hashmap seen;\n };\n \n struct packfile_list_entry {\n+\tstruct hashmap_entry ent;\n \tstruct packfile_list_entry *next;\n \tstruct packed_git *pack;\n };\n \n+void packfile_list_init(struct packfile_list *list);\n void packfile_list_clear(struct packfile_list *list);\n void packfile_list_remove(struct packfile_list *list, struct packed_git *pack);\n void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack);\n"},{"id":"550475","messageId":"an1z3uy7Xtqw3U_l@pks.im","threadId":"66166","inReplyTo":"20260812212955.GA152730@coredump.intra.peff.net","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-08-13T07:35:58Z","receivedAt":"2026-08-13T07:36:10Z","isPatch":true,"body":"On Wed, Aug 12, 2026 at 05:29:55PM -0400, Jeff King wrote:\n> On Wed, Aug 12, 2026 at 12:51:30PM -0700, Junio C Hamano wrote:\n> \n> > \"Johannes Schindelin via GitGitGadget\" \n> > writes:\n> > \n> > > In one reported use case (https://github.com/microsoft/git/issues/970),\n> > > N equals 37,815 and caused a slow-down of a simple `git rev-parse\n> > > --short HEAD` (which is regularly executed as part of `GIT_PS1`) from\n> > > 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times\n> > > increased from under 2 minutes to over half an hour.\n> > \n> > Face with Rolling Eyes (1f644) 🙄\n> > \n> > As we grow older, more and more extreme use cases that we initially\n> > thought were simply crazy become reality.\n> \n> Sort of. The quadratic adding became a problem long ago, hence\n> ec48540fe8 (packfile.c: speed up loading lots of packfiles, 2019-11-27).\n> \n> So this was something we already dealt with that regressed. We can even\n> see the regression in our perf suite:\n> \n> $ GIT_SKIP_TESTS='p5303.[1-9] p5303.1[0-9]' ./run 589127caa730^ 589127caa730 p5303-many-packs.sh\n> Test 589127caa730^ 589127caa730\n> ----------------------------------------------------------------------\n> 5303.21: load 10,000 packs 0.13(0.11+0.02) 0.45(0.42+0.02) +246.2%\n> \n> Unfortunately I don't think anybody pays close attention to the perf\n> suite (partially because it's clunky and expensive to run, but also\n> because it often requires human judgement to decide when something is a\n> real change and not just a blip).\n\nYeah, that's a problem indeed. At GitLab we do have Bencher set up for\ncontinuous benchmarking [1], but due to recent changes to our CI setup\nthose are now very flaky because seemingly, we flip-flop between two\ndifferent runners that have different specs. But we're obviously missing\na test there with lots of packfiles, so we didn't catch this regression.\n\nThanks!\n\nPatrick\n\n[1]: https://bencher.dev/perf/git/plots\n"},{"id":"550480","messageId":"ed5c651f-648f-f58c-bbd3-3db295515913@gmx.de","threadId":"66166","inReplyTo":"20260812212955.GA152730@coredump.intra.peff.net","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2026-08-13T08:25:25Z","receivedAt":"2026-08-13T08:25:33Z","isPatch":true,"body":"Hi Jeff,\n\nOn Wed, 12 Aug 2026, Jeff King wrote:\n\n> On Wed, Aug 12, 2026 at 12:51:30PM -0700, Junio C Hamano wrote:\n> \n> > \"Johannes Schindelin via GitGitGadget\" \n> > writes:\n> [...]\n> but...\n> \n> > > --- a/t/perf/p5303-many-packs.sh\n> > > +++ b/t/perf/p5303-many-packs.sh\n> > > @@ -141,4 +141,8 @@ test_perf \"load 10,000 packs\" '\n> > > \tgit rev-parse --verify \"HEAD^{commit}\"\n> > > '\n> > > \n> > > +test_perf \"abbreviate with 10,000 packs\" '\n> > > +\tgit rev-parse --short HEAD\n> > > +'\n> \n> ...I wonder what value this is adding. It shows the same slowdown as the\n> existing test you can see in the context (and whose results I showed\n> above).\n\nI do think that there is value in adding this. It not only directly\nreflects what GIT_PS1 runs, but it also exercises a subtly different path:\n`--short` has to look for the unique abbreviation, whereas `--verify` can\nstop as soon as it found the OID already.\n\nCiao,\nJohannes\n"},{"id":"550481","messageId":"14489f51-fa34-a354-47a5-be64da968835@gmx.de","threadId":"66166","inReplyTo":"xmqqfr0jw20t.fsf@gitster.g","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2026-08-13T08:26:40Z","receivedAt":"2026-08-13T08:26:48Z","isPatch":true,"body":"Hi Junio,\n\nOn Wed, 12 Aug 2026, Junio C Hamano wrote:\n\n> \"Johannes Schindelin via GitGitGadget\" \n> writes:\n> \n> > In one reported use case (https://github.com/microsoft/git/issues/970),\n> > N equals 37,815 and caused a slow-down of a simple `git rev-parse\n> > --short HEAD` (which is regularly executed as part of `GIT_PS1`) from\n> > 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times\n> > increased from under 2 minutes to over half an hour.\n> \n> Face with Rolling Eyes (1f644) 🙄\n> \n> As we grow older, more and more extreme use cases that we initially\n> thought were simply crazy become reality.\n\nI have to take back the claim about the clone time, the hunt for that CI\nregression is still ongoing, and this patch does _not_ fix it.\n\nCiao,\nJohannes\n\n> \n> > Let's fix this by establishing a fast path for known-new packfiles.\n> \n> As long as the caller reliably knows that the pack it has is new and\n> cannot be on the list, there is no reason to cycle through all the\n> packs in the ring to attempt removing it in vain.\n> \n> Clever and clean.\n> \n> > diff --git a/packfile.c b/packfile.c\n> > index 0eee45055f..f80f05a1fe 100644\n> > --- a/packfile.c\n> > +++ b/packfile.c\n> > @@ -781,7 +781,7 @@ void packfile_store_add_pack(struct odb_source_packed *store,\n> > \tif (pack->pack_fd != -1)\n> > \t\tpack_open_fds++;\n> > \n> > -\tpackfile_list_append(&store->packs, pack);\n> > +\tpackfile_list_append(&store->packs, pack, 1);\n> > \tstrmap_put(&store->packs_by_path, pack->pack_name, pack);\n> > }\n> > \n> > diff --git a/t/perf/p5303-many-packs.sh b/t/perf/p5303-many-packs.sh\n> > index af173a7b73..4221f9dd70 100755\n> > --- a/t/perf/p5303-many-packs.sh\n> > +++ b/t/perf/p5303-many-packs.sh\n> > @@ -141,4 +141,8 @@ test_perf \"load 10,000 packs\" '\n> > \tgit rev-parse --verify \"HEAD^{commit}\"\n> > '\n> > \n> > +test_perf \"abbreviate with 10,000 packs\" '\n> > +\tgit rev-parse --short HEAD\n> > +'\n> > +\n> > test_done\n> >\n> > base-commit: 11c6700f10234578d10523faf35656ca491425c9\n> \n"},{"id":"550487","messageId":"704409ee-0319-7493-cdc9-8cdb0fea1ace@gmx.de","threadId":"66166","inReplyTo":"6EA76E66-E80C-4F19-8806-FAE8294ACFB7@gmail.com","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2026-08-13T09:04:46Z","receivedAt":"2026-08-13T09:04:52Z","isPatch":true,"body":"Hi Ben,\n\nOn Wed, 12 Aug 2026, Ben Knoble wrote:\n\n> > Le 12 août 2026 à 15:15, Johannes Schindelin via GitGitGadget\n> > a écrit :\n> > \n> > [...]\n> > packfile: fix perf regression with many packs\n> > \n> > This issue was spotted by a Microsoft Git user with the massive\n> > amount of packfiles typical of an average, long-running monorepo\n> > checkout.\n> \n> As a different kind of intermediate solution, would turning on\n> maintenance for that user’s checkout help? (Not sure that would help CI\n> clone times unless the server repacks, of course.)\n\nI should have clarified that the issue is a _Scalar_ clone. And\nspecifically a _Microsoft Git Scalar_ clone.\n\nThis matters because, for various reasons that I don't want to elaborate\non because today I'm in need of lifting up my mood, a substantial part of\nMicrosoft Git failed to get upstreamed to core Git.\n\nOne of these is the \"shared cache repository\", i.e. a bare repository that\nis established as an alternate of the actual clone, and into which the\nactual scheduled fetches go. For full details, see\nhttps://github.com/microsoft/git/commit/55226d12ed36 (scalar: do\ninitialize `gvfs.sharedCache`, 2021-05-03).\n\nNow, maintenance _does_ run, usually, on that shared cache repository\n(being careful not to inadvertently drop objects merely because they're\nunreachable within the shared cache repository). So theoretically, you're\nright that maintenance should help this issue.\n\nFor reasons (which I don't have the time to find out, but I suspect that\nmaintenance simply takes too long and does not finish by the time the\nmachine is shut down for the day), it is still not exactly rare to find\nsetups with five-digit packfile counts. And since we _can_ handle this\nmore gracefully, we should ;-)\n\nCiao,\nJohannes\n"},{"id":"550488","messageId":"b4860540-6114-2a7b-e266-d1fc2f0041b9@gmx.de","threadId":"66166","inReplyTo":"an1zz02GNqDu-0Oz@pks.im","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2026-08-13T09:20:11Z","receivedAt":"2026-08-13T09:20:17Z","isPatch":true,"body":"Hi Patrick,\n\nOn Thu, 13 Aug 2026, Patrick Steinhardt wrote:\n\n> On Wed, Aug 12, 2026 at 07:11:09PM +0000, Johannes Schindelin via GitGitGadget wrote:\n> > From: Johannes Schindelin \n> > \n> > Since 589127caa730 (packfile: move list of packs into the packfile\n> > store, 2025-10-30), there is a performance regression when many\n> > packfiles need to be loaded: `packfile_store_add_pack()` now calls\n> > `packfile_list_remove_internal()` to detect whether the packfile was\n> > _already_ in the list, if if so, move it to the end of the list. This\n> \n> Nit: s/if if/and if/\n\nThanks, will fix, along with dropping the claim that the CI clone was\nfixed by this patch.\n\n> \n> > function linearly scans the existing list before every insertion. Newly\n> > loading N packs therefore has complexity O(N²).\n> > \n> > In one reported use case (https://github.com/microsoft/git/issues/970),\n> > N equals 37,815 and caused a slow-down of a simple `git rev-parse\n> > --short HEAD` (which is regularly executed as part of `GIT_PS1`) from\n> > 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times\n> > increased from under 2 minutes to over half an hour.\n> \n> Wow, 38k packfiles is a lot.\n\nYes.\n\n> > Let's fix this by establishing a fast path for known-new packfiles.\n> > \n> > The keen reader will note that there is currently only a single,\n> > \"known-new\" caller of the `packfile_list_append()` function, and wonder\n> > why not simply remove this check whether the packfile already exists in\n> > the list? Originally, when above-mentioned commit introduced that logic,\n> > there was a second caller in `prepare_midx()`, which would have required\n> > that check, but that caller was removed in 6aff1f25a046 (packfile:\n> > always add packfiles to MRU when adding a pack, 2025-10-30). Still, the\n> > function is declared in a header file, and to avoid any problems with\n> > in-flight or downstream callers, it is safer to extend the signature to\n> > be explicit whether or not to skip that check.\n> \n> Quite conservative, but fair enough.\n> \n> > diff --git a/packfile-list.c b/packfile-list.c\n> > index 01fb913abf..1379ab3a4f 100644\n> > --- a/packfile-list.c\n> > +++ b/packfile-list.c\n> > @@ -57,11 +57,12 @@ void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack)\n> > \t\tlist->tail = entry;\n> > }\n> > \n> > -void packfile_list_append(struct packfile_list *list, struct packed_git *pack)\n> > +void packfile_list_append(struct packfile_list *list, struct packed_git *pack,\n> > +\t\t\t int is_new)\n> > {\n> > \tstruct packfile_list_entry *entry;\n> > \n> > -\tentry = packfile_list_remove_internal(list, pack);\n> > +\tentry = is_new ? NULL : packfile_list_remove_internal(list, pack);\n> > \tif (!entry) {\n> > \t\tentry = xmalloc(sizeof(*entry));\n> > \t\tentry->pack = pack;\n> \n> I wonder whether we should slightly reformulate this and rename `is_new`\n> to `accept_duplicates`. Because ultimately, that is what we're doing\n> now: instead of ensuring that the packfile is unique in the list, we\n> just don't care and just append the entry to the list.\n\nHmm. I don't quite agree, we're _not_ accepting duplicates. We know that\nthose packfiles _cannot_ be duplicates.\n\n> An alternative would be to use a hashmap here that tracks the packs that\n> have already been added. It has the advantage that it also covers the\n> `prepend()` operation and that callers don't have to be aware of this\n> mechanism at all. Furthermore, moving preexisting entries to the back or\n> front could become O(logn) if the list was doubly-linked. We do this\n> operation quite often to re-sort entries in the list when looking up\n> objects.\n\nIndeed, that was my initial reaction, too. I was well on my way to start\nwriting a hashmap-based fix when the AI assistant pointed out that no\nduplicates could possibly exist yet.\n\n> Overall though I'm not quite sure whether the added complexity would be\n> worth it, see below patch.\n\nWow, you got a lot further than I did! And yes, I agree that we do not\n(yet?) need to deal with the added complexity.\n\nCiao,\nJohannes\n\n> \n> Thanks!\n> \n> Patrick\n> \n> diff --git a/http-push.c b/http-push.c\n> index 94a1fac9ab..52b00e7c95 100644\n> --- a/http-push.c\n> +++ b/http-push.c\n> @@ -1729,6 +1729,7 @@ int cmd_main(int argc, const char **argv)\n> \tconst char *gitdir;\n> \n> \tCALLOC_ARRAY(repo, 1);\n> +\tpackfile_list_init(&repo->packs);\n> \n> \targv++;\n> \tfor (i = 1; i < argc; i++, argv++) {\n> @@ -1992,6 +1993,7 @@ int cmd_main(int argc, const char **argv)\n> cleanup:\n> \tif (info_ref_lock)\n> \t\tunlock_remote(info_ref_lock);\n> +\tpackfile_list_clear(&repo->packs);\n> \tfree(repo->url);\n> \tfree(repo);\n> \n> diff --git a/http-walker.c b/http-walker.c\n> index b58a3b2a92..541437e52d 100644\n> --- a/http-walker.c\n> +++ b/http-walker.c\n> @@ -325,6 +325,7 @@ static void process_alternates_response(void *callback_data)\n> \t\t\t\t\twarning(\"adding alternate object store: %s\",\n> \t\t\t\t\t\ttarget.buf);\n> \t\t\t\t\tCALLOC_ARRAY(newalt, 1);\n> +\t\t\t\t\tpackfile_list_init(&newalt->packs);\n> \t\t\t\t\tnewalt->base = strbuf_detach(&target, NULL);\n> \n> \t\t\t\t\twhile (tail->next != NULL)\n> @@ -609,6 +610,7 @@ struct walker *get_http_walker(const char *url)\n> \tstruct walker *walker = xmalloc(sizeof(struct walker));\n> \n> \tCALLOC_ARRAY(data->alt, 1);\n> +\tpackfile_list_init(&data->alt->packs);\n> \tdata->alt->base = xstrdup(url);\n> \tfor (s = data->alt->base + strlen(data->alt->base) - 1; *s == '/'; --s)\n> \t\t*s = 0;\n> diff --git a/odb/source-packed.c b/odb/source-packed.c\n> index 0890704e76..082c2494cb 100644\n> --- a/odb/source-packed.c\n> +++ b/odb/source-packed.c\n> @@ -835,6 +835,7 @@ struct odb_source_packed *odb_source_packed_new(struct object_database *odb,\n> \n> \tCALLOC_ARRAY(packed, 1);\n> \todb_source_init(&packed->base, odb, ODB_SOURCE_PACKED, path, local);\n> +\tpackfile_list_init(&packed->packs);\n> \tstrmap_init(&packed->packs_by_path);\n> \n> \tpacked->base.free = odb_source_packed_free;\n> diff --git a/packfile-list.c b/packfile-list.c\n> index 01fb913abf..d3c4843d8d 100644\n> --- a/packfile-list.c\n> +++ b/packfile-list.c\n> @@ -2,6 +2,28 @@\n> #include \"packfile.h\"\n> #include \"packfile-list.h\"\n> \n> +static unsigned int packfile_list_entry_hash(struct packfile_list_entry *e)\n> +{\n> +\treturn memhash(&e->pack, sizeof(e->pack));\n> +}\n> +\n> +static int packfile_list_entry_cmp(const void *data UNUSED,\n> +\t\t\t\t const struct hashmap_entry *h1,\n> +\t\t\t\t const struct hashmap_entry *h2,\n> +\t\t\t\t const void *keydata UNUSED)\n> +{\n> +\tconst struct packfile_list_entry *e1, *e2;\n> +\te1 = container_of(h1, const struct packfile_list_entry, ent);\n> +\te2 = container_of(h2, const struct packfile_list_entry, ent);\n> +\treturn e1->pack != e2->pack;\n> +}\n> +\n> +void packfile_list_init(struct packfile_list *list)\n> +{\n> +\tmemset(list, 0, sizeof(*list));\n> +\thashmap_init(&list->seen, packfile_list_entry_cmp, NULL, 0);\n> +}\n> +\n> void packfile_list_clear(struct packfile_list *list)\n> {\n> \tstruct packfile_list_entry *e, *next;\n> @@ -12,6 +34,20 @@ void packfile_list_clear(struct packfile_list *list)\n> \t}\n> \n> \tlist->head = list->tail = NULL;\n> +\n> +\thashmap_clear(&list->seen);\n> +}\n> +\n> +static struct packfile_list_entry *packfile_list_lookup(struct packfile_list *list,\n> +\t\t\t\t\t\t\tstruct packed_git *pack)\n> +{\n> +\tstruct packfile_list_entry key = { .pack = pack };\n> +\tstruct hashmap_entry *ent;\n> +\n> +\thashmap_entry_init(&key.ent, packfile_list_entry_hash(&key));\n> +\tent = hashmap_get(&list->seen, &key.ent, NULL);\n> +\n> +\treturn ent ? container_of(ent, struct packfile_list_entry, ent) : NULL;\n> }\n> \n> static struct packfile_list_entry *packfile_list_remove_internal(struct packfile_list *list,\n> @@ -38,20 +74,33 @@ static struct packfile_list_entry *packfile_list_remove_internal(struct packfile\n> \n> void packfile_list_remove(struct packfile_list *list, struct packed_git *pack)\n> {\n> -\tfree(packfile_list_remove_internal(list, pack));\n> +\tstruct packfile_list_entry key = { .pack = pack };\n> +\n> +\thashmap_entry_init(&key.ent, packfile_list_entry_hash(&key));\n> +\tif (hashmap_remove(&list->seen, &key.ent, NULL)) {\n> +\t\tstruct packfile_list_entry *e = packfile_list_remove_internal(list, pack);\n> +\t\tif (!e)\n> +\t\t\tBUG(\"corrupt packfile list\");\n> +\t\tfree(e);\n> +\t}\n> }\n> \n> void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack)\n> {\n> \tstruct packfile_list_entry *entry;\n> \n> -\tentry = packfile_list_remove_internal(list, pack);\n> -\tif (!entry) {\n> +\tif (packfile_list_lookup(list, pack)) {\n> +\t\tentry = packfile_list_remove_internal(list, pack);\n> +\t\tif (!entry)\n> +\t\t\tBUG(\"corrupt packfile list\");\n> +\t} else {\n> \t\tentry = xmalloc(sizeof(*entry));\n> \t\tentry->pack = pack;\n> +\t\thashmap_entry_init(&entry->ent, packfile_list_entry_hash(entry));\n> +\t\thashmap_add(&list->seen, &entry->ent);\n> \t}\n> -\tentry->next = list->head;\n> \n> +\tentry->next = list->head;\n> \tlist->head = entry;\n> \tif (!list->tail)\n> \t\tlist->tail = entry;\n> @@ -61,13 +110,18 @@ void packfile_list_append(struct packfile_list *list, struct packed_git *pack)\n> {\n> \tstruct packfile_list_entry *entry;\n> \n> -\tentry = packfile_list_remove_internal(list, pack);\n> -\tif (!entry) {\n> +\tif (packfile_list_lookup(list, pack)) {\n> +\t\tentry = packfile_list_remove_internal(list, pack);\n> +\t\tif (!entry)\n> +\t\t\tBUG(\"corrupt packfile list\");\n> +\t} else {\n> \t\tentry = xmalloc(sizeof(*entry));\n> \t\tentry->pack = pack;\n> +\t\thashmap_entry_init(&entry->ent, packfile_list_entry_hash(entry));\n> +\t\thashmap_add(&list->seen, &entry->ent);\n> \t}\n> -\tentry->next = NULL;\n> \n> +\tentry->next = NULL;\n> \tif (list->tail) {\n> \t\tlist->tail->next = entry;\n> \t\tlist->tail = entry;\n> diff --git a/packfile-list.h b/packfile-list.h\n> index 1b05e2aa36..bfb7017852 100644\n> --- a/packfile-list.h\n> +++ b/packfile-list.h\n> @@ -1,17 +1,22 @@\n> #ifndef PACKFILE_LIST_H\n> #define PACKFILE_LIST_H\n> \n> +#include \"hashmap.h\"\n> +\n> struct object_id;\n> \n> struct packfile_list {\n> \tstruct packfile_list_entry *head, *tail;\n> +\tstruct hashmap seen;\n> };\n> \n> struct packfile_list_entry {\n> +\tstruct hashmap_entry ent;\n> \tstruct packfile_list_entry *next;\n> \tstruct packed_git *pack;\n> };\n> \n> +void packfile_list_init(struct packfile_list *list);\n> void packfile_list_clear(struct packfile_list *list);\n> void packfile_list_remove(struct packfile_list *list, struct packed_git *pack);\n> void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack);\n> \n"},{"id":"550493","messageId":"an2V7S-DkdypsGIE@pks.im","threadId":"66166","inReplyTo":"b4860540-6114-2a7b-e266-d1fc2f0041b9@gmx.de","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-08-13T10:01:17Z","receivedAt":"2026-08-13T10:01:25Z","isPatch":true,"body":"On Thu, Aug 13, 2026 at 11:20:11AM +0200, Johannes Schindelin wrote:\n> On Thu, 13 Aug 2026, Patrick Steinhardt wrote:\n> > I wonder whether we should slightly reformulate this and rename `is_new`\n> > to `accept_duplicates`. Because ultimately, that is what we're doing\n> > now: instead of ensuring that the packfile is unique in the list, we\n> > just don't care and just append the entry to the list.\n> \n> Hmm. I don't quite agree, we're _not_ accepting duplicates. We know that\n> those packfiles _cannot_ be duplicates.\n\nI know that we're not, but this is only because the caller knows that\nthe packs are new. Seen outside that context though the new parameter\nreally just tells us whether or not we want to deduplicate packs or not.\n\nAnyway, I'm splitting hairs and I won't insist on a change here.\n\n> > An alternative would be to use a hashmap here that tracks the packs that\n> > have already been added. It has the advantage that it also covers the\n> > `prepend()` operation and that callers don't have to be aware of this\n> > mechanism at all. Furthermore, moving preexisting entries to the back or\n> > front could become O(logn) if the list was doubly-linked. We do this\n> > operation quite often to re-sort entries in the list when looking up\n> > objects.\n> \n> Indeed, that was my initial reaction, too. I was well on my way to start\n> writing a hashmap-based fix when the AI assistant pointed out that no\n> duplicates could possibly exist yet.\n> \n> > Overall though I'm not quite sure whether the added complexity would be\n> > worth it, see below patch.\n> \n> Wow, you got a lot further than I did! And yes, I agree that we do not\n> (yet?) need to deal with the added complexity.\n\nI may want to pursue this patch anyway, as I think that the reordering\nwould be sped up by that change quite signifcantly. And that would make\na difference indeed when you have 38k packfiles, at least when you\nassume that objects are evenly distributed across all of those and that\nwe perform reads of random objects.\n\nI could do that tomorrow, and in that case it'd supersede your patch.\nBut I'm also happy to have this improvement here land first and then\nI'll pursue this change eventually.\n\nThanks!\n\nPatrick\n"},{"id":"550495","messageId":"07585246-48cf-2d70-b022-8cb430fe82fb@gmx.de","threadId":"66166","inReplyTo":"an2V7S-DkdypsGIE@pks.im","subject":"Re: [PATCH] packfile: fix perf regression with many packsy","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2026-08-13T10:42:10Z","receivedAt":"2026-08-13T10:42:15Z","isPatch":true,"body":"Hi Patrick,\n\nOn Thu, 13 Aug 2026, Patrick Steinhardt wrote:\n\n> On Thu, Aug 13, 2026 at 11:20:11AM +0200, Johannes Schindelin wrote:\n> > On Thu, 13 Aug 2026, Patrick Steinhardt wrote:\n> > > I wonder whether we should slightly reformulate this and rename `is_new`\n> > > to `accept_duplicates`. Because ultimately, that is what we're doing\n> > > now: instead of ensuring that the packfile is unique in the list, we\n> > > just don't care and just append the entry to the list.\n> > \n> > Hmm. I don't quite agree, we're _not_ accepting duplicates. We know that\n> > those packfiles _cannot_ be duplicates.\n> \n> I know that we're not, but this is only because the caller knows that\n> the packs are new. Seen outside that context though the new parameter\n> really just tells us whether or not we want to deduplicate packs or not.\n> \n> Anyway, I'm splitting hairs and I won't insist on a change here.\n\nYou do have a point, though, `is_new` is too narrow. How about\n`skip_dup_check`?\n\n> > > An alternative would be to use a hashmap here that tracks the packs that\n> > > have already been added. It has the advantage that it also covers the\n> > > `prepend()` operation and that callers don't have to be aware of this\n> > > mechanism at all. Furthermore, moving preexisting entries to the back or\n> > > front could become O(logn) if the list was doubly-linked. We do this\n> > > operation quite often to re-sort entries in the list when looking up\n> > > objects.\n> > \n> > Indeed, that was my initial reaction, too. I was well on my way to start\n> > writing a hashmap-based fix when the AI assistant pointed out that no\n> > duplicates could possibly exist yet.\n> > \n> > > Overall though I'm not quite sure whether the added complexity would be\n> > > worth it, see below patch.\n> > \n> > Wow, you got a lot further than I did! And yes, I agree that we do not\n> > (yet?) need to deal with the added complexity.\n> \n> I may want to pursue this patch anyway, as I think that the reordering\n> would be sped up by that change quite signifcantly. And that would make\n> a difference indeed when you have 38k packfiles, at least when you\n> assume that objects are evenly distributed across all of those and that\n> we perform reads of random objects.\n> \n> I could do that tomorrow, and in that case it'd supersede your patch.\n\nI don't think that it would _quite_ supersede this patch. Sure, while\nsearching through a hashset instead of a single-linked list is faster, it\nis not as fast as skipping the search altogether.\n\nCiao,\nJohannes\n\n> But I'm also happy to have this improvement here land first and then\n> I'll pursue this change eventually.\n> \n> Thanks!\n> \n> Patrick\n> \n"},{"id":"550496","messageId":"an2mrUb9DI6Jbj6y@pks.im","threadId":"66166","inReplyTo":"07585246-48cf-2d70-b022-8cb430fe82fb@gmx.de","subject":"Re: [PATCH] packfile: fix perf regression with many packsy","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-08-13T11:12:45Z","receivedAt":"2026-08-13T11:12:54Z","isPatch":true,"body":"On Thu, Aug 13, 2026 at 12:42:10PM +0200, Johannes Schindelin wrote:\n> Hi Patrick,\n> \n> On Thu, 13 Aug 2026, Patrick Steinhardt wrote:\n> \n> > On Thu, Aug 13, 2026 at 11:20:11AM +0200, Johannes Schindelin wrote:\n> > > On Thu, 13 Aug 2026, Patrick Steinhardt wrote:\n> > > > I wonder whether we should slightly reformulate this and rename `is_new`\n> > > > to `accept_duplicates`. Because ultimately, that is what we're doing\n> > > > now: instead of ensuring that the packfile is unique in the list, we\n> > > > just don't care and just append the entry to the list.\n> > > \n> > > Hmm. I don't quite agree, we're _not_ accepting duplicates. We know that\n> > > those packfiles _cannot_ be duplicates.\n> > \n> > I know that we're not, but this is only because the caller knows that\n> > the packs are new. Seen outside that context though the new parameter\n> > really just tells us whether or not we want to deduplicate packs or not.\n> > \n> > Anyway, I'm splitting hairs and I won't insist on a change here.\n> \n> You do have a point, though, `is_new` is too narrow. How about\n> `skip_dup_check`?\n\nSounds reasonable.\n\n> > > > An alternative would be to use a hashmap here that tracks the packs that\n> > > > have already been added. It has the advantage that it also covers the\n> > > > `prepend()` operation and that callers don't have to be aware of this\n> > > > mechanism at all. Furthermore, moving preexisting entries to the back or\n> > > > front could become O(logn) if the list was doubly-linked. We do this\n> > > > operation quite often to re-sort entries in the list when looking up\n> > > > objects.\n> > > \n> > > Indeed, that was my initial reaction, too. I was well on my way to start\n> > > writing a hashmap-based fix when the AI assistant pointed out that no\n> > > duplicates could possibly exist yet.\n> > > \n> > > > Overall though I'm not quite sure whether the added complexity would be\n> > > > worth it, see below patch.\n> > > \n> > > Wow, you got a lot further than I did! And yes, I agree that we do not\n> > > (yet?) need to deal with the added complexity.\n> > \n> > I may want to pursue this patch anyway, as I think that the reordering\n> > would be sped up by that change quite signifcantly. And that would make\n> > a difference indeed when you have 38k packfiles, at least when you\n> > assume that objects are evenly distributed across all of those and that\n> > we perform reads of random objects.\n> > \n> > I could do that tomorrow, and in that case it'd supersede your patch.\n> \n> I don't think that it would _quite_ supersede this patch. Sure, while\n> searching through a hashset instead of a single-linked list is faster, it\n> is not as fast as skipping the search altogether.\n\nI guess that's fair. Let's move forward with your patch for now then.\n\nThanks!\n\nPatrick\n"},{"id":"550498","messageId":"2CE87145-D86E-47DF-8761-8FBCFB774C51@gmail.com","threadId":"66166","inReplyTo":"704409ee-0319-7493-cdc9-8cdb0fea1ace@gmx.de","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Ben Knoble","fromEmail":"ben.knoble@gmail.com","sentAt":"2026-08-13T11:18:48Z","receivedAt":"2026-08-13T11:19:01Z","isPatch":true,"body":"\n\n> Le 13 août 2026 à 05:04, Johannes Schindelin a écrit :\n> \n> Hi Ben,\n> \n> On Wed, 12 Aug 2026, Ben Knoble wrote:\n> \n>>> Le 12 août 2026 à 15:15, Johannes Schindelin via GitGitGadget\n>>> a écrit :\n>>> \n>>> [...]\n>>> packfile: fix perf regression with many packs\n>>> \n>>> This issue was spotted by a Microsoft Git user with the massive\n>>> amount of packfiles typical of an average, long-running monorepo\n>>> checkout.\n>> \n>> As a different kind of intermediate solution, would turning on\n>> maintenance for that user’s checkout help? (Not sure that would help CI\n>> clone times unless the server repacks, of course.)\n> \n> I should have clarified that the issue is a _Scalar_ clone. And\n> specifically a _Microsoft Git Scalar_ clone.\n> \n> This matters because, for various reasons that I don't want to elaborate\n> on because today I'm in need of lifting up my mood, a substantial part of\n> Microsoft Git failed to get upstreamed to core Git.\n> \n> One of these is the \"shared cache repository\", i.e. a bare repository that\n> is established as an alternate of the actual clone, and into which the\n> actual scheduled fetches go. For full details, see\n> https://github.com/microsoft/git/commit/55226d12ed36 (scalar: do\n> initialize `gvfs.sharedCache`, 2021-05-03).\n> \n> Now, maintenance _does_ run, usually, on that shared cache repository\n> (being careful not to inadvertently drop objects merely because they're\n> unreachable within the shared cache repository). So theoretically, you're\n> right that maintenance should help this issue.\n> \n> For reasons (which I don't have the time to find out, but I suspect that\n> maintenance simply takes too long and does not finish by the time the\n> machine is shut down for the day), it is still not exactly rare to find\n> setups with five-digit packfile counts. And since we _can_ handle this\n> more gracefully, we should ;-)\n> \n> Ciao,\n> Johannes\n\nThanks, very informative!\n\nWhat I actually meant, sorry if I wasn’t clear, is that maintenance seems likely to help the local (à la PS1) case more than the clone. But maybe it will suffer from the same « takes too long » problem, idk."},{"id":"550506","messageId":"xmqq33wiunz5.fsf@gitster.g","threadId":"66166","inReplyTo":"an1zz02GNqDu-0Oz@pks.im","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-08-13T13:52:30Z","receivedAt":"2026-08-13T13:52:34Z","isPatch":true,"body":"Patrick Steinhardt writes:\n\n>> -void packfile_list_append(struct packfile_list *list, struct packed_git *pack)\n>> +void packfile_list_append(struct packfile_list *list, struct packed_git *pack,\n>> +\t\t\t int is_new)\n>> {\n>> \tstruct packfile_list_entry *entry;\n>> \n>> -\tentry = packfile_list_remove_internal(list, pack);\n>> +\tentry = is_new ? NULL : packfile_list_remove_internal(list, pack);\n>> \tif (!entry) {\n>> \t\tentry = xmalloc(sizeof(*entry));\n>> \t\tentry->pack = pack;\n>\n> I wonder whether we should slightly reformulate this and rename `is_new`\n> to `accept_duplicates`. Because ultimately, that is what we're doing\n> now: instead of ensuring that the packfile is unique in the list, we\n> just don't care and just append the entry to the list.\n\nI had the same thought. The current callers might have been vetted\nthoroughly, but the next caller might not be so careful, and for\nthat matter, the code paths to reach current caller may change in\nthe future to break the promise of ever throwing a new pack at\npackfile_list.\n\nIs it well understood what bad things it will lead to to have\nduplicated entries on a packfile_list (other than it would make it\neven less efficient to prove the non-existence of a pack on it, and\npossibly a bit more efficient, depending on where duplicates are, to\nprove the existence of a pack on it?)\n\n"},{"id":"550525","messageId":"pull.2202.v2.git.1786633010179.gitgitgadget@gmail.com","threadId":"66166","inReplyTo":"pull.2202.git.1786561870638.gitgitgadget@gmail.com","subject":"[PATCH v2] packfile: fix perf regression with many packs","fromName":"Johannes Schindelin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-08-13T14:56:49Z","receivedAt":"2026-08-13T14:56:52Z","isPatch":true,"body":"From: Johannes Schindelin \n\nSince 589127caa730 (packfile: move list of packs into the packfile\nstore, 2025-10-30), there is a performance regression when many\npackfiles need to be loaded: `packfile_store_add_pack()` now calls\n`packfile_list_remove_internal()` to detect whether the packfile was\n_already_ in the list, and if so, move it to the end of the list. This\nfunction linearly scans the existing list before every insertion. Newly\nloading N packs therefore has complexity O(N²).\n\nIn one reported use case (https://github.com/microsoft/git/issues/970),\nN equals 37,815 and caused a slow-down of a simple `git rev-parse\n--short HEAD` (which is regularly executed as part of `GIT_PS1`) from\n0.4s to 4.5s.\n\nLet's fix this by establishing a fast path for known-new packfiles.\n\nThe keen reader will note that there is currently only a single,\n\"known-new\" caller of the `packfile_list_append()` function, and wonder\nwhy not simply remove this check whether the packfile already exists in\nthe list? Originally, when above-mentioned commit introduced that logic,\nthere was a second caller in `prepare_midx()`, which would have required\nthat check, but that caller was removed in 6aff1f25a046 (packfile:\nalways add packfiles to MRU when adding a pack, 2025-10-30). Still, the\nfunction is declared in a header file, and to avoid any problems with\nin-flight or downstream callers, it is safer to extend the signature to\nbe explicit whether or not to skip that check.\n\nSigned-off-by: Johannes Schindelin \n---\n packfile: fix perf regression with many packs\n \n This issue was spotted by a Microsoft Git user with the massive amount\n of packfiles typical of an average, long-running monorepo checkout.\n \n Changes since v1:\n \n * Fixed a typo in the commit message\n * Dropped the claim that this patch fixes the CI clone perf regression\n that's still being root-caused.\n * Renamed the is_new parameter to the more informative skip_dup_check.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2202%2Fdscho%2Ffix-perf-regression-in-v2.53-with-many-packfiles-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2202/dscho/fix-perf-regression-in-v2.53-with-many-packfiles-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/2202\n\nRange-diff vs v1:\n\n 1: 3dfb305e58 ! 1: b892964f7e packfile: fix perf regression with many packs\n @@ Commit message\n store, 2025-10-30), there is a performance regression when many\n packfiles need to be loaded: `packfile_store_add_pack()` now calls\n `packfile_list_remove_internal()` to detect whether the packfile was\n - _already_ in the list, if if so, move it to the end of the list. This\n + _already_ in the list, and if so, move it to the end of the list. This\n function linearly scans the existing list before every insertion. Newly\n loading N packs therefore has complexity O(N²).\n \n In one reported use case (https://github.com/microsoft/git/issues/970),\n N equals 37,815 and caused a slow-down of a simple `git rev-parse\n --short HEAD` (which is regularly executed as part of `GIT_PS1`) from\n - 0.4s to 4.5s. In another, heavily exercised CI scenario, clone times\n - increased from under 2 minutes to over half an hour.\n + 0.4s to 4.5s.\n \n Let's fix this by establishing a fast path for known-new packfiles.\n \n @@ packfile-list.c: void packfile_list_prepend(struct packfile_list *list, struct p\n \n -void packfile_list_append(struct packfile_list *list, struct packed_git *pack)\n +void packfile_list_append(struct packfile_list *list, struct packed_git *pack,\n -+\t\t\t int is_new)\n ++\t\t\t int skip_dup_check)\n {\n \tstruct packfile_list_entry *entry;\n \n -\tentry = packfile_list_remove_internal(list, pack);\n -+\tentry = is_new ? NULL : packfile_list_remove_internal(list, pack);\n ++\tentry = skip_dup_check ? NULL : packfile_list_remove_internal(list, pack);\n \tif (!entry) {\n \t\tentry = xmalloc(sizeof(*entry));\n \t\tentry->pack = pack;\n @@ packfile-list.h: struct packfile_list_entry {\n void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack);\n -void packfile_list_append(struct packfile_list *list, struct packed_git *pack);\n +void packfile_list_append(struct packfile_list *list, struct packed_git *pack,\n -+\t\t\t int is_new);\n ++\t\t\t int skip_dup_check);\n \n /*\n * Find the pack within the \"packs\" list whose index contains the object\n\n\n packfile-list.c | 5 +++--\n packfile-list.h | 3 ++-\n packfile.c | 2 +-\n t/perf/p5303-many-packs.sh | 4 ++++\n 4 files changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/packfile-list.c b/packfile-list.c\nindex 01fb913abf..d6d411823c 100644\n--- a/packfile-list.c\n+++ b/packfile-list.c\n@@ -57,11 +57,12 @@ void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack)\n \t\tlist->tail = entry;\n }\n \n-void packfile_list_append(struct packfile_list *list, struct packed_git *pack)\n+void packfile_list_append(struct packfile_list *list, struct packed_git *pack,\n+\t\t\t int skip_dup_check)\n {\n \tstruct packfile_list_entry *entry;\n \n-\tentry = packfile_list_remove_internal(list, pack);\n+\tentry = skip_dup_check ? NULL : packfile_list_remove_internal(list, pack);\n \tif (!entry) {\n \t\tentry = xmalloc(sizeof(*entry));\n \t\tentry->pack = pack;\ndiff --git a/packfile-list.h b/packfile-list.h\nindex 1b05e2aa36..2b4b98b226 100644\n--- a/packfile-list.h\n+++ b/packfile-list.h\n@@ -15,7 +15,8 @@ struct packfile_list_entry {\n void packfile_list_clear(struct packfile_list *list);\n void packfile_list_remove(struct packfile_list *list, struct packed_git *pack);\n void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack);\n-void packfile_list_append(struct packfile_list *list, struct packed_git *pack);\n+void packfile_list_append(struct packfile_list *list, struct packed_git *pack,\n+\t\t\t int skip_dup_check);\n \n /*\n * Find the pack within the \"packs\" list whose index contains the object\ndiff --git a/packfile.c b/packfile.c\nindex 0eee45055f..f80f05a1fe 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -781,7 +781,7 @@ void packfile_store_add_pack(struct odb_source_packed *store,\n \tif (pack->pack_fd != -1)\n \t\tpack_open_fds++;\n \n-\tpackfile_list_append(&store->packs, pack);\n+\tpackfile_list_append(&store->packs, pack, 1);\n \tstrmap_put(&store->packs_by_path, pack->pack_name, pack);\n }\n \ndiff --git a/t/perf/p5303-many-packs.sh b/t/perf/p5303-many-packs.sh\nindex af173a7b73..4221f9dd70 100755\n--- a/t/perf/p5303-many-packs.sh\n+++ b/t/perf/p5303-many-packs.sh\n@@ -141,4 +141,8 @@ test_perf \"load 10,000 packs\" '\n \tgit rev-parse --verify \"HEAD^{commit}\"\n '\n \n+test_perf \"abbreviate with 10,000 packs\" '\n+\tgit rev-parse --short HEAD\n+'\n+\n test_done\n\nbase-commit: 11c6700f10234578d10523faf35656ca491425c9\n-- \ngitgitgadget\n"},{"id":"550534","messageId":"20260813161036.GA1386479@coredump.intra.peff.net","threadId":"66166","inReplyTo":"ed5c651f-648f-f58c-bbd3-3db295515913@gmx.de","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-08-13T16:10:36Z","receivedAt":"2026-08-13T16:10:41Z","isPatch":true,"body":"On Thu, Aug 13, 2026 at 10:25:25AM +0200, Johannes Schindelin wrote:\n\n> > > > +test_perf \"abbreviate with 10,000 packs\" '\n> > > > +\tgit rev-parse --short HEAD\n> > > > +'\n> > \n> > ...I wonder what value this is adding. It shows the same slowdown as the\n> > existing test you can see in the context (and whose results I showed\n> > above).\n> \n> I do think that there is value in adding this. It not only directly\n> reflects what GIT_PS1 runs, but it also exercises a subtly different path:\n> `--short` has to look for the unique abbreviation, whereas `--verify` can\n> stop as soon as it found the OID already.\n\nYes, though the regression your patch fixes is about creating the\ninitial pack list, so it happens whether we open each pack or not.\n\nWe do test multiple cases earlier in the file where we look at each\nobject (both a stock rev-list, and one where we abbreviate, looking for\nperf problems in the shortening code itself). But we only do that for\n1/50/1000 packs, not the big 10,000 pack case.\n\nI dunno. It probably is not hurting much to have some redundancy in the\ntests because this one in particular is not too expensive to run. So I\nam OK either way.\n\n-Peff\n"},{"id":"550535","messageId":"20260813161525.GB1386479@coredump.intra.peff.net","threadId":"66166","inReplyTo":"an1zz02GNqDu-0Oz@pks.im","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-08-13T16:15:25Z","receivedAt":"2026-08-13T16:15:29Z","isPatch":true,"body":"On Thu, Aug 13, 2026 at 09:35:49AM +0200, Patrick Steinhardt wrote:\n\n> An alternative would be to use a hashmap here that tracks the packs that\n> have already been added. It has the advantage that it also covers the\n> `prepend()` operation and that callers don't have to be aware of this\n> mechanism at all. Furthermore, moving preexisting entries to the back or\n> front could become O(logn) if the list was doubly-linked. We do this\n> operation quite often to re-sort entries in the list when looking up\n> objects.\n\nDon't we already use such a hashmap via packfile_store_add_pack() and\npackfile_store_load_pack()? That comes from ec48540fe8 (packfile.c:\nspeed up loading lots of packfiles, 2019-11-27) and is how we know that\nthis \"is_new\" flag is true (otherwise we'd get duplicates during\n\"reprepare\" operations).\n\n-Peff\n"},{"id":"550597","messageId":"an7IhgES-reCzQMr@pks.im","threadId":"66166","inReplyTo":"20260813161525.GB1386479@coredump.intra.peff.net","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-08-14T07:49:26Z","receivedAt":"2026-08-14T07:49:32Z","isPatch":true,"body":"On Thu, Aug 13, 2026 at 12:15:25PM -0400, Jeff King wrote:\n> On Thu, Aug 13, 2026 at 09:35:49AM +0200, Patrick Steinhardt wrote:\n> \n> > An alternative would be to use a hashmap here that tracks the packs that\n> > have already been added. It has the advantage that it also covers the\n> > `prepend()` operation and that callers don't have to be aware of this\n> > mechanism at all. Furthermore, moving preexisting entries to the back or\n> > front could become O(logn) if the list was doubly-linked. We do this\n> > operation quite often to re-sort entries in the list when looking up\n> > objects.\n> \n> Don't we already use such a hashmap via packfile_store_add_pack() and\n> packfile_store_load_pack()? That comes from ec48540fe8 (packfile.c:\n> speed up loading lots of packfiles, 2019-11-27) and is how we know that\n> this \"is_new\" flag is true (otherwise we'd get duplicates during\n> \"reprepare\" operations).\n\nThat's a good point, we indeed do! Maybe it would make sense then to\nremove that map from the packfile store and instead move it into the\npackfile list to make it more generally useful.\n\nPatrick\n"},{"id":"550598","messageId":"an7ItVYrKZFXg2ci@pks.im","threadId":"66166","inReplyTo":"pull.2202.v2.git.1786633010179.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] packfile: fix perf regression with many packs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-08-14T07:50:13Z","receivedAt":"2026-08-14T07:50:20Z","isPatch":true,"body":"On Thu, Aug 13, 2026 at 02:56:49PM +0000, Johannes Schindelin via GitGitGadget wrote:\n> From: Johannes Schindelin \n> Changes since v1:\n> \n> * Fixed a typo in the commit message\n> * Dropped the claim that this patch fixes the CI clone perf regression\n> that's still being root-caused.\n> * Renamed the is_new parameter to the more informative skip_dup_check.\n\nThanks, I'm happy with this version. We can still iterate on the other\npatrs of the discussion after this patch has landed, as needed.\n\nPatrick\n"},{"id":"550618","messageId":"xmqqy0e8pxos.fsf@gitster.g","threadId":"66166","inReplyTo":"an7ItVYrKZFXg2ci@pks.im","subject":"Re: [PATCH v2] packfile: fix perf regression with many packs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-08-14T14:46:11Z","receivedAt":"2026-08-14T14:46:14Z","isPatch":true,"body":"Patrick Steinhardt writes:\n\n> On Thu, Aug 13, 2026 at 02:56:49PM +0000, Johannes Schindelin via GitGitGadget wrote:\n>> From: Johannes Schindelin \n>> Changes since v1:\n>> \n>> * Fixed a typo in the commit message\n>> * Dropped the claim that this patch fixes the CI clone perf regression\n>> that's still being root-caused.\n>> * Renamed the is_new parameter to the more informative skip_dup_check.\n>\n> Thanks, I'm happy with this version. We can still iterate on the other\n> patrs of the discussion after this patch has landed, as needed.\n\nThanks. I do not offhand recall if I said anything on this\niteration, but it looked good to me, too. Let me mark it for\n'next'.\n\n"},{"id":"550624","messageId":"20260814165546.GA2563235@coredump.intra.peff.net","threadId":"66166","inReplyTo":"an7IhgES-reCzQMr@pks.im","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-08-14T16:55:46Z","receivedAt":"2026-08-14T16:55:54Z","isPatch":true,"body":"On Fri, Aug 14, 2026 at 09:49:26AM +0200, Patrick Steinhardt wrote:\n\n> On Thu, Aug 13, 2026 at 12:15:25PM -0400, Jeff King wrote:\n> > On Thu, Aug 13, 2026 at 09:35:49AM +0200, Patrick Steinhardt wrote:\n> > \n> > > An alternative would be to use a hashmap here that tracks the packs that\n> > > have already been added. It has the advantage that it also covers the\n> > > `prepend()` operation and that callers don't have to be aware of this\n> > > mechanism at all. Furthermore, moving preexisting entries to the back or\n> > > front could become O(logn) if the list was doubly-linked. We do this\n> > > operation quite often to re-sort entries in the list when looking up\n> > > objects.\n> > \n> > Don't we already use such a hashmap via packfile_store_add_pack() and\n> > packfile_store_load_pack()? That comes from ec48540fe8 (packfile.c:\n> > speed up loading lots of packfiles, 2019-11-27) and is how we know that\n> > this \"is_new\" flag is true (otherwise we'd get duplicates during\n> > \"reprepare\" operations).\n> \n> That's a good point, we indeed do! Maybe it would make sense then to\n> remove that map from the packfile store and instead move it into the\n> packfile list to make it more generally useful.\n\nThe map protects more than just adding to the list; it avoids all of\nadd_packed_git(), which allocates and does a bunch of stat() calls. So\nit couldn't just be a check in packfile_list_append(), but would have to\nbe a separate existence check well before that.\n\nThat's not impossible, but it would be a lot easier to see what\ngeneralized pattern would be most useful if there were more than one\ncaller of packfile_list_append(). ;)\n\n-Peff\n"},{"id":"550679","messageId":"aoKZvxE8oP5B6O_4@pks.im","threadId":"66166","inReplyTo":"20260814165546.GA2563235@coredump.intra.peff.net","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-08-17T05:18:55Z","receivedAt":"2026-08-17T05:19:01Z","isPatch":true,"body":"On Fri, Aug 14, 2026 at 12:55:46PM -0400, Jeff King wrote:\n> On Fri, Aug 14, 2026 at 09:49:26AM +0200, Patrick Steinhardt wrote:\n> \n> > On Thu, Aug 13, 2026 at 12:15:25PM -0400, Jeff King wrote:\n> > > On Thu, Aug 13, 2026 at 09:35:49AM +0200, Patrick Steinhardt wrote:\n> > > \n> > > > An alternative would be to use a hashmap here that tracks the packs that\n> > > > have already been added. It has the advantage that it also covers the\n> > > > `prepend()` operation and that callers don't have to be aware of this\n> > > > mechanism at all. Furthermore, moving preexisting entries to the back or\n> > > > front could become O(logn) if the list was doubly-linked. We do this\n> > > > operation quite often to re-sort entries in the list when looking up\n> > > > objects.\n> > > \n> > > Don't we already use such a hashmap via packfile_store_add_pack() and\n> > > packfile_store_load_pack()? That comes from ec48540fe8 (packfile.c:\n> > > speed up loading lots of packfiles, 2019-11-27) and is how we know that\n> > > this \"is_new\" flag is true (otherwise we'd get duplicates during\n> > > \"reprepare\" operations).\n> > \n> > That's a good point, we indeed do! Maybe it would make sense then to\n> > remove that map from the packfile store and instead move it into the\n> > packfile list to make it more generally useful.\n> \n> The map protects more than just adding to the list; it avoids all of\n> add_packed_git(), which allocates and does a bunch of stat() calls. So\n> it couldn't just be a check in packfile_list_append(), but would have to\n> be a separate existence check well before that.\n> \n> That's not impossible, but it would be a lot easier to see what\n> generalized pattern would be most useful if there were more than one\n> caller of packfile_list_append(). ;)\n\nWe only have a single caller that appends, but we have some more that\nuse `packfile_list_prepend()`. And there we basically have the same\nproblem.\n\nPatrick\n"},{"id":"550690","messageId":"20260817072113.GA690018@coredump.intra.peff.net","threadId":"66166","inReplyTo":"aoKZvxE8oP5B6O_4@pks.im","subject":"Re: [PATCH] packfile: fix perf regression with many packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-08-17T07:21:13Z","receivedAt":"2026-08-17T07:21:21Z","isPatch":true,"body":"On Mon, Aug 17, 2026 at 07:18:55AM +0200, Patrick Steinhardt wrote:\n\n> > The map protects more than just adding to the list; it avoids all of\n> > add_packed_git(), which allocates and does a bunch of stat() calls. So\n> > it couldn't just be a check in packfile_list_append(), but would have to\n> > be a separate existence check well before that.\n> > \n> > That's not impossible, but it would be a lot easier to see what\n> > generalized pattern would be most useful if there were more than one\n> > caller of packfile_list_append(). ;)\n> \n> We only have a single caller that appends, but we have some more that\n> use `packfile_list_prepend()`. And there we basically have the same\n> problem.\n\nAh, indeed. I see prepend calls sprinkled in some rather hot code paths,\nincluding the MRU adjustment from find_pack_entry(). That is a possible\ncandidate for Dscho's clone slowdown[1].\n\nBut I don't think would not want to pay the cost for a hash de-dup\nthere. We are not adding a new pack at all, but just adjusting the\nplacement, and that should be a quick O(1) if we are using a\ndoubly-linked list.\n\nIt's harder to construct a synthetic test for prepending because of pack\nlocality. If two subsequent requests both try to move pack A to the\nfront of the list, the second prepend()'s removal operation will find\nthe pack at the front in essentially constant time.\n\nBut we can spread the history across packs like this (I recommend\nrunning on a ram disk, otherwise the checkpoint sync() makes it take\nforever):\n\n git init\n for i in $(seq 10000); do\n echo \"commit refs/heads/foo\"\n echo \"committer $i +0000\"\n echo \"data <