www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Thoughts on strides in arrays..

reply Regan Heath <regan netwin.co.nz> writes:
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/
Jul 07 2004
parent reply Norbert Nemec <Norbert.Nemec gmx.de> writes:
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.
Jul 07 2004
parent reply "Ivan Senji" <ivan.senji public.srce.hr> writes:
"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.
Jul 08 2004
parent Norbert Nemec <Norbert.Nemec gmx.de> writes:
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.
Jul 08 2004