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

Re: [PATCH] ls-files: filter pathspec before lstat

From
Jeff King <peff@peff.net>
Date
Jun 8, 2026, 23:25 UTC
Message-ID
<20260608232516.GA357822@coredump.intra.peff.net>
In-Reply-To
<20260608230315.GC340696@coredump.intra.peff.net>
On Mon, Jun 08, 2026 at 07:03:15PM -0400, Jeff King wrote:
Show 15 quoted lines
> > Adding an extra early `match_pathspec()` check before making slow
> > system calls like `lstat()` makes sense, especially when most of the
> > index entries need to be skipped.  But if most of them would match,
> > then we would end up doing the same match_pathspec() calls twice for
> > each path, and run lstat() anyway, so you may also be able to
> > construct a perf test that demonstrates a case where this approach
> > is not a clear win (or even degradation), perhaps?
> 
> The patchspec matching is linear in the number of pathspecs, so it's
> easy to get quadratic-ish results by just asking about:
> 
>   git ls-files -- $(git ls-files)
> 
> So that probably provides an easy regression demonstration for this
> patch.
Ah, yeah, it is easy to demonstrate. Making a repo of size $n like this:
  n=10000
  git init
  for i in $(seq $n); do
    echo $i >file$i
  done
  git add .
  git commit -m foo
If we then run:
  time git ls-files -- $(git ls-files) >/dev/null

then n=1000 takes ~15ms for me, but n=10000 takes ~800ms. So that shows the slowdown of the existing pathspec code as the number of pathspecs grows.

With this patch, starting with n=10000 and adding in "-m" (which triggers the code in this patch), like:

  time git ls-files -m -- $(git ls-files) >/dev/null

the time goes from ~15ms (without the patch) to ~800ms with it. Which makes sense. Nothing is modified, so the current code which puts the lstat() check first eliminates each entry before we even consider pathspecs. So it doesn't hit the slow case at all.

But after the patch, we do a preliminary pathspec match and pay the cost.

So it really is a question of how many items are actually modified, the cost of lstat(), and the cost of pathspec matching (which varies with the size of the pathspec).

But like I said, this is kind of a silly case. If it actually starts to matter in the real world, I think it may be more productive to make the pathspec code scale better.

-Peff
Previous: Jeff KingNext: Tamir Duberstein
Message 10 of 11 in “ls-files: filter pathspec before lstat”
  1. ls-files: filter pathspec before lstatTamir Duberstein, Jun 7, 2026
  2. Kristoffer HaugsbakkJun 7, 2026
  3. Tamir DubersteinJun 7, 2026
  4. Kristoffer HaugsbakkJun 7, 2026
  5. Tamir DubersteinJun 7, 2026
  6. Kristoffer HaugsbakkSep 6, 2026
  7. Junio C HamanoJun 8, 2026
  8. Tamir DubersteinJun 8, 2026
  9. Jeff KingJun 8, 2026
  10. Jeff KingJun 8, 2026
  11. Tamir DubersteinJun 9, 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.