Re: fastest data structure

["SteveD" <nospam_steved94@attbi.com>]

"Etienne Baudin" <pfoxNO@SPAMfree.fr> wrote in message
news:at5kmf$3ia$1@news-reader12.wanadoo.fr...
> Hello,
>
> I'd like to know which of these 2 data structures is the fastest to
proceed
> :

Here is my version of a test program to answer the question:

with Ada.Float_Text_Io;
with Ada.Real_Time;
with Ada.Text_IO;

procedure Timing_Test is

   package Float_Text_Io renames Ada.Float_Text_IO;
   package Real_Time renames Ada.Real_Time;
   use type Real_Time.Time_Span;
   package Text_Io renames Ada.Text_IO;

   type My_Type is array (1 .. 100) of Integer;

   type Cell;
   type Ptr is access all Cell;
   type Cell is
      record
         Comp : My_Type;
         Next : Ptr;
      end record;

   procedure Processing (
         Data : My_Type ) is
      Value : Integer;
      pragma Volatile( Value );
   begin
      Value := 42;
   end Processing;

   subtype Testrange is Integer range 1 .. 100_000;

   A : array (Testrange) of My_Type;
   B : array (Testrange) of aliased Cell;
   P : Ptr;

   Start_Time : Real_Time.Time;
   End_Time : Real_Time.Time;
begin
   for I in B'First .. B'Last - 1 loop
      B( I ).Next := B( I + 1 )'access;
   end loop;
   B( B'Last ).Next := null;

   start_Time := Real_Time.Clock;
   for I in A'range loop
      Processing( A(I) );
   end loop;
   End_Time := Real_Time.Clock;
   Text_Io.Put( "Time for array based loop is " );
   Float_Text_Io.Put( Float( Real_Time.To_Duration( end_Time -
Start_TIme ) ), 3, 5, 0 );
   Text_Io.New_Line;

   start_Time := Real_Time.Clock;
   P := B( 1 )'access;
   while (P /= null) loop
      Processing( P.Comp );
      P := P.Next;
   end loop;
   End_Time := Real_Time.Clock;
   Text_Io.Put( "Time for linked list based loop is " );
   Float_Text_Io.Put( Float( Real_Time.To_Duration( end_Time -
Start_TIme ) ), 3, 5, 0 );
   Text_Io.New_Line;

end Timing_Test;

My results are with optimization turned off:

Time for array based loop is   0.00038
Time for linked list based loop is   0.00216

With optimization turned on and checks turned off:

Time for array based loop is   0.00013
Time for linked list based loop is   0.00230

I am using Gnat 3.15p on W2k running on an AMD Athlon 900.

The only way to really answer this question is either through testing (as I
did)
or careful analysis of the code generated by the compiler.

The other thing to note is while the two implementations differ in timing
by an order of magnitude, the overall time is only a couple of milliseconds.

Depending on your application this may or may not matter.

Steve
(The Duck)

>
> Which of the loops is supposed to be the fastest ? Each of the loop should
> run between 1000 and 10_000 times (faces of a 3d object) many (60
expected)
> times per sec, that's why I try to get the best performances.
>
> Thanks
> Etienne Baudin
>
>