Skip Menu |
Report information
Id: 131211
Status: pending release
Priority: 0/
Queue: perl5

Owner: Nobody
Requestors: avar <avar [at] cpan.org>
Cc:
AdminCc:

Operating System: (no value)
PatchStatus: (no value)
Severity: medium
Type: core
Perl Version: 5.26.0
Fixed In: 5.27.10



Date: Tue, 25 Apr 2017 07:46:00 +0000 (UTC)
CC: avar [...] cpan.org
To: perlbug [...] perl.org
Subject: The glob() function is exponential on pathological patterns
From: avar [...] cpan.org
This is a bug report for perl from avar@cpan.org, generated with the help of perlbug 1.40 running under perl 5.26.0. ----------------------------------------------------------------- [Please describe your issue here] Russ Cox has published a paper describing pathological cases in various glob implementations. Perl is among the languages which have pathological behavior: https://research.swtch.com/glob Here's the stand-alone Perl program he used to test: https://news.ycombinator.com/item?id=14189384 Running that as instructed on blead compiled just now gives; $ ./perl -Ilib /tmp/tglob.pl 0 0.000006676 1 0.000017405 2 0.000089812 3 0.002393341 4 0.034584737 5 0.597905397 6 9.679453373 ^C [Please do not change anything below this line] ----------------------------------------------------------------- --- Flags: category=core severity=medium --- This perlbug was built using Perl 5.26.0 - Tue Apr 25 07:38:42 UTC 2017 It is being executed now by Perl 5.26.0 - Tue Apr 11 12:13:46 UTC 2017. Site configuration information for perl 5.26.0: Configured by avar at Tue Apr 11 12:13:46 UTC 2017. Summary of my perl5 (revision 5 version 26 subversion 0) configuration: Commit id: b57dd509f79945100ac318635982f75a676b5560 Platform: osname=linux osvers=3.16.0-4-amd64 archname=x86_64-linux-thread-multi uname='linux u.nix.is 3.16.0-4-amd64 #1 smp debian 3.16.7-2 (2014-11-06) x86_64 gnulinux ' config_args='-DDEBUGGING=both -Doptimize=-ggdb3 -Dusethreads -Dprefix=/home/avar/perl5/installed -Dusedevel -des' hint=previous useposix=true d_sigaction=define useithreads=define usemultiplicity=define use64bitint=define use64bitall=define uselongdouble=undef usemymalloc=n default_inc_excludes_dot=define bincompat5005=undef Compiler: cc='cc' ccflags ='-D_REENTRANT -D_GNU_SOURCE -DDEBUGGING -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64' optimize='-ggdb3' cppflags='-D_REENTRANT -D_GNU_SOURCE -DDEBUGGING -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include' ccversion='' gccversion='4.2.1 Compatible Clang 3.8.1 (tags/RELEASE_381/final)' gccosandvers='' intsize=4 longsize=8 ptrsize=8 doublesize=8 byteorder=12345678 doublekind=3 d_longlong=define longlongsize=8 d_longdbl=define longdblsize=16 longdblkind=3 ivtype='long' ivsize=8 nvtype='double' nvsize=8 Off_t='off_t' lseeksize=8 alignbytes=8 prototype=define Linker and Libraries: ld='cc' ldflags =' -fstack-protector-strong -L/usr/local/lib' libpth=/usr/local/lib /usr/lib/llvm-3.8/bin/../lib/clang/3.8.1/lib /usr/include/x86_64-linux-gnu /usr/lib /lib/x86_64-linux-gnu /lib/../lib /usr/lib/x86_64-linux-gnu /usr/lib/../lib /lib /usr/local/lib /usr/lib/llvm-3.8/bin/../lib/clang/3.8.1/lib /usr/include/x86_64-linux-gnu /usr/lib libs=-lpthread -lnsl -ldb -ldl -lm -lcrypt -lutil -lc perllibs=-lpthread -lnsl -ldl -lm -lcrypt -lutil -lc libc=libc-2.24.so so=so useshrplib=false libperl=libperl.a gnulibc_version='2.24' Dynamic Linking: dlsrc=dl_dlopen.xs dlext=so d_dlsymun=undef ccdlflags='-Wl,-E' cccdlflags='-fPIC' lddlflags='-shared -ggdb3 -L/usr/local/lib -fstack-protector-strong' --- @INC for perl 5.26.0: /home/avar/perl5/installed/lib/site_perl/5.26.0/x86_64-linux-thread-multi /home/avar/perl5/installed/lib/site_perl/5.26.0 /home/avar/perl5/installed/lib/5.26.0/x86_64-linux-thread-multi /home/avar/perl5/installed/lib/5.26.0 --- Environment for perl 5.26.0: HOME=/home/avar LANG=en_US.utf8 LANGUAGE=en_US:en LD_LIBRARY_PATH (unset) LOGDIR (unset) PATH=/home/avar/local/bin:/home/avar/perl5/installed/bin:/home/v-perlbrew/perl5/perlbrew/bin:/home/v-perlbrew/perl5/perlbrew/perls/current/bin:/home/avar/local/bin:/home/avar/g/misc-scripts:/home/avar/bin:/usr/local/bin:/usr/bin:/bin:/usr/games PERLDOC=-MPod::Text::Ansi PERL_BADLANG (unset) SHELL=/bin/bash
RT-Send-CC: perl5-porters [...] perl.org
Download (untitled) / with headers
text/plain 2.5k
On Tue, 25 Apr 2017 00:55:40 -0700, avar wrote: Show quoted text
> > This is a bug report for perl from avar@cpan.org, > generated with the help of perlbug 1.40 running under perl 5.26.0. > > > ----------------------------------------------------------------- > [Please describe your issue here] > > Russ Cox has published a paper describing pathological cases in > various glob implementations. Perl is among the languages which have > pathological behavior: https://research.swtch.com/glob > > Here's the stand-alone Perl program he used to test: > https://news.ycombinator.com/item?id=14189384 > > Running that as instructed on blead compiled just now gives; > > $ ./perl -Ilib /tmp/tglob.pl > 0 0.000006676 > 1 0.000017405 > 2 0.000089812 > 3 0.002393341 > 4 0.034584737 > 5 0.597905397 > 6 9.679453373 > ^C >
On Mageia Linux v6 x86-64, I am unable to reproduce the problem. With this program: #!/usr/bin/perl use Time::HiRes qw(clock_gettime); $| = 1; chdir "/tmp/glob" || die "$!"; for($i=0; $i<39; $i++) { $pattern = ("a*"x$i) . "b"; $t = clock_gettime(CLOCK_REALTIME); $mul = 10; for($j=0; $j<$mul; $j++) { glob $pattern; } $t1 = clock_gettime(CLOCK_REALTIME); printf("%d %.9f\n", $i, ($t1-$t)/$mul); } I am getting these results: shlomif@telaviv1:~$ /home/shlomif/apps/perl/bleadperl/bin/perl5.26.0 glob.pl 0 0.000003338 1 0.000008678 2 0.000007653 3 0.000007105 4 0.000007439 5 0.000007081 6 0.000007033 7 0.000007129 8 0.000006604 9 0.000005126 10 0.000004387 11 0.000005317 12 0.000004339 13 0.000005627 14 0.000004649 15 0.000007057 16 0.000005078 17 0.000005078 18 0.000008106 19 0.000008273 20 0.000008774 21 0.000008297 22 0.000008583 23 0.000007963 24 0.000005221 25 0.000004697 26 0.000004840 27 0.000005531 28 0.000006461 29 0.000005412 30 0.000005102 31 0.000004864 32 0.000004888 33 0.000004959 34 0.000004983 35 0.000004911 36 0.000005150 37 0.000004888 38 0.000005007 shlomif@telaviv1:~$ shlomif@telaviv1:~$ /home/shlomif/apps/perl/bleadperl/bin/perl5.26.0 --version This is perl 5, version 26, subversion 0 (v5.26.0 (v5.25.11-29-g4b05bc8)) built for x86_64-linux-thread-multi Copyright 1987-2017, Larry Wall Perl may be copied only under the terms of either the Artistic License or the GNU General Public License, which may be found in the Perl 5 source kit. Complete documentation for Perl, including FAQ lists, should be found on this system using "man perl" or "perldoc perl". If you have access to the Internet, point your browser at http://www.perl.org/, the Perl Home Page. shlomif@telaviv1:~$ /usr/bin/perl works fine as well.
Date: Tue, 25 Apr 2017 13:25:48 +0200
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
To: Shlomi Fish via RT <perlbug-followup [...] perl.org>
From: Paul Johnson <paul [...] pjcj.net>
Download (untitled) / with headers
text/plain 233b
On Tue, Apr 25, 2017 at 03:58:13AM -0700, Shlomi Fish via RT wrote: Show quoted text
> On Mageia Linux v6 x86-64, I am unable to reproduce the problem.
Did you remember to create the test file? -- Paul Johnson - paul@pjcj.net http://www.pjcj.net
Date: Tue, 25 Apr 2017 13:01:15 +0100
From: Dave Mitchell <davem [...] iabyn.com>
CC: perl5-porters [...] perl.org
To: Shlomi Fish via RT <perlbug-followup [...] perl.org>
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
Download (untitled) / with headers
text/plain 1.4k
On Tue, Apr 25, 2017 at 03:58:13AM -0700, Shlomi Fish via RT wrote: Show quoted text
> On Tue, 25 Apr 2017 00:55:40 -0700, avar wrote:
> > > > This is a bug report for perl from avar@cpan.org, > > generated with the help of perlbug 1.40 running under perl 5.26.0. > > > > > > ----------------------------------------------------------------- > > [Please describe your issue here] > > > > Russ Cox has published a paper describing pathological cases in > > various glob implementations. Perl is among the languages which have > > pathological behavior: https://research.swtch.com/glob > > > > Here's the stand-alone Perl program he used to test: > > https://news.ycombinator.com/item?id=14189384 > > > > Running that as instructed on blead compiled just now gives; > > > > $ ./perl -Ilib /tmp/tglob.pl > > 0 0.000006676 > > 1 0.000017405 > > 2 0.000089812 > > 3 0.002393341 > > 4 0.034584737 > > 5 0.597905397 > > 6 9.679453373 > > ^C > >
> > On Mageia Linux v6 x86-64, I am unable to reproduce the problem. With this program:
I can reproduce it with blead an linux. Did you create the file /tmp/glob/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa as well as the directory /tmp/glob? -- More than any other time in history, mankind faces a crossroads. One path leads to despair and utter hopelessness. The other, to total extinction. Let us pray we have the wisdom to choose correctly. -- Woody Allen
RT-Send-CC: perl5-porters [...] perl.org
Download (untitled) / with headers
text/plain 1.5k
On Tue, 25 Apr 2017 05:01:42 -0700, davem wrote: Show quoted text
> On Tue, Apr 25, 2017 at 03:58:13AM -0700, Shlomi Fish via RT wrote:
> > On Tue, 25 Apr 2017 00:55:40 -0700, avar wrote:
> > > > > > This is a bug report for perl from avar@cpan.org, > > > generated with the help of perlbug 1.40 running under perl 5.26.0. > > > > > > > > > ----------------------------------------------------------------- > > > [Please describe your issue here] > > > > > > Russ Cox has published a paper describing pathological cases in > > > various glob implementations. Perl is among the languages which > > > have > > > pathological behavior: https://research.swtch.com/glob > > > > > > Here's the stand-alone Perl program he used to test: > > > https://news.ycombinator.com/item?id=14189384 > > > > > > Running that as instructed on blead compiled just now gives; > > > > > > $ ./perl -Ilib /tmp/tglob.pl > > > 0 0.000006676 > > > 1 0.000017405 > > > 2 0.000089812 > > > 3 0.002393341 > > > 4 0.034584737 > > > 5 0.597905397 > > > 6 9.679453373 > > > ^C > > >
> > > > On Mageia Linux v6 x86-64, I am unable to reproduce the problem. With > > this program:
> > I can reproduce it with blead an linux. Did you create the file > > /tmp/glob/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa > > as well as the directory /tmp/glob?
Sorry - I missed that part - I thought the program was self-contained. Now I can reproduce that problem with the 'a'x100 file created, and furthermore «shlomif@telaviv1:/tmp/glob$ bash -c 'echo a*a*a*a*a*a*a*a*b'» hangs.
From: demerphq <demerphq [...] gmail.com>
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
To: Perl5 Porteros <perl5-porters [...] perl.org>
CC: "bugs-bitbucket [...] rt.perl.org" <bugs-bitbucket [...] rt.perl.org>
Date: Tue, 25 Apr 2017 14:48:10 +0200
Download (untitled) / with headers
text/plain 1.5k
On 25 April 2017 at 09:55, Ævar Arnfjörð Bjarmason <perlbug-followup@perl.org> wrote: Show quoted text
> # New Ticket Created by Ævar Arnfjörð Bjarmason > # Please include the string: [perl #131211] > # in the subject line of all future correspondence about this issue. > # <URL: https://rt.perl.org/Ticket/Display.html?id=131211 > > > > > This is a bug report for perl from avar@cpan.org, > generated with the help of perlbug 1.40 running under perl 5.26.0. > > > ----------------------------------------------------------------- > [Please describe your issue here] > > Russ Cox has published a paper describing pathological cases in > various glob implementations. Perl is among the languages which have > pathological behavior: https://research.swtch.com/glob > > Here's the stand-alone Perl program he used to test: > https://news.ycombinator.com/item?id=14189384 > > Running that as instructed on blead compiled just now gives; > > $ ./perl -Ilib /tmp/tglob.pl > 0 0.000006676 > 1 0.000017405 > 2 0.000089812 > 3 0.002393341 > 4 0.034584737 > 5 0.597905397 > 6 9.679453373 > ^C
For some time now we have used the code in File::Glob for glob(). The code involved in this slowdown is in ext/File-Glob/bsd_glob.c in the match function, which uses recursion to handle *. It looks like it wouldn't be too difficult to modify this code to implement the optimisation from Russ Cox, and probably at the same time rip out the recursion which seems to be a poor trade off between clean code and performance. Yves
Date: Tue, 25 Apr 2017 15:20:01 +0200
CC: "bugs-bitbucket [...] rt.perl.org" <bugs-bitbucket [...] rt.perl.org>
To: Perl5 Porteros <perl5-porters [...] perl.org>
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
From: demerphq <demerphq [...] gmail.com>
Download (untitled) / with headers
text/plain 1.8k
On 25 April 2017 at 14:48, demerphq <demerphq@gmail.com> wrote: Show quoted text
> On 25 April 2017 at 09:55, Ævar Arnfjörð Bjarmason > <perlbug-followup@perl.org> wrote:
>> # New Ticket Created by Ævar Arnfjörð Bjarmason >> # Please include the string: [perl #131211] >> # in the subject line of all future correspondence about this issue. >> # <URL: https://rt.perl.org/Ticket/Display.html?id=131211 > >> >> >> >> This is a bug report for perl from avar@cpan.org, >> generated with the help of perlbug 1.40 running under perl 5.26.0. >> >> >> ----------------------------------------------------------------- >> [Please describe your issue here] >> >> Russ Cox has published a paper describing pathological cases in >> various glob implementations. Perl is among the languages which have >> pathological behavior: https://research.swtch.com/glob >> >> Here's the stand-alone Perl program he used to test: >> https://news.ycombinator.com/item?id=14189384 >> >> Running that as instructed on blead compiled just now gives; >> >> $ ./perl -Ilib /tmp/tglob.pl >> 0 0.000006676 >> 1 0.000017405 >> 2 0.000089812 >> 3 0.002393341 >> 4 0.034584737 >> 5 0.597905397 >> 6 9.679453373 >> ^C
> > For some time now we have used the code in File::Glob for glob(). > > The code involved in this slowdown is in ext/File-Glob/bsd_glob.c in > the match function, which uses recursion to handle *. It looks like it > wouldn't be too difficult to modify this code to implement the > optimisation from Russ Cox, and probably at the same time rip out the > recursion which seems to be a poor trade off between clean code and > performance.
Turn out I am wrong, and this was a fine trade off. Implementing Cox'es algorithm is nearly trivial from what I can tell. See (poorly tested) code in: cc026bf6160d7f86febc2fbc7a5d42ef93676e9f (that is a branch not blead) cheers, Yves -- perl -Mre=debug -e "/just|another|perl|hacker/"
RT-Send-CC: perl5-porters [...] perl.org
Download (untitled) / with headers
text/plain 1.1k
On Tue, 25 Apr 2017 07:55:40 GMT, avar wrote: Show quoted text
> > This is a bug report for perl from avar@cpan.org, > generated with the help of perlbug 1.40 running under perl 5.26.0. > > > ----------------------------------------------------------------- > [Please describe your issue here] > > Russ Cox has published a paper describing pathological cases in > various glob implementations. Perl is among the languages which have > pathological behavior: https://research.swtch.com/glob > > Here's the stand-alone Perl program he used to test: > https://news.ycombinator.com/item?id=14189384 > > Running that as instructed on blead compiled just now gives; > > $ ./perl -Ilib /tmp/tglob.pl > 0 0.000006676 > 1 0.000017405 > 2 0.000089812 > 3 0.002393341 > 4 0.034584737 > 5 0.597905397 > 6 9.679453373 > ^C >
Similar results in a FreeBSD-10.3 VM: ##### $ uname -a FreeBSD localhost 10.3-RELEASE FreeBSD 10.3-RELEASE #0 r297264: Fri Mar 25 02:10:02 UTC 2016 root@releng1.nyi.freebsd.org:/usr/obj/usr/src/sys/GENERIC amd64 $ perl 131211-glob.pl 0 0.000006342 1 0.000010133 2 0.000054526 3 0.000910425 4 0.033007574 5 0.644674540 6 10.338732958 ^C ##### -- James E Keenan (jkeenan@cpan.org)
Date: Tue, 25 Apr 2017 15:26:32 +0200
From: demerphq <demerphq [...] gmail.com>
To: Perl5 Porteros <perl5-porters [...] perl.org>
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
CC: "bugs-bitbucket [...] rt.perl.org" <bugs-bitbucket [...] rt.perl.org>
Download (untitled) / with headers
text/plain 2.7k
On 25 April 2017 at 15:20, demerphq <demerphq@gmail.com> wrote: Show quoted text
> On 25 April 2017 at 14:48, demerphq <demerphq@gmail.com> wrote:
>> On 25 April 2017 at 09:55, Ævar Arnfjörð Bjarmason >> <perlbug-followup@perl.org> wrote:
>>> # New Ticket Created by Ævar Arnfjörð Bjarmason >>> # Please include the string: [perl #131211] >>> # in the subject line of all future correspondence about this issue. >>> # <URL: https://rt.perl.org/Ticket/Display.html?id=131211 > >>> >>> >>> >>> This is a bug report for perl from avar@cpan.org, >>> generated with the help of perlbug 1.40 running under perl 5.26.0. >>> >>> >>> ----------------------------------------------------------------- >>> [Please describe your issue here] >>> >>> Russ Cox has published a paper describing pathological cases in >>> various glob implementations. Perl is among the languages which have >>> pathological behavior: https://research.swtch.com/glob >>> >>> Here's the stand-alone Perl program he used to test: >>> https://news.ycombinator.com/item?id=14189384 >>> >>> Running that as instructed on blead compiled just now gives; >>> >>> $ ./perl -Ilib /tmp/tglob.pl >>> 0 0.000006676 >>> 1 0.000017405 >>> 2 0.000089812 >>> 3 0.002393341 >>> 4 0.034584737 >>> 5 0.597905397 >>> 6 9.679453373 >>> ^C
>> >> For some time now we have used the code in File::Glob for glob(). >> >> The code involved in this slowdown is in ext/File-Glob/bsd_glob.c in >> the match function, which uses recursion to handle *. It looks like it >> wouldn't be too difficult to modify this code to implement the >> optimisation from Russ Cox, and probably at the same time rip out the >> recursion which seems to be a poor trade off between clean code and >> performance.
> > Turn out I am wrong, and this was a fine trade off. Implementing > Cox'es algorithm is nearly trivial from what I can tell. See (poorly > tested) code in: > > cc026bf6160d7f86febc2fbc7a5d42ef93676e9f
Timing data with my patch: $ ./perl -Ilib t.pl 0 0.000003076 1 0.000007701 2 0.000005579 3 0.000005555 4 0.000005651 5 0.000005722 6 0.000005627 7 0.000009108 8 0.000005674 9 0.000005889 10 0.000005794 11 0.000005937 12 0.000006032 13 0.000006008 14 0.000006080 15 0.000006104 16 0.000005984 17 0.000006080 18 0.000006008 19 0.000006056 20 0.000007892 21 0.000006175 22 0.000006247 23 0.000006318 24 0.000006366 25 0.000006318 26 0.000006437 27 0.000006509 28 0.000006509 29 0.000008941 30 0.000006461 31 0.000008488 32 0.000006604 33 0.000006652 34 0.000006604 35 0.000006533 36 0.000006676 37 0.000006628 38 0.000006700 Timing data without: $ perl t.pl 0 0.000002098 1 0.000008988 2 0.000034094 3 0.001035738 4 0.025789261 5 0.485890818 ^C Yves -- perl -Mre=debug -e "/just|another|perl|hacker/"
RT-Send-CC: perl5-porters [...] perl.org
Download (untitled) / with headers
text/plain 1.7k
On Tue, 25 Apr 2017 13:26:46 GMT, demerphq wrote: Show quoted text
> > > > Turn out I am wrong, and this was a fine trade off. Implementing > > Cox'es algorithm is nearly trivial from what I can tell. See (poorly > > tested) code in: > > > > cc026bf6160d7f86febc2fbc7a5d42ef93676e9f
> > Timing data with my patch: > > $ ./perl -Ilib t.pl > 0 0.000003076 > 1 0.000007701 > 2 0.000005579 > 3 0.000005555 > 4 0.000005651 > 5 0.000005722 > 6 0.000005627 > 7 0.000009108 > 8 0.000005674 > 9 0.000005889 > 10 0.000005794 > 11 0.000005937 > 12 0.000006032 > 13 0.000006008 > 14 0.000006080 > 15 0.000006104 > 16 0.000005984 > 17 0.000006080 > 18 0.000006008 > 19 0.000006056 > 20 0.000007892 > 21 0.000006175 > 22 0.000006247 > 23 0.000006318 > 24 0.000006366 > 25 0.000006318 > 26 0.000006437 > 27 0.000006509 > 28 0.000006509 > 29 0.000008941 > 30 0.000006461 > 31 0.000008488 > 32 0.000006604 > 33 0.000006652 > 34 0.000006604 > 35 0.000006533 > 36 0.000006676 > 37 0.000006628 > 38 0.000006700 > > Timing data without: > > $ perl t.pl > 0 0.000002098 > 1 0.000008988 > 2 0.000034094 > 3 0.001035738 > 4 0.025789261 > 5 0.485890818 > ^C > > Yves >
I got similar improvements with your branch. On Linux: ##### $ git show | head -5 commit cc026bf6160d7f86febc2fbc7a5d42ef93676e9f Author: Yves Orton <demerphq@gmail.com> Date: Tue Apr 25 15:17:06 2017 +0200 fixup File::Glob degenerate matching $ ./perl -Ilib ~/learn/perl/p5p/131211-glob.pl 0 0.001660299 1 0.000013208 2 0.000006318 3 0.000005698 4 0.000005698 5 0.000009537 6 0.000010729 7 0.000010729 8 0.000010967 ##### On the same FreeBSD-10.3 VM mentioned earlier: ##### $ ./perl -Ilib ~/learn/perl/p5p/131211-glob.pl 0 0.000963306 1 0.000015020 2 0.000012088 3 0.000012040 4 0.000011826 5 0.000014067 6 0.000014067 7 0.000013590 8 0.000014305 ##### -- James E Keenan (jkeenan@cpan.org)
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
To: Perl RT Bug Tracker <perlbug-followup [...] perl.org>
Date: Tue, 25 Apr 2017 16:22:17 +0200
From: demerphq <demerphq [...] gmail.com>
CC: Perl5 Porteros <perl5-porters [...] perl.org>
Download (untitled) / with headers
text/plain 2.1k
On 25 April 2017 at 15:55, James E Keenan via RT <perlbug-followup@perl.org> wrote: Show quoted text
> On Tue, 25 Apr 2017 13:26:46 GMT, demerphq wrote:
>> > >> > Turn out I am wrong, and this was a fine trade off. Implementing >> > Cox'es algorithm is nearly trivial from what I can tell. See (poorly >> > tested) code in: >> > >> > cc026bf6160d7f86febc2fbc7a5d42ef93676e9f
>> >> Timing data with my patch: >> >> $ ./perl -Ilib t.pl >> 0 0.000003076 >> 1 0.000007701 >> 2 0.000005579 >> 3 0.000005555 >> 4 0.000005651 >> 5 0.000005722 >> 6 0.000005627 >> 7 0.000009108 >> 8 0.000005674 >> 9 0.000005889 >> 10 0.000005794 >> 11 0.000005937 >> 12 0.000006032 >> 13 0.000006008 >> 14 0.000006080 >> 15 0.000006104 >> 16 0.000005984 >> 17 0.000006080 >> 18 0.000006008 >> 19 0.000006056 >> 20 0.000007892 >> 21 0.000006175 >> 22 0.000006247 >> 23 0.000006318 >> 24 0.000006366 >> 25 0.000006318 >> 26 0.000006437 >> 27 0.000006509 >> 28 0.000006509 >> 29 0.000008941 >> 30 0.000006461 >> 31 0.000008488 >> 32 0.000006604 >> 33 0.000006652 >> 34 0.000006604 >> 35 0.000006533 >> 36 0.000006676 >> 37 0.000006628 >> 38 0.000006700 >> >> Timing data without: >> >> $ perl t.pl >> 0 0.000002098 >> 1 0.000008988 >> 2 0.000034094 >> 3 0.001035738 >> 4 0.025789261 >> 5 0.485890818 >> ^C >> >> Yves >>
> > I got similar improvements with your branch. > > On Linux: > > ##### > $ git show | head -5 > commit cc026bf6160d7f86febc2fbc7a5d42ef93676e9f > Author: Yves Orton <demerphq@gmail.com> > Date: Tue Apr 25 15:17:06 2017 +0200 > > fixup File::Glob degenerate matching > > $ ./perl -Ilib ~/learn/perl/p5p/131211-glob.pl > 0 0.001660299 > 1 0.000013208 > 2 0.000006318 > 3 0.000005698 > 4 0.000005698 > 5 0.000009537 > 6 0.000010729 > 7 0.000010729 > 8 0.000010967 > ##### > > On the same FreeBSD-10.3 VM mentioned earlier: > > ##### > $ ./perl -Ilib ~/learn/perl/p5p/131211-glob.pl > 0 0.000963306 > 1 0.000015020 > 2 0.000012088 > 3 0.000012040 > 4 0.000011826 > 5 0.000014067 > 6 0.000014067 > 7 0.000013590 > 8 0.000014305 > #####
Thanks. FWIW, i realize my patch is wrong tho. Close but no cigar. I need to fix it. cheers, Yves -- perl -Mre=debug -e "/just|another|perl|hacker/"
RT-Send-CC: perl5-porters [...] perl.org
Download (untitled) / with headers
text/plain 1.1k
On Tue, 25 Apr 2017 07:22:34 -0700, demerphq wrote: Show quoted text
> On 25 April 2017 at 15:55, James E Keenan via RT > <perlbug-followup@perl.org> wrote:
> > On Tue, 25 Apr 2017 13:26:46 GMT, demerphq wrote:
> >> > > >> > Turn out I am wrong, and this was a fine trade off. Implementing > >> > Cox'es algorithm is nearly trivial from what I can tell. See (poorly > >> > tested) code in: > >> > > >> > cc026bf6160d7f86febc2fbc7a5d42ef93676e9f
> >> [snip]
> > #####
> > Thanks. FWIW, i realize my patch is wrong tho. Close but no cigar. I > need to fix it. > > cheers, > Yves >
I wasn't following this closely, but a patch got applied as 0db967b2e6a without the ticket being closed, and now os390 is failing # Failed test 'tried all the patterns without bailing out' # at ../ext/File-Glob/t/rt131211.t line 49. # got: '8' # expected: '10' # Failed test 'time to fail less than 10x the time to match' # at ../ext/File-Glob/t/rt131211.t line 54. # elapsed_match=0.292587518692017 elapsed_fail=52.9407045841217 # Looks like you failed 2 tests of 13. ext/File-Glob/t/rt131211 ...................................... FAILED at test 1 -- Karl Williamson
CC: Perl5 Porteros <perl5-porters [...] perl.org>
From: demerphq <demerphq [...] gmail.com>
Date: Tue, 11 Jul 2017 16:44:04 +0200
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
To: Perl RT Bug Tracker <perlbug-followup [...] perl.org>
Download (untitled) / with headers
text/plain 1.3k
On 11 July 2017 at 04:32, Karl Williamson via RT <perlbug-followup@perl.org> wrote: Show quoted text
> On Tue, 25 Apr 2017 07:22:34 -0700, demerphq wrote:
>> On 25 April 2017 at 15:55, James E Keenan via RT >> <perlbug-followup@perl.org> wrote:
>> > On Tue, 25 Apr 2017 13:26:46 GMT, demerphq wrote:
>> >> > >> >> > Turn out I am wrong, and this was a fine trade off. Implementing >> >> > Cox'es algorithm is nearly trivial from what I can tell. See (poorly >> >> > tested) code in: >> >> > >> >> > cc026bf6160d7f86febc2fbc7a5d42ef93676e9f
>> >> [snip]
>> > #####
>> >> Thanks. FWIW, i realize my patch is wrong tho. Close but no cigar. I >> need to fix it. >> >> cheers, >> Yves >>
> > I wasn't following this closely, but a patch got applied as 0db967b2e6a without the ticket being closed, and now os390 is failing > > # Failed test 'tried all the patterns without bailing out' > # at ../ext/File-Glob/t/rt131211.t line 49. > # got: '8' > # expected: '10' > # Failed test 'time to fail less than 10x the time to match' > # at ../ext/File-Glob/t/rt131211.t line 54. > # elapsed_match=0.292587518692017 elapsed_fail=52.9407045841217 > # Looks like you failed 2 tests of 13. > ext/File-Glob/t/rt131211 ...................................... FAILED at test 1
That is very weird. Does os390 use this code? Yves -- perl -Mre=debug -e "/just|another|perl|hacker/"
From: Karl Williamson <public [...] khwilliamson.com>
Date: Tue, 11 Jul 2017 10:18:31 -0600
CC: Perl5 Porteros <perl5-porters [...] perl.org>
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
To: demerphq <demerphq [...] gmail.com>, Perl RT Bug Tracker <perlbug-followup [...] perl.org>
Download (untitled) / with headers
text/plain 1.5k
On 07/11/2017 08:44 AM, demerphq wrote: Show quoted text
> On 11 July 2017 at 04:32, Karl Williamson via RT > <perlbug-followup@perl.org> wrote:
>> On Tue, 25 Apr 2017 07:22:34 -0700, demerphq wrote:
>>> On 25 April 2017 at 15:55, James E Keenan via RT >>> <perlbug-followup@perl.org> wrote:
>>>> On Tue, 25 Apr 2017 13:26:46 GMT, demerphq wrote:
>>>>>> >>>>>> Turn out I am wrong, and this was a fine trade off. Implementing >>>>>> Cox'es algorithm is nearly trivial from what I can tell. See (poorly >>>>>> tested) code in: >>>>>> >>>>>> cc026bf6160d7f86febc2fbc7a5d42ef93676e9f
>>>>> [snip]
>>>> #####
>>> >>> Thanks. FWIW, i realize my patch is wrong tho. Close but no cigar. I >>> need to fix it. >>> >>> cheers, >>> Yves >>>
>> >> I wasn't following this closely, but a patch got applied as 0db967b2e6a without the ticket being closed, and now os390 is failing >> >> # Failed test 'tried all the patterns without bailing out' >> # at ../ext/File-Glob/t/rt131211.t line 49. >> # got: '8' >> # expected: '10' >> # Failed test 'time to fail less than 10x the time to match' >> # at ../ext/File-Glob/t/rt131211.t line 54. >> # elapsed_match=0.292587518692017 elapsed_fail=52.9407045841217 >> # Looks like you failed 2 tests of 13. >> ext/File-Glob/t/rt131211 ...................................... FAILED at test 1
> > That is very weird. Does os390 use this code?
It looks like the hints file defines PERL_EXTERNAL_GLOB, so unless I'm missing something, we should just skip this test on all platforms where that is defined.
From: demerphq <demerphq [...] gmail.com>
Date: Tue, 11 Jul 2017 18:21:52 +0200
CC: Perl RT Bug Tracker <perlbug-followup [...] perl.org>, Perl5 Porteros <perl5-porters [...] perl.org>
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
To: Karl Williamson <public [...] khwilliamson.com>
Download (untitled) / with headers
text/plain 1.9k
On 11 July 2017 at 18:18, Karl Williamson <public@khwilliamson.com> wrote: Show quoted text
> On 07/11/2017 08:44 AM, demerphq wrote:
>> >> On 11 July 2017 at 04:32, Karl Williamson via RT >> <perlbug-followup@perl.org> wrote:
>>> >>> On Tue, 25 Apr 2017 07:22:34 -0700, demerphq wrote:
>>>> >>>> On 25 April 2017 at 15:55, James E Keenan via RT >>>> <perlbug-followup@perl.org> wrote:
>>>>> >>>>> On Tue, 25 Apr 2017 13:26:46 GMT, demerphq wrote:
>>>>>>> >>>>>>> >>>>>>> Turn out I am wrong, and this was a fine trade off. Implementing >>>>>>> Cox'es algorithm is nearly trivial from what I can tell. See (poorly >>>>>>> tested) code in: >>>>>>> >>>>>>> cc026bf6160d7f86febc2fbc7a5d42ef93676e9f
>>>>>> >>>>>> [snip]
>>>>> >>>>> #####
>>>> >>>> >>>> Thanks. FWIW, i realize my patch is wrong tho. Close but no cigar. I >>>> need to fix it. >>>> >>>> cheers, >>>> Yves >>>>
>>> >>> I wasn't following this closely, but a patch got applied as 0db967b2e6a >>> without the ticket being closed, and now os390 is failing >>> >>> # Failed test 'tried all the patterns without bailing out' >>> # at ../ext/File-Glob/t/rt131211.t line 49. >>> # got: '8' >>> # expected: '10' >>> # Failed test 'time to fail less than 10x the time to match' >>> # at ../ext/File-Glob/t/rt131211.t line 54. >>> # elapsed_match=0.292587518692017 elapsed_fail=52.9407045841217 >>> # Looks like you failed 2 tests of 13. >>> ext/File-Glob/t/rt131211 ...................................... FAILED at >>> test 1
>> >> >> That is very weird. Does os390 use this code?
> > > It looks like the hints file defines PERL_EXTERNAL_GLOB, so unless I'm > missing something, we should just skip this test on all platforms where that > is defined.
I would be happy if you were to apply that. On the other hand, if that is true then the os390 glob suffers the same underlying failure that this test and bugfix was trying to fix. So maybe they should just use our glob. Yves -- perl -Mre=debug -e "/just|another|perl|hacker/"
CC: Perl RT Bug Tracker <perlbug-followup [...] perl.org>, Perl5 Porteros <perl5-porters [...] perl.org>
From: Karl Williamson <public [...] khwilliamson.com>
Date: Tue, 11 Jul 2017 10:37:42 -0600
To: demerphq <demerphq [...] gmail.com>
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
Download (untitled) / with headers
text/plain 2.1k
On 07/11/2017 10:21 AM, demerphq wrote: Show quoted text
> On 11 July 2017 at 18:18, Karl Williamson <public@khwilliamson.com> wrote:
>> On 07/11/2017 08:44 AM, demerphq wrote:
>>> >>> On 11 July 2017 at 04:32, Karl Williamson via RT >>> <perlbug-followup@perl.org> wrote:
>>>> >>>> On Tue, 25 Apr 2017 07:22:34 -0700, demerphq wrote:
>>>>> >>>>> On 25 April 2017 at 15:55, James E Keenan via RT >>>>> <perlbug-followup@perl.org> wrote:
>>>>>> >>>>>> On Tue, 25 Apr 2017 13:26:46 GMT, demerphq wrote:
>>>>>>>> >>>>>>>> >>>>>>>> Turn out I am wrong, and this was a fine trade off. Implementing >>>>>>>> Cox'es algorithm is nearly trivial from what I can tell. See (poorly >>>>>>>> tested) code in: >>>>>>>> >>>>>>>> cc026bf6160d7f86febc2fbc7a5d42ef93676e9f
>>>>>>> >>>>>>> [snip]
>>>>>> >>>>>> #####
>>>>> >>>>> >>>>> Thanks. FWIW, i realize my patch is wrong tho. Close but no cigar. I >>>>> need to fix it. >>>>> >>>>> cheers, >>>>> Yves >>>>>
>>>> >>>> I wasn't following this closely, but a patch got applied as 0db967b2e6a >>>> without the ticket being closed, and now os390 is failing >>>> >>>> # Failed test 'tried all the patterns without bailing out' >>>> # at ../ext/File-Glob/t/rt131211.t line 49. >>>> # got: '8' >>>> # expected: '10' >>>> # Failed test 'time to fail less than 10x the time to match' >>>> # at ../ext/File-Glob/t/rt131211.t line 54. >>>> # elapsed_match=0.292587518692017 elapsed_fail=52.9407045841217 >>>> # Looks like you failed 2 tests of 13. >>>> ext/File-Glob/t/rt131211 ...................................... FAILED at >>>> test 1
>>> >>> >>> That is very weird. Does os390 use this code?
>> >> >> It looks like the hints file defines PERL_EXTERNAL_GLOB, so unless I'm >> missing something, we should just skip this test on all platforms where that >> is defined.
> > I would be happy if you were to apply that. On the other hand, if that > is true then the os390 glob suffers the same underlying failure that > this test and bugfix was trying to fix. So maybe they should just use > our glob. > > Yves > >
But there is a reason for them not using ours. ISTR the expansions have incompatibilities with ours
CC: Perl RT Bug Tracker <perlbug-followup [...] perl.org>, Perl5 Porteros <perl5-porters [...] perl.org>
From: demerphq <demerphq [...] gmail.com>
Date: Tue, 11 Jul 2017 18:52:34 +0200
To: Karl Williamson <public [...] khwilliamson.com>
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
Download (untitled) / with headers
text/plain 2.4k
On 11 July 2017 at 18:37, Karl Williamson <public@khwilliamson.com> wrote: Show quoted text
> On 07/11/2017 10:21 AM, demerphq wrote:
>> >> On 11 July 2017 at 18:18, Karl Williamson <public@khwilliamson.com> wrote:
>>> >>> On 07/11/2017 08:44 AM, demerphq wrote:
>>>> >>>> >>>> On 11 July 2017 at 04:32, Karl Williamson via RT >>>> <perlbug-followup@perl.org> wrote:
>>>>> >>>>> >>>>> On Tue, 25 Apr 2017 07:22:34 -0700, demerphq wrote:
>>>>>> >>>>>> >>>>>> On 25 April 2017 at 15:55, James E Keenan via RT >>>>>> <perlbug-followup@perl.org> wrote:
>>>>>>> >>>>>>> >>>>>>> On Tue, 25 Apr 2017 13:26:46 GMT, demerphq wrote:
>>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> Turn out I am wrong, and this was a fine trade off. Implementing >>>>>>>>> Cox'es algorithm is nearly trivial from what I can tell. See >>>>>>>>> (poorly >>>>>>>>> tested) code in: >>>>>>>>> >>>>>>>>> cc026bf6160d7f86febc2fbc7a5d42ef93676e9f
>>>>>>>> >>>>>>>> >>>>>>>> [snip]
>>>>>>> >>>>>>> >>>>>>> #####
>>>>>> >>>>>> >>>>>> >>>>>> Thanks. FWIW, i realize my patch is wrong tho. Close but no cigar. I >>>>>> need to fix it. >>>>>> >>>>>> cheers, >>>>>> Yves >>>>>>
>>>>> >>>>> I wasn't following this closely, but a patch got applied as 0db967b2e6a >>>>> without the ticket being closed, and now os390 is failing >>>>> >>>>> # Failed test 'tried all the patterns without bailing out' >>>>> # at ../ext/File-Glob/t/rt131211.t line 49. >>>>> # got: '8' >>>>> # expected: '10' >>>>> # Failed test 'time to fail less than 10x the time to match' >>>>> # at ../ext/File-Glob/t/rt131211.t line 54. >>>>> # elapsed_match=0.292587518692017 elapsed_fail=52.9407045841217 >>>>> # Looks like you failed 2 tests of 13. >>>>> ext/File-Glob/t/rt131211 ...................................... FAILED >>>>> at >>>>> test 1
>>>> >>>> >>>> >>>> That is very weird. Does os390 use this code?
>>> >>> >>> >>> It looks like the hints file defines PERL_EXTERNAL_GLOB, so unless I'm >>> missing something, we should just skip this test on all platforms where >>> that >>> is defined.
>> >> >> I would be happy if you were to apply that. On the other hand, if that >> is true then the os390 glob suffers the same underlying failure that >> this test and bugfix was trying to fix. So maybe they should just use >> our glob. >> >> Yves >> >>
> > But there is a reason for them not using ours. ISTR the expansions have > incompatibilities with ours
Hmm. Well I guess I cant be responsible for fixing that. ;-) Yves -- perl -Mre=debug -e "/just|another|perl|hacker/"
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
To: demerphq <demerphq [...] gmail.com>
CC: Perl RT Bug Tracker <perlbug-followup [...] perl.org>, Perl5 Porteros <perl5-porters [...] perl.org>
Date: Thu, 13 Jul 2017 22:45:08 -0600
From: Karl Williamson <public [...] khwilliamson.com>
Download (untitled) / with headers
text/plain 2.7k
On 07/11/2017 10:52 AM, demerphq wrote: Show quoted text
> On 11 July 2017 at 18:37, Karl Williamson <public@khwilliamson.com> wrote:
>> On 07/11/2017 10:21 AM, demerphq wrote:
>>> >>> On 11 July 2017 at 18:18, Karl Williamson <public@khwilliamson.com> wrote:
>>>> >>>> On 07/11/2017 08:44 AM, demerphq wrote:
>>>>> >>>>> >>>>> On 11 July 2017 at 04:32, Karl Williamson via RT >>>>> <perlbug-followup@perl.org> wrote:
>>>>>> >>>>>> >>>>>> On Tue, 25 Apr 2017 07:22:34 -0700, demerphq wrote:
>>>>>>> >>>>>>> >>>>>>> On 25 April 2017 at 15:55, James E Keenan via RT >>>>>>> <perlbug-followup@perl.org> wrote:
>>>>>>>> >>>>>>>> >>>>>>>> On Tue, 25 Apr 2017 13:26:46 GMT, demerphq wrote:
>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> Turn out I am wrong, and this was a fine trade off. Implementing >>>>>>>>>> Cox'es algorithm is nearly trivial from what I can tell. See >>>>>>>>>> (poorly >>>>>>>>>> tested) code in: >>>>>>>>>> >>>>>>>>>> cc026bf6160d7f86febc2fbc7a5d42ef93676e9f
>>>>>>>>> >>>>>>>>> >>>>>>>>> [snip]
>>>>>>>> >>>>>>>> >>>>>>>> #####
>>>>>>> >>>>>>> >>>>>>> >>>>>>> Thanks. FWIW, i realize my patch is wrong tho. Close but no cigar. I >>>>>>> need to fix it. >>>>>>> >>>>>>> cheers, >>>>>>> Yves >>>>>>>
>>>>>> >>>>>> I wasn't following this closely, but a patch got applied as 0db967b2e6a >>>>>> without the ticket being closed, and now os390 is failing >>>>>> >>>>>> # Failed test 'tried all the patterns without bailing out' >>>>>> # at ../ext/File-Glob/t/rt131211.t line 49. >>>>>> # got: '8' >>>>>> # expected: '10' >>>>>> # Failed test 'time to fail less than 10x the time to match' >>>>>> # at ../ext/File-Glob/t/rt131211.t line 54. >>>>>> # elapsed_match=0.292587518692017 elapsed_fail=52.9407045841217 >>>>>> # Looks like you failed 2 tests of 13. >>>>>> ext/File-Glob/t/rt131211 ...................................... FAILED >>>>>> at >>>>>> test 1
>>>>> >>>>> >>>>> >>>>> That is very weird. Does os390 use this code?
>>>> >>>> >>>> >>>> It looks like the hints file defines PERL_EXTERNAL_GLOB, so unless I'm >>>> missing something, we should just skip this test on all platforms where >>>> that >>>> is defined.
>>> >>> >>> I would be happy if you were to apply that. On the other hand, if that >>> is true then the os390 glob suffers the same underlying failure that >>> this test and bugfix was trying to fix. So maybe they should just use >>> our glob. >>> >>> Yves >>> >>>
>> >> But there is a reason for them not using ours. ISTR the expansions have >> incompatibilities with ours
> > Hmm. Well I guess I cant be responsible for fixing that. ;-) > > Yves > >
I have now pushed a commit to blead that skips this test if ccflags has -DPERL_EXTERNAL_GLOB in it: 5a993d81c4b1abf13cd3ae4cbc04f26c7516bc37 Is there a reason this ticket hasn't been closed?
To: Karl Williamson <public [...] khwilliamson.com>
CC: demerphq <demerphq [...] gmail.com>, Perl RT Bug Tracker <perlbug-followup [...] perl.org>, Perl5 Porteros <perl5-porters [...] perl.org>
Subject: Re: [perl #131211] The glob() function is exponential on pathological patterns
Date: Tue, 20 Mar 2018 13:37:50 +0000
From: Dave Mitchell <davem [...] iabyn.com>
Download (untitled) / with headers
text/plain 534b
On Thu, Jul 13, 2017 at 10:45:08PM -0600, Karl Williamson wrote: Show quoted text
> I have now pushed a commit to blead that skips this test if ccflags has > -DPERL_EXTERNAL_GLOB in it: > 5a993d81c4b1abf13cd3ae4cbc04f26c7516bc37 > > Is there a reason this ticket hasn't been closed?
There was an issue with ext/File-Glob/t/rt131211.t intermittently failing due to timing issues. I tried fixing that a month ago with v5.27.8-405-gf548aec and have not seen any smoke failures since, so I'm closing the ticket now. -- You're only as old as you look.


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

For issues related to this RT instance (aka "perlbug"), please contact perlbug-admin at perl.org