This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
fnmatch has exponential running time
- From: Bruno Haible <bruno at clisp dot org>
- To: libc-alpha at sourceware dot org
- Cc: bug-gnulib at gnu dot org
- Date: Thu, 22 Mar 2007 21:21:37 +0100
- Subject: fnmatch has exponential running time
fnmatch() has a worst-case complexity O(m*n) where m is the size of the
pattern and n is the size of the sample string. Unfortunately glibc has
chosen an implementation with exponential running time.
$ mkdir foo
$ cd foo
$ touch aaaabbbbccccddddeeeeffffgggghhhhiiiijjjjkkkkllllmmmmnnnnooooppppqqqqrrrrssssttttuuuuvvvvwwwwxxxxyyyy
$ time find . -name 'a*b*d*e*f*g*h*i*j*z*'
real 0m0.028s
user 0m0.028s
sys 0m0.000s
$ time find . -name 'a*b*d*e*f*g*h*i*j*k*z*'
real 0m0.095s
user 0m0.092s
sys 0m0.000s
$ time find . -name 'a*b*d*e*f*g*h*i*j*k*l*z*'
real 0m0.377s
user 0m0.348s
sys 0m0.004s
$ time find . -name 'a*b*d*e*f*g*h*i*j*k*l*m*z*'
real 0m1.381s
user 0m1.336s
sys 0m0.008s
$ time find . -name 'a*b*d*e*f*g*h*i*j*k*l*m*n*z*'
real 0m5.108s
user 0m5.016s
sys 0m0.004s
$ time find . -name 'a*b*d*e*f*g*h*i*j*k*l*m*n*o*z*'
real 0m19.393s
user 0m18.913s
sys 0m0.008s
$ time find . -name 'a*b*d*e*f*g*h*i*j*k*l*m*n*o*p*z*'
real 1m13.241s
user 1m11.840s
sys 0m0.004s
$ time find . -name 'a*b*d*e*f*g*h*i*j*k*l*m*n*o*p*q*z*'
real 4m50.007s
user 4m44.002s
sys 0m0.056s
A gdb stack trace shows this:
#0 0xf7ed3150 in wmemchr () from /lib/libc.so.6
#1 0xf7ef67d1 in internal_fnwmatch () from /lib/libc.so.6
#2 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#3 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#4 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#5 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#6 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#7 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#8 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#9 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#10 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#11 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#12 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#13 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#14 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#15 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#16 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#17 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#18 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#19 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#20 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#21 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#22 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#23 0xf7ef68c9 in internal_fnwmatch () from /lib/libc.so.6
#24 0xf7ef7821 in fnmatch@GLIBC_2.0 () from /lib/libc.so.6
#25 0x00000004 in ?? ()
So, apparently fnmnatch() is implemented in a recursive way, and does
backtracking. Even though no backtracking is needed at all for patterns
like the above.
Bruno