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

[Jeff King <peff@peff.net>]

On Mon, Aug 17, 2026 at 07:18:55AM +0200, Patrick Steinhardt wrote:

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

Ah, indeed. I see prepend calls sprinkled in some rather hot code paths,
including the MRU adjustment from find_pack_entry(). That is a possible
candidate for Dscho's clone slowdown[1].

But I don't think would not want to pay the cost for a hash de-dup
there. We are not adding a new pack at all, but just adjusting the
placement, and that should be a quick O(1) if we are using a
doubly-linked list.

It's harder to construct a synthetic test for prepending because of pack
locality. If two subsequent requests both try to move pack A to the
front of the list, the second prepend()'s removal operation will find
the pack at the front in essentially constant time.

But we can spread the history across packs like this (I recommend
running on a ram disk, otherwise the checkpoint sync() makes it take
forever):

  git init
  for i in $(seq 10000); do
    echo "commit refs/heads/foo"
    echo "committer <none@example.com> $i +0000"
    echo "data <<EOF"
    echo "commit message $i"
    echo "EOF"
    echo
    echo checkpoint
  done |
  git -c fastimport.unpackLimit=0 fast-import

And then timing "git rev-list --count foo" is interesting as the number
of packs grows:

  -   500:   18ms
  -  1000:   34ms
  -  2000:  103ms
  -  4000:  374ms
  -  8000: 1648ms
  - 16000: 6351ms

You can see the quadratic growth taking over around 2000 packs. But I'm
not sure that is proving anything about list management. Lookup across
packs is linear, so this situation is inherently quadratic. I think you
could probably make an argument that the list management follows exactly
the same quadratic patterns, and thus the MRU optimizes the removal from
the prepend, too.

Still, it seems prudent for these MRU updates to use a constant-time
movement within the list, rather than an explicit duplicate check and
removal.

-Peff