Performance of element access in Vector

Performance of element access in Vector

[Maciej Sobczak]

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

Re: Performance of element access in Vector

[george.priv]

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

Re: Performance of element access in Vector

[george.priv]

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

Re: Performance of element access in Vector

[Georg Bauhaus]

george.priv@gmail.com schrieb:
> 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.

>> Each of the tests increments all vectors elements, using several
>> element access methods.

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

> Very interesting.
> 
> It seems that compiler is unable to inline.  I've added extra test to
> see what will be performance with raw array:

Starting from your test I have added a fake loop.
It is made to simulate the indirection typical of
Vector access, calling Increment via 'Access .
Indeed, inlining does not seem to happen.
Is this a GNAT feature?

gnatmake -O1 -W -g -gnato test_p.adb
raw array                : 00:00:57.47
raw array process        : 00:02:13.70

gnatmake -s -O2 -gnatn -gnatN -W -gnatp test_p.adb
raw array                : 00:00:29.42
raw array process        : 00:01:04.18


with Ada.Calendar.Formatting;
with Ada.Text_IO;

procedure Test_P is
   Iterations: constant := 10_000;

   procedure Increment (I : in out Integer) is
   begin
      I := I + 1;
   end Increment;

   type Int_Array is array(Positive range <>) of Integer;

   Start : Ada.Calendar.Time;
   Stop : Ada.Calendar.Time;

   use type Ada.Calendar.Time;

   procedure Test_0A (Container: in out Int_Array;
		      Process: not null access procedure (Element: in out Integer))  is
   begin
      Start := Ada.Calendar.Clock;

      for J in 1 .. Iterations loop
	 for Index in Container'Range loop
	    Process(Container(Index));
	 end loop;
      end loop;

      Stop := Ada.Calendar.Clock;
      Ada.Text_IO.Put_Line
        ("raw array process        : " &
           Ada.Calendar.Formatting.Image (Stop - Start, True));
   end Test_0A;

   procedure Test_0(Container: in out Int_Array) is
   begin
      Start := Ada.Calendar.Clock;

      for J in 1 .. Iterations loop
         for I in Container'range loop
            Container(I) := Container(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;

   Z: Int_Array(Positive range 1 .. 1_000_000);
begin
   Test_0(Z);
   Test_0A(Z, Increment'Access);
end Test_P;

Re: Performance of element access in Vector

[(see below)]

On 19/01/2009 03:23, in article
c8a97381-667c-4fda-8a1b-b4035f4281b8@o40g2000yqb.googlegroups.com,
"george.priv@gmail.com" <george.priv@gmail.com> wrote:
> 
> 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

On my very modest MacBook Pro, using:
GNATMAKE 4.4.0 20080329 (experimental) [trunk revision 133715]

With command:
gnatmake -funwind-tables  -g -gnatfl05wawCwl -gnatNnp \
-falign-loops=24  -fno-stack-check -funroll-loops -fsched-interblock -O3 A \
-largs -lgcc_eh -bargs -Sev

I get:

raw array                : 00:00:08.44
direct index             : 00:00:11.06
Update_Element and index : 00:00:50.31
direct cursor            : 00:00:20.51
Update_Element and cursor: 00:00:56.03
Iterate                  : 00:01:40.47

So it seems to be question of compiler version and options.

-- 
Bill Findlay
<surname><forename> chez blueyonder.co.uk

Re: Performance of element access in Vector

[Randy Brukardt]

"Maciej Sobczak" <see.my.homepage@gmail.com> wrote in message 
news:0a8baaf0-19f7-40c0-a041-884e93fa7020@w39g2000prb.googlegroups.com...
...
> 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.

Update_Element was added to handle large element types (such as other 
containers) where the overhead of copying them would be prohibitive. I doubt 
that it could be efficient for small objects that can cheaply be passed by 
copy.

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

What happens in C++ when the element whose reference you are using is 
deleted? In Ada.Containers, you'll get Program_Error if you try to do that - 
not a dangling pointer and havoc.

                                  Randy.

Re: Performance of element access in Vector

[Maciej Sobczak]

On 20 Sty, 03:17, "Randy Brukardt" <ra...@rrsoftware.com> wrote:

> What happens in C++ when the element whose reference you are using is
> deleted?

Formally speaking - undefined behavior.

The difference is, however, that it is possible to use vectors in C++
without going into undefined behavior, whereas it seems to be
impossible to use Vectors in Ada without being slow.

I think that given two correct programs a typical customer will pick
the faster one.

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Database Access Library for Ada: www.inspirel.com/soci-ada

Re: Performance of element access in Vector

[Dmitry A. Kazakov]

On Tue, 20 Jan 2009 00:03:03 -0800 (PST), Maciej Sobczak wrote:

> The difference is, however, that it is possible to use vectors in C++
> without going into undefined behavior, whereas it seems to be
> impossible to use Vectors in Ada without being slow.

There might be something wrong with the concept they share...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Performance of element access in Vector

[george.priv]

On Jan 20, 3:26 am, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> On Tue, 20 Jan 2009 00:03:03 -0800 (PST), Maciej Sobczak wrote:
> > The difference is, however, that it is possible to use vectors in C++
> > without going into undefined behavior, whereas it seems to be
> > impossible to use Vectors in Ada without being slow.
>
> There might be something wrong with the concept they share...
>
> --
> Regards,
> Dmitry A. Kazakovhttp://www.dmitry-kazakov.de

Unlike C++ for simple objects I don't see advantage of using vectors
vs. arrays in Ada.  Only that it provide uniform ways to traverse
through all containers?  Anything else I am missing?

Re: Performance of element access in Vector

[Maciej Sobczak]

On 20 Sty, 23:07, george.p...@gmail.com wrote:

> Unlike C++ for simple objects I don't see advantage of using vectors
> vs. arrays in Ada. Only that it provide uniform ways to traverse
> through all containers?  Anything else I am missing?

Growing/shrinking.

Vector can be built by appending without prior knowledge of the
element count. Think about reading data from files, databases, etc.
This is probably the most useful feature of this data structure.
Of course, it is also useful for element removal - Vector
automatically tracks its size. When compared to this, messing around
with explicit length (i.e. how many elements are "used" in the raw
array) management is too error prone.

In other words, Vector is not only dynamic, it is also self-conscious.

In C++ the only real reason to frown upon vector is in high-integrity
or constrained environments because of the dynamic memory issues.
Otherwise, in a general-purpose programming, it is superior to raw
arrays in 95% of cases and recommended as a "default" array-like
container. It also guarantees continuous storage, which makes it a
very nice direct I/O buffer - although this is not widely recognized.

For someone coming from the C++ universe the inability of Vectors in
Ada to do all these things with comparable performance is
disappointing and it looks like the notion of reference as a first-
class program entity is crucial here.

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Database Access Library for Ada: www.inspirel.com/soci-ada

Re: Performance of element access in Vector

[george.priv]

On Jan 21, 3:52 am, Maciej Sobczak <see.my.homep...@gmail.com> wrote:
> On 20 Sty, 23:07, george.p...@gmail.com wrote:
>
> > Unlike C++ for simple objects I don't see advantage of using vectors
> > vs. arrays in Ada. Only that it provide uniform ways to traverse
> > through all containers?  Anything else I am missing?
>
> Growing/shrinking.
>
> Vector can be built by appending without prior knowledge of the
> element count. Think about reading data from files, databases, etc.
> This is probably the most useful feature of this data structure.
> Of course, it is also useful for element removal - Vector
> automatically tracks its size. When compared to this, messing around
> with explicit length (i.e. how many elements are "used" in the raw
> array) management is too error prone.
>

Letting vector grow causes unpredictable run-time penalties.
Inserting/deleting elements can be time consuming.  If worse come to
worse these can be addressed in totally different programming paradigm
foreign to C++.

> In other words, Vector is not only dynamic, it is also self-conscious.
>
> In C++ the only real reason to frown upon vector is in high-integrity
> or constrained environments because of the dynamic memory issues.
> Otherwise, in a general-purpose programming, it is superior to raw
> arrays in 95% of cases and recommended as a "default" array-like
> container. It also guarantees continuous storage, which makes it a
> very nice direct I/O buffer - although this is not widely recognized.
>

Agree

> For someone coming from the C++ universe the inability of Vectors in
> Ada to do all these things with comparable performance is
> disappointing and it looks like the notion of reference as a first-
> class program entity is crucial here.
>

If you just try to get away from C++ paradigm you can find other ways
to address these issues with raw arrays.  Think in functional
programming framework for a change.

George


> --
> Maciej Sobczak *www.msobczak.com*www.inspirel.com
>
> Database Access Library for Ada:www.inspirel.com/soci-ada

Re: Performance of element access in Vector

[Georg Bauhaus]

george.priv@gmail.com schrieb:

> If you just try to get away from C++ paradigm you can find other ways
> to address these issues with raw arrays.  Think in functional
> programming framework for a change.


I'm curious.  Vector algorithms use the STL paradigm specifically,
rather than some C++ paradigm.  The STL with its generic algorithms
has a Scheme history (and an Ada one).  FP languages tend to start
from sequential access to data, using recursion on the tail of some
list as their model.  The STL notions of ::iterator and
::reverse_iterator, in particular considering their const variants,
suggest the same, to me at least.  So I have two questions:

1) How does straight forward STL iteration differ from
FP recursion on lists? (Only thing I can think of is
that non-pure languages can use destructive update
of array components, so to speak (tampering in some Ada sense).)

2) Can we rely on pure FPL style compilation techniques
(as if there were neither refs nor monads) to achieve
compact representation of lists/arrays in memory,
and little copying?
(I am assuming that memory use is an important criterion
when targetting small capacity hardware.)

Re: Performance of element access in Vector

[Maciej Sobczak]

On 22 Sty, 11:01, Georg Bauhaus <rm.dash-bauh...@futureapps.de> wrote:

> 1) How does straight forward STL iteration differ from
> FP recursion on lists?

Try to iterate over more than one sequence, in parallel, but not
necessarily with the same "speed".
Like, let's say, in merge sort.

You are right - the STL iteration is *straightforward*. :-)

> 2) Can we rely on pure FPL style compilation techniques

What for? You have a very nice *imperative* language - why would you
like to rely on non-imperative compilation techniques?

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Database Access Library for Ada: www.inspirel.com/soci-ada

Re: Performance of element access in Vector

[george.priv]

On Jan 22, 5:01 am, Georg Bauhaus <rm.dash-bauh...@futureapps.de>
wrote:
> george.p...@gmail.com schrieb:
>
> > If you just try to get away from C++ paradigm you can find other ways
> > to address these issues with raw arrays.  Think in functional
> > programming framework for a change.
>
> I'm curious.  Vector algorithms use the STL paradigm specifically,
> rather than some C++ paradigm.  The STL with its generic algorithms
> has a Scheme history (and an Ada one).  FP languages tend to start
> from sequential access to data, using recursion on the tail of some
> list as their model.  The STL notions of ::iterator and
> ::reverse_iterator, in particular considering their const variants,
> suggest the same, to me at least.  So I have two questions:
>
> 1) How does straight forward STL iteration differ from
> FP recursion on lists? (Only thing I can think of is
> that non-pure languages can use destructive update
> of array components, so to speak (tampering in some Ada sense).)
>
> 2) Can we rely on pure FPL style compilation techniques
> (as if there were neither refs nor monads) to achieve
> compact representation of lists/arrays in memory,
> and little copying?
> (I am assuming that memory use is an important criterion
> when targetting small capacity hardware.)

  The issue raised by Maciej was about reading arrays of a-priory
unknown size. That will be impossible with C/C++ arrays (not
vector<>).  I was trying to say that the elements of FP may be helpful
and Ada allows to use elements of FP with native array operations.
Trying to apply these technique to everything will be impractical.

G.

Re: Performance of element access in Vector

[Dmitry A. Kazakov]

On Tue, 20 Jan 2009 14:07:07 -0800 (PST), george.priv@gmail.com wrote:

> On Jan 20, 3:26�am, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
>> On Tue, 20 Jan 2009 00:03:03 -0800 (PST), Maciej Sobczak wrote:
>>> The difference is, however, that it is possible to use vectors in C++
>>> without going into undefined behavior, whereas it seems to be
>>> impossible to use Vectors in Ada without being slow.
>>
>> There might be something wrong with the concept they share...
>>
> Unlike C++ for simple objects I don't see advantage of using vectors
> vs. arrays in Ada.

Yes

> Only that it provide uniform ways to traverse
> through all containers?

Arrays do it already. Ordered containers must have array interface.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Performance of element access in Vector

[Maciej Sobczak]

On 21 Sty, 09:59, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

> > Only that it provide uniform ways to traverse
> > through all containers?
>
> Arrays do it already.

You mean that arrays have the Iterate method? Or cursor-like interface
with No_Element sentinel? I'm afraid they don't.

> Ordered containers must have array interface.

You mean that containers overload the () indexing? I'm afraid they
don't.

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Database Access Library for Ada: www.inspirel.com/soci-ada

Re: Performance of element access in Vector

[Dmitry A. Kazakov]

On Wed, 21 Jan 2009 01:19:48 -0800 (PST), Maciej Sobczak wrote:

> On 21 Sty, 09:59, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
> 
>>> Only that it provide uniform ways to traverse
>>> through all containers?
>>
>> Arrays do it already.
> 
> You mean that arrays have the Iterate method?

The language Ada has iteration methods, for example for-loop.

> Or cursor-like interface
> with No_Element sentinel? I'm afraid they don't.

They have array interface, which is much better than cursors and even so
No_Element-stuff.

>> Ordered containers must have array interface.
> 
> You mean that containers overload the () indexing? I'm afraid they
> don't.

That containers implement element access using an index from 1D space, if
we are talking about iterations.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Performance of element access in Vector

[Maciej Sobczak]

On 21 Sty, 11:19, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

> > You mean that arrays have the Iterate method?
>
> The language Ada has iteration methods, for example for-loop.

No, for-loops are not iteration methods, they are control structures.
Iteration methods are defined by particular interfaces and these are
different for arrays and Vectors.

> >> Ordered containers must have array interface.
>
> > You mean that containers overload the () indexing? I'm afraid they
> > don't.
>
> That containers implement element access using an index from 1D space, if
> we are talking about iterations.

This similarity can be interesting as a theory, but is useless in
practice.

Can you *reuse* a piece of code that traverses an array (or Vector)
and apply it to a Vector (or array, respectively)?

There are two reuse mechanisms in Ada, one with class-wide types and
run-time polymorphism and one with generics. Neither one can be
applied to the arrays vs. Vectors problem.
That's why, as far as I'm concerned, arrays and Vectors do not share
any interface.

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Database Access Library for Ada: www.inspirel.com/soci-ada

Re: Performance of element access in Vector

[Dmitry A. Kazakov]

On Wed, 21 Jan 2009 05:14:17 -0800 (PST), Maciej Sobczak wrote:

> On 21 Sty, 11:19, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
> 
>>> You mean that arrays have the Iterate method?
>>
>> The language Ada has iteration methods, for example for-loop.
> 
> No, for-loops are not iteration methods, they are control structures.

They are methods of iteration. You mean that for-loop is not a primitive
operation of array. Why should it be?

> Iteration methods are defined by particular interfaces and these are
> different for arrays and Vectors.

Yes, as an ugly hack container libraries provide "foreach" as a primitive
operation. It is even so ugly because neither Ada nor C++ support multiple
dispatch in order to make such a primitive operation truly primitive for
both the container and the element, or maybe for three, including
index/cursor.

>>>> Ordered containers must have array interface.
>>
>>> You mean that containers overload the () indexing? I'm afraid they don't.
>>
>> That containers implement element access using an index from 1D space, if
>> we are talking about iterations.
> 
> This similarity can be interesting as a theory, but is useless in
> practice.

I don't see any problems. For-loops were in practical use long before any
container libraries.

> Can you *reuse* a piece of code that traverses an array (or Vector)
> and apply it to a Vector (or array, respectively)?

You wrap for-loop into a procedure, that is.

> There are two reuse mechanisms in Ada, one with class-wide types and
> run-time polymorphism and one with generics. Neither one can be
> applied to the arrays vs. Vectors problem.

Why? It is trivial to define a primitive operation containing a loop.

> That's why, as far as I'm concerned, arrays and Vectors do not share
> any interface.

They shall share array interface when ordered.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Performance of element access in Vector

[Georg Bauhaus]

Maciej Sobczak schrieb:
> On 21 Sty, 09:59, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
> 
>>> Only that it provide uniform ways to traverse
>>> through all containers?
>> Arrays do it already.
> 
> You mean that arrays have the Iterate method? Or cursor-like interface
> with No_Element sentinel? I'm afraid they don't.

In a formal sense, the container types do not have
an iteration interface either,  because Cursor
is its own type...

OTOH, generic algorithms such as Generic_Anonymous_Array_Sort
can be used with plain arrays or Vectors or ...

A message sent recently to the Ada Comments list
suggests a few new (generic) ideas.

Re: Performance of element access in Vector

[Alex R. Mosteo]

george.priv@gmail.com wrote:

> On Jan 20, 3:26 am, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
>> On Tue, 20 Jan 2009 00:03:03 -0800 (PST), Maciej Sobczak wrote:
>> > The difference is, however, that it is possible to use vectors in C++
>> > without going into undefined behavior, whereas it seems to be
>> > impossible to use Vectors in Ada without being slow.
>>
>> There might be something wrong with the concept they share...
>>
>> --
>> Regards,
>> Dmitry A. Kazakovhttp://www.dmitry-kazakov.de
> 
> Unlike C++ for simple objects I don't see advantage of using vectors
> vs. arrays in Ada.  Only that it provide uniform ways to traverse
> through all containers?  Anything else I am missing?

I like the ability to store unconstrained/classwide types. Basically it 
saves you the need of using a wrapper or access type. Take for example the 
basic newbie-head-scratching array of "strings".

Re: Performance of element access in Vector

[Randy Brukardt]

> "Maciej Sobczak" <see.my.homepage@gmail.com> wrote:

>> What happens in C++ when the element whose reference you are using is 
>> deleted?
>
>Formally speaking - undefined behavior.
>The difference is, however, that it is possible to use vectors in C++ 
>without going into undefined behavior, whereas it seems to be impossible to 
>use Vectors in Ada without being slow.

Maybe it is possible to avoid undefined behavior, but only if you (the 
programmer) never makes mistakes. I don't think such a programmer exists.

The containers in Ada are designed to be safe; that necessarily requires 
giving up a bit of performance. We didn't go all the way to perfectly safe 
in order to keep some modicum of performance.

But, honestly, if the performance of some data structure in your program is 
critical enough to make it worth timing, then it should not be written using 
a predefined container -- anybodies predefined containers. But for the vast 
majority of programs (probably over 90% of uses), the performance of a 
container (so long as it is reasonable) is not relevant.

>I think that given two correct programs a typical customer will pick
>the faster one.

In the absense of using SPARK or somthing like it, there are no correct 
programs. There are only more or less buggy ones, and ones that are more 
tolerant of bugs. (Testing proves nothing whatsoever about correctness; it 
can only prove that a program appears to work for a particular set of input. 
And I say "appears to work" because getting the right answer doesn't prove 
anything about the absense of bugs, either, it only proves that there aren't 
any bugs that change the answer. We Ada programmers do spend some time 
fixing bugs that don't actually affect the answer (such as unused 
initialization values that are out of range).)

So the real question is what amount of confidence that you have in the 
correctness of the program. Sadly, end users cannot tell the quality of the 
development process used on a program, so they end up thinking all programs 
are barely functioning garbage and then pick the one that is faster by 0.01 
sec (which is not noticable to a human) or, more likely, pick the one with 
the "cooler" graphics (despite the fact that the program itself is barely 
usable and not at all understandable).

                      Randy.

Re: Performance of element access in Vector

[Maciej Sobczak]

On 21 Sty, 00:01, "Randy Brukardt" <ra...@rrsoftware.com> wrote:

> Maybe it is possible to avoid undefined behavior, but only if you (the
> programmer) never makes mistakes. I don't think such a programmer exists.

Can you show a realistic example of such a mistake?
I'm asking, because I don't remember having this problem.

> The containers in Ada are designed to be safe; that necessarily requires
> giving up a bit of performance.

The problem here is that the compiler does not inline Update_Element/
Query_Element callbacks. Safety and performance are not in conflict
here, it is just a quality of implementation issue.
You can have both.

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Database Access Library for Ada: www.inspirel.com/soci-ada

Re: Performance of element access in Vector

[Georg Bauhaus]

Maciej Sobczak schrieb:

> The problem here is that the compiler does not inline Update_Element/
> Query_Element callbacks. Safety and performance are not in conflict
> here, it is just a quality of implementation issue.
> You can have both.

FWIW, if Iterate/Process is made a generic procedure as
in the original AI-302, and Increment is made a library
level procedure,  then GNAT confirms, in a sense,
that there might be a quality of implementation issue:

raw array                : 00:00:29.78
raw array process        : 00:01:06.74
raw array generic        : 00:00:29.78


with Increment;

...


   generic
      with procedure Process (Element: in out Integer);
   procedure Test_0B (Container: in out Int_Array);


   procedure Test_0B (Container: in out Int_Array)  is
   begin
      Start := Ada.Calendar.Clock;

      for J in 1 .. Iterations loop
         for Index in Container'Range loop
            Process(Container(Index));
         end loop;
      end loop;

      Stop := Ada.Calendar.Clock;
      Ada.Text_IO.Put_Line
        ("raw array generic        : " &
           Ada.Calendar.Formatting.Image (Stop - Start, True));
   end Test_0B;


   declare
      procedure Test_G is new Test_0B(Process => Increment);
   begin
      Test_G(Z);
   end;

Re: Performance of element access in Vector

[Alex R. Mosteo]

Georg Bauhaus wrote:

> Maciej Sobczak schrieb:
> 
>> The problem here is that the compiler does not inline Update_Element/
>> Query_Element callbacks. Safety and performance are not in conflict
>> here, it is just a quality of implementation issue.
>> You can have both.
> 
> FWIW, if Iterate/Process is made a generic procedure as
> in the original AI-302, and Increment is made a library
> level procedure,  then GNAT confirms, in a sense,
> that there might be a quality of implementation issue:
> 
> raw array                : 00:00:29.78
> raw array process        : 00:01:06.74
> raw array generic        : 00:00:29.78

Do you mean, IIUC, that if 'process' where properly inlined, the timing 
would be same for the three instances? That would be nice.

Re: Performance of element access in Vector

[Georg Bauhaus]

Alex R. Mosteo schrieb:
> Georg Bauhaus wrote:
> 
>> Maciej Sobczak schrieb:
>>
>>> The problem here is that the compiler does not inline Update_Element/
>>> Query_Element callbacks. Safety and performance are not in conflict
>>> here, it is just a quality of implementation issue.
>>> You can have both.
>> FWIW, if Iterate/Process is made a generic procedure as
>> in the original AI-302, and Increment is made a library
>> level procedure,  then GNAT confirms, in a sense,
>> that there might be a quality of implementation issue:
>>
>> raw array                : 00:00:29.78
>> raw array process        : 00:01:06.74
>> raw array generic        : 00:00:29.78
> 
> Do you mean, IIUC, that if 'process' where properly inlined, the timing 
> would be same for the three instances? That would be nice.

The third line seems to indicate the possibility
of inlining, provided nothing else gets in the
way---in the case of 'Access to procedure; can't say.
Complete example with Increment made a library level
procedure for all three methods:

-- 8<--

procedure Increment (I : in out Integer);
pragma Inline(Increment);


with Ada.Calendar.Formatting;
with Ada.Text_IO;
with Increment;

procedure Test_P is
   Iterations: constant := 10_000;

   type Int_Array is array(Positive range <>) of Integer;

   Start : Ada.Calendar.Time;
   Stop : Ada.Calendar.Time;

   use type Ada.Calendar.Time;

   procedure Test_0A (Container: in out Int_Array;
                      Process: not null access procedure (Element: in
out Integer))  is
   begin
      Start := Ada.Calendar.Clock;

      for J in 1 .. Iterations loop
         for Index in Container'Range loop
            Process(Container(Index));
         end loop;
      end loop;

      Stop := Ada.Calendar.Clock;
      Ada.Text_IO.Put_Line
        ("raw array process        : " &
           Ada.Calendar.Formatting.Image (Stop - Start, True));
   end Test_0A;

   generic
      with procedure Process (Element: in out Integer);
   procedure Test_0B (Container: in out Int_Array);


   procedure Test_0B (Container: in out Int_Array)  is
   begin
      Start := Ada.Calendar.Clock;

      for J in 1 .. Iterations loop
         for Index in Container'Range loop
            Process(Container(Index));
         end loop;
      end loop;

      Stop := Ada.Calendar.Clock;
      Ada.Text_IO.Put_Line
        ("raw array generic        : " &
           Ada.Calendar.Formatting.Image (Stop - Start, True));
   end Test_0B;


   procedure Test_0(Container: in out Int_Array) is
   begin
      Start := Ada.Calendar.Clock;

      for J in 1 .. Iterations loop
         for I in Container'range loop
            Container(I) := Container(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;

   Z: Int_Array(Positive range 1 .. 1_000_000);
begin
   Test_0(Z);
   Test_0A(Z, Increment'Access);
   declare
      procedure Test_G is new Test_0B(Process => Increment);
   begin
      Test_G(Z);
   end;
end Test_P;


procedure Increment (I : in out Integer) is
begin
   I := I + 1;
end Increment;