]> git.saurik.com Git - bison.git/blobdiff - etc/bench.pl.in
The single-stack C++ parser is now the standard one.
[bison.git] / etc / bench.pl.in
index 804d4c8f0c4b4b725944afe842ff890c75ba4bd6..91c35b997aa218feeb3b06c22128e9ca30a0c012 100755 (executable)
@@ -23,22 +23,126 @@ bench.pl - perform benches on Bison parsers.
 
 =head1 SYNOPSIS
 
 
 =head1 SYNOPSIS
 
-  ./bench.pl
+  ./bench.pl [OPTIONS]... BENCHES
+
+=head1 BENCHES
+
+Specify the set of benches to run.  I<bench-name> should be one of:
+
+=over 4
+
+=item I<fusion>
+
+Test F<lalr1.cc> with three stacks against F<lalr1-fusion.cc> which
+uses a single one.
+
+=item I<push>
+
+Test the push parser vs. the pull interface.  Use the C parser.
+
+=item I<variant>
+
+Test the use of variants instead of union in the C++ parser.
+
+=back
+
+=head1 OPTIONS
+
+=item B<-c>, B<--cflags>=I<flags>
+
+Flags to pass to the C or C++ compiler.  Defaults to -O2.
+
+=item B<-h>, B<--help>
+
+Display this message and exit succesfully.  The more verbose, the more
+details.
+
+=item B<-i>, B<--iterations>=I<integer>
+
+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 -1.
+
+=item B<-q>, B<--quiet>
+
+Decrease the verbosity level (defaults to 1).
+
+=item B<-v>, B<--verbose>
+
+Raise the verbosity level (defaults to 1).
+
+=back
 
 =cut
 
 
 =cut
 
+use strict;
 use IO::File;
 use IO::File;
-use Benchmark qw (:all);
+
+##################################################################
+
+=head1 VARIABLES
+
+=over 4
+
+=item C<@bench>
+
+The list of benches to run.
+
+=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 $bison = $ENV{'BISON'} || '@abs_top_builddir@/tests/bison';
 my $cc = $ENV{'CC'} || 'gcc';
+my $cxx = $ENV{'CXX'} || 'g++';
+my $cflags = '-O2';
+my $iterations = -1;
+my $verbose = 1;
 
 
-##################################################################
-
-=head2 Functions
+=head1 FUNCTIONS
 
 =over 4
 
 
 =over 4
 
+=item C<verbose($level, $message)>
+
+Report the C<$message> is C<$level> E<lt>= C<$verbose>.
+
+=cut
+
+sub verbose($$)
+{
+  my ($level, $message) = @_;
+  print STDERR $message
+    if $level <= $verbose;
+}
+
+
+######################################################################
+
 =item C<directives($bench, @directive)>
 
 Format the list of directives for Bison for bench named C<$bench>.
 =item C<directives($bench, @directive)>
 
 Format the list of directives for Bison for bench named C<$bench>.
@@ -47,14 +151,16 @@ Format the list of directives for Bison for bench named C<$bench>.
 
 sub directives($@)
 {
 
 sub directives($@)
 {
-  my ($bench, @directives) = @_;
+  my ($bench, @directive) = @_;
   my $res = "/* Directives for bench `$bench'. */\n";
   my $res = "/* Directives for bench `$bench'. */\n";
-  $res .= join ("\n", @directives);
+  $res .= join ("\n", @directive) . "\n";
   $res .= "/* End of directives for bench `$bench'. */\n";
   return $res;
 }
 
   $res .= "/* End of directives for bench `$bench'. */\n";
   return $res;
 }
 
-=item C<triangular_grammar ($base, $max, @directives)>
+######################################################################
+
+=item C<generate_grammar_triangular ($base, $max, @directive)>
 
 Create a large triangular grammar which looks like :
 
 
 Create a large triangular grammar which looks like :
 
@@ -72,18 +178,18 @@ Create a large triangular grammar which looks like :
   | "1" "2" "3" "4" "5"  END    { $$ = 5; }
   ;
 
   | "1" "2" "3" "4" "5"  END    { $$ = 5; }
   ;
 
-C<$base> is the base name for the file to create (C<$base.y>).
+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
 C<$max> is the number of such rules (here, 5).  You may pass
-additional Bison C<@directives>.
+additional Bison C<@directive>.
 
 The created parser is self contained: it includes its scanner, and
 source of input.
 =cut
 
 
 The created parser is self contained: it includes its scanner, and
 source of input.
 =cut
 
-sub triangular_grammar ($$$)
+sub generate_grammar_triangular ($$@)
 {
 {
-  my ($base, $max, @directives) = @_;
-  my $directives = directives ($base, @directives);
+  my ($base, $max, @directive) = @_;
+  my $directives = directives ($base, @directive);
 
   my $out = new IO::File ">$base.y"
     or die;
 
   my $out = new IO::File ">$base.y"
     or die;
@@ -171,7 +277,7 @@ EOF
 
 =item C<calc_input ($base, $max)>
 
 
 =item C<calc_input ($base, $max)>
 
-Generate the input file C<$base.input> for the calc parser.  The input
+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.
 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.
@@ -191,18 +297,19 @@ sub calc_input ($$)
 }
 
 ##################################################################
 }
 
 ##################################################################
-=item C<calc_grammar ($base, $max, @directives)>
 
 
-Generate a Bison file C<$base.y> that for a calculator parser in C.
-Pass the additional Bison C<@directives>.  C<$max> is ignored, but
-left to have the same interface as C<triangular_grammar>.
+=item C<generate_grammar_calc ($base, $max, @directive)>
+
+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<triangular_grammar>.
 
 =cut
 
 
 =cut
 
-sub calc_grammar ($$$)
+sub generate_grammar_calc ($$@)
 {
 {
-  my ($base, $max, @directives) = @_;
-  my $directives = directives ($base, @directives);
+  my ($base, $max, @directive) = @_;
+  my $directives = directives ($base, @directive);
 
   my $out = new IO::File ">$base.y"
     or die;
 
   my $out = new IO::File ">$base.y"
     or die;
@@ -401,29 +508,217 @@ EOF
 
 ##################################################################
 
 
 ##################################################################
 
+=item C<generate_grammar_variant ($base, $max, @directive)>
+
+Generate a Bison file F<$base.y> that uses, or not, the Boost.Variants
+depending on the C<@directive>.
+
+=cut
+
+sub generate_grammar_variant ($$@)
+{
+  my ($base, $max, @directive) = @_;
+  my $directives = directives ($base, @directive);
+  my $variant = grep { $_ eq '%define variant' } @directive;
+
+  my $out = new IO::File ">$base.y"
+    or die;
+  print $out <<EOF;
+%language "C++"
+%defines
+$directives
+
+%code requires // variant.h
+{
+#include <string>
+}
+
+%code // variant.c
+{
+#include <algorithm>
+#include <iostream>
+#include <sstream>
+
+// Prototype of the yylex function providing subsequent tokens.
+static yy::parser::token_type yylex(yy::parser::semantic_type* yylval);
+
+#define STAGE_MAX    ($max * 10) // max = $max
+#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';
+%token <std::string> TEXT
+%token <int> NUMBER
+%printer { std::cerr << "Number: " << $$; } <int>
+%printer { std::cerr << "Text: " << $$; } <std::string>
+%token END_OF_FILE 0
+%type <std::string> 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 Bison variants.
+      print $out <<'EOF';
+%union {int ival; std::string* sval;}
+%token <sval> TEXT
+%token <ival> NUMBER
+%printer { std::cerr << "Number: " << $$; } <ival>
+%printer { std::cerr << "Text: " << *$$; } <sval>
+%token END_OF_FILE 0
+%type <sval> 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->build<int>(), yylval->ival) = stage;
+      return yy::parser::token::NUMBER;
+    }
+  else
+    {
+      IF_VARIANTS(yylval->build<std::string>() =, 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<generate_grammar ($name, $base, @directive)>
+
+Generate F<$base.y> by calling C<&generate_grammar_$name>.
+
+=cut
+
+sub generate_grammar ($$@)
+{
+  my ($name, $base, @directive) = @_;
+  verbose 2, "Generating $base.y\n";
+  my %generator =
+    (
+      "calc"       => \&generate_grammar_calc,
+      "triangular" => \&generate_grammar_triangular,
+      "variant"    => \&generate_grammar_variant,
+    );
+  &{$generator{$name}}($base, 200, @directive);
+}
+
+##################################################################
+
+=item C<run ($command)>
+
+Run, possibly verbosely, the shell C<$command>.
+
+=cut
+
+sub run ($)
+{
+  my ($command) = @_;
+  verbose 2, "$command\n";
+  system ("$command") == 0
+    or die "$command failed";
+}
+
+##################################################################
+
 =item C<compile ($base)>
 
 =item C<compile ($base)>
 
-Compile C<$base.y> to an executable C<$base> using the C compiler.
+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) = @_;
 
 =cut
 
 sub compile ($)
 {
   my ($base) = @_;
-  system ("$bison $base.y -o $base.c") == 0
-    or die;
-  system ("$cc -o $base $base.c") == 0
-    or die;
+  my $language = `sed -ne '/%language "\\(.*\\)"/{s//\\1/;p;q;}' $base.y`;
+  chomp $language;
+
+  my $compiler = $language eq 'C++' ? $cxx : $cc;
+
+  run "$bison $base.y -o $base.c";
+  run "$compiler -o $base $cflags $base.c";
 }
 
 }
 
+######################################################################
+
 =item C<bench_grammar ($gram, %bench)>
 
 Generate benches for C<$gram>.  C<$gram> should be C<calc> or
 C<triangle>.  C<%bench> is a hash of the form:
 
 =item C<bench_grammar ($gram, %bench)>
 
 Generate benches for C<$gram>.  C<$gram> should be C<calc> or
 C<triangle>.  C<%bench> is a hash of the form:
 
-  C<$name> => C<@directives>
+  $name => @directive
 
 
-where C<$name> is the name of the bench, and C<@directives> are the
+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.
 
 Bison directive to use for this bench.  All the benches are compared
 against each other, repeated 50 times.
 
@@ -433,25 +728,53 @@ sub bench_grammar ($%)
 {
   my ($gram, %test) = @_;
 
 {
   my ($gram, %test) = @_;
 
+  use Benchmark qw (:all :hireswallclock);
+
   # Set up the benches as expected by timethese.
   my %bench;
   # Set up the benches as expected by timethese.
   my %bench;
+  # For each bench, capture the size.
+  my %size;
   while (my ($name, $directives) = each %test)
     {
   while (my ($name, $directives) = each %test)
     {
-      print STDERR "$name\n";
-      # Call the Bison input file generator.
-      my $generator = "$gram" . "_grammar";
-      &$generator ($name, 200, @$directives);
+      generate_grammar ($gram, $name, @$directives);
+      # Compile the executable.
       compile ($name);
       $bench{$name} = "system ('./$name');";
       compile ($name);
       $bench{$name} = "system ('./$name');";
+      chop($size{$name} = `wc -c <$name`);
     }
 
     }
 
-  print "$gram:\n";
   # Run the benches.
   # Run the benches.
-  my $res = timethese (50, \%bench, 'nop');
-  # Output the result.
+  #
+  # 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 2, "Running the benches for $gram\n";
+  my $res = timethese ($iterations, \%bench, 'nop');
+
+  # Output the speed result.
   cmpthese ($res, 'nop');
   cmpthese ($res, 'nop');
+
+  # Display the sizes.
+  print "Sizes (decreasing):\n";
+  my $width = 10;
+  for my $bench (keys %size)
+    {
+      $width = length $bench
+        if $width < length $bench;
+    }
+  # Benches sorted by decreasing size.
+  my @benches_per_size = sort {$size{$b} <=> $size{$a}} keys %size;
+  for my $bench (@benches_per_size)
+    {
+      printf "%${width}s: %5.2fkB\n", $bench, $size{$bench} / 1024;
+    }
 }
 
 }
 
+######################################################################
 
 =item C<bench_push_parser ()>
 
 
 =item C<bench_push_parser ()>
 
@@ -462,7 +785,6 @@ interfaces.
 
 sub bench_push_parser ()
 {
 
 sub bench_push_parser ()
 {
-  print STDERR "Using $bison, $cc.\n";
   calc_input ('calc', 200);
   bench_grammar
     ('calc',
   calc_input ('calc', 200);
   bench_grammar
     ('calc',
@@ -475,7 +797,94 @@ sub bench_push_parser ()
     );
 }
 
     );
 }
 
-bench_push_parser();
+######################################################################
+
+=item C<bench_variant_parser ()>
+
+Bench the C++ lalr1.cc parser using Boost.Variants or %union.
+
+=cut
+
+sub bench_variant_parser ()
+{
+  bench_grammar
+    ('variant',
+     (
+      "f-union"         => ['%skeleton "lalr1.cc"'],
+      "f-uni-deb"   => ['%skeleton "lalr1.cc"', '%debug'],
+      "f-var"       => ['%skeleton "lalr1.cc"', '%define variant'],
+      "f-var-deb" => ['%skeleton "lalr1.cc"', '%debug', '%define variant'],
+      "f-var-dtr"       => ['%skeleton "lalr1.cc"', '%define variant', "%code {\n#define VARIANT_DESTROY\n}"],
+      "f-var-deb-dtr" => ['%skeleton "lalr1.cc"', '%debug', '%define variant', "%code {\n#define VARIANT_DESTROY\n}"],
+      "f-var-deb-dtr-ass" => ['%skeleton "lalr1.cc"', '%debug', '%define variant', "%code {\n#define VARIANT_DESTROY\n}", "%define assert"],
+     )
+    );
+}
+
+######################################################################
+
+=item C<bench_fusion_parser ()>
+
+Bench the C++ lalr1.cc parser using Boost.Variants or %union.
+
+=cut
+
+sub bench_fusion_parser ()
+{
+  bench_grammar
+    ('variant',
+     (
+      "split"         => ['%skeleton "lalr1-split.cc"'],
+      "fused"         => ['%skeleton "lalr1.cc"'],
+     )
+    );
+}
+
+############################################################################
+
+sub help ($)
+{
+  my ($verbose) = @_;
+  use Pod::Usage;
+  # See <URL:http://perldoc.perl.org/pod2man.html#NOTES>.
+  pod2usage( { -message => "Bench Bison parsers",
+               -exitval => 0,
+               -verbose => $verbose,
+               -output  => \*STDOUT });
+}
+
+######################################################################
+
+sub getopt ()
+{
+  use Getopt::Long;
+  my %option = (
+    "c|cflags=s"     => \$cflags,
+    "h|help"         => sub { help ($verbose) },
+    "i|iterations=i" => \$iterations,
+    "q|quiet"        => sub { --$verbose },
+    "v|verbose"      => sub { ++$verbose },
+    );
+  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";
+
+for my $b (@ARGV)
+{
+  verbose 1, "Running benchmark $b.\n";
+  bench_fusion_parser()  if $b eq "fusion";
+  bench_push_parser()    if $b eq "push";
+  bench_variant_parser() if $b eq "variant";
+}
 
 ### Setup "GNU" style for perl-mode and cperl-mode.
 ## Local Variables:
 
 ### Setup "GNU" style for perl-mode and cperl-mode.
 ## Local Variables: