From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.4 required=5.0 tests=AC_FROM_MANY_DOTS,BAYES_00, LOTS_OF_MONEY autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,229a77b902096176 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-12-11 05:03:50 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!arclight.uoregon.edu!wn13feed!wn11feed!worldnet.att.net!207.217.77.102!newsfeed2.earthlink.net!newsfeed.earthlink.net!stamper.news.pas.earthlink.net!stamper.news.atl.earthlink.net!harp.news.atl.earthlink.net!not-for-mail From: "Marin David Condic" Newsgroups: comp.lang.ada Subject: Re: fastest data structure Date: Wed, 11 Dec 2002 08:03:13 -0500 Organization: MindSpring Enterprises Message-ID: References: NNTP-Posting-Host: d1.56.b0.ab X-Server-Date: 11 Dec 2002 13:03:45 GMT X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.00.2314.1300 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 Xref: archiver1.google.com comp.lang.ada:31680 Date: 2002-12-11T13:03:45+00:00 List-Id: 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 wrote in message news:ScyJ9.313000$QZ.46513@sccrnsc02... > > "Etienne Baudin" 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 > > > > > >