performance measurements

Each table row shows performance measurements for this Ada 2005 GNAT 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 fannkuch-redux benchmark to see what this program should do.

 notes

GNATMAKE 4.6

gcc version 4.8.2 (Ubuntu 4.8.2-19ubuntu1)

 fannkuch-redux Ada 2005 GNAT program source code

--
-- The Computer Language Benchmarks Game
-- http://benchmarksgame.alioth.debian.org/
--
-- Based on code by Dave Fladebo, Eckehard Berns, Heiner Marxen, Hongwei Xi,
-- and The Anh Tran, and on the Java version of fannkuchredux by Oleg Mazurov.
-- Contributed by Jonathan Parker, Oct 2010.
--

with Ada.Command_Line;
with Ada.Text_Io; use Ada.Text_Io;

procedure Fannkuchredux is

   Multitasking_Desired : constant Boolean := True;

   type Fann_Int is mod 2**64;

   N_image : constant String   := Ada.Command_Line.Argument (1);
   N       : constant Fann_Int := Fann_Int'Value (N_image);

   pragma Assert (N > 1,  "Input argument N must be integer > 1.");
   pragma Assert (N < 21, "Input argument N must be integer < 21.");
   --  21! is too large for a 64-bit Fann_Int.

   Fann_0 : constant Fann_Int := 0;
   Fann_First : constant Fann_Int := Fann_0;
   Fann_Last  : constant Fann_Int := Fann_0 + (N - 1);

   subtype Perm_Index is Fann_Int range Fann_First .. Fann_Last;
   type Permutation is array(Perm_Index) of Fann_Int;

   -- The N! permutations are indexed from 0 to N!-1.  The indices 
   -- and the factorials have type Perm_id_Range. 

   subtype Perm_id_Range is Fann_Int;
   subtype Enum_Index is Fann_Int range Fann_First .. Fann_Last+1;
   type Enumeration is array(Enum_Index) of Perm_id_Range; -- holds N!'s

   No_of_Tasks : constant := 12; 
   -- Using stnd setting of 12, Chunk_Size = (N! / No_of_Tasks) is even for N>3.

   type Task_id_Range is range 1 .. No_of_Tasks;

   type Integer_64 is range -2**63+1 .. 2**63-1; -- for checksums

   procedure Get_Count_of_Flips
     (Perm       : in    Permutation;
      Flip_Count :   out Fann_Int)
   is 
      Lo, Hi : Fann_Int;
      tmp    : Fann_Int;
      P_1st  : Fann_Int    := Perm(Fann_First);
      Perm1  : Permutation := Perm;
   begin
      Flip_Count := Fann_0;
      while P_1st /= Fann_First loop  -- Flip until P_1st = Fann_First
         Hi := P_1st - 1;
         Lo := Fann_First + 1;
         while Lo < Hi loop
            tmp       := Perm1(Lo);
            Perm1(Lo) := Perm1(Hi);
            Lo := Lo + 1;
            Perm1(Hi) := tmp;
            Hi := Hi - 1;
         end loop;
         tmp          := Perm1(P_1st);
         Perm1(P_1st) := P_1st;
         P_1st        := tmp;
         Flip_Count   := Flip_Count + 1;
      end loop;
   end Get_Count_of_Flips;

   procedure Get_First_Permutation 
     (Perm_id   : in     Perm_id_Range;
      Factorial : in     Enumeration;
      Perm      :    out Permutation;
      Count     :    out Permutation) 
   is
      p_id : Perm_id_Range := Perm_id;
      Perm1 : Permutation;
      d : Fann_Int;
   begin
      Count := (others => Fann_Int'First);

      for i in Perm'Range loop
         Perm(i) := i;
      end loop;

      for i in reverse Count'First+1 .. Count'Last loop
         d        := Fann_Int (p_id  /  Factorial(i));
         p_id     := p_id mod Factorial(i); 
         Count(i) := d;

         Perm1 := Perm;
         for j in 0 .. i loop
            if j+d <= i then
               Perm(j) :=  Perm1(j+d);
            else
               Perm(j) :=  Perm1(j+d-i-1);
            end if;
         end loop;
      end loop;

   end Get_First_Permutation;

   procedure Get_Next_Permutation 
     (Perm  : in out Permutation;
      Count : in out Permutation)
   is
      i : Fann_Int := 1;
      First : Fann_Int := Perm(1);
      Next_First : Fann_Int;
   begin
      Perm(1) := Perm(0);
      Perm(0) := First;

      Count(i) := Count(i) + 1;
      while  Count(i) > i  loop
         Count(i) := 0;
         i := i + 1;

         Perm(0)    := Perm(1);
         Next_First := Perm(1);
         for j in 1 .. i-1  loop
            Perm(j) := Perm(j+1);  
         end loop;
         Perm(i) := First;
         First   := Next_First;

         Count(i) := Count(i) + 1;
      end loop;

   end Get_Next_Permutation;

   procedure Get_Checksum_and_Flips 
     (Task_id   : in     Task_id_Range;
      Factorial : in     Enumeration;
      Max_Flips :    out Fann_Int;
      Checksum  :    out Integer_64)
   is
      Perm_id, Perm_id_Min, Perm_id_Max : Perm_id_Range;
      Flip_Count  : Fann_Int;
      Perm, Count : Permutation;
      Chunk_Size  : Perm_id_Range;
   begin

      Chunk_Size := Factorial(N) / No_of_Tasks;
      pragma Assert (Chunk_Size mod 2 = 0); -- so checksums work if No_of_Tasks>1.

      Perm_id_Min := Perm_id_Range (Task_id - Task_id_Range'First) * Chunk_Size;
      Perm_id_Max := Perm_id_Range'Min (Factorial(N), Perm_id_Min+Chunk_Size) - 1;
      --  for the First task:   Perm_id_Min = 0;  Perm_id_Max := Chunk_Size-1
      --  Perm_id ultimately runs from 0 .. Factorial(N)-1

      Get_First_Permutation (Perm_id_Min, Factorial, Perm, Count);
      --  Initialize Perm and Count

      Max_Flips := 1;
      Checksum  := 0;
      Perm_id   := Perm_id_Min;
      loop
         if  Perm(0) /= 0  then
            Get_Count_of_Flips (Perm, Flip_Count);
            Max_Flips := Fann_Int'Max (Max_Flips, Flip_Count);
            if Perm_id mod 2 = 0 then 
               Checksum := Checksum + Integer_64 (Flip_Count); 
            else 
               Checksum := Checksum - Integer_64 (Flip_Count); 
            end if;
         end if;

         exit when Perm_id = Perm_id_Max;  -- return
         Perm_id := Perm_id + 1;

         Get_Next_Permutation (Perm, Count);
      end loop;

   end Get_Checksum_and_Flips;

   task type Flip_Counter is
      pragma Storage_Size (2**14);
      entry Start 
        (Task_id   : in Task_id_Range;
         Factorial : in Enumeration);
      entry Return_Result 
        (Partial_Flip_Count : out Fann_Int;
         Partial_Checksum   : out Integer_64);
   end Flip_Counter;

   task body Flip_Counter is
      Task_id_Local : Task_id_Range;
      Max_Flips     : Fann_Int;
      Checksum      : Integer_64;
      F : Enumeration;
   begin
      accept Start 
        (Task_id   : in Task_id_Range;
         Factorial : in Enumeration)
      do
         Task_id_Local := Task_id;
         F := Factorial;
      end Start;

      Get_Checksum_and_Flips (Task_id_Local, F, Max_Flips, Checksum);

      accept Return_Result 
        (Partial_Flip_Count : out Fann_Int;
         Partial_Checksum   : out Integer_64)
      do
         Partial_Flip_Count := Max_Flips;
         Partial_Checksum   := Checksum;
      end Return_Result;
   end Flip_Counter;

   type Flip_Data   is array (Task_id_Range) of Fann_Int;
   type Chksum_Data is array (Task_id_Range) of Integer_64;
   Flip_Count_Storage : Flip_Data   := (others => 0);
   Checksum_Storage   : Chksum_Data := (others => 0);
   Checksum  : Integer_64 := 0;
   Max_Flips : Fann_Int   := 0;

   Factorial : Enumeration;

begin
   if not (N > 3 or (not Multitasking_Desired and No_of_Tasks = 1)) then
      Put_Line ("Set Multitasking_Desired = False and No_of_Tasks = 1 for N < 4");
      raise Program_Error;
   end if;

   Factorial(0) := 1;
   for i in Enum_Index range 1 .. Enum_Index'Last loop
      Factorial(i) := Factorial(i-1) * Perm_id_Range (i);
   end loop;

   if Multitasking_Desired then

      declare  -- and launch 1 task for each t in Task_id_Range:

         Counter : array(Task_id_Range) of Flip_Counter; -- the tasks.

      begin 

         for t in Task_id_Range loop
            Counter(t).Start (t, Factorial);
         end loop;

         for t in Task_id_Range loop
            Counter(t).Return_Result (Max_Flips, Checksum);
            Flip_Count_Storage(t) := Max_Flips;
            Checksum_Storage(t)   := Checksum;
         end loop;

      end;

   else  -- Sequential:
    
      for t in Task_id_Range loop
         Get_Checksum_and_Flips (t, Factorial, Max_Flips, Checksum);
         Flip_Count_Storage(t) := Max_Flips;
         Checksum_Storage(t)   := Checksum;
      end loop;

   end if;

   Max_Flips := 0;
   for t in Task_id_Range loop
      if Flip_Count_Storage(t) > Max_Flips then
         Max_Flips := Flip_Count_Storage(t);
      end if;
   end loop;

   Checksum := 0;
   for t in Task_id_Range loop
      Checksum := Checksum + Checksum_Storage(t); 
   end loop;

   declare
      C_Image : constant String := Integer_64'Image (Checksum);
   begin
      Put_Line (C_image(2..C_image'Last));
      Put ("Pfannkuchen("); Put (N_image); Put (") =");
      Put (Fann_Int'Image (Max_Flips));
   end;

end Fannkuchredux;

 make, command-line, and program output logs

Sat, 19 Jan 2013 07:38:05 GMT

MAKE:
/usr/bin/gnatchop -r -w fannkuchredux.gnat
splitting fannkuchredux.gnat into:
   fannkuchredux.adb
/usr/bin/gnatmake -O3 -fomit-frame-pointer -march=native -msse3 -mfpmath=sse -gnatNp -f fannkuchredux.adb -o fannkuchredux.gnat_run 
gcc-4.6 -c -O3 -fomit-frame-pointer -march=native -msse3 -mfpmath=sse -gnatNp fannkuchredux.adb
gnatbind -x fannkuchredux.ali
gnatlink fannkuchredux.ali -O3 -fomit-frame-pointer -march=native -msse3 -mfpmath=sse -o fannkuchredux.gnat_run
0.60s to complete and log all make actions

COMMAND LINE:
./fannkuchredux.gnat_run 12

PROGRAM OUTPUT:
3968050
Pfannkuchen(12) = 65

Revised BSD license

  Home   Conclusions   License   Play