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 [EMAIL PROTECTED] () 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
