Oops.

$ mkdir /tmp/x
$ cd /tmp/x
$ touch $(perl -e 'print "a" x 100')
$ pattern="b"
$ for i in $(seq 8)
> do
> time sh -c "echo $pattern >/dev/null"
> pattern="a*$pattern"
> done
0.00u 0.00s 0.00r sh -c echo b >/dev/null
0.00u 0.00s 0.00r sh -c echo a*b >/dev/null
0.00u 0.00s 0.00r sh -c echo a*a*b >/dev/null
0.00u 0.00s 0.00r sh -c echo a*a*a*b >/dev/null
0.02u 0.00s 0.02r sh -c echo a*a*a*a*b >/dev/null
0.42u 0.00s 0.42r sh -c echo a*a*a*a*a*b >/dev/null
7.21u 0.00s 7.22r sh -c echo a*a*a*a*a*a*b >/dev/null
103.64u 0.12s 103.84r sh -c echo a*a*a*a*a*a*a*b >/dev/null
$

This is particularly ridiculous, because there is no alternation except for character classes in glob patterns, so there is absolutely no need for backtracking. You don't even need a fancy NFA simulation. You just have to split the pattern at the *s and then look for each piece in turn, once. It's not just linear time, it's easy linear time. Go's path.Match implements this linear time algorithm.

And if you didn't want to write your own search, you could always transliterate the pattern into a regular expression and invoke a linear-time regular expression search implementation (swtch.com/~rsc/regexp/regexp1.html).

The above is using bash but I expect the same behavior from nearly all shells. Even Plan 9's rc gets this wrong. The only shell I've found that gets this right: Windows's cmd.exe, at least on Windows 7. Hat tip to Microsoft.
Shared publiclyView activity