Re: [PATCH] match_pathname(): give fnmatch one char of prefix context

On Thu, Oct 23, 2025 at 01:28:11PM -0700, Junio C Hamano wrote:

I wanted some actual numbers, so here's more than anybody probably cares to read on the subject. This is the test script I came up with:

-- >8 -- #!/bin/sh

pattern=$1; shift
path=$1; shift
versions=
for i in "$@"; do
	versions="${versions:+$versions,}$i"
done

rm -rf repo

git init repo cd repo

echo "/$pattern" >.gitignore
for i in $(seq 1 1000000); do
	eval "echo \"$path\""
done >input

hyperfine -L git "$versions" -n "{git}" '../{git} check-ignore -q --no-index --stdin <input || true' -- 8< --

The idea is to just match $path a million times against $path, with as little other junk as possible. And we test it against a series of builds, which are:

  - git.orig; the current tip of 'master'

  - git.none; ripping out the prefix-match entirely, leaving it to
    wildmatch to match those characters.

  - git.fullonly; leaving the early return when the prefix consumes the
    whole name, but not advancing name/pattern by the prefix amount
    before handing it to fnmatch

  - git.minusone; shrinking the prefix by one to give fnmatch one char
    of context (i.e., the patch under discussion)

Here are results for a long name that matches exactly:

  $ long='this is an extremely long pattern that has no globs in it'
  $ ./test "$long" "$long" git.*
  Benchmark 1: git.fullonly
    Time (mean ± σ):     311.0 ms ±   5.9 ms    [User: 302.5 ms, System: 8.4 ms]
    Range (min … max):   303.4 ms … 319.3 ms    10 runs
  
  Benchmark 2: git.minusone
    Time (mean ± σ):     316.4 ms ±   4.8 ms    [User: 303.5 ms, System: 12.9 ms]
    Range (min … max):   306.3 ms … 323.5 ms    10 runs
  
  Benchmark 3: git.none
    Time (mean ± σ):     455.3 ms ±  12.2 ms    [User: 444.4 ms, System: 10.8 ms]
    Range (min … max):   442.1 ms … 475.1 ms    10 runs
  
  Benchmark 4: git.orig
    Time (mean ± σ):     320.8 ms ±   6.8 ms    [User: 307.8 ms, System: 12.9 ms]
    Range (min … max):   311.7 ms … 331.0 ms    10 runs
  
  Summary
    git.fullonly ran
      1.02 ± 0.02 times faster than git.minusone
      1.03 ± 0.03 times faster than git.orig
      1.46 ± 0.05 times faster than git.none

So we can see that "git.none" performs way worse than the rest of them. I.e., this optimization really is doing something. That wasn't immediately obvious to me, since it's all O(n) in the end. But presumably wildmatch's slow char-by-char walk is much less fast than what amounts to a strcmp().

Interestingly fullonly is a little faster, even though we should never be running the removed code in this case. I guess the function fits in cache a little better? :)

Now let's try the same thing with paths that only prefix match:

  $ ./test "$long" "$long-\$i" git.*

  Benchmark 1: git.fullonly
    Time (mean ± σ):     472.1 ms ±   6.1 ms    [User: 458.0 ms, System: 14.0 ms]
    Range (min … max):   463.1 ms … 484.9 ms    10 runs
  
  Benchmark 2: git.minusone
    Time (mean ± σ):     334.4 ms ±   5.5 ms    [User: 324.3 ms, System: 10.0 ms]
    Range (min … max):   325.7 ms … 340.6 ms    10 runs
  
  Benchmark 3: git.none
    Time (mean ± σ):     461.7 ms ±   6.0 ms    [User: 448.8 ms, System: 12.8 ms]
    Range (min … max):   449.2 ms … 473.6 ms    10 runs
  
  Benchmark 4: git.orig
    Time (mean ± σ):     334.4 ms ±   3.4 ms    [User: 325.5 ms, System: 8.8 ms]
    Range (min … max):   326.0 ms … 338.1 ms    10 runs
  
  Summary
    git.minusone ran
      1.00 ± 0.02 times faster than git.orig
      1.38 ± 0.03 times faster than git.none
      1.41 ± 0.03 times faster than git.fullonly

This matches what I'd expect. git.fullonly performs even worse than git.none now (because we're matching that long prefix only to hand the entire thing off to wildmatch to do it again). There is a possible optimization missing in the code for this case, where we know we've eaten all of "patternlen" but not all "namelen" (so we know we cannot match), but it's probably rare enough not to worry about (and certainly fnmatch should be able to figure that out quickly).

The other interesting thing here is that git.minusone performs about the same as git.orig. So adding one character back for fnmatch to process is not a big deal. It's a small constant amount of extra work.

Note that neither pattern has a wildcard here! We could test that with:

  $ ./test "$long-*" "$long-\$i" git.*

but the timings are roughly the same as above. In either case, fnmatch will accept or reject pretty quickly once it hits the part after "$long". So all we are really measuring is how long fnmatch takes to walk over that first prefix part without wildcards.

So the obvious takeaway is that yes, fnmatch is much slower than strmcp. That doesn't tell us how _often_ these cases kick in. That is, the intuition we were talking about above is that matching "foo" with "foo" is a lot more common than "foo*" matching "foobar". And no amount of playing with made-up inputs will tell us that. ;)

But my inclination is to leave the optimization in place, assuming we do not find any more corner cases that foil the one-char-of-context hack. It's not much code, and it definitely _can_ help.

-Peff