3 ms·

There's another way for glob() implementations to mitigate these sort of patterns that Russ doesn't discuss, but can be inferred from a careful reading of the d

by avar 10y ago

There's another way for glob() implementations to mitigate these sort of patterns that Russ doesn't discuss, but can be inferred from a careful reading of the different examples in this new glob() article & the 2007 regex article. In the regex article he notes that e.g. perl is subject to pathological behavior when you match a?^na^n against an a^n: $ time perl -wE 'my $l = shift; my $str = "a" x $l; my $rx = "a?" x $l . $str; $str =~ /${rx}/' 28 real 0m13.278s However changing the pattern to /${rx}b/ makes it execute almost instantly. This is because the matcher will look ahead for fixed non-pattern strings found in the pattern, and deduce that whatever globbing we're trying to match now it can't possibly matter if the string doesn't have a "b" in it. I wonder if any globbing implementations take advantage of that class of optimization, and if there's any cases where Russ's suggested solution of not backtracking produces different results than you'd get by backtracking, in particular with some of the extended non-POSIX glob syntax out there.

rurban 10y ago
That's not globbing but using the regex matcher. perl's glob does the same as PHP, it simply calls the system glob. So I'm curious why the graph displays it as exponential on linux, where it should be linear. In your example pcre2 performs much better than perl btw: it errors with match limit exceeded (-47), while perl happily burns exponential CPU. It's now even worse than before Russ' original perl article. Now it descends into heap memory, before only into the stack. So now it will keep crunching forever on the whole heap, while before the perl 5.10 rewrite triggered by Russ it died fast on stack overflow.
- avar 10y ago
  > That's not globbing but using the regex matcher. Indeed. I'm just using the regex behavior to show that perl's regex matcher uses a general optimization to defeat patterns like the ones Russ is discussing using a strategy orthogonal to handling backtracking. But Russ doesn't talk about using this strategy to optimize glob(), so it's worth pointing out that it could just as well be used in a glob() implementation. I.e. just try to find a fixed part later in the pattern, and if it can't be found fail the entire match. > I'm curious why the graph displays [perl] > as exponential on linux, where it should be linear. The glob() routine in perl uses a fork of a BSD glob which ships with perl: https://github.com/Perl/perl5/blob/blead/ext/File-Glob/bsd_glob.c https://github.com/Perl/perl5/blob/blead/ext/File-Glob/bsd_g... > pcre2 performs much better than perl btw: it > errors with match limit exceeded (-47) The pcre2 library will still perform better if you adjust the match limit so that the pattern actually matches, e.g. with --match-limit=1000000000 to pcre2grep. That finishes in around 1s with PCRE, 10s with Perl. But in general a regex library can't be said to perform better just because it errors out with a match limit error sooner. That just means it's compiled with different defaults.
- rsc 10y ago
  Empirically, Perl's glob does not call the system glob. On my Linux system Perl (5.18.2) is slow but the system glob is fast. Create a file named /tmp/glob/$(perl -e 'print "a"x100') in an otherwise empty /tmp/glob and then try: $ cat tglob.pl #!/usr/bin/perl use Time::HiRes qw(clock_gettime); $| = 1; chdir "/tmp/glob" || die "$!"; for($i=0; $i<9; $i++) { $pattern = ("a*"x$i) . "b"; $t = clock_gettime(CLOCK_REALTIME); $mul = 10; if($i >= 5){ $mul = 1; } for($j=0; $j<$mul; $j++) { glob $pattern; } $t1 = clock_gettime(CLOCK_REALTIME); printf("%d %.9f\n", $i, ($t1-$t)/$mul); } $ perl -v This is perl 5, version 18, subversion 2 (v5.18.2) built for x86_64-linux-gnu-thread-multi ... $ perl tglob.pl 0 0.000004911 1 0.000016212 2 0.000088072 3 0.002416682 4 0.030226517 5 0.452545881 6 6.872966528 ^C You're the second person to claim that Perl calls the system glob though (someone in my blog comments did too). Maybe different versions of Perl do different things? This is Ubuntu 14.04 if that matters.
  - demerphq 10y ago
    No you are right. Modern perls use the BSD code in File::Glob.
    - rsc 10y ago
      More discussion at https://research.swtch.com/glob#comment-3272455315 https://research.swtch.com/glob#comment-3272455315
  - rurban 10y ago
    It uses the wrong system glob :) It either calls out on VMS or Windows to a perlglob executable, or uses BSD glob from a shared lib. So whenever perl makes a choice it makes the wrong one.
rsc 10y ago
Scanning for fixed non-pattern strings would help this example. It wouldn't help the general case (which is to say, it wouldn't help always), whereas a better algorithm would.

by avar 10y ago

rurban 10y ago

That's not globbing but using the regex matcher. perl's glob does the same as PHP, it simply calls the system glob. So I'm curious why the graph displays it as exponential on linux, where it should be linear. In your example pcre2 performs much better than perl btw: it errors with match limit exceeded (-47), while perl happily burns exponential CPU. It's now even worse than before Russ' original perl article. Now it descends into heap memory, before only into the stack. So now it will keep crunching forever on the whole heap, while before the perl 5.10 rewrite triggered by Russ it died fast on stack overflow.

avar 10y ago
> That's not globbing but using the regex matcher. Indeed. I'm just using the regex behavior to show that perl's regex matcher uses a general optimization to defeat patterns like the ones Russ is discussing using a strategy orthogonal to handling backtracking. But Russ doesn't talk about using this strategy to optimize glob(), so it's worth pointing out that it could just as well be used in a glob() implementation. I.e. just try to find a fixed part later in the pattern, and if it can't be found fail the entire match. > I'm curious why the graph displays [perl] > as exponential on linux, where it should be linear. The glob() routine in perl uses a fork of a BSD glob which ships with perl: https://github.com/Perl/perl5/blob/blead/ext/File-Glob/bsd_glob.c https://github.com/Perl/perl5/blob/blead/ext/File-Glob/bsd_g... > pcre2 performs much better than perl btw: it > errors with match limit exceeded (-47) The pcre2 library will still perform better if you adjust the match limit so that the pattern actually matches, e.g. with --match-limit=1000000000 to pcre2grep. That finishes in around 1s with PCRE, 10s with Perl. But in general a regex library can't be said to perform better just because it errors out with a match limit error sooner. That just means it's compiled with different defaults.
rsc 10y ago
Empirically, Perl's glob does not call the system glob. On my Linux system Perl (5.18.2) is slow but the system glob is fast. Create a file named /tmp/glob/$(perl -e 'print "a"x100') in an otherwise empty /tmp/glob and then try: $ cat tglob.pl #!/usr/bin/perl use Time::HiRes qw(clock_gettime); $| = 1; chdir "/tmp/glob" || die "$!"; for($i=0; $i<9; $i++) { $pattern = ("a*"x$i) . "b"; $t = clock_gettime(CLOCK_REALTIME); $mul = 10; if($i >= 5){ $mul = 1; } for($j=0; $j<$mul; $j++) { glob $pattern; } $t1 = clock_gettime(CLOCK_REALTIME); printf("%d %.9f\n", $i, ($t1-$t)/$mul); } $ perl -v This is perl 5, version 18, subversion 2 (v5.18.2) built for x86_64-linux-gnu-thread-multi ... $ perl tglob.pl 0 0.000004911 1 0.000016212 2 0.000088072 3 0.002416682 4 0.030226517 5 0.452545881 6 6.872966528 ^C You're the second person to claim that Perl calls the system glob though (someone in my blog comments did too). Maybe different versions of Perl do different things? This is Ubuntu 14.04 if that matters.
- demerphq 10y ago
  No you are right. Modern perls use the BSD code in File::Glob.
  - rsc 10y ago
    More discussion at https://research.swtch.com/glob#comment-3272455315 https://research.swtch.com/glob#comment-3272455315
- rurban 10y ago
  It uses the wrong system glob :) It either calls out on VMS or Windows to a perlglob executable, or uses BSD glob from a shared lib. So whenever perl makes a choice it makes the wrong one.

rsc 10y ago

Scanning for fixed non-pattern strings would help this example. It wouldn't help the general case (which is to say, it wouldn't help always), whereas a better algorithm would.