After reading the various posts on arrays, slicing, indexing and striding I was thinking about striding, it's not something I have ever had the need to do (I'm not big on maths/graphics programming), but it's interesting to me nonetheless.

I felt the need to share these thoughts.. well, just cos. :)

The bit that intrigues me is how you'd implement it. Given the internals of D arrays, they are a pointer and a length, eg..

template Array(T) {
  uint length;
  T *pointer;
}

Then how do you represent a stride of that array? To me it seems it would have to be an array of pointers, or, a copy of the original data in a new array.

Assuming copying is not desired, you could use an array of pointers, but, you want it to behave like an array of the data pointed to, so in effect you'd want to perform some redirection internally.

Plus you need to keep a reference to the original data to stop the GC collecting it and invalidating all your stride pointers.

template Stride(T) {
  T*[] pointers;
  T[] original;
}

Not sure what effect proper rectangular arrays will have on this idea. I think it'll work with them too.

Regan.

-- 
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/

For a full explanation see the Multidim-Array proposal
        http://homepages.uni-regensburg.de/~nen10015/documents/D-multidimarray.html

In short words:

* dynamic arrays as we have them now stay unstrided. In string handling, striding is of little use, so strings deserve their "lightweight"-array type

* newly introduced are the full-fledged N-dimensional, strided arrays. These hold, in addition to "T *ptr" and the "int[N] range" field a "int[N] stride" field giving the strides in the individual directions.

For continuously stored arrays, the strides can be calculated from the ranges.

The idea to add striding arose from the fact that already with unstrided slicing of N-d arrays, the data will be stored non-continuously, so the strides cannot be calculated from the ranges any more. All but the lowest dimension will need a stride field anyway to implement unstrided slicing. So why not just add the last "stride"-field as well, adding a tiny bit of overhead but simplifying the concept and offering many new possibilities.

The idea of using pointers to each data element would be even more flexible, of course, but the overhead for that would be tremendous.



Regan Heath wrote:

> After reading the various posts on arrays, slicing, indexing and striding I was thinking about striding, it's not something I have ever had the need to do (I'm not big on maths/graphics programming), but it's interesting to me nonetheless.
> 
> I felt the need to share these thoughts.. well, just cos. :)
> 
> The bit that intrigues me is how you'd implement it. Given the internals of D arrays, they are a pointer and a length, eg..
> 
> template Array(T) {
>    uint length;
>    T *pointer;
> }
> 
> Then how do you represent a stride of that array? To me it seems it would have to be an array of pointers, or, a copy of the original data in a new array.
> 
> Assuming copying is not desired, you could use an array of pointers, but, you want it to behave like an array of the data pointed to, so in effect you'd want to perform some redirection internally.
> 
> Plus you need to keep a reference to the original data to stop the GC collecting it and invalidating all your stride pointers.
> 
> template Stride(T) {
>    T*[] pointers;
>    T[] original;
> }
> 
> Not sure what effect proper rectangular arrays will have on this idea. I think it'll work with them too.
> 
> Regan.
> 

"Norbert Nemec" <Norbert.Nemec@gmx.de> wrote in message news:ccir6v$gqo$1@digitaldaemon.com...
> For a full explanation see the Multidim-Array proposal
>
http://homepages.uni-regensburg.de/~nen10015/documents/D-multidimarray.html
>
> In short words:
>
> * dynamic arrays as we have them now stay unstrided. In string handling, striding is of little use, so strings deserve their "lightweight"-array type
>
> * newly introduced are the full-fledged N-dimensional, strided arrays.
These
> hold, in addition to "T *ptr" and the "int[N] range" field a "int[N] stride" field giving the strides in the individual directions.
>
> For continuously stored arrays, the strides can be calculated from the ranges.
>
> The idea to add striding arose from the fact that already with unstrided slicing of N-d arrays, the data will be stored non-continuously, so the strides cannot be calculated from the ranges any more. All but the lowest dimension will need a stride field anyway to implement unstrided slicing. So why not just add the last "stride"-field as well, adding a tiny bit of overhead but simplifying the concept and offering many new possibilities.

Just one question:
If i have:
int[[2]] zbuffer = new int[800,600];

and i create:
int[[2]] partOfBuffer = zbuffer[30..100,30..100];
Now this new array naturally isn't continous,
could there be a way to make it continuous, maybe
by saying that dup creates a continuous array out of a slice?

int[[2]] partOfBuffer = zbuffer[30..100,30..100].dup;

This copies the data to a new array that is continuous.


> The idea of using pointers to each data element would be even more
flexible,
> of course, but the overhead for that would be tremendous.
>
>
>
> Regan Heath wrote:
>
> > After reading the various posts on arrays, slicing, indexing and
striding
> > I was thinking about striding, it's not something I have ever had the
need
> > to do (I'm not big on maths/graphics programming), but it's interesting
to
> > me nonetheless.
> >
> > I felt the need to share these thoughts.. well, just cos. :)
> >
> > The bit that intrigues me is how you'd implement it. Given the internals of D arrays, they are a pointer and a length, eg..
> >
> > template Array(T) {
> >    uint length;
> >    T *pointer;
> > }
> >
> > Then how do you represent a stride of that array? To me it seems it
would
> > have to be an array of pointers, or, a copy of the original data in a
new
> > array.
> >
> > Assuming copying is not desired, you could use an array of pointers,
but,
> > you want it to behave like an array of the data pointed to, so in effect you'd want to perform some redirection internally.
> >
> > Plus you need to keep a reference to the original data to stop the GC collecting it and invalidating all your stride pointers.
> >
> > template Stride(T) {
> >    T*[] pointers;
> >    T[] original;
> > }
> >
> > Not sure what effect proper rectangular arrays will have on this idea. I think it'll work with them too.
> >
> > Regan.
> >
>

Ivan Senji wrote:

> Just one question:
> If i have:
> int[[2]] zbuffer = new int[800,600];
> 
> and i create:
> int[[2]] partOfBuffer = zbuffer[30..100,30..100];
> Now this new array naturally isn't continous,
> could there be a way to make it continuous, maybe
> by saying that dup creates a continuous array out of a slice?
> 
> int[[2]] partOfBuffer = zbuffer[30..100,30..100].dup;
> 
> This copies the data to a new array that is continuous.

That is nearly exactly what happens. There is a variety of .dup_xxx properties proposed that show slightly different behavior. In general, .dup is defined to guarantee a certain quality of the array. If the compiler finds that this quality is already given, it may optimize away the unnecessary .dup action.

The plain .dup actually is defined as a synonym for .dup_unique - and guarantees that no other reference to the array exists and the array is writable. This is what you need for copy-on-write.

Other examples are .dup_continuous, .dup_aligned, .dup_c_aligned, or stuff like .dup_unique_continuous, etc.

For plain, high-level D code, you should never need anything but .dup - all other variants are meant for interfacing and for low-level operations.