Slow global pattern match if match fails

[p5pRT]

Migrated from rt.perl.org#120446 (status was 'resolved')

Searchable as RT120446$

[p5pRT]

From @hknutzen

This is a bug report for perl from heinz.knutzen@​gmail.com,
generated with the help of perlbug 1.39 running under perl 5.19.5.

---

I tried perl 5.19.5 to increase the runtime performance of my perl
application.
But it became much slower.

The problem can be shown at this small example.

slow.pl

my $in = 'a' x shift . 'b';
while ($in =~ /\Ga/g) {
  last if ($in =~/\Gb/gc);
}
<<<<<<<<<<<<<<<<<<<<

If run with version 5.19.5, the runtime grows quadratically with the
size of $in.
With version 5.18.0, the runtime grows linearly.

Runtime for both versions of perl​:
for i in 1 2 4 8 16; do /usr/bin/time -f "%Us" perl5.19.5 slow.pl
${i}0000; done
0.08s
0.30s
1.18s
4.66s
18.54s
for i in 1 2 4 8 16; do /usr/bin/time -f "%Us" perl5.18.0 slow.pl
${i}0000; done
0.01s
0.03s
0.04s
0.06s
0.12s

---

---

Flags​:
  category=core
  severity=low

---

Site configuration information for perl 5.19.5​:

Configured by hk at Sat Nov 2 22​:50​:53 CET 2013.

Summary of my perl5 (revision 5 version 19 subversion 5) configuration​:
 
  Platform​:
  osname=linux, osvers=3.8.0-33-generic, archname=i686-linux
  uname='linux buero 3.8.0-33-generic #48~precise1-ubuntu smp thu oct
24 16​:31​:16 utc 2013 i686 athlon i386 gnulinux '
  config_args='-de -Dprefix=/home/hk/perl5/perlbrew/perls/perl-5.19.5
-Dusedevel'
  hint=recommended, useposix=true, d_sigaction=define
  useithreads=undef, usemultiplicity=undef
  useperlio=define, d_sfio=undef, uselargefiles=define, usesocks=undef
  use64bitint=undef, use64bitall=undef, uselongdouble=undef
  usemymalloc=n, bincompat5005=undef
  Compiler​:
  cc='cc', ccflags ='-fno-strict-aliasing -pipe -fstack-protector
-I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64',
  optimize='-O2',
  cppflags='-fno-strict-aliasing -pipe -fstack-protector
-I/usr/local/include'
  ccversion='', gccversion='4.6.3', gccosandvers=''
  intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=1234
  d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=12
  ivtype='long', ivsize=4, nvtype='double', nvsize=8, Off_t='off_t',
lseeksize=8
  alignbytes=4, prototype=define
  Linker and Libraries​:
  ld='cc', ldflags =' -fstack-protector -L/usr/local/lib'
  libpth=/usr/local/lib /lib/i386-linux-gnu /lib/../lib
/usr/lib/i386-linux-gnu /usr/lib/../lib /lib /usr/lib
  libs=-lnsl -ldl -lm -lcrypt -lutil -lc
  perllibs=-lnsl -ldl -lm -lcrypt -lutil -lc
  libc=, so=so, useshrplib=false, libperl=libperl.a
  gnulibc_version='2.15'
  Dynamic Linking​:
  dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E'
  cccdlflags='-fPIC', lddlflags='-shared -O2 -L/usr/local/lib
-fstack-protector'

---

@​INC for perl 5.19.5​:
 
/home/hk/perl5/perlbrew/perls/perl-5.19.5/lib/site_perl/5.19.5/i686-linux
  /home/hk/perl5/perlbrew/perls/perl-5.19.5/lib/site_perl/5.19.5
  /home/hk/perl5/perlbrew/perls/perl-5.19.5/lib/5.19.5/i686-linux
  /home/hk/perl5/perlbrew/perls/perl-5.19.5/lib/5.19.5
  .

---

Environment for perl 5.19.5​:
  HOME=/home/hk
  LANG=de_DE.UTF-8
  LANGUAGE=de_DE​:en
  LD_LIBRARY_PATH (unset)
  LOGDIR (unset)
 
PATH=/home/hk/perl5/perlbrew/bin​:/home/hk/perl5/perlbrew/perls/perl-5.19.5/bin​:/home/hk/bin​:/usr/local/sbin​:/usr/local/bin​:/usr/sbin​:/usr/bin​:/sbin​:/bin
  PERLBREW_BASHRC_VERSION=0.43
  PERLBREW_HOME=/home/hk/.perlbrew
  PERLBREW_MANPATH=/home/hk/perl5/perlbrew/perls/perl-5.19.5/man
 
PERLBREW_PATH=/home/hk/perl5/perlbrew/bin​:/home/hk/perl5/perlbrew/perls/perl-5.19.5/bin
  PERLBREW_PERL=perl-5.19.5
  PERLBREW_ROOT=/home/hk/perl5/perlbrew
  PERLBREW_VERSION=0.43
  PERL_BADLANG (unset)
  SHELL=/bin/bash

[p5pRT]

From @wolfsage

$ ../perl-1/Porting/bisect.pl -j 4 -e 'my $in = "a" x 160000 . "b";
while ($in =~ /\Ga/g) { last if ($in =~ /\Gb/gc); }' --timeout 2
--start=v5.18.0 --end=v5.19.5

HEAD is now at cf44e60 fix intuit_start() with \G
bad - Timeout when running ./perl -Ilib -e my $in = "a" x 160000 .
"b"; while ($in =~ /\Ga/g) { last
if ($in =~ /\Gb/gc); }
cf44e60 is the first bad commit
commit cf44e60
Author​: David Mitchell <davem@​iabyn.com>
Date​: Fri Jul 19 02​:08​:56 2013 +0100

  fix intuit_start() with \G

  Intuit assumed that any anchor, including \G, anchored at BOS or after \n.
  This obviously isn't the case for \G, so exclude RXf_ANCH_GPOS from the
  RXf_ANCH branch.

  This has never been spotted before, since intuit used to be skipped when
  \G was present.

:100644 100644 94dc3ceb53b08a5c9cac8f162abeb9799242f8f1
43d66c911f9e6f8f3f79816c4f699f7a3cc33b99 Mreg
exec.c
:040000 040000 d984c77a33b2e7052c218fbd912632caec44e55e
0be87202a125e169d15babd243ca136806367370 Mt
bisect run success
That took 1416 seconds

-- Matthew Horsfall (alh)

[p5pRT]

The RT System itself - Status changed from 'new' to 'open'

[p5pRT]

From @iabyn

On Sun, Nov 03, 2013 at 11​:13​:48AM -0500, Matthew Horsfall (alh) wrote​:

$ ../perl-1/Porting/bisect.pl -j 4 -e 'my $in = "a" x 160000 . "b";
while ($in =~ /\Ga/g) { last if ($in =~ /\Gb/gc); }' --timeout 2
--start=v5.18.0 --end=v5.19.5

HEAD is now at cf44e60 fix intuit_start() with \G
bad - Timeout when running ./perl -Ilib -e my $in = "a" x 160000 .
"b"; while ($in =~ /\Ga/g) { last
if ($in =~ /\Gb/gc); }
cf44e60 is the first bad commit
commit cf44e60
Author​: David Mitchell <davem@​iabyn.com>
Date​: Fri Jul 19 02​:08​:56 2013 +0100

fix intuit\_start\(\) with \\G

Now fixed with this​:

commit 0b2c2a8
Author​: David Mitchell <davem@​iabyn.com>
AuthorDate​: Tue Nov 5 12​:29​:07 2013 +0000
Commit​: David Mitchell <davem@​iabyn.com>
CommitDate​: Tue Nov 5 12​:33​:25 2013 +0000

  RT #120446​: /\Ga/ running slowly on long strings
 
  This commit reverts my commit cf44e60
  (except for the tests), which incorrectly disabled fix-string intuiting
  in the presence of anchored \G. I thought that the old behaviour was
  logically incorrect, but it wasn't (or at least I don't see it that way
  now, and none of the tests I added at the time fail under the old regime).

M regexec.c
M t/re/pat.t

--
"Strange women lying in ponds distributing swords is no basis for a system
of government. Supreme executive power derives from a mandate from the
masses, not from some farcical aquatic ceremony."
  -- Dennis, "Monty Python and the Holy Grail"

[p5pRT]

@iabyn - Status changed from 'open' to 'resolved'