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.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD, FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,bb7cc916bd63ab43 X-Google-Attributes: gid103376,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII Path: g2news1.google.com!news1.google.com!postnews.google.com!o40g2000yqb.googlegroups.com!not-for-mail From: george.priv@gmail.com Newsgroups: comp.lang.ada Subject: Re: Performance of element access in Vector Date: Sun, 18 Jan 2009 19:23:40 -0800 (PST) Organization: http://groups.google.com Message-ID: References: <0a8baaf0-19f7-40c0-a041-884e93fa7020@w39g2000prb.googlegroups.com> NNTP-Posting-Host: 69.250.188.114 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: posting.google.com 1232335421 4884 127.0.0.1 (19 Jan 2009 03:23:41 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Mon, 19 Jan 2009 03:23:41 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: o40g2000yqb.googlegroups.com; posting-host=69.250.188.114; posting-account=VnNb3AoAAACTpRtCcTrcjmPX7cs92k1Q User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.0.5) Gecko/2008120122 Firefox/3.0.5,gzip(gfe),gzip(gfe) Xref: g2news1.google.com comp.lang.ada:3433 Date: 2009-01-18T19:23:40-08:00 List-Id: On Jan 18, 4:42=A0pm, Maciej Sobczak wrote: > In a nearby thread I have asked about the performance of > Update_Element in Vector. > The question was related to using the same interface in smart pointers > (and other containers/handlers). > > So I wrote a test: > > with Ada.Calendar.Formatting; > with Ada.Containers.Vectors; > with Ada.Text_IO; > > procedure A is > > =A0 =A0package Int_Vectors is new Ada.Containers.Vectors > =A0 =A0 =A0(Index_Type =3D> Positive, Element_Type =3D> Integer); > > =A0 =A0V : Int_Vectors.Vector :=3D Int_Vectors.To_Vector(0, 1_000_000); > > =A0 =A0procedure Increment (I : in out Integer) is > =A0 =A0begin > =A0 =A0 =A0 I :=3D I + 1; > =A0 =A0end Increment; > > =A0 =A0Iterations : constant :=3D 10_000; > > =A0 =A0Start : Ada.Calendar.Time; > =A0 =A0Stop : Ada.Calendar.Time; > > =A0 =A0use type Ada.Calendar.Time; > > =A0 =A0procedure Test_1 is > =A0 =A0begin > =A0 =A0 =A0 Start :=3D Ada.Calendar.Clock; > > =A0 =A0 =A0 for J in 1 .. Iterations loop > =A0 =A0 =A0 =A0 =A0for I in V.First_Index .. V.Last_Index loop > =A0 =A0 =A0 =A0 =A0 =A0 V.Replace_Element (I, V.Element (I) + 1); > =A0 =A0 =A0 =A0 =A0end loop; > =A0 =A0 =A0 end loop; > > =A0 =A0 =A0 Stop :=3D Ada.Calendar.Clock; > =A0 =A0 =A0 Ada.Text_IO.Put_Line > =A0 =A0 =A0 =A0 ("direct index =A0 =A0 =A0 =A0 =A0 =A0 : " & > =A0 =A0 =A0 =A0 =A0 =A0Ada.Calendar.Formatting.Image (Stop - Start, True)= ); > =A0 =A0end Test_1; > > =A0 =A0procedure Test_2 is > =A0 =A0begin > =A0 =A0 =A0 Start :=3D Ada.Calendar.Clock; > > =A0 =A0 =A0 for J in 1 .. Iterations loop > =A0 =A0 =A0 =A0 =A0for I in V.First_Index .. V.Last_Index loop > =A0 =A0 =A0 =A0 =A0 =A0 V.Update_Element (I, Increment'Access); > =A0 =A0 =A0 =A0 =A0end loop; > =A0 =A0 =A0 end loop; > > =A0 =A0 =A0 Stop :=3D Ada.Calendar.Clock; > =A0 =A0 =A0 Ada.Text_IO.Put_Line > =A0 =A0 =A0 =A0 ("Update_Element and index : " & > =A0 =A0 =A0 =A0 =A0 =A0Ada.Calendar.Formatting.Image (Stop - Start, True)= ); > =A0 =A0end Test_2; > > =A0 =A0procedure Test_3 is > =A0 =A0 =A0 C : Int_Vectors.Cursor; > =A0 =A0begin > =A0 =A0 =A0 Start :=3D Ada.Calendar.Clock; > > =A0 =A0 =A0 for J in 1 .. Iterations loop > =A0 =A0 =A0 =A0 =A0C :=3D V.First; > =A0 =A0 =A0 =A0 =A0while Int_Vectors.Has_Element (C) loop > =A0 =A0 =A0 =A0 =A0 =A0 V.Replace_Element (C, Int_Vectors.Element (C) + 1= ); > =A0 =A0 =A0 =A0 =A0 =A0 Int_Vectors.Next (C); > =A0 =A0 =A0 =A0 =A0end loop; > =A0 =A0 =A0 end loop; > > =A0 =A0 =A0 Stop :=3D Ada.Calendar.Clock; > =A0 =A0 =A0 Ada.Text_IO.Put_Line > =A0 =A0 =A0 =A0 ("direct cursor =A0 =A0 =A0 =A0 =A0 =A0: " & > =A0 =A0 =A0 =A0 =A0 =A0Ada.Calendar.Formatting.Image (Stop - Start, True)= ); > =A0 =A0end Test_3; > > =A0 =A0procedure Test_4 is > =A0 =A0 =A0 C : Int_Vectors.Cursor; > =A0 =A0begin > =A0 =A0 =A0 Start :=3D Ada.Calendar.Clock; > > =A0 =A0 =A0 for J in 1 .. Iterations loop > =A0 =A0 =A0 =A0 =A0C :=3D V.First; > =A0 =A0 =A0 =A0 =A0while Int_Vectors.Has_Element (C) loop > =A0 =A0 =A0 =A0 =A0 =A0 V.Update_Element (C, Increment'Access); > =A0 =A0 =A0 =A0 =A0 =A0 Int_Vectors.Next (C); > =A0 =A0 =A0 =A0 =A0end loop; > =A0 =A0 =A0 end loop; > > =A0 =A0 =A0 Stop :=3D Ada.Calendar.Clock; > =A0 =A0 =A0 Ada.Text_IO.Put_Line > =A0 =A0 =A0 =A0 ("Update_Element and cursor: " & > =A0 =A0 =A0 =A0 =A0 =A0Ada.Calendar.Formatting.Image (Stop - Start, True)= ); > =A0 =A0end Test_4; > > =A0 =A0procedure Test_5 is > > =A0 =A0 =A0 procedure Increment (C : in Int_Vectors.Cursor) is > =A0 =A0 =A0 begin > =A0 =A0 =A0 =A0 =A0V.Replace_Element (C, Int_Vectors.Element (C) + 1); > =A0 =A0 =A0 end Increment; > > =A0 =A0begin > =A0 =A0 =A0 Start :=3D Ada.Calendar.Clock; > > =A0 =A0 =A0 for J in 1 .. Iterations loop > =A0 =A0 =A0 =A0 =A0V.Iterate (Increment'Access); > =A0 =A0 =A0 end loop; > > =A0 =A0 =A0 Stop :=3D Ada.Calendar.Clock; > =A0 =A0 =A0 Ada.Text_IO.Put_Line > =A0 =A0 =A0 =A0 ("Iterate =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0: " & > =A0 =A0 =A0 =A0 =A0 =A0Ada.Calendar.Formatting.Image (Stop - Start, True)= ); > =A0 =A0end Test_5; > > begin > =A0 =A0Test_1; > =A0 =A0Test_2; > =A0 =A0Test_3; > =A0 =A0Test_4; > =A0 =A0Test_5; > end A; > > Each of the tests increments all vectors elements, using several > element access methods. > Here we go: > > ~/temp/ada $ gnatmake -O2 -gnatn -gnatN a > gcc -c -O2 -gnatn -gnatN a.adb > gnatbind -x a.ali > gnatlink a.ali > ~/temp/ada $ ./a > direct index =A0 =A0 =A0 =A0 =A0 =A0 : 00:00:23.34 > Update_Element and index : 00:02:17.20 > direct cursor =A0 =A0 =A0 =A0 =A0 =A0: 00:01:03.32 > Update_Element and cursor: 00:02:25.82 > Iterate =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0: 00:01:48.67 > ~/temp/ada $ > > The test shows that Update_Element is several time slower than > accessing elements by index. Cursor also adds some overhead. > > A possible conclusion is that for small elements (simple numeric > types, etc.) it makes sense to access elements by index, when they are > copied from and into the container. For larger elements the benefit of > accessing element in-place can be greater than the overhead of > Update_Element. > > Just to stir the discussion a bit, a straightforward implementation of > the same test in C++ (with the same base compiler and a single -O2 > option) runs in 13s with indexed access and in 9.5s with iterators - > both are based on the use of references, which do not exist in Ada. > Not very easy to neglect this difference. > > All comments are welcome. > > -- > Maciej Sobczak *www.msobczak.com*www.inspirel.com > > Database Access Library for Ada:www.inspirel.com/soci-ada Very interesting. It seems that compiler is unable to inline. I've added extra test to see what will be performance with raw array: Z : array (0 .. 1_000_000) of Integer :=3D (others =3D> 0); procedure Test_0 is begin Start :=3D Ada.Calendar.Clock; for J in 1 .. Iterations loop for I in Z'range loop Z(I) :=3D Z(I) + 1; end loop; end loop; Stop :=3D Ada.Calendar.Clock; Ada.Text_IO.Put_Line ("raw array : " & Ada.Calendar.Formatting.Image (Stop - Start, True)); end Test_0; Results came as: raw array : 00:00:09.82 direct index : 00:00:23.02 Update_Element and index : 00:01:29.96 direct cursor : 00:02:22.65 Update_Element and cursor: 00:03:36.51 Iterate : 00:02:13.03