/mobile Handheld Friendly website

 performance measurements

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

 N  CPU secs Elapsed secs Memory KB Code B ≈ CPU Load
120.070.07?769  0% 0% 0% 100%
161.521.532,612769  0% 1% 1% 99%
2033.2533.2765,828769  0% 1% 1% 100%

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

Free Pascal Compiler version 2.6.0 [2011/12/23] for i386

 binary-trees Pascal Free Pascal program source code

(*
  The Computer Language Benchmarks Game
  http://benchmarksgame.alioth.debian.org/

  contributed by Vitaly Trifonof based on a contribution of Ales Katona
*)

program BinaryTrees;

type
  PNode = ^TNode;
  TNode = record
    l, r: PNode;
    i: Longint;
  end;

function CreateNode(l2, r2: PNode; const i2: Longint): PNode; inline;
begin
  CreateNode := GetMem(SizeOf(TNode));
  CreateNode^.l:=l2;
  CreateNode^.r:=r2;
  CreateNode^.i:=i2;
end;


(* Destroy node and it subnodes in one procedure *)

procedure DestroyNode(ANode: PNode); inline;
var
  LNode, RNode: PNode;
begin
  LNode := ANode^.l;
  if LNode <> nil then
  begin
    RNode := ANode^.r;
    if LNode^.l <> nil then
    begin
      DestroyNode(LNode^.l);
      DestroyNode(LNode^.r);
      FreeMem(LNode, SizeOf(TNode));

      DestroyNode(RNode^.l);
      DestroyNode(RNode^.r);
      FreeMem(RNode, SizeOf(TNode));
    end
    else
    begin
      DestroyNode(LNode);
      DestroyNode(RNode);
    end
  end;

  FreeMem(ANode, SizeOf(TNode));
end;


(* Left subnodes check in cycle, right recursive *)

function CheckNode(ANode: PNode): Longint; inline;
begin
  CheckNode := 0;
  while ANode^.l <> nil do
  begin
    CheckNode += ANode^.i - CheckNode(ANode^.r);
    ANode := ANode^.l
  end;
  CheckNode += ANode^.i;
end;


(*
   Create node and it subnodes in one function

   make(1,a)=(2I-1)=Ia make(2,Ia-1)=(2(2I-1)-1)=(4I-3)
                       make(2,Ia)  =(2(2I-1))  =(4I-2)

   make(1,b)=(2I)=Ib   make(2,Ib-1)=(2(2I)-1)  =(4I-1)
                       make(2,Ib)  =(2(2I))    =(4I)
*)

function Make(d, i: Longint): PNode;
var
  fi: Longint;
begin
  case d of
   0: Make:=CreateNode(nil, nil, i);
   1: Make:=CreateNode(CreateNode(nil, nil, 2*i-1), CreateNode(nil, nil, 2*i),i);
  else
      d -= 2; fi := 4*i;
      Make:=CreateNode(
                           CreateNode( Make(d, fi-3),Make(d, fi-2), 2*i-1 ),
                           CreateNode( Make(d, fi-1),Make(d, fi), 2*i ),
                           i
                        )
  end
end;

const
  mind = 4;

var
  maxd : Longint = 10;
  strd,
  iter,
  c, d, i : Longint;
  tree, llt : PNode;

begin
  if ParamCount = 1 then
    Val(ParamStr(1), maxd);

  if maxd < mind+2 then
     maxd := mind + 2;

  strd:=maxd + 1;
  tree:=Make(strd, 0);
  Writeln('stretch tree of depth ', strd, #9' check: ', CheckNode(tree));
  DestroyNode(tree);

  llt:=Make(maxd, 0);

  d:=mind;
  while d <= maxd do begin
    iter:=1 shl (maxd - d + mind);
    c:=0;
    for i:=1 to Iter do begin
      tree:=Make(d, i);
      c:=c + CheckNode(tree);
      DestroyNode(tree);
      tree:=Make(d, -i);
      c:=c + CheckNode(tree);
      DestroyNode(tree);
    end;
    Writeln(2 * Iter, #9' trees of depth ', d, #9' check: ', c);
    Inc(d, 2);
  end;

  Writeln('long lived tree of depth ', maxd, #9' check: ', CheckNode(llt));
  DestroyNode(llt);
end.

 make, command-line, and program output logs

Sat, 02 Feb 2013 03:24:16 GMT

MAKE:
mv binarytrees.fpascal binarytrees.pas
/usr/local/src/fpc-2.6.0.i386-linux/bin/fpc -FuInclude/fpascal -XXs -Oppentiumm -Cppentiumm -O3 -Cfsse2  -oFPASCAL_RUN binarytrees.pas
Free Pascal Compiler version 2.6.0 [2011/12/23] for i386
Copyright (c) 1993-2011 by Florian Klaempfl and others
Target OS: Linux for i386
Compiling binarytrees.pas
Linking FPASCAL_RUN
/usr/bin/ld: warning: link.res contains output sections; did you forget -T?
140 lines compiled, 0.1 sec 
mv FPASCAL_RUN binarytrees.fpascal_run
rm binarytrees.pas
0.13s to complete and log all make actions

COMMAND LINE:
./binarytrees.fpascal_run 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