Re: Performance of element access in Vector

[george.priv@gmail.com]

On Jan 18, 4:42 pm, Maciej Sobczak <see.my.homep...@gmail.com> 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
>
>    package Int_Vectors is new Ada.Containers.Vectors
>      (Index_Type => Positive, Element_Type => Integer);
>
>    V : Int_Vectors.Vector := Int_Vectors.To_Vector(0, 1_000_000);
>
>    procedure Increment (I : in out Integer) is
>    begin
>       I := I + 1;
>    end Increment;
>
>    Iterations : constant := 10_000;
>
>    Start : Ada.Calendar.Time;
>    Stop : Ada.Calendar.Time;
>
>    use type Ada.Calendar.Time;
>
>    procedure Test_1 is
>    begin
>       Start := Ada.Calendar.Clock;
>
>       for J in 1 .. Iterations loop
>          for I in V.First_Index .. V.Last_Index loop
>             V.Replace_Element (I, V.Element (I) + 1);
>          end loop;
>       end loop;
>
>       Stop := Ada.Calendar.Clock;
>       Ada.Text_IO.Put_Line
>         ("direct index             : " &
>            Ada.Calendar.Formatting.Image (Stop - Start, True));
>    end Test_1;
>
>    procedure Test_2 is
>    begin
>       Start := Ada.Calendar.Clock;
>
>       for J in 1 .. Iterations loop
>          for I in V.First_Index .. V.Last_Index loop
>             V.Update_Element (I, Increment'Access);
>          end loop;
>       end loop;
>
>       Stop := Ada.Calendar.Clock;
>       Ada.Text_IO.Put_Line
>         ("Update_Element and index : " &
>            Ada.Calendar.Formatting.Image (Stop - Start, True));
>    end Test_2;
>
>    procedure Test_3 is
>       C : Int_Vectors.Cursor;
>    begin
>       Start := Ada.Calendar.Clock;
>
>       for J in 1 .. Iterations loop
>          C := V.First;
>          while Int_Vectors.Has_Element (C) loop
>             V.Replace_Element (C, Int_Vectors.Element (C) + 1);
>             Int_Vectors.Next (C);
>          end loop;
>       end loop;
>
>       Stop := Ada.Calendar.Clock;
>       Ada.Text_IO.Put_Line
>         ("direct cursor            : " &
>            Ada.Calendar.Formatting.Image (Stop - Start, True));
>    end Test_3;
>
>    procedure Test_4 is
>       C : Int_Vectors.Cursor;
>    begin
>       Start := Ada.Calendar.Clock;
>
>       for J in 1 .. Iterations loop
>          C := V.First;
>          while Int_Vectors.Has_Element (C) loop
>             V.Update_Element (C, Increment'Access);
>             Int_Vectors.Next (C);
>          end loop;
>       end loop;
>
>       Stop := Ada.Calendar.Clock;
>       Ada.Text_IO.Put_Line
>         ("Update_Element and cursor: " &
>            Ada.Calendar.Formatting.Image (Stop - Start, True));
>    end Test_4;
>
>    procedure Test_5 is
>
>       procedure Increment (C : in Int_Vectors.Cursor) is
>       begin
>          V.Replace_Element (C, Int_Vectors.Element (C) + 1);
>       end Increment;
>
>    begin
>       Start := Ada.Calendar.Clock;
>
>       for J in 1 .. Iterations loop
>          V.Iterate (Increment'Access);
>       end loop;
>
>       Stop := Ada.Calendar.Clock;
>       Ada.Text_IO.Put_Line
>         ("Iterate                  : " &
>            Ada.Calendar.Formatting.Image (Stop - Start, True));
>    end Test_5;
>
> begin
>    Test_1;
>    Test_2;
>    Test_3;
>    Test_4;
>    Test_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             : 00:00:23.34
> Update_Element and index : 00:02:17.20
> direct cursor            : 00:01:03.32
> Update_Element and cursor: 00:02:25.82
> Iterate                  : 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 := (others => 0);


   procedure Test_0 is
   begin
      Start := Ada.Calendar.Clock;

      for J in 1 .. Iterations loop
         for I in Z'range loop
            Z(I) := Z(I) + 1;
         end loop;
      end loop;


      Stop := 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