Benchmark sequences vs left recursion

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;

}

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%     --