Re: Efficient Sequential Access to Arrays

[Georg Bauhaus <rm.dash-bauhaus@futureapps.de>]

On 15.07.12 22:03, Keean Schupke wrote:
> On Sunday, 15 July 2012 20:48:35 UTC+1, Dmitry A. Kazakov  wrote:
>> On Sun, 15 Jul 2012 11:40:08 -0700 (PDT), Keean Schupke wrote:
>>
>> > However in order to achieve this performance I needed to rework the arrays
>> > as the use of Indexes was too slow.
>>
>> You have to measure it in order to know. Write two variants and compare
>> their performance.
>
> Have done, the difference is about 10k simulations per second.
>
>>
>> > An example of this is lets say we are
>> > accessing element 5 from array A "A(5)" this requires a multiplication to
>> > access (base_address + index * record_size).
>>
>> It does not, because 5 is constant.
>
> Obviously the index is not actually a constant but the result of selecting a random element in the list. The multiplication is necessary for finding this first element, but the operations on relative elements (+/-1, +/-2 etc) can use addition with a pointer, not so with an index.

There is address arithmetic in System.*. For the simple case of
constant distances, something like the following might have some
hints. Or it might if redone after thinking. procedure Grab has
the multiplication for offsets of components of a record type
object in an array.

The point is that one may express offsets by referring
to type attributes that follow from representation clauses
and then convert between addresses and pointers.

with Ada.Numerics.Float_Random;    use  Ada.Numerics.Float_Random;
with System.Address_To_Access_Conversions, System.Storage_Elements;
procedure Iter_Arrays (Size : Natural) is

    Storage_Elements : constant := 1;

    type Index is mod 2**32;
    type Data is digits 6;
    for Data'Size use 32;

    G : Generator;

    type Things is record
       One: Data := Data (Random (G));
       Two: Data := Data (Random (G));
    end record;

    for Things use record
       One at 0 * Storage_Elements range 0 .. Data'Size - 1;
       Two at 4 * Storage_Elements range 0 .. Data'Size - 1;
    end record;
    pragma Assert (Things'Size = 64);

    type List is array (Index range <>) of Things;
    for List'Alignment use 4 * Storage_Elements;
    for List'Component_Size use 64;


--  using array indexing

    procedure Bumble (A : in out List; Step : Index) is
    begin
       for K in A'First + Step .. A'Last - Step loop
          declare
             Diff_Backward : constant Data := A (K).One - A (K - Step).Two;
             Diff_Forward : constant Data := A (K).Two - A (K + Step).One;
          begin
             if (abs Diff_Backward) < (abs Diff_Forward) then
                A (K).One := A (K - Step).One;
             else
                A (K).Two := A (K + Step).Two;
             end if;
          end;
       end loop;
    end Bumble;


--  using relative addresses

    package Indirection is new System.Address_To_Access_Conversions
      (Object => Data);
    subtype Data_Pointer is Indirection.Object_Pointer;


    procedure Grab  (A : in out List; Step : Index) is
       -- [A] = [one][two][one][two]...[one][two]
       use System.Storage_Elements, Indirection;
       Offset_Backward : constant Storage_Offset :=
         Storage_Offset (0 + Step * 8 + 4);
       Offset_Forward : constant Storage_Offset :=
         Storage_Offset (0 - Step * 8 + 0);
    begin
       for K in A'First + Step .. A'Last - Step loop
          declare
             Back : constant Data_Pointer :=
               To_Pointer (A (K).One'Address + Offset_Backward);
             Ahead : constant Data_Pointer :=
               To_Pointer (A (K).Two'Address + Offset_Backward);
             Diff_Backward : constant Data := A (K).One - Back.all;
             Diff_Forward : constant Data := A (K).One - Ahead.all;
          begin
             if (abs Diff_Backward) < (abs Diff_Forward) then
                A (K).One := A (K - Step).One;
             else
                A (K).Two := A (K + Step).Two;
             end if;
          end;
       end loop;
    end Grab;

    Test_Data : List (0 .. Index(Size));

begin
    Bumble (Test_Data, 2);
    Grab (Test_Data, 3);
end Iter_Arrays;