git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Johannes Schindelin <johannes.schindelin@gmx.de>
Date
Aug 13, 2026, 09:20 UTC
Message-ID
<b4860540-6114-2a7b-e266-d1fc2f0041b9@gmx.de>
In-Reply-To
<an1zz02GNqDu-0Oz@pks.im>
Hi Patrick,
On Thu, 13 Aug 2026, Patrick Steinhardt wrote:
Show 10 quoted lines
> 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.

Show 11 quoted 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.
Yes.
Show 39 quoted 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.
> 
> > 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.

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

> 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

Show 199 quoted lines
> 
> 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);
> 
Previous: Patrick SteinhardtNext: Patrick Steinhardt
Message 12 of 24 in “packfile: fix perf regression with many packs”
  1. packfile: fix perf regression with many packsJohannes Schindelin via GitGitGadget, Aug 12, 2026
  2. Junio C HamanoAug 12, 2026
  3. Jeff KingAug 12, 2026
  4. Patrick SteinhardtAug 13, 2026
  5. Johannes SchindelinAug 13, 2026
  6. Jeff KingAug 13, 2026
  7. Johannes SchindelinAug 13, 2026
  8. Ben KnobleAug 12, 2026
  9. Johannes SchindelinAug 13, 2026
  10. Ben KnobleAug 13, 2026
  11. Patrick SteinhardtAug 13, 2026
  12. Johannes SchindelinAug 13, 2026
  13. Patrick SteinhardtAug 13, 2026
  14. Johannes SchindelinAug 13, 2026
  15. Patrick SteinhardtAug 13, 2026
  16. Junio C HamanoAug 13, 2026
  17. Jeff KingAug 13, 2026
  18. Patrick SteinhardtAug 14, 2026
  19. Jeff KingAug 14, 2026
  20. Patrick SteinhardtAug 17, 2026
  21. Jeff KingAug 17, 2026
  22. packfile: fix perf regression with many packsJohannes Schindelin via GitGitGadget, Aug 13, 2026
  23. Patrick SteinhardtAug 14, 2026
  24. Junio C HamanoAug 14, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.