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

[Patrick Steinhardt <ps@pks.im>]

On Wed, Aug 12, 2026 at 07:11:09PM +0000, Johannes Schindelin via GitGitGadget wrote:
> From: Johannes Schindelin <johannes.schindelin@gmx.de>
> 
> Since 589127caa730 (packfile: move list of packs into the packfile
> store, 2025-10-30), there is a performance regression when many
> packfiles need to be loaded: `packfile_store_add_pack()` now calls
> `packfile_list_remove_internal()` to detect whether the packfile was
> _already_ in the list, if if so, move it to the end of the list. This

Nit: s/if if/and if/

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

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

> diff --git a/packfile-list.c b/packfile-list.c
> index 01fb913abf..1379ab3a4f 100644
> --- a/packfile-list.c
> +++ b/packfile-list.c
> @@ -57,11 +57,12 @@ void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack)
>  		list->tail = entry;
>  }
>  
> -void packfile_list_append(struct packfile_list *list, struct packed_git *pack)
> +void packfile_list_append(struct packfile_list *list, struct packed_git *pack,
> +			  int is_new)
>  {
>  	struct packfile_list_entry *entry;
>  
> -	entry = packfile_list_remove_internal(list, pack);
> +	entry = is_new ? NULL : packfile_list_remove_internal(list, pack);
>  	if (!entry) {
>  		entry = xmalloc(sizeof(*entry));
>  		entry->pack = pack;

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

diff --git a/http-push.c b/http-push.c
index 94a1fac9ab..52b00e7c95 100644
--- a/http-push.c
+++ b/http-push.c
@@ -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);
 
diff --git a/http-walker.c b/http-walker.c
index b58a3b2a92..541437e52d 100644
--- a/http-walker.c
+++ b/http-walker.c
@@ -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;
diff --git a/odb/source-packed.c b/odb/source-packed.c
index 0890704e76..082c2494cb 100644
--- a/odb/source-packed.c
+++ b/odb/source-packed.c
@@ -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;
diff --git a/packfile-list.c b/packfile-list.c
index 01fb913abf..d3c4843d8d 100644
--- a/packfile-list.c
+++ b/packfile-list.c
@@ -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;
diff --git a/packfile-list.h b/packfile-list.h
index 1b05e2aa36..bfb7017852 100644
--- a/packfile-list.h
+++ b/packfile-list.h
@@ -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);