From: Tamir Duberstein Date: Tue, 09 Jun 2026 00:13:37 GMT Subject: Re: [PATCH] ls-files: filter pathspec before lstat Message-ID: In-Reply-To: <20260608232516.GA357822@coredump.intra.peff.net> On Mon, Jun 8, 2026 at 4:25 PM Jeff King wrote: > > On Mon, Jun 08, 2026 at 07:03:15PM -0400, Jeff King wrote: > > > > 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. Yeah, agreed. Still, it exposed an easy-to-avoid downside in this patch, so I limited the early match to a single pathspec in v2. With 10,000 clean files, hyperfine measured 112.5 ms ± 6.6 ms for the parent and 494.1 ms ± 17.2 ms for v1. With the restriction, the patched version took 104.9 ms ± 2.2 ms against 110.1 ms ± 4.1 ms for the parent. Thanks for pointing it out!