X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/0925d5bfd40aac15b9c55cd1b60e28befc4bd55d..59c544c2683a1ce534404a4891b7e3435e3a242c:/etc/bench.pl.in diff --git a/etc/bench.pl.in b/etc/bench.pl.in index ca433493..ae50516f 100755 --- a/etc/bench.pl.in +++ b/etc/bench.pl.in @@ -17,17 +17,149 @@ # You should have received a copy of the GNU General Public License # along with this program. If not, see . +=head1 NAME + +bench.pl - perform benches on Bison parsers. + +=head1 SYNOPSIS + + ./bench.pl + +=head1 OPTIONS + +=over 4 + +=item B<-c>, B<--cflags>=I + +Flags to pass to the C or C++ compiler. + +=item B<-i>, B<--iterations>=I + +Say how many times a single test of the bench must be run. If +negative, specify the minimum number of CPU seconds to run. Defaults +to -3. + +=item B<-v>, B<--verbose> + +Raise the verbosity level. Currently only affects B<--help>. + +=back + +=cut + use IO::File; -use Benchmark qw (:all); + +################################################################## + +=head1 VARIABLES + +=over 4 + +=item C<$bison> + +The Bison program to use to compile the grammar. + +=item C<$cc> + +The C compiler. + +=item C<$cxx> + +The C++ compiler. + +=item C<$cflags> + +Compiler flags (C or C++). + +=item C<$iterations> + +The number of times the parser is run for a bench. + +=item C<$verbose> + +Verbosity level. + +=back + +=cut my $bison = $ENV{'BISON'} || '@abs_top_builddir@/tests/bison'; my $cc = $ENV{'CC'} || 'gcc'; +my $cxx = $ENV{'CXX'} || 'g++'; +my $cflags = ''; +my $iterations = -3; +my $verbose = 0; -################################################################## +=head1 FUNCTIONS + +=over 4 + +=item C + +Report the C<$message> is C<$level> E= C<$verbose>. + +=cut + +sub verbose($$) +{ + my ($level, $message) = @_; + print STDERR $message + if $level <= $verbose; +} + +=item C + +Format the list of directives for Bison for bench named C<$bench>. + +The special fake C<%variant> directive requests the use of +Boost.Variants instead of a regular union. So don't pass it, it is +not a valid directive. + +=cut + +sub directives($@) +{ + my ($bench, @directive) = @_; + my $res = "/* Directives for bench `$bench'. */\n"; + for my $d (@directive) + { + $res .= $d . "\n" + unless $d eq '%variant'; + } + $res .= "/* End of directives for bench `$bench'. */\n"; + return $res; +} + +=item C + +Create a large triangular grammar which looks like : + + input: + exp { if ($1 != 0) abort (); $$ = $1; } + | input exp { if ($2 != $1 + 1) abort (); $$ = $2; } + ; + + exp: + END { $$ = 0; } + | "1" END { $$ = 1; } + | "1" "2" END { $$ = 2; } + | "1" "2" "3" END { $$ = 3; } + | "1" "2" "3" "4" END { $$ = 4; } + | "1" "2" "3" "4" "5" END { $$ = 5; } + ; + +C<$base> is the base name for the file to create (F<$base.y>). +C<$max> is the number of such rules (here, 5). You may pass +additional Bison C<@directive>. + +The created parser is self contained: it includes its scanner, and +source of input. +=cut sub triangular_grammar ($$$) { - my ($base, $max, $directives) = @_; + my ($base, $max, @directive) = @_; + my $directives = directives ($base, @directive); my $out = new IO::File ">$base.y" or die; @@ -41,6 +173,7 @@ sub triangular_grammar ($$$) static int yylex (void); static void yyerror (const char *msg); %} +$directives %union { int val; @@ -112,6 +245,15 @@ EOF ################################################################## +=item C + +Generate the input file F<$base.input> for the calc parser. The input +is composed of two expressions. The first one is using left recursion +only and consumes no stack. The second one requires a deep stack. +These two expressions are repeated C<$max> times in the output file. + +=cut + sub calc_input ($$) { my ($base, $max) = @_; @@ -125,10 +267,18 @@ sub calc_input ($$) } ################################################################## +=item C + +Generate a Bison file F<$base.y> for a calculator parser in C. Pass +the additional Bison C<@directive>. C<$max> is ignored, but left to +have the same interface as C. + +=cut sub calc_grammar ($$$) { - my ($base, $max, $directives) = @_; + my ($base, $max, @directive) = @_; + my $directives = directives ($base, @directive); my $out = new IO::File ">$base.y" or die; @@ -148,9 +298,9 @@ static semantic_value global_result = 0; static int global_count = 0; %} -/* Exercise %union. */ $directives %error-verbose +/* Exercise %union. */ %union { semantic_value ival; @@ -327,44 +477,330 @@ EOF ################################################################## +=item C + +Generate a Bison file F<$base.y> that uses, or not, the Boost.Variants +depending on the C<@directive>. + +=cut + +sub variant_grammar ($$$) +{ + my ($base, $max, @directive) = @_; + my $directives = directives ($base, @directive); + my $variant = grep { $_ eq '%variant' } @directive; + + my $out = new IO::File ">$base.y" + or die; + print $out < +} + +%code // variant.c +{ +#include +#include +#include + +// Prototype of the yylex function providing subsequent tokens. +static yy::parser::token_type yylex(yy::parser::semantic_type* yylval); + +#define STAGE_MAX ($max * 10) +#define USE_VARIANTS $variant +#if USE_VARIANTS +# define IF_VARIANTS(True, False) True +#else +# define IF_VARIANTS(True, False) False +#endif +} +EOF + + if ($variant) + { + print $out <<'EOF'; +%code variant {int,std::string} +%token TEXT +%token NUMBER +%printer { std::cerr << "Number: " << $$; } +%printer { std::cerr << "Text: " << $$; } +%token END_OF_FILE 0 +%type text result + +%% +result: + text { /* Throw away the result. */ } +; + +text: + /* nothing */ { /* This will generate an empty string */ } +| text TEXT { std::swap($$,$1); $$.append($2); } +| text NUMBER { + std::swap($$,$1); + std::ostringstream ss; + ss << ' ' << $2; + $$.append(ss.str()); + } +; +EOF + } + else + { + # Not using Boost variants. + print $out <<'EOF'; +%union {int ival; std::string* sval;} +%token TEXT +%token NUMBER +%printer { std::cerr << "Number: " << $$; } +%printer { std::cerr << "Text: " << *$$; } +%token END_OF_FILE 0 +%type text result + +%% +result: + text { delete $1; } +; + +text: + /* nothing */ { $$ = new std::string; } +| text TEXT { $$->append(*$2); delete $2; } +| text NUMBER { + std::ostringstream ss; + ss << ' ' << $2; + $$->append(ss.str()); + } +; +EOF + } + + print $out <<'EOF'; +%% +static +yy::parser::token_type +yylex(yy::parser::semantic_type* yylval) +{ + static int stage = -1; + ++stage; + if (stage == STAGE_MAX) + return yy::parser::token::END_OF_FILE; + else if (stage % 2) + { + IF_VARIANTS(*yylval, yylval->ival) = stage; + return yy::parser::token::NUMBER; + } + else + { + IF_VARIANTS(*yylval =, yylval->sval = new) std::string("A string."); + return yy::parser::token::TEXT; + } + abort(); +} + +// Mandatory error function +void +yy::parser::error(const yy::parser::location_type& yylloc, + const std::string& message) +{ + std::cerr << yylloc << ": " << message << std::endl; +} + +int main(int argc, char *argv[]) +{ + yy::parser p; +#if YYDEBUG + p.set_debug_level(!!getenv("YYDEBUG")); +#endif + p.parse(); + return 0; +} +EOF +} + +################################################################## + +=item C + +Compile C<$base.y> to an executable C, Using the C or C++ compiler +depending on the %language specification in C<$base.y>. + +=cut + sub compile ($) { my ($base) = @_; + my $language = `sed -ne '/%language "\\(.*\\)"/{s//\\1/;p;q;}' $base.y`; + chomp $language; + + my $compiler = $language eq 'C++' ? $cxx : $cc; + system ("$bison $base.y -o $base.c") == 0 or die; - system ("$cc -o $base $base.c") == 0 + system ("$compiler -o $base $cflags $base.c") == 0 or die; } -sub bench_grammar ($) +=item C + +Generate benches for C<$gram>. C<$gram> should be C or +C. C<%bench> is a hash of the form: + + $name => @directive + +where C<$name> is the name of the bench, and C<@directive> are the +Bison directive to use for this bench. All the benches are compared +against each other, repeated 50 times. + +=cut + +sub bench_grammar ($%) { - my ($gram) = @_; - my %test = - ( - "pull-impure" => '', - "pull-pure" => '%define api.pure', - "push-impure" => '%define api.push_pull "both"', - "push-pure" => '%define api.push_pull "both" %define api.pure', - ); + my ($gram, %test) = @_; + + use Benchmark qw (:all :hireswallclock); + # Set up the benches as expected by timethese. my %bench; + # For each bench, capture the size. + my %size; while (my ($name, $directives) = each %test) { - print STDERR "$name\n"; + verbose 1, "Generating $name\n"; + # Call the Bison input file generator. my $generator = "$gram" . "_grammar"; - &$generator ($name, 200, $directives); + &$generator ($name, 200, @$directives); + # Compile the executable. compile ($name); $bench{$name} = "system ('./$name');"; + chop($size{$name} = `wc -c <$name`); } - print "$gram:\n"; - my $res = timethese (50, \%bench, 'nop'); + # Run the benches. + # + # STYLE can be any of 'all', 'none', 'noc', 'nop' or 'auto'. 'all' + # shows each of the 5 times available ('wallclock' time, user time, + # system time, user time of children, and system time of + # children). 'noc' shows all except the two children times. 'nop' + # shows only wallclock and the two children times. 'auto' (the + # default) will act as 'all' unless the children times are both + # zero, in which case it acts as 'noc'. 'none' prevents output. + verbose 1, "Running the benches for $gram\n"; + my $res = timethese ($iterations, \%bench, 'nop'); + + # Output the speed result. cmpthese ($res, 'nop'); + + # Display the sizes. + print "Sizes:\n"; + my $width = 10; + for my $bench (keys %size) + { + $width = length $bench + if $width < length $bench; + } + for my $bench (keys %size) + { + printf "%${width}s: %5dkB\n", $bench, int ($size{$bench} / 1024); + } } -print STDERR "Using $bison, $cc.\n"; -calc_input ('calc', 200); -bench_grammar ('calc'); + +=item C + +Bench the C push parser against the pull parser, pure and impure +interfaces. + +=cut + +sub bench_push_parser () +{ + calc_input ('calc', 200); + bench_grammar + ('calc', + ( + "pull-impure" => [], + "pull-pure" => ['%define api.pure'], + "push-impure" => ['%define api.push_pull "both"'], + "push-pure" => ['%define api.push_pull "both"', '%define api.pure'], + ) + ); +} + +=item C + +Bench the C++ lalr1.cc parser using Boost.Variants or %union. + +=cut + +sub bench_variant_parser () +{ + bench_grammar + ('variant', + ( + "union" => [], + "variant" => ['%variant'], + "union-debug" => ['%debug'], + "variant-debug" => ['%debug', '%variant'], + ) + ); +} + +=item C + +Bench the C++ lalr1.cc parser using Boost.Variants or %union. + +=cut + +sub bench_fusion_parser () +{ + bench_grammar + ('variant', + ( + "split" => [], + "fused" => ['%skeleton "lalr1-fusion.cc"'], + ) + ); +} + +############################################################################ + +sub help ($) +{ + my ($verbose) = @_; + use Pod::Usage; + # See . + pod2usage( { -message => "Bench Bison parsers", + -exitval => 0, + -verbose => $verbose, + -output => \*STDOUT }); +} + +sub getopt () +{ + use Getopt::Long; + %option = ("h|help" => sub { help ($verbose) }, + "v|verbose" => sub { ++$verbose }, + "c|cflags=s" => \$cflags, + "i|iterations=i" => \$iterations); + Getopt::Long::Configure ("bundling", "pass_through"); + GetOptions (%option) + or exit 1; +} + +###################################################################### + +getopt; +verbose 1, "Using bison=$bison.\n"; +verbose 1, "Using cc=$cc.\n"; +verbose 1, "Using cxx=$cxx.\n"; +verbose 1, "Using cflags=$cflags.\n"; +# bench_push_parser(); +# bench_variant_parser(); +bench_fusion_parser(); ### Setup "GNU" style for perl-mode and cperl-mode. ## Local Variables: