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

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

From
Jeff King <peff@peff.net>
Date
Aug 17, 2026, 07:21 UTC
Message-ID
<20260817072113.GA690018@coredump.intra.peff.net>
In-Reply-To
<aoKZvxE8oP5B6O_4@pks.im>
On Mon, Aug 17, 2026 at 07:18:55AM +0200, Patrick Steinhardt wrote:
Show 12 quoted 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.
> > 
> > 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
Previous: Patrick SteinhardtNext: Johannes Schindelin via GitGitGadget
Message 21 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.