#! /usr/bin/perl -w
-# Copyright (C) 2006 Free Software Foundation, Inc.
+# Copyright (C) 2006, 2008 Free Software Foundation, Inc.
#
# This file is part of Bison, the GNU Compiler Compiler.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
+=head1 NAME
+
+bench.pl - perform benches on Bison parsers.
+
+=head1 SYNOPSIS
+
+ ./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
+
+use strict;
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 $cxx = $ENV{'CXX'} || 'g++';
+my $cflags = '-O2';
+my $iterations = -1;
+my $verbose = 1;
-##################################################################
+=head1 FUNCTIONS
-sub triangular_grammar ($$$)
+=over 4
+
+=item C<verbose($level, $message)>
+
+Report the C<$message> is C<$level> E<lt>= C<$verbose>.
+
+=cut
+
+sub verbose($$)
{
- my ($base, $max, $directives) = @_;
+ 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>.
+
+=cut
+
+sub directives($@)
+{
+ my ($bench, @directive) = @_;
+ my $res = "/* Directives for bench `$bench'. */\n";
+ $res .= join ("\n", @directive) . "\n";
+ $res .= "/* End of directives for bench `$bench'. */\n";
+ return $res;
+}
+
+######################################################################
+
+=item C<generate_grammar_triangular ($base, $max, @directive)>
+
+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 generate_grammar_triangular ($$@)
+{
+ my ($base, $max, @directive) = @_;
+ my $directives = directives ($base, @directive);
my $out = new IO::File ">$base.y"
or die;
static int yylex (void);
static void yyerror (const char *msg);
%}
+$directives
%union
{
int val;
##################################################################
+=item C<calc_input ($base, $max)>
+
+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) = @_;
##################################################################
-sub calc_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
+
+sub generate_grammar_calc ($$@)
{
- my ($base, $max, $directives) = @_;
+ my ($base, $max, @directive) = @_;
+ my $directives = directives ($base, @directive);
my $out = new IO::File ">$base.y"
or die;
static int global_count = 0;
%}
-/* Exercise %union. */
$directives
%error-verbose
+/* Exercise %union. */
%union
{
semantic_value ival;
/* Skip white space. */
while ((c = get_char ()) == ' ' || c == '\t')
- {
-
- }
+ continue;
/* process numbers */
if (c == '.' || isdigit (c))
##################################################################
-sub compile ($)
+=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) = @_;
- system ("$bison $base.y -o $base.c") == 0
- or die;
- system ("$cc -o $base $base.c") == 0
+ 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>
}
-sub bench_grammar ($)
+%code // variant.c
{
- my ($gram) = @_;
- my %test =
+#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 =
(
- "yacc.c-pull-impure" => '',
- "yacc.c-pull-pure" => '%pure-parser',
- "push.c-pull-impure" => '%skeleton "push.c"',
- "push.c-pull-pure" => '%skeleton "push.c" %pure-parser',
- "push.c-push-impure" => '%skeleton "push.c" %push-pull-parser',
- "push.c-push-pure" => '%skeleton "push.c" %push-pull-parser %pure-parser',
+ "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)>
+
+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;
+ 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:
+
+ $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, %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";
- my $generator = "$gram" . "_grammar";
- &$generator ($name, 200, $directives);
+ generate_grammar ($gram, $name, @$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 2, "Running the benches for $gram\n";
+ my $res = timethese ($iterations, \%bench, 'nop');
+
+ # Output the speed result.
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;
+ }
}
-print STDERR "Using $bison, $cc.\n";
-calc_input ('calc', 200);
-bench_grammar ('calc');
+######################################################################
+
+=item C<bench_push_parser ()>
+
+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_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:
projects / bison.git / blobdiff