Performance of element access in Vector

[Maciej Sobczak <see.my.homepage@gmail.com>]

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