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"
donerm -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.noneSo 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.fullonlyThis 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
