REQ: Extend slices for n dimensional arrays for Ada 202X

REQ: Extend slices for n dimensional arrays for Ada 202X

[Lucretia]

Hi,

Array slices are a very powerful feature of the language as it is right now, but the fact that they are limited to 1-dimensional arrays if short sighted. By having slices be applicable to all types of arrays would make memory copy operations much easier to do and would also eliminate possible array index calculation errors that we see in other languages.

Example:

When using my SDL bindings I would like to be able to copy a texture or sub-texture, be that 1D, 2D or 3D, from one texture to an area within another texture. As an example, this would be perfect for implementing a movie player, decode frame into buffer, e.g.

  Texture (x1 .. x2, y1 .. y2) := Buffer;  --  Buffer is the correct size.

Because these would be primitive types, there would be no way to provide an alternative copy operation which doesn't use the CPU, so I would suggest a new attribute to allow for this:

  for Texture_Type'Copy use GPU_Copy;

where GPU_Copy could be defined as:

  procedure GPU_Copy (Source : in out Texture_Type; Dest : in Texture_Type);

This is not just useful for games which can get quite low-level as can be seen, it could be used to implement DMA copying on an embedded system, or offloading to another MCU on the board.

Another point is that this could open Ada up even more into new areas of work, such as games. 

Luke.

Re: REQ: Extend slices for n dimensional arrays for Ada 202X

[Lucretia]

On Thursday, 26 January 2017 13:29:47 UTC, Lucretia  wrote:

> 
>   Texture (x1 .. x2, y1 .. y2) := Buffer;  --  Buffer is the correct size.

I forgot to mention something else. I put the above notation down as someone in #Ada liked tha, but I would prefer the following:

  Texture (x1, y1 .. x2, y2) := Buffer;  --  Buffer is the correct size.

The reasoning is as follows:

1) That is easier for people to visualise.
2) That follows how n-dimensional arrays are accessed in Ada, i.e.

  procedure Test is
     type Matrix is array (1 .. 4, 1 .. 4) of Float;
   
     I : Matrix;
  begin
     I (1, 4) := 0.0;
  end Test;

Luke.

Re: REQ: Extend slices for n dimensional arrays for Ada 202X

[Lucretia]

On Thursday, 26 January 2017 14:01:22 UTC, Lucretia  wrote:

>   procedure Test is
>      type Matrix is array (1 .. 4, 1 .. 4) of Float;
>    
>      I : Matrix;
>   begin
>      I (1, 4) := 0.0;
>   end Test;

Hate when I'm in a rush, I forget things, as an example of the above, getting the 3D matrix from the 4D one would be as follows:

M3D := I (1, 1 .. 3, 3); --  Just the rotation and scale elements!

Luke.

Re: REQ: Extend slices for n dimensional arrays for Ada 202X

[Dmitry A. Kazakov]

On 26/01/2017 15:01, Lucretia wrote:
> On Thursday, 26 January 2017 13:29:47 UTC, Lucretia  wrote:
>
>>
>>   Texture (x1 .. x2, y1 .. y2) := Buffer;  --  Buffer is the correct size.
>
> I forgot to mention something else. I put the above notation down as
> someone in #Ada liked tha, but I would prefer the following:
>
>   Texture (x1, y1 .. x2, y2) := Buffer;  --  Buffer is the correct size.

I don't understand the latter. (X1, Y1) .. (X2, Y2) is not a submatrix 
it is a linear slice:

  I   1 2 3 4
      -------
  1 | a b c d
  2 | e f g h
  3 | i j k l
  4 | m n o p

Submatrix 1..2, 2..4 is

      1 2 3
      -----
  1 | b c d
  2 | f g h

(1,2) .. (2,4) is a vector

  1 | b
  2 | c
  3 | d
  4 | e
  5 | f
  6 | g
  7 | h

> The reasoning is as follows:
>
> 1) That is easier for people to visualise.
> 2) That follows how n-dimensional arrays are accessed in Ada, i.e.
>
>   procedure Test is
>      type Matrix is array (1 .. 4, 1 .. 4) of Float;
>
>      I : Matrix;
>   begin
>      I (1, 4) := 0.0;
>   end Test;

It does not follow. The indexing notation is as a tuple

    I1 x I2 x ... x IN

Where Ik is either a singleton (collapsed dimension) or a subset of the 
index (in Ada a range).

With generic subsets I ({1,2},{2,4}) would mean

       1 2
       ---
   1 | b d
   2 | f g

You forgot notation for whole index range:

   I (<>, 1)  -- column 1.

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

Re: REQ: Extend slices for n dimensional arrays for Ada 202X

[Alejandro R. Mosteo]

On 26/01/17 15:52, Dmitry A. Kazakov wrote:

> You forgot notation for whole index range:
>
>   I (<>, 1)  -- column 1.
>

Rings a bell from Matlab. Nice!

Re: REQ: Extend slices for n dimensional arrays for Ada 202X

[Lucretia]

On Thursday, 26 January 2017 14:52:04 UTC, Dmitry A. Kazakov  wrote:
> On 26/01/2017 15:01, Lucretia wrote:
> > On Thursday, 26 January 2017 13:29:47 UTC, Lucretia  wrote:
> >
> >>
> >>   Texture (x1 .. x2, y1 .. y2) := Buffer;  --  Buffer is the correct size.
> >
> > I forgot to mention something else. I put the above notation down as
> > someone in #Ada liked tha, but I would prefer the following:
> >
> >   Texture (x1, y1 .. x2, y2) := Buffer;  --  Buffer is the correct size.
> 
> I don't understand the latter. (X1, Y1) .. (X2, Y2) is not a submatrix 
> it is a linear slice:

You're being deliberately obtuse. I even spelt out the semantics above. The language designers spell out the semantics of the language constructs as I did.

For the 1D case, we define an array as:

  type Some_Array is array (Positive range 1 .. 5) of Integer;

Access an element with:

  T : Some_Array;

  T (4) := 3;

Slice with:

  S : Some_Array := T (2 .. 4);

For the 2D and above case, we define an array as:

  type Some_Array is array (Positive range 1 .. 5, Positive range 1 .. 10) of Integer;

Access an element with:

  T : Some_Array;

  T (1, 1) := 3;

So we could slice with:

  S : Some_Array := T (2, 2 .. 4, 6);  -- Square slice!

So in the following case (row-major order):

  | 1 2 3 4
-----------
1 | a e i m
2 | b f j n
3 | c g k o
4 | d h l p

A slice of (2,2 .. 3,4) would give:

  | 1 2
-------
1 | f j
2 | g k
3 | h l

Not a linear vector, because that's not the semantics I'm looking for, is it?

> 
> You forgot notation for whole index range:
> 
>    I (<>, 1)  -- column 1.

This is irrelevant as you cannot assign I (<>) in the 1D case anyway.

Luke.

Re: Extend slices for n dimensional arrays for Ada 202X

[Randy Brukardt]

"Lucretia" <laguest9000@googlemail.com> wrote in message 
news:df643a73-3e84-4517-ba81-7bc50d0c0d54@googlegroups.com...
Hi,

>Array slices are a very powerful feature of the language as it is right 
>now, but the fact
>that they are limited to 1-dimensional arrays if short sighted. By having 
>slices be
>applicable to all types of arrays would make memory copy operations much
>easier to do and would also eliminate possible array index calculation 
>errors that
>we see in other languages.

Maybe much easier for you, but a nightmare for the compiler, as the array 
components would not be contiguous in any way. The performance of

>  Texture (x1 .. x2, y1 .. y2) := Buffer;  --  Buffer is the correct size.

would be roughly the same as explicitly writing the pair of for loops:

    for I1 in x1 .. x2 loop
        for I2 in y1 .. y2 loop
              Texture (I1, I2) := Buffer (I1 - <offset1>, I2 - <offset2>);
        end loop;
    end loop;

There's no way to speed it up in general.

Moreover, slices are names in Ada, so they can be passed as "in out" 
parameters. Consider implementing:

                Invert (Texture (x1 .. x2, y1 .. y2));

where the elements of Texture are not continuous.

1-dimensional slices are just that: a contigious slice of an array. That is 
true only in unusual cases for multi-dimensional arrays.

The existing implementation of unconstrained arrays is to pass a bounds 
descriptor and pointer at the data - such an implementation would not work 
here. Moreover, this would cause a distributed overhead -- all parameter 
passing of unconstrained multi-dimensional arrays would have support 
non-contiguous components, slowing all operations significantly.

For us to even consider such an operation in Ada, its use would have to be 
highly constrained, so that its existence would not impact the performance 
of other operations (such as the matrix libraries in Annex G). But if that 
was the case, then it would look more bolted-on than an integrated feature 
of the language. We have enough of those as it is.

So I don't see this happening - it doesn't make sense in the context of Ada 
implementation strategies.

                                   Randy.

Re: Extend slices for n dimensional arrays for Ada 202X

[Robert Eachus]

On Thursday, January 26, 2017 at 1:29:07 PM UTC-5, Randy Brukardt wrote:

> So I don't see this happening - it doesn't make sense in the context of Ada 
> implementation strategies.

Randy, I hope you are confused.  First, if you are copying one array to another with correct (possibly sliding) bounds, you should check the bounds, then do whatever copy is fastest on the current hardware.  (This is moving from 64 to 128 bits at a time, and current hardware supports single instruction 256-bit and even 512-bit moves.)  Yes, technically, if in strict mode and the floating-point type you are using does not use non-signalling infinities, you might need to discover where an exception occurs and do a partial copy.  But if this is an object to object assignment, the best code with signalling infinities would be to scan the data for signalling entries, then do the copy.  Having to back out half the copy is messy. 

For decades I've been doing linear algebra in Ada where sometimes it helps to have some arrays in row-major order and others in column-major order.  Take simple matrix multiplication for example A * B --> C.  If I declare B as  "with Convention => Fortran;" now I get significantly faster results from:
      for I in A'Range(1) loop
        for J in B'Range(2) loop
          Temp := 0.0;
          for K in A'Range(2) loop
            Temp := Temp + A(I,K) * B(K,J);
          end loop;
          C(I,J) := Temp;
        end loop;
      end loop;

If you try it for reasonably large I, J, and K, you should find that the payoff is large compared to the cost of transposing B once. (It is possible to transpose B in place (the J=K case is a lot easier than the general case) but I'm used to having way more (virtual and real) memory than I need 

In this case, B is accessed in the proper fashion.  But the "ugly" computations you complained about would be needed to iterate over B in row major order.  I just assumed that all compilers generate the correct code for the hard case, which I don't use anyway. ;-)

Re: Extend slices for n dimensional arrays for Ada 202X

[Robert Eachus]

Whoops!  I apologize an editing error made this sound nasty...

On Thursday, January 26, 2017 at 8:54:53 PM UTC-5, Robert Eachus wrote:
> On Thursday, January 26, 2017 at 1:29:07 PM UTC-5, Randy Brukardt wrote:
> 
> > So I don't see this happening - it doesn't make sense in the context of Ada 
> > implementation strategies.
> 
> Randy, I hope you are confused.
...about how your compiler deals with copying complex objects.  About 30 years ago, Dave Emery found that the Verdix compiler was moving strings a byte at a time and wrote a (32-bit) word at a time routine (in Ada) which did all the messy misalignment stuff, and did go byte at a time for short strings.  Verdix asked permission to put the code in their run-time.  So Dave wrote it up--I don't remember if it was for Ada Letters or Ada Europe, but anyway made it public domain.  AS far as I knew all the Ada compilers picked it up, it about doubled Dhrystone scores. ;-)
  
It would be nice to have one-dimensional slices of two dimensional arrays.  But supporting Fortran interfaces messes that up, unless someone could figure out a way to make the situation work for the easy cases and illegal for the difficult cases.  I do have code which maps a series of vectors onto a matrix.  It is not too difficult, but tends to end up with theoretically non-portable code.  (You need to know the size of the descriptor at the start of an unconstrained array.  I suspect it is the same for all compilers for the normal cases, but no guarantee.

I guess you could use the same (Unchecked_Conversion) method to put (constrained) records on top of an array if you want to step through the columns.  But as I said above, on modern hardware it just pays too well to do the transpose.  You do the transpose several rows at a time, sized based on caches.  Figuring the 'right' size for a given machine takes work, best if you can do it is to read from multiple rows and put together one cache line in the output.

Re: Extend slices for n dimensional arrays for Ada 202X

[Lucretia]

On Friday, 27 January 2017 01:54:53 UTC, Robert Eachus  wrote:

> Randy, I hope you are confused.  First, if you are copying one array to 

You think this is doable for small arrays where the CPU handles the copy, what about the massive arrays I'm talking about? Also the case of the custom copy routine where another, more custom, processor handles the copy?

Re: Extend slices for n dimensional arrays for Ada 202X

[Randy Brukardt]

"Robert Eachus" <rieachus@comcast.net> wrote in message 
news:fb3687c7-0a40-4f8e-abfc-0438a45d2374@googlegroups.com...
On Thursday, January 26, 2017 at 1:29:07 PM UTC-5, Randy Brukardt wrote:

>> So I don't see this happening - it doesn't make sense in the context of 
>> Ada
>> implementation strategies.

>Randy, I hope you are confused.

I'm not confused. The case in question is a 2-dimensional slice where the 
sliced components are not (necessarily) contiguous. For instance:
    type Matrix_Type is array (Positive range <>, Positive range <>) of ...;
    Matrix : Matrix_Type (1..4, 1..4);
    procedure Proc (M : in out Matrix_Type);

    Proc (Matrix (2..3, 2..3));

The problem is that there can be no copying going on here, so the only way 
to do this is to pass a thunk. Which would necessarily have to be the case 
for any unconstrained multidimensional parameter passing.

Even copying can be an issue, since again the components on both sides can 
be discontiguous and in different ways. Of course a compiler can optimize 
the simple cases, but the general case has to be a loop.

Single dimensional slices are of course completely different, and I wasn't 
talking about them. (Although your advice for copying them is 25 years out 
of date: Intel hardware, at least, automatically makes many of those 
optimizations so there is no value to manually doing them yourself - that 
actually would make your code slower.)

                                   Randy.

Re: Extend slices for n dimensional arrays for Ada 202X

[Robert Eachus]

On Friday, January 27, 2017 at 6:30:32 PM UTC-5, Randy Brukardt wrote:

> Single dimensional slices are of course completely different, and I wasn't 
> talking about them. (Although your advice for copying them is 25 years out 
> of date: Intel hardware, at least, automatically makes many of those 
> optimizations so there is no value to manually doing them yourself - that 
> actually would make your code slower.)

As it happens, when I get down to the point of considering actual cache sizes and TLBs, I am coding for AMD CPUs.  (Even have one in this system. ;-)  But believe me, 4 or 5% time improvement is considered worthwhile, and I am usually doing finding 50% or more.  It also turns out that I am usually working on low-level routines often in BLAS that are eating loads of CPU time.  Oh, and I have yet to convince anyone to make the main program Ada instead of Fortran, but that's another issue.

Yes, modern CPUs will reorder operations to improve performance, but the reorder buffers have a limited reach.  So if you are transposing an array which is thousands of rows and columns in size, the programmer has to bring the instructions that should be brought together close enough that the CPU can do the rest.

Re: Extend slices for n dimensional arrays for Ada 202X

[Dmitry A. Kazakov]

On 26/01/2017 19:29, Randy Brukardt wrote:

> So I don't see this happening - it doesn't make sense in the context of Ada
> implementation strategies.

That is why I keep on saying, give users the array interface (and the 
array slice interface) and let users implement their custom arrays.

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

Re: Extend slices for n dimensional arrays for Ada 202X

[G.B.]

On 27.01.17 10:34, Dmitry A. Kazakov wrote:
> On 26/01/2017 19:29, Randy Brukardt wrote:
>
>> So I don't see this happening - it doesn't make sense in the context of Ada
>> implementation strategies.
>
> That is why I keep on saying, give users the array interface (and the array slice interface) and let users implement their custom arrays.
>

Will some Iterator_Interface and generalized
loop iteration not provide for custom arrays?


-- 
"HOTDOGS ARE NOT BOOKMARKS"
Springfield Elementary teaching staff

Re: Extend slices for n dimensional arrays for Ada 202X

[Dmitry A. Kazakov]

On 27/01/2017 14:53, G.B. wrote:
> On 27.01.17 10:34, Dmitry A. Kazakov wrote:
>> On 26/01/2017 19:29, Randy Brukardt wrote:
>>
>>> So I don't see this happening - it doesn't make sense in the context
>>> of Ada
>>> implementation strategies.
>>
>> That is why I keep on saying, give users the array interface (and the
>> array slice interface) and let users implement their custom arrays.
>
> Will some Iterator_Interface and generalized
> loop iteration not provide for custom arrays?

Not even close. Remember the question was about slices. A slice in 
copying context is an object of same or related type. The latter is when 
some dimensions get collapsed. E.g. a vector taken from a matrix, it is 
another type.

In the referential context it is even more complicated. A slice is 
always a type of different representation. As Randy has explained, Ada's 
built-in array types were designed with referential slices in mind.

It is a complex network of related types you cannot emulate with crude 
hacks like iterator interface.

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

Re: Extend slices for n dimensional arrays for Ada 202X

[Randy Brukardt]

"G.B." <bauhaus@notmyhomepage.invalid> wrote in message 
news:o6fja1$vq8$1@dont-email.me...
> On 27.01.17 10:34, Dmitry A. Kazakov wrote:
>> On 26/01/2017 19:29, Randy Brukardt wrote:
>>
>>> So I don't see this happening - it doesn't make sense in the context of 
>>> Ada
>>> implementation strategies.
>>
>> That is why I keep on saying, give users the array interface (and the 
>> array slice interface)
>> and let users implement their custom arrays.
>>
>
> Will some Iterator_Interface and generalized
> loop iteration not provide for custom arrays?

...and generalized indexing.

But those features don't have an provision for slices, and I don't see any 
way that they could be usefully extended to give slices. I tried a few years 
ago to come up with a Root_String_Class, which mostly would work well, but 
it gets ugly when dealing with slices and string literals. You can make 
something that works like a slice, but assigning into them or passing them 
as parameters would always require copies. Whether that's acceptable would 
depend on the application. (It doesn't seem to be a general solution.)

I'm unconvinced that Dmitry's array interfaces would have been any better: 
general slices really don't fit very well into any type model since they're 
a different shape (in general) than the originating array type.

                                      Randy.

Re: Extend slices for n dimensional arrays for Ada 202X

[Dmitry A. Kazakov]

On 2017-01-28 00:37, Randy Brukardt wrote:

> ... general slices really don't fit very well into any type model since they're
> a different shape (in general) than the originating array type.

It depends on the slice. When some dimensions are collapsed the result 
is a different but related type. When all dimensions are retained the 
type is same (or equivalent).

You consider a scenario where the array and its "full" slice have the 
same representation like in Ada 83. It would mean either keeping actual 
constraints in the object (bad) or else providing a universal mechanism 
of user-defined constraints passed along with the object. [Generic user 
constraints]

Another method is using a class-wide operation where both array and 
slice are expected. Slice would be a sibling type of different 
representation, both array and slice derived from the same abstract parent.

P.S. My vision of ideal Ada is when its type system would allow moving 
built-in arrays and records into the specification of the package 
Standard. [Tagged types should have had nothing to do with record types.]

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