fastest data structure

fastest data structure

[Etienne Baudin]

Hello,

I'd like to know which of these 2 data structures is the fastest to proceed
:

an simple array of  "My_type" (My type is a record...)
or a liked liste of  "My_Type"

with these definitions
    A : array (integer range <>) of My_Type
vs
    type ptr is access cell
    type cell is record
        comp : My_Type;
        next : ptr;
    end record;

for i in A'range loop
    processing A(i)
end loop;

while (p != null) loop
    process p.comp;
    p := p.next;
end loop;

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

Re: fastest data structure

[Gautier direct_replies_not_read]

Etienne Baudin:

>I'd like to know which of these 2 data structures is the fastest to proceed

>an simple array of  "My_type" (My type is a record...)
>or a liked liste of  "My_Type"
>
>with these definitions
>     A : array (integer range <>) of My_Type
>vs
>     type ptr is access cell
>     type cell is record
>         comp : My_Type;
>         next : ptr;
>     end record;
...

From a pifometric point of view, I would say the array - with a 
loop-unrolling
option to the compiler. But it depends on the size of your record, the 3D 
graphics
system, etc. . My guess is that the speed will be very near for the two 
variants.
But, the better is to compare, say with a lot of small faces so you have a 
greater
CPU time for the traversal of your structure and a smaller time for the 
processing,
so you see a bit more the comparison.
HTH
________________________________________________________
Gautier  --  http://www.mysunrise.ch/users/gdm/gsoft.htm

NB: For a direct answer, e-mail address on the Web site!

_________________________________________________________________
STOP MORE SPAM with the new MSN 8 and get 2 months FREE* 
http://join.msn.com/?page=features/junkmail

Re: fastest data structure

[Victor Porton]

In article <at5kmf$3ia$1@news-reader12.wanadoo.fr>,
	"Etienne Baudin" <pfoxNO@SPAMfree.fr> writes:
> Hello,
> 
> I'd like to know which of these 2 data structures is the fastest to proceed
>:
> 
> an simple array of  "My_type" (My type is a record...)
> or a liked liste of  "My_Type"

[skip]

> for i in A'range loop
>     processing A(i)
> end loop;
> 
> while (p != null) loop
>     process p.comp;
>     p := p.next;
> end loop;

Depends on CPU and compiler.

IMO, the first is faster in most cases (may be in 95% of cases).

Re: fastest data structure

[Jeffrey Carter]

Etienne Baudin wrote:
> for i in A'range loop
>     processing A(i)
> end loop;
> 
> while (p != null) loop
>     process p.comp;
>     p := p.next;
> end loop;

If you're actually doing something interesting and useful in your 
processing, I suspect the difference will be so small you won't even 
notice it.

-- 
Jeff Carter
"From this day on, the official language of San Marcos will be Swedish."
Bananas

Re: fastest data structure

[SteveD]

"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
>
>

Re: fastest data structure

[Marin David Condic]

I'm glad someone actually ran a test. When you've got two alternate
implementations that don't have any obvious performance differences (Binary
search vs linear search for example) the only way you can be sure is to run
a timing benchmark. Its also really important to note that just because one
works faster than the other in this test, that this is not sufficient reason
to believe that this will be true for different Ada compilers and different
targets. There may have even been different switches you could have set with
Gnat that might have changed the performance outcome. The really important
point being you can't really know without testing and unless you test all
implementations everywhere, you can't come to general conclusions about
performance of some feature within a language.

MDC
--
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jast.mil/

Send Replies To: m c o n d i c @ a c m . o r g

    "I'd trade it all for just a little more"
        --  Charles Montgomery Burns, [4F10]
======================================================================

SteveD <nospam_steved94@attbi.com> wrote in message
news:ScyJ9.313000$QZ.46513@sccrnsc02...
>
> "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
> >
> >
>
>

Re: fastest data structure

[Etienne Baudin]

Thanks for answers and the test program. I just modified My_type with a
record like that

type My_Type is record
    un : Integer;
    deux : Integer;
    trois : Integer;
    quatre : Integer;
    cinq : Integer;
    six : Integer;
 end record;

and process:

   procedure Processing (Data : My_Type ) is
      value : Integer;
      pragma Volatile( Value );
   begin
      value := data.un;
      value := data.un;
      value := data.un;
      value := data.un;
   end Processing;

and I obtained some weird results :

-- when I let the six components in My_type
Time for array based loop is   0.00151
Time for linked list based loop is   0.00175

-- with only 3 components in the record
Time for array based loop is   0.00109
Time for linked list based loop is   0.00112

--with only 1 component :
Time for array based loop is   0.00050
Time for linked list based loop is   0.00047

The process is the same with the 3 test (always reading "un") , and the
running time seems depend on the record size....??

Etienne Baudin

Re: fastest data structure

[Lutz Donnerhacke]

* Etienne Baudin wrote:
> The process is the same with the 3 test (always reading "un") , and the
> running time seems depend on the record size....??

The increment can be done in a simple (incrementing by 4) or complex
(increment by 17) way. Processors are optimized on special increments. The
other way to compute the new address is even optimized on special offsets.
Futhermore smaller records increases the data locality, so the cache does a
better job on smaller data.

Re: fastest data structure

[tmoran]

> running time seems depend on the record size....??
Perhaps the single element record is passed by copy in a register while
the larger records are passed by reference?  What are the speeds of
your memory (cache?) and CPU - the array may need a multiply of some
sort, while the pointer may need a memory reference.
  If this is actually significant in your application, perhaps you should
re-examine your algorithm and then code in hand-optimized assembly.

Re: fastest data structure

[SteveD]

  I am not surprised by your results.

  When more time that is spent in "Processing" a smaller percentage of
overall time is spent in the loop overhead.  When the size of the records is
increased, the time it takes to copy those records is increased.

  Also:  If you're doing serious timing tests it is a good idea to run
enough iterations to get the overal times significantly longer that the
system clock rate.  I usually shoot for overall times of at least a few
seconds.

  Since you seem to be focused on optimizing, I would like to quote from
Meiler Page-Jones "The Practical Guide to Structured Systems Design" (an old
book, but may of the principles still hold).

  Jackson gives two rules for determining when to optimize:
    1. Don't do it.
    2. Don't do it yet.
  Optimize only the parts of a system worth optimizing.  One of the old
systems
  proverbs, the 90-10 rule, says: In a typical application, 90 percent of
the total
  run time is devoted to executing only 10 percent of the code.

  With the added corrolaries (I can't quote the source):
  It's easier to optimize a working system than it is to make an optimized
system work.

Steve
(The Duck)

"Etienne Baudin" <pfoxNO@SPAMfree.fr> wrote in message
news:at7k2o$9fb$1@news-reader10.wanadoo.fr...
> Thanks for answers and the test program. I just modified My_type with a
> record like that
>
> type My_Type is record
>     un : Integer;
>     deux : Integer;
>     trois : Integer;
>     quatre : Integer;
>     cinq : Integer;
>     six : Integer;
>  end record;
>
> and process:
>
>    procedure Processing (Data : My_Type ) is
>       value : Integer;
>       pragma Volatile( Value );
>    begin
>       value := data.un;
>       value := data.un;
>       value := data.un;
>       value := data.un;
>    end Processing;
>
> and I obtained some weird results :
>
> -- when I let the six components in My_type
> Time for array based loop is   0.00151
> Time for linked list based loop is   0.00175
>
> -- with only 3 components in the record
> Time for array based loop is   0.00109
> Time for linked list based loop is   0.00112
>
> --with only 1 component :
> Time for array based loop is   0.00050
> Time for linked list based loop is   0.00047
>
> The process is the same with the 3 test (always reading "un") , and the
> running time seems depend on the record size....??
>
> Etienne Baudin
>
>

Re: fastest data structure

[P R Keeble]

>   Since you seem to be focused on optimizing, I would like to quote
>   from 
> Meiler Page-Jones "The Practical Guide to Structured Systems Design"
> (an old book, but may of the principles still hold).
> 
>   Jackson gives two rules for determining when to optimize:
>     1. Don't do it.
>     2. Don't do it yet.
>   Optimize only the parts of a system worth optimizing.  One of the
>   old 
> systems
>   proverbs, the 90-10 rule, says: In a typical application, 90 percent
>   of 
> the total
>   run time is devoted to executing only 10 percent of the code.
> 
>   With the added corrolaries (I can't quote the source):
>   It's easier to optimize a working system than it is to make an
>   optimized 
> system work.
> 
> Steve
> (The Duck)
> 

And Knuth will add to that "Premature optimisation is the root of all 
evil".

Can't say I agree its the reason my mother still cooks but it's 
reasponsible for everything else!

Re: fastest data structure

[Simon Wright]

"SteveD" <nospam_steved94@attbi.com> writes:

>   Optimize only the parts of a system worth optimizing.  One of the
> old systems proverbs, the 90-10 rule, says: In a typical
> application, 90 percent of the total run time is devoted to
> executing only 10 percent of the code.

One problem with code generators (including compilers) is that you
tend to get distributed overhead. If you have a generic that is
instantiated in hundreds of places in your system, it's very hard to
see the inefficiencies using something like gprof.

Re: fastest data structure

[Randy Brukardt]

Simon Wright wrote in message ...
>"SteveD" <nospam_steved94@attbi.com> writes:
>
>>   Optimize only the parts of a system worth optimizing.  One of the
>> old systems proverbs, the 90-10 rule, says: In a typical
>> application, 90 percent of the total run time is devoted to
>> executing only 10 percent of the code.
>
>One problem with code generators (including compilers) is that you
>tend to get distributed overhead. If you have a generic that is
>instantiated in hundreds of places in your system, it's very hard to
>see the inefficiencies using something like gprof.

Unless your compiler uses code-shared generics. (Plug for Janus/Ada. :-)

Of course, then you have the distributed overhead of generic sharing.
(I'm afraid that there still is no free lunch.)

          Randy Brukardt.