packfile: fix perf regression with many packs

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.

packfile.c +1 -1

index 0eee45055f..f80f05a1fe 100644
@@ -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);
 }
 

t/perf/p5303-many-packs.sh +4 -0

index af173a7b73..4221f9dd70 100755
@@ -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

"Johannes Schindelin via GitGitGadget" <[email protected]>

Quoted 5 lines · 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.

t/perf/p5303-many-packs.sh test_perf "load 10,000 packs" ' · line 146

Quoted 9 lines

t/perf/p5303-many-packs.sh +3 -0

@@ -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
+'

Quoted 9 lines · Junio C Hamano

"Johannes Schindelin via GitGitGadget" <[email protected]>

Quoted 5 lines · 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.

Quoted 4 lines

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).

Quoted 2 lines · Junio C Hamano

"Johannes Schindelin via GitGitGadget" <[email protected]> writes:

[...]
but...

Quoted 6 lines

Quoted 6 lines

t/perf/p5303-many-packs.sh +0 -0

@@ -141,4 +141,8 @@ test_perf "load 10,000 packs" '
 	git rev-parse --verify "HEAD^{commit}"
 '
 

Quoted 3 lines

t/perf/p5303-many-packs.sh test_perf "load 10,000 packs" ' · line 146

Quoted 3 lines

t/perf/p5303-many-packs.sh +3 -0

+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).

Quoted 7 lines

Quoted 3 lines

t/perf/p5303-many-packs.sh test_perf "load 10,000 packs" ' · line 146

Quoted 3 lines

t/perf/p5303-many-packs.sh +3 -0

+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).

I do think that there is value in adding this. It not only directly reflects what GIT_PS1 runs, but it also exercises a subtly different path:
--short has to look for the unique abbreviation, whereas --verify can stop as soon as it found the OID already.

"Johannes Schindelin via GitGitGadget" <[email protected]>

Quoted 5 lines · 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.

Quoted 2 lines

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.

Quoted 28 lines

packfile.c +1 -1

index 0eee45055f..f80f05a1fe 100644
@@ -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);
 }
 

t/perf/p5303-many-packs.sh +4 -0

index af173a7b73..4221f9dd70 100755
@@ -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

From: Johannes Schindelin <[email protected]>

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 <[email protected]>

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

Quoted 6 lines

Le 12 août 2026 à 15:15, Johannes Schindelin via GitGitGadget <[email protected]> a écrit :

[...]
packfile: fix perf regression with many packs

Quoted 3 lines

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.)

Hi Ben,

Quoted 6 lines · Ben Knoble

Quoted 6 lines

Le 12 août 2026 à 15:15, Johannes Schindelin via GitGitGadget <[email protected]> a écrit :

[...]
packfile: fix perf regression with many packs

Quoted 7 lines

Quoted 3 lines

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.)

I should have clarified that the issue is a _Scalar_ clone. And specifically a _Microsoft Git Scalar_ clone.

This matters because, for various reasons that I don't want to elaborate on because today I'm in need of lifting up my mood, a substantial part of Microsoft Git failed to get upstreamed to core Git.

One of these is the "shared cache repository", i.e. a bare repository that is established as an alternate of the actual clone, and into which the actual scheduled fetches go. For full details, see
https://github.com/microsoft/git/commit/55226d12ed36 (scalar: do initialize gvfs.sharedCache, 2021-05-03).

Now, maintenance _does_ run, usually, on that shared cache repository (being careful not to inadvertently drop objects merely because they're unreachable within the shared cache repository). So theoretically, you're right that maintenance should help this issue.

For reasons (which I don't have the time to find out, but I suspect that maintenance simply takes too long and does not finish by the time the machine is shut down for the day), it is still not exactly rare to find setups with five-digit packfile counts. And since we _can_ handle this more gracefully, we should ;-)

Ciao,
Johannes

From: Johannes Schindelin <[email protected]>

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.

packfile-list.c +0 -1

index 01fb913abf..1379ab3a4f 100644
@@ -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)

Quoted 7 lines · Johannes Schindelin via GitGitGadget

From: Johannes Schindelin <[email protected]>

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

Nit: s/if if/and if/

Quoted 9 lines

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.

Wow, 38k packfiles is a lot.

Quoted 12 lines

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.

Quite conservative, but fair enough.

Quoted 14 lines

packfile-list.c +2 -1

index 01fb913abf..1379ab3a4f 100644
@@ -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;
 

packfile-list.c static struct packfile_list_entry *packfile_list_remove_internal(struct packfile · line 98

Quoted 5 lines

packfile-list.c +1 -1

-	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;

I wonder whether we should slightly reformulate this and rename is_new to accept_duplicates. Because ultimately, that is what we're doing
now: instead of ensuring that the packfile is unique in the list, we just don't care and just append the entry to the list.

An alternative would be to use a hashmap here that tracks the packs that have already been added. It has the advantage that it also covers the prepend() operation and that callers don't have to be aware of this mechanism at all. Furthermore, moving preexisting entries to the back or front could become O(logn) if the list was doubly-linked. We do this operation quite often to re-sort entries in the list when looking up objects.

Overall though I'm not quite sure whether the added complexity would be worth it, see below patch.

Thanks!

Patrick

http-push.c +2 -0

index 94a1fac9ab..52b00e7c95 100644
@@ -1729,6 +1729,7 @@ int cmd_main(int argc, const char **argv)
 	const char *gitdir;
 
 	CALLOC_ARRAY(repo, 1);
+	packfile_list_init(&repo->packs);
 
 	argv++;
 	for (i = 1; i < argc; i++, argv++) {

@@ -1992,6 +1993,7 @@ int cmd_main(int argc, const char **argv)
  cleanup:
 	if (info_ref_lock)
 		unlock_remote(info_ref_lock);
+	packfile_list_clear(&repo->packs);
 	free(repo->url);
 	free(repo);
 

http-walker.c +2 -0

index b58a3b2a92..541437e52d 100644
@@ -325,6 +325,7 @@ static void process_alternates_response(void *callback_data)
 					warning("adding alternate object store: %s",
 						target.buf);
 					CALLOC_ARRAY(newalt, 1);
+					packfile_list_init(&newalt->packs);
 					newalt->base = strbuf_detach(&target, NULL);
 
 					while (tail->next != NULL)

@@ -609,6 +610,7 @@ struct walker *get_http_walker(const char *url)
 	struct walker *walker = xmalloc(sizeof(struct walker));
 
 	CALLOC_ARRAY(data->alt, 1);
+	packfile_list_init(&data->alt->packs);
 	data->alt->base = xstrdup(url);
 	for (s = data->alt->base + strlen(data->alt->base) - 1; *s == '/'; --s)
 		*s = 0;

odb/source-packed.c +1 -0

index 0890704e76..082c2494cb 100644
@@ -835,6 +835,7 @@ struct odb_source_packed *odb_source_packed_new(struct object_database *odb,
 
 	CALLOC_ARRAY(packed, 1);
 	odb_source_init(&packed->base, odb, ODB_SOURCE_PACKED, path, local);
+	packfile_list_init(&packed->packs);
 	strmap_init(&packed->packs_by_path);
 
 	packed->base.free = odb_source_packed_free;

packfile-list.c +61 -7

index 01fb913abf..d3c4843d8d 100644
@@ -2,6 +2,28 @@
 #include "packfile.h"
 #include "packfile-list.h"
 
+static unsigned int packfile_list_entry_hash(struct packfile_list_entry *e)
+{
+	return memhash(&e->pack, sizeof(e->pack));
+}
+
+static int packfile_list_entry_cmp(const void *data UNUSED,
+				   const struct hashmap_entry *h1,
+				   const struct hashmap_entry *h2,
+				   const void *keydata UNUSED)
+{
+	const struct packfile_list_entry *e1, *e2;
+	e1 = container_of(h1, const struct packfile_list_entry, ent);
+	e2 = container_of(h2, const struct packfile_list_entry, ent);
+	return e1->pack != e2->pack;
+}
+
+void packfile_list_init(struct packfile_list *list)
+{
+	memset(list, 0, sizeof(*list));
+	hashmap_init(&list->seen, packfile_list_entry_cmp, NULL, 0);
+}
+
 void packfile_list_clear(struct packfile_list *list)
 {
 	struct packfile_list_entry *e, *next;

@@ -12,6 +34,20 @@ void packfile_list_clear(struct packfile_list *list)
 	}
 
 	list->head = list->tail = NULL;
+
+	hashmap_clear(&list->seen);
+}
+
+static struct packfile_list_entry *packfile_list_lookup(struct packfile_list *list,
+							struct packed_git *pack)
+{
+	struct packfile_list_entry key = { .pack = pack };
+	struct hashmap_entry *ent;
+
+	hashmap_entry_init(&key.ent, packfile_list_entry_hash(&key));
+	ent = hashmap_get(&list->seen, &key.ent, NULL);
+
+	return ent ? container_of(ent, struct packfile_list_entry, ent) : NULL;
 }
 
 static struct packfile_list_entry *packfile_list_remove_internal(struct packfile_list *list,

@@ -38,20 +74,33 @@ static struct packfile_list_entry *packfile_list_remove_internal(struct packfile
 
 void packfile_list_remove(struct packfile_list *list, struct packed_git *pack)
 {
-	free(packfile_list_remove_internal(list, pack));
+	struct packfile_list_entry key = { .pack = pack };
+
+	hashmap_entry_init(&key.ent, packfile_list_entry_hash(&key));
+	if (hashmap_remove(&list->seen, &key.ent, NULL)) {
+		struct packfile_list_entry *e = packfile_list_remove_internal(list, pack);
+		if (!e)
+			BUG("corrupt packfile list");
+		free(e);
+	}
 }
 
 void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack)
 {
 	struct packfile_list_entry *entry;
 
-	entry = packfile_list_remove_internal(list, pack);
-	if (!entry) {
+	if (packfile_list_lookup(list, pack)) {
+		entry = packfile_list_remove_internal(list, pack);
+		if (!entry)
+			BUG("corrupt packfile list");
+	} else {
 		entry = xmalloc(sizeof(*entry));
 		entry->pack = pack;
+		hashmap_entry_init(&entry->ent, packfile_list_entry_hash(entry));
+		hashmap_add(&list->seen, &entry->ent);
 	}
-	entry->next = list->head;
 
+	entry->next = list->head;
 	list->head = entry;
 	if (!list->tail)
 		list->tail = entry;

@@ -61,13 +110,18 @@ void packfile_list_append(struct packfile_list *list, struct packed_git *pack)
 {
 	struct packfile_list_entry *entry;
 
-	entry = packfile_list_remove_internal(list, pack);
-	if (!entry) {
+	if (packfile_list_lookup(list, pack)) {
+		entry = packfile_list_remove_internal(list, pack);
+		if (!entry)
+			BUG("corrupt packfile list");
+	} else {
 		entry = xmalloc(sizeof(*entry));
 		entry->pack = pack;
+		hashmap_entry_init(&entry->ent, packfile_list_entry_hash(entry));
+		hashmap_add(&list->seen, &entry->ent);
 	}
-	entry->next = NULL;
 
+	entry->next = NULL;
 	if (list->tail) {
 		list->tail->next = entry;
 		list->tail = entry;

packfile-list.h +5 -0

index 1b05e2aa36..bfb7017852 100644
@@ -1,17 +1,22 @@
 #ifndef PACKFILE_LIST_H
 #define PACKFILE_LIST_H
 
+#include "hashmap.h"
+
 struct object_id;
 
 struct packfile_list {
 	struct packfile_list_entry *head, *tail;
+	struct hashmap seen;
 };
 
 struct packfile_list_entry {
+	struct hashmap_entry ent;
 	struct packfile_list_entry *next;
 	struct packed_git *pack;
 };
 
+void packfile_list_init(struct packfile_list *list);
 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);

Quoted 4 lines · Patrick Steinhardt

I wonder whether we should slightly reformulate this and rename is_new to accept_duplicates. Because ultimately, that is what we're doing
now: instead of ensuring that the packfile is unique in the list, we just don't care and just append the entry to the list.

Hmm. I don't quite agree, we're _not_ accepting duplicates. We know that those packfiles _cannot_ be duplicates.

Quoted 7 lines

An alternative would be to use a hashmap here that tracks the packs that have already been added. It has the advantage that it also covers the prepend() operation and that callers don't have to be aware of this mechanism at all. Furthermore, moving preexisting entries to the back or front could become O(logn) if the list was doubly-linked. We do this operation quite often to re-sort entries in the list when looking up objects.

Indeed, that was my initial reaction, too. I was well on my way to start writing a hashmap-based fix when the AI assistant pointed out that no duplicates could possibly exist yet.

Quoted 2 lines

Overall though I'm not quite sure whether the added complexity would be worth it, see below patch.

Wow, you got a lot further than I did! And yes, I agree that we do not (yet?) need to deal with the added complexity.

Quoted 6 lines · Johannes Schindelin

Quoted 4 lines · Patrick Steinhardt

I wonder whether we should slightly reformulate this and rename is_new to accept_duplicates. Because ultimately, that is what we're doing
now: instead of ensuring that the packfile is unique in the list, we just don't care and just append the entry to the list.

Quoted 2 lines

Hmm. I don't quite agree, we're _not_ accepting duplicates. We know that those packfiles _cannot_ be duplicates.

I know that we're not, but this is only because the caller knows that the packs are new. Seen outside that context though the new parameter really just tells us whether or not we want to deduplicate packs or not.

Anyway, I'm splitting hairs and I won't insist on a change here.

Quoted 12 lines

Quoted 7 lines

An alternative would be to use a hashmap here that tracks the packs that have already been added. It has the advantage that it also covers the prepend() operation and that callers don't have to be aware of this mechanism at all. Furthermore, moving preexisting entries to the back or front could become O(logn) if the list was doubly-linked. We do this operation quite often to re-sort entries in the list when looking up objects.

Indeed, that was my initial reaction, too. I was well on my way to start writing a hashmap-based fix when the AI assistant pointed out that no duplicates could possibly exist yet.

Quoted 5 lines

Quoted 2 lines

Overall though I'm not quite sure whether the added complexity would be worth it, see below patch.

Wow, you got a lot further than I did! And yes, I agree that we do not (yet?) need to deal with the added complexity.

I may want to pursue this patch anyway, as I think that the reordering would be sped up by that change quite signifcantly. And that would make a difference indeed when you have 38k packfiles, at least when you assume that objects are evenly distributed across all of those and that we perform reads of random objects.

I could do that tomorrow, and in that case it'd supersede your patch.

But I'm also happy to have this improvement here land first and then I'll pursue this change eventually.

Thanks!

Patrick

Hi Patrick,

Quoted 10 lines · Patrick Steinhardt

Quoted 8 lines · Johannes Schindelin

Quoted 4 lines · Patrick Steinhardt

I wonder whether we should slightly reformulate this and rename is_new to accept_duplicates. Because ultimately, that is what we're doing
now: instead of ensuring that the packfile is unique in the list, we just don't care and just append the entry to the list.

Hmm. I don't quite agree, we're _not_ accepting duplicates. We know that those packfiles _cannot_ be duplicates.

Quoted 5 lines

I know that we're not, but this is only because the caller knows that the packs are new. Seen outside that context though the new parameter really just tells us whether or not we want to deduplicate packs or not.

Anyway, I'm splitting hairs and I won't insist on a change here.

You do have a point, though, is_new is too narrow. How about skip_dup_check?

Quoted 24 lines

Quoted 12 lines

Quoted 7 lines

An alternative would be to use a hashmap here that tracks the packs that have already been added. It has the advantage that it also covers the prepend() operation and that callers don't have to be aware of this mechanism at all. Furthermore, moving preexisting entries to the back or front could become O(logn) if the list was doubly-linked. We do this operation quite often to re-sort entries in the list when looking up objects.

Indeed, that was my initial reaction, too. I was well on my way to start writing a hashmap-based fix when the AI assistant pointed out that no duplicates could possibly exist yet.

Quoted 5 lines

Quoted 2 lines

Overall though I'm not quite sure whether the added complexity would be worth it, see below patch.

Wow, you got a lot further than I did! And yes, I agree that we do not (yet?) need to deal with the added complexity.

I may want to pursue this patch anyway, as I think that the reordering would be sped up by that change quite signifcantly. And that would make a difference indeed when you have 38k packfiles, at least when you assume that objects are evenly distributed across all of those and that we perform reads of random objects.

Quoted 1 line

I could do that tomorrow, and in that case it'd supersede your patch.

I don't think that it would _quite_ supersede this patch. Sure, while searching through a hashset instead of a single-linked list is faster, it is not as fast as skipping the search altogether.

Quoted 6 lines

(quoted diff) +2 -1

-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;

packfile-list.c static struct packfile_list_entry *packfile_list_remove_internal(struct packfile · line 98

Quoted 5 lines

packfile-list.c +1 -1

-	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;

I wonder whether we should slightly reformulate this and rename is_new to accept_duplicates. Because ultimately, that is what we're doing
now: instead of ensuring that the packfile is unique in the list, we just don't care and just append the entry to the list.

An alternative would be to use a hashmap here that tracks the packs that have already been added. It has the advantage that it also covers the prepend() operation and that callers don't have to be aware of this mechanism at all. Furthermore, moving preexisting entries to the back or front could become O(logn) if the list was doubly-linked. We do this operation quite often to re-sort entries in the list when looking up objects.

Quoted 7 lines · Patrick Steinhardt

An alternative would be to use a hashmap here that tracks the packs that have already been added. It has the advantage that it also covers the prepend() operation and that callers don't have to be aware of this mechanism at all. Furthermore, moving preexisting entries to the back or front could become O(logn) if the list was doubly-linked. We do this operation quite often to re-sort entries in the list when looking up objects.

Don't we already use such a hashmap via packfile_store_add_pack() and packfile_store_load_pack()? That comes from ec48540fe8 (packfile.c:
speed up loading lots of packfiles, 2019-11-27) and is how we know that this "is_new" flag is true (otherwise we'd get duplicates during "reprepare" operations).

Quoted 10 lines · Jeff King

Quoted 7 lines · Patrick Steinhardt

An alternative would be to use a hashmap here that tracks the packs that have already been added. It has the advantage that it also covers the prepend() operation and that callers don't have to be aware of this mechanism at all. Furthermore, moving preexisting entries to the back or front could become O(logn) if the list was doubly-linked. We do this operation quite often to re-sort entries in the list when looking up objects.

Quoted 5 lines

Don't we already use such a hashmap via packfile_store_add_pack() and packfile_store_load_pack()? That comes from ec48540fe8 (packfile.c:
speed up loading lots of packfiles, 2019-11-27) and is how we know that this "is_new" flag is true (otherwise we'd get duplicates during "reprepare" operations).

That's a good point, we indeed do! Maybe it would make sense then to remove that map from the packfile store and instead move it into the packfile list to make it more generally useful.

Quoted 17 lines · Patrick Steinhardt

Quoted 10 lines · Jeff King

Quoted 7 lines · Patrick Steinhardt

An alternative would be to use a hashmap here that tracks the packs that have already been added. It has the advantage that it also covers the prepend() operation and that callers don't have to be aware of this mechanism at all. Furthermore, moving preexisting entries to the back or front could become O(logn) if the list was doubly-linked. We do this operation quite often to re-sort entries in the list when looking up objects.

Quoted 5 lines

Don't we already use such a hashmap via packfile_store_add_pack() and packfile_store_load_pack()? That comes from ec48540fe8 (packfile.c:
speed up loading lots of packfiles, 2019-11-27) and is how we know that this "is_new" flag is true (otherwise we'd get duplicates during "reprepare" operations).

Quoted 3 lines

That's a good point, we indeed do! Maybe it would make sense then to remove that map from the packfile store and instead move it into the packfile list to make it more generally useful.

The map protects more than just adding to the list; it avoids all of add_packed_git(), which allocates and does a bunch of stat() calls. So it couldn't just be a check in packfile_list_append(), but would have to be a separate existence check well before that.

That's not impossible, but it would be a lot easier to see what generalized pattern would be most useful if there were more than one caller of packfile_list_append(). ;)

Quoted 5 lines

The map protects more than just adding to the list; it avoids all of add_packed_git(), which allocates and does a bunch of stat() calls. So it couldn't just be a check in packfile_list_append(), but would have to be a separate existence check well before that.

Quoted 3 lines

That's not impossible, but it would be a lot easier to see what generalized pattern would be most useful if there were more than one caller of packfile_list_append(). ;)

We only have a single caller that appends, but we have some more that use packfile_list_prepend(). And there we basically have the same problem.

From: Johannes Schindelin <[email protected]>
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.

Quoted 7 lines · Johannes Schindelin via GitGitGadget

From: Johannes Schindelin <[email protected]>
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.

Thanks, I'm happy with this version. We can still iterate on the other patrs of the discussion after this patch has landed, as needed.