This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]