develooper Front page | perl.perl5.porters | Postings from April 2017

[perl #131211] The glob() function is exponential on pathologicalpatterns

Thread Previous | Thread Next
From:
"Ævar" "Arnfjörð" Bjarmason
Date:
April 25, 2017 07:55
Subject:
[perl #131211] The glob() function is exponential on pathologicalpatterns
Message ID:
rt-4.0.24-9116-1493106941-441.131211-75-0@perl.org
# 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


[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


Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About