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

[Johannes Schindelin <Johannes.Schindelin@gmx.de>]

[-- Attachment #1: Type: text/plain, Size: 10715 bytes --]

Hi Patrick,

On Thu, 13 Aug 2026, Patrick Steinhardt wrote:

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

Thanks, will fix, along with dropping the claim that the CI clone was
fixed by this patch.

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

Yes.

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

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

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

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

Ciao,
Johannes

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