The following code builds a large alternation regex which on 5.10.0 should cause demerphq's cool tries code to kick in, and it seems to. When I specify 13,104 alternations, it can search a 1MB string in under 3 seconds which is very impressive. However, if I increase it by one alternation to 13,105, it suddenly goes pathelogical and takes 646 seconds to complete the same task.

The alternations I am using are 10-chars giving an array size of 13,105 * 10 + internals ~= 128k. This number rings a bell. I seem to recall that this is the magic number at which memory allocations bypass the normal allocation mechanism and go straight to allocating virtual memory? I've done a cursory grep of the sources trying to confirm this without success. Does anyone know anything about it?

It would also be useful to know if 5.10 builds other than AS1000 are similarly affected. If anyone with such a build has the time to try this out for me, the required command line options are shown after the __END__ token below:

#! perl -slw
use strict;

$|++;

srand 1;

sub rndStr{ join'', @_[ map{ rand @_ } 1 .. shift ] }

our $N ||= 1000;
our $S ||= 30e6;

my $chrom = chr(0) x $S;
substr( $chrom, $_, 1, ('A', 'C', 'G', 'T' )[ rand 4 ] ) for 0 .. $S-1
+;

my @probes = map rndStr( 10, 'A', 'C', 'G', 'T' ), 0 .. $N;

warn "Trying $N probes with perl $]";

warn time;
my $re = join '|', @probes[ 0 .. $N ];
$re = qr[$re];

printf "$-[ 0 ] : '$1'\n" while $chrom =~ m[($re)]g;

print "\n";
warn time;

__END__
C:\test>\Perl510\bin\perl5.10.0.exe -s 668954.p10 -S=1e6 -N=13104 | wc
+ -l
Trying 13104 probes with perl 5.010000 at 668954.p10 line 18.
1203549864 at 668954.p10 line 20.
1203549867 at 668954.p10 line 27.
  11282

C:\test>\Perl510\bin\perl5.10.0.exe -s 668954.p10 -S=1e6 -N=13105 | wc
+ -l
Trying 13105 probes with perl 5.010000 at 668954.p10 line 18.
1203549872 at 668954.p10 line 20.
1203550518 at 668954.p10 line 27.
  11282
[download]