/mobile Handheld Friendly website

 performance measurements

Each table row shows performance measurements for this Perl program with a particular command-line input value N.

 N  CPU secs Elapsed secs Memory KB Code B ≈ CPU Load

Read the ↓ make, command line, and program output logs to see how this program was run.

Read binary-trees benchmark to see what this program should do.

 notes

This is perl 5, version 18, subversion 0 (v5.18.0) built for x86_64-linux-thread-multi

Compile-time options: HAS_TIMES MULTIPLICITY PERLIO_LAYERS
                        PERL_DONT_CREATE_GVSV
                        PERL_HASH_FUNC_ONE_AT_A_TIME_HARD
                        PERL_IMPLICIT_CONTEXT PERL_MALLOC_WRAP
                        PERL_PRESERVE_IVUV PERL_SAWAMPERSAND USE_64_BIT_ALL
                        USE_64_BIT_INT USE_ITHREADS USE_LARGE_FILES
                        USE_LOCALE USE_LOCALE_COLLATE USE_LOCALE_CTYPE
                        USE_LOCALE_NUMERIC USE_PERLIO USE_PERL_ATOF
                        USE_REENTRANT_API

 binary-trees Perl #2 program source code

# The Computer Language Benchmarks Game
# http://benchmarksgame.alioth.debian.org/
#
# Contributed by Doug King
# Corrected by Heiner Marxen
# Tree-building made non-recursive by Steffen Mueller

use integer;

sub item_check {
    my ($tree) = @_;

    return $tree->[2] unless (defined $tree->[0]);
    return $tree->[2] + item_check($tree->[0]) - item_check($tree->[1]);
}


sub bottom_up_tree {
    my($depth) = @_;

    my @pool;
    push @pool, [undef, undef, -$_] foreach 0..2**$depth-1;

    foreach my $exponent (reverse(0..($depth-1))) {
        push @pool, [reverse(splice(@pool, 0, 2)), $_] 
                       foreach reverse(-(2**$exponent-1) .. 0);
    }
    return $pool[0];
}


my $n = shift @ARGV;

my $min_depth = 4;
my $max_depth;

if ( ($min_depth + 2) > $n) {
    $max_depth = $min_depth + 2;
} else {
    $max_depth = $n;
}

{
    my $stretch_depth = $max_depth + 1;
    my $stretch_tree = bottom_up_tree($stretch_depth);
    print "stretch tree of depth $stretch_depth\t check: ",
           item_check($stretch_tree), "\n";
}

my $long_lived_tree = bottom_up_tree($max_depth);

my $depth = $min_depth;
while( $depth <= $max_depth ) {
    my $iterations = 2 ** ($max_depth - $depth + $min_depth);
    my $check = 0;

    foreach my $i (1..$iterations) {
	my $temp_tree = bottom_up_tree($depth);
	$check += item_check($temp_tree);

	$temp_tree = bottom_up_tree($depth);
	$check += item_check($temp_tree);
    }

    print $iterations * 2, "\t trees of depth $depth\t check: ", $check, "\n";
    $depth += 2;
}

print "long lived tree of depth $max_depth\t check: ", 
       item_check($long_lived_tree), "\n";

 make, command-line, and program output logs

Mon, 04 Feb 2013 04:28:30 GMT

COMMAND LINE:
/usr/local/src/perl-5.16.2/bin/perl binarytrees.perl-2.perl 20

PROGRAM OUTPUT:
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1

Revised BSD license

  Home   Conclusions   License   Play