Skip to content

Instantly share code, notes, and snippets.

@rns

rns/bslr.pl

Last active August 27, 2015 21:02
Show Gist options
  • Save rns/84605eb1551d45918e2b to your computer and use it in GitHub Desktop.
Save rns/84605eb1551d45918e2b to your computer and use it in GitHub Desktop.
Download ZIP
Benchmark sequences vs left recursion
Raw
bslr.pl
#!/usr/bin/env perl
use 5.010;
use strict;
use warnings;
use Marpa::R2;
use Getopt::Long;
use constant ITEM_COUNT_START => 5000;
use constant ITEM_COUNT_END => 30000;
use constant ITEM_COUNT_STEP => 5000;
my ($start, $end, $step) = (ITEM_COUNT_START, ITEM_COUNT_END, ITEM_COUNT_STEP);
use constant CMP_COUNT => -5;
my ($cmp_count);
$cmp_count = CMP_COUNT;
sub usage {
die <<"END_OF_USAGE_MESSAGE";
$0: Benchmark Sequences vs. Left Recursion in Marpa
Usage: $0 [ --help ] [ --cmpcount count ] [ --range start end step ]
Runs benchmark of Marpa::R2 sequences vs. left recursion
in the specified range of sequence sizes.
Options:
--help: this message
--range start end step: sets the range of sequence sizes.
Default range of sequence sizes: start = $start, end = $end, step = $step
--cmpcount count: sets the value of \$count arg of Benchmark’s timethese().
Default value: $cmp_count. Hint: set -5 to run the code for 5 CPU seconds,
10 to run it 10 times.\n
END_OF_USAGE_MESSAGE
}
my ($help, @range);
GetOptions('help' => \$help, 'range=i{3}' => \@range, 'cmpcount=i' => \$cmp_count);
do { usage(); exit 0 } if $help;
say q{ Benchmark Marpa Sequences vs. Left Recursion };
say q{===================================================================};
say q{Legend: CS = Comma-Separated, NS = uNSeparated, LR = left recursion};
say q{-------------------------------------------------------------------};
if (@range){
($start, $end, $step) = @range;
say qq{Using custom range of sequence sizes: $start-$end \@$step};
}
else{
say qq{Using default range of sequence sizes: $start-$end \@$step};
}
if ($cmp_count != CMP_COUNT){
say qq{Using custom timethese() count = $cmp_count};
}
else{
say qq{Using default timethese() count = $cmp_count};
}
my $rules = {
'CS SEQ' => [
q{ sequence ::= item+ separator => [,] },
[ ['item'], ['item'] ]
],
'CS LR' => [
q{ sequence ::= item | sequence (',') item },
[ [ ['item'] ], ['item'] ]
],
'NS SEQ' => [
q{ sequence ::= item+ },
[ ['item'], ['item'] ]
],
'NS LR' => [
q{ sequence ::= item | sequence item },
[ [ ['item'] ], ['item'] ]
],
};
say q{-------------------------------------------------------------------};
say q{Expected run time: approx. },
$cmp_count * keys( %{$rules} ) * ( ( $start - $end ) / $step ),
q{ seconds.};
say q{-------------------------------------------------------------------};
my $g_template = q{
:default ::= action => [ value ]
lexeme default = action => [ value ] latm => 1
__SEQUENCE_RULES__
item ~ 'item'
:discard ~ whitespace
whitespace ~ [\s]+
};
say q{Preparing and testing closures.};
my $comma_separated_input;
my $unseparated_input;
use Test::More;
for my $desc ( keys %{ $rules } ){
my ($rule, $expected_value) = @{ $rules->{$desc} };
my $g_source = $g_template;
$g_source =~ s/__SEQUENCE_RULES__/$rule/;
my $g = Marpa::R2::Scanless::G->new( { source => \$g_source } );
my $sub;
if ($desc =~ /^NS /){
$sub = sub { $g->parse( \$unseparated_input ) };
$unseparated_input = 'item item';
die unless is_deeply ${ $sub->() }, $expected_value, "$desc closure";
}
elsif ($desc =~ /^CS /){
$sub = sub { $g->parse( \$comma_separated_input ) };
$comma_separated_input = 'item, item';
die unless is_deeply ${ $sub->() }, $expected_value, "$desc closure";
}
$rules->{$desc} = $sub;
}
done_testing;
say q{Closures prepared and tested.};
say q{-------------------------------------------------------------------};
use Benchmark qw{ timethese cmpthese };
for (
my $item_count = $start; $item_count <= $end; $item_count += $step
){
say "\n# Sequence size: $item_count items\n";
$comma_separated_input = 'item, ' x $item_count;
chop $comma_separated_input for 1..2;
$unseparated_input = 'item ' x $item_count;
chop $unseparated_input;
my $r = timethese ($cmp_count, $rules);
say q{-------------------------------------------------------------------};
cmpthese $r;
}
Raw
output
Benchmark Marpa Sequences vs. Left Recursion
===================================================================
Legend: CS = Comma-Separated, NS = uNSeparated, LR = left recursion
-------------------------------------------------------------------
Using default range of sequence sizes: 5000-30000 @5000
Using default timethese() count = -5
-------------------------------------------------------------------
Expected run time: approx. 100 seconds.
-------------------------------------------------------------------
Preparing and testing closures.
ok 1 - NS LR closure
ok 2 - CS LR closure
ok 3 - NS SEQ closure
ok 4 - CS SEQ closure
1..4
Closures prepared and tested.
-------------------------------------------------------------------
# Sequence size: 5000 items
Benchmark: running CS LR, CS SEQ, NS LR, NS SEQ for at least 5 CPU seconds...
CS LR: 6 wallclock secs ( 5.44 usr + 0.00 sys = 5.44 CPU) @ 7.72/s (n=42)
CS SEQ: 6 wallclock secs ( 5.44 usr + 0.00 sys = 5.44 CPU) @ 7.72/s (n=42)
NS LR: 5 wallclock secs ( 5.25 usr + 0.00 sys = 5.25 CPU) @ 11.24/s (n=59)
NS SEQ: 5 wallclock secs ( 5.38 usr + 0.00 sys = 5.38 CPU) @ 11.72/s (n=63)
-------------------------------------------------------------------
Rate CS SEQ CS LR NS LR NS SEQ
CS SEQ 7.72/s -- 0% -31% -34%
CS LR 7.72/s 0% -- -31% -34%
NS LR 11.2/s 46% 46% -- -4%
NS SEQ 11.7/s 52% 52% 4% --
# Sequence size: 10000 items
Benchmark: running CS LR, CS SEQ, NS LR, NS SEQ for at least 5 CPU seconds...
CS LR: 5 wallclock secs ( 5.22 usr + 0.01 sys = 5.23 CPU) @ 3.82/s (n=20)
CS SEQ: 5 wallclock secs ( 4.98 usr + 0.02 sys = 5.00 CPU) @ 3.80/s (n=19)
NS LR: 5 wallclock secs ( 5.06 usr + 0.00 sys = 5.06 CPU) @ 5.53/s (n=28)
NS SEQ: 5 wallclock secs ( 5.27 usr + 0.00 sys = 5.27 CPU) @ 5.70/s (n=30)
-------------------------------------------------------------------
Rate CS SEQ CS LR NS LR NS SEQ
CS SEQ 3.80/s -- -1% -31% -33%
CS LR 3.82/s 1% -- -31% -33%
NS LR 5.53/s 46% 45% -- -3%
NS SEQ 5.70/s 50% 49% 3% --
# Sequence size: 15000 items
Benchmark: running CS LR, CS SEQ, NS LR, NS SEQ for at least 5 CPU seconds...
CS LR: 6 wallclock secs ( 5.20 usr + 0.00 sys = 5.20 CPU) @ 2.50/s (n=13)
CS SEQ: 5 wallclock secs ( 5.27 usr + 0.02 sys = 5.28 CPU) @ 2.46/s (n=13)
NS LR: 5 wallclock secs ( 5.00 usr + 0.00 sys = 5.00 CPU) @ 3.60/s (n=18)
NS SEQ: 5 wallclock secs ( 5.14 usr + 0.00 sys = 5.14 CPU) @ 3.70/s (n=19)
-------------------------------------------------------------------
Rate CS SEQ CS LR NS LR NS SEQ
CS SEQ 2.46/s -- -1% -32% -33%
CS LR 2.50/s 2% -- -31% -32%
NS LR 3.60/s 46% 44% -- -3%
NS SEQ 3.70/s 50% 48% 3% --
# Sequence size: 20000 items
Benchmark: running CS LR, CS SEQ, NS LR, NS SEQ for at least 5 CPU seconds...
CS LR: 6 wallclock secs ( 5.42 usr + 0.00 sys = 5.42 CPU) @ 1.84/s (n=10)
CS SEQ: 6 wallclock secs ( 5.39 usr + 0.00 sys = 5.39 CPU) @ 1.85/s (n=10)
NS LR: 5 wallclock secs ( 5.20 usr + 0.00 sys = 5.20 CPU) @ 2.69/s (n=14)
NS SEQ: 5 wallclock secs ( 5.05 usr + 0.00 sys = 5.05 CPU) @ 2.77/s (n=14)
-------------------------------------------------------------------
Rate CS LR CS SEQ NS LR NS SEQ
CS LR 1.84/s -- -1% -31% -33%
CS SEQ 1.85/s 1% -- -31% -33%
NS LR 2.69/s 46% 45% -- -3%
NS SEQ 2.77/s 50% 50% 3% --
# Sequence size: 25000 items
Benchmark: running CS LR, CS SEQ, NS LR, NS SEQ for at least 5 CPU seconds...
CS LR: 6 wallclock secs ( 5.44 usr + 0.00 sys = 5.44 CPU) @ 1.47/s (n=8)
CS SEQ: 5 wallclock secs ( 5.37 usr + 0.00 sys = 5.37 CPU) @ 1.49/s (n=8)
NS LR: 5 wallclock secs ( 5.20 usr + 0.00 sys = 5.20 CPU) @ 2.11/s (n=11)
NS SEQ: 6 wallclock secs ( 5.41 usr + 0.00 sys = 5.41 CPU) @ 2.22/s (n=12)
-------------------------------------------------------------------
Rate CS LR CS SEQ NS LR NS SEQ
CS LR 1.47/s -- -1% -30% -34%
CS SEQ 1.49/s 1% -- -30% -33%
NS LR 2.11/s 44% 42% -- -5%
NS SEQ 2.22/s 51% 49% 5% --
# Sequence size: 30000 items
Benchmark: running CS LR, CS SEQ, NS LR, NS SEQ for at least 5 CPU seconds...
CS LR: 5 wallclock secs ( 5.73 usr + 0.02 sys = 5.75 CPU) @ 1.22/s (n=7)
CS SEQ: 6 wallclock secs ( 5.67 usr + 0.00 sys = 5.67 CPU) @ 1.23/s (n=7)
NS LR: 5 wallclock secs ( 5.11 usr + 0.00 sys = 5.11 CPU) @ 1.76/s (n=9)
NS SEQ: 6 wallclock secs ( 5.45 usr + 0.00 sys = 5.45 CPU) @ 1.83/s (n=10)
-------------------------------------------------------------------
Rate CS LR CS SEQ NS LR NS SEQ
CS LR 1.22/s -- -1% -31% -34%
CS SEQ 1.23/s 1% -- -30% -33%
NS LR 1.76/s 45% 43% -- -4%
NS SEQ 1.83/s 51% 49% 4% --
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment