www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Flat multi-dim arrays.

reply Dave <Dave_member pathlink.com> writes:
A current thread delved into "deep" copy for multidim arrays, but maybe a
different approach to MD
arrays that would a) make things easier to .dup, b) more efficient and c)
perhaps appeal to the
numerical computing folks as well?

int[,] arr = new int[100,100];
int[,,] arr = new int[50,10,20];
...

- They would be allocated from a single contiguous chunk of memory for speed
and ease of .dup'ing
and array operations:

int[,] ar2=arr.dup; // int[][] arra2 = alloc2D!(int)(arr.length,arr[0].length);
                     // memcpy(ar2[0].ptr,arr[0].ptr,arr.length * arr[0].length
* int.sizeof);

ar2[] = 10;         // _memset32(ar2[0].ptr,10,ar2.length * ar2[0].length);

foreach(i; ar2) {}  // foreach(i; cast(int[])ar2[0].ptr[0 .. ar2.length *
ar2[0].length]) {}

(the array of T are allocated from the same contiguous pool of memory).

- The compiler frontend would convert operands like arr[10,10] into arr[10][10]
to use the already
optimized compiler backend code for jagged array access (and array bounds
checking). They would also
be passed into and out of functions as arr[][]. Also consistent with the
opIndex and opIndexAssign
overload syntax, so the new syntax doesn't create inconsistencies with UDT op
overloading (actually
seems more consistent because there isn't a way to overload [][]). Fortran
programmers may be more
comfortable with the [x,y] syntax too (?)

- I tested this with the linpack benchmark and the performance doubled on my
machine for a 500 x 500
matrix by just changing the array allocation from jagged to one flat /
contiguous chunk of memory.
For smaller arrays the performance is the same or perhaps a little better,
especially for native
types > 32 bit (longs, doubles, reals).

- Perhaps leave stuff like array slicing out, at least to start with. But
considering that a simple
conversion to native jagged arrays is taking place, this shouldn't be really
difficult to implement
either(?).

- No new operators or keywords. These would be a natural extension to D's
improved built-in arrays,
especially because the memory management is easily handled by the GC.

- Maximum rank of 7 for compatibility w/ Fortran.

- Would be another reason to switch from C and/or C++ for things like numerical
analysis.

Thoughts?

- Dave
Aug 07 2006
parent reply Dave <Dave_member pathlink.com> writes:
What, not even a "that sucks!" from someone <g>

I'm pretty sure the syntax has been proposed before, but not the same
implementation ideas.


relatively low hanging and 
juicy fruit (but Walter would have to tell us how low hanging it is for sure,
of course).

Thanks,

- Dave

Dave wrote:
 
 A current thread delved into "deep" copy for multidim arrays, but maybe 
 a different approach to MD
 arrays that would a) make things easier to .dup, b) more efficient and 
 c) perhaps appeal to the
 numerical computing folks as well?
 
 int[,] arr = new int[100,100];
 int[,,] arr = new int[50,10,20];
 ...
 
 - They would be allocated from a single contiguous chunk of memory for 
 speed and ease of .dup'ing
 and array operations:
 
 int[,] ar2=arr.dup; // int[][] arra2 = 
 alloc2D!(int)(arr.length,arr[0].length);
                     // memcpy(ar2[0].ptr,arr[0].ptr,arr.length * 
 arr[0].length * int.sizeof);
 
 ar2[] = 10;         // _memset32(ar2[0].ptr,10,ar2.length * ar2[0].length);
 
 foreach(i; ar2) {}  // foreach(i; cast(int[])ar2[0].ptr[0 .. ar2.length 
 * ar2[0].length]) {}
 
 (the array of T are allocated from the same contiguous pool of memory).
 
 - The compiler frontend would convert operands like arr[10,10] into 
 arr[10][10] to use the already
 optimized compiler backend code for jagged array access (and array 
 bounds checking). They would also
 be passed into and out of functions as arr[][]. Also consistent with the 
 opIndex and opIndexAssign
 overload syntax, so the new syntax doesn't create inconsistencies with 
 UDT op overloading (actually
 seems more consistent because there isn't a way to overload [][]). 
 Fortran programmers may be more
 comfortable with the [x,y] syntax too (?)
 
 - I tested this with the linpack benchmark and the performance doubled 
 on my machine for a 500 x 500
 matrix by just changing the array allocation from jagged to one flat / 
 contiguous chunk of memory.
 For smaller arrays the performance is the same or perhaps a little 
 better, especially for native
 types > 32 bit (longs, doubles, reals).
 
 - Perhaps leave stuff like array slicing out, at least to start with. 
 But considering that a simple
 conversion to native jagged arrays is taking place, this shouldn't be 
 really difficult to implement
 either(?).
 
 - No new operators or keywords. These would be a natural extension to 
 D's improved built-in arrays,
 especially because the memory management is easily handled by the GC.
 
 - Maximum rank of 7 for compatibility w/ Fortran.
 
 - Would be another reason to switch from C and/or C++ for things like 
 numerical analysis.
 
 Thoughts?
 
 - Dave
Aug 10 2006
next sibling parent reply Don Clugston <dac nospam.com.au> writes:
Dave wrote:
 
 What, not even a "that sucks!" from someone <g>
 
 I'm pretty sure the syntax has been proposed before, but not the same 
 implementation ideas.
 

 relatively low hanging and juicy fruit (but Walter would have to tell us 
 how low hanging it is for sure, of course).
Have you read Norbert Nemec's original multi-dim array proposal (you can find it on Wiki4D)? The key feature is "strided slices", which seem to be essential for dealing with multi-dim arrays. Something like that could get most of the fruit on the tree... Norbert's idea is not quite well developed enough yet, though, to be truly compelling. I think wants to Get It Right. If you can develop an idea for strided arrays which folds neatly into the existing language, that would be extremely valuable.
 
 Thanks,
 
 - Dave
 
 Dave wrote:
 A current thread delved into "deep" copy for multidim arrays, but 
 maybe a different approach to MD
 arrays that would a) make things easier to .dup, b) more efficient and 
 c) perhaps appeal to the
 numerical computing folks as well?

 int[,] arr = new int[100,100];
 int[,,] arr = new int[50,10,20];
 ...

 - They would be allocated from a single contiguous chunk of memory for 
 speed and ease of .dup'ing
 and array operations:

 int[,] ar2=arr.dup; // int[][] arra2 = 
 alloc2D!(int)(arr.length,arr[0].length);
                     // memcpy(ar2[0].ptr,arr[0].ptr,arr.length * 
 arr[0].length * int.sizeof);

 ar2[] = 10;         // _memset32(ar2[0].ptr,10,ar2.length * 
 ar2[0].length);

 foreach(i; ar2) {}  // foreach(i; cast(int[])ar2[0].ptr[0 .. 
 ar2.length * ar2[0].length]) {}

 (the array of T are allocated from the same contiguous pool of memory).

 - The compiler frontend would convert operands like arr[10,10] into 
 arr[10][10] to use the already
 optimized compiler backend code for jagged array access (and array 
 bounds checking). They would also
 be passed into and out of functions as arr[][]. Also consistent with 
 the opIndex and opIndexAssign
 overload syntax, so the new syntax doesn't create inconsistencies with 
 UDT op overloading (actually
 seems more consistent because there isn't a way to overload [][]). 
 Fortran programmers may be more
 comfortable with the [x,y] syntax too (?)

 - I tested this with the linpack benchmark and the performance doubled 
 on my machine for a 500 x 500
 matrix by just changing the array allocation from jagged to one flat / 
 contiguous chunk of memory.
 For smaller arrays the performance is the same or perhaps a little 
 better, especially for native
 types > 32 bit (longs, doubles, reals).

 - Perhaps leave stuff like array slicing out, at least to start with. 
 But considering that a simple
 conversion to native jagged arrays is taking place, this shouldn't be 
 really difficult to implement
 either(?).

 - No new operators or keywords. These would be a natural extension to 
 D's improved built-in arrays,
 especially because the memory management is easily handled by the GC.

 - Maximum rank of 7 for compatibility w/ Fortran.

 - Would be another reason to switch from C and/or C++ for things like 
 numerical analysis.

 Thoughts?

 - Dave
Aug 10 2006
next sibling parent Dave <Dave_member pathlink.com> writes:
Don Clugston wrote:
 Dave wrote:
 What, not even a "that sucks!" from someone <g>

 I'm pretty sure the syntax has been proposed before, but not the same 
 implementation ideas.


 relatively low hanging and juicy fruit (but Walter would have to tell 
 us how low hanging it is for sure, of course).
Have you read Norbert Nemec's original multi-dim array proposal (you can find it on Wiki4D)? The key feature is "strided slices", which seem to be essential for dealing with multi-dim arrays. Something like that could get most of the fruit on the tree... Norbert's idea is not quite well developed enough yet, though, to be truly compelling. I think wants to Get It Right. If you can develop an idea for strided arrays which folds neatly into the existing language, that would be extremely valuable.
Thanks - that's great feedback (obviously I'm coming at it from the POV of someone not involved w/ numerics work and who also knows little Fortran). Maybe I inadvertently copied most of Norbert's proposal - if so that wasn't intended. The implementation ideas were just a "first cut" that (I think) could be done pretty efficiently with the current compiler internals. I'll check out "strided slices" and see if something falls in my lap. - Dave
 Thanks,

 - Dave

 Dave wrote:
 A current thread delved into "deep" copy for multidim arrays, but 
 maybe a different approach to MD
 arrays that would a) make things easier to .dup, b) more efficient 
 and c) perhaps appeal to the
 numerical computing folks as well?

 int[,] arr = new int[100,100];
 int[,,] arr = new int[50,10,20];
 ...

 - They would be allocated from a single contiguous chunk of memory 
 for speed and ease of .dup'ing
 and array operations:

 int[,] ar2=arr.dup; // int[][] arra2 = 
 alloc2D!(int)(arr.length,arr[0].length);
                     // memcpy(ar2[0].ptr,arr[0].ptr,arr.length * 
 arr[0].length * int.sizeof);

 ar2[] = 10;         // _memset32(ar2[0].ptr,10,ar2.length * 
 ar2[0].length);

 foreach(i; ar2) {}  // foreach(i; cast(int[])ar2[0].ptr[0 .. 
 ar2.length * ar2[0].length]) {}

 (the array of T are allocated from the same contiguous pool of memory).

 - The compiler frontend would convert operands like arr[10,10] into 
 arr[10][10] to use the already
 optimized compiler backend code for jagged array access (and array 
 bounds checking). They would also
 be passed into and out of functions as arr[][]. Also consistent with 
 the opIndex and opIndexAssign
 overload syntax, so the new syntax doesn't create inconsistencies 
 with UDT op overloading (actually
 seems more consistent because there isn't a way to overload [][]). 
 Fortran programmers may be more
 comfortable with the [x,y] syntax too (?)

 - I tested this with the linpack benchmark and the performance 
 doubled on my machine for a 500 x 500
 matrix by just changing the array allocation from jagged to one flat 
 / contiguous chunk of memory.
 For smaller arrays the performance is the same or perhaps a little 
 better, especially for native
 types > 32 bit (longs, doubles, reals).

 - Perhaps leave stuff like array slicing out, at least to start with. 
 But considering that a simple
 conversion to native jagged arrays is taking place, this shouldn't be 
 really difficult to implement
 either(?).

 - No new operators or keywords. These would be a natural extension to 
 D's improved built-in arrays,
 especially because the memory management is easily handled by the GC.

 - Maximum rank of 7 for compatibility w/ Fortran.

 - Would be another reason to switch from C and/or C++ for things like 
 numerical analysis.

 Thoughts?

 - Dave
Aug 10 2006
prev sibling parent =?iso-8859-1?q?Knud_S=F8rensen?= <12tkvvb02 sneakemail.com> writes:
On Thu, 10 Aug 2006 20:19:10 +0200, Don Clugston wrote:


 Have you read Norbert Nemec's original multi-dim array proposal (you can 
 find it on Wiki4D)? The key feature is "strided slices", which seem to 
 be essential for dealing with multi-dim arrays. Something like that 
 could get most of the fruit on the tree... Norbert's idea is not quite 
 well developed enough yet, though, to be truly compelling. I think 

 wants to Get It Right. If you can develop an idea for strided arrays 
 which folds neatly into the existing language, that would be extremely 
 valuable.
 
Walters comment to Nemec's proposal where that it where 2.0 stuff. So, I think the 2.0 series will contain extended arrays stuff and vectorization stuff. http://all-technology.com/eigenpolls/dwishlist/index.php?it=10
Aug 10 2006
prev sibling next sibling parent reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Dave wrote:
 
 What, not even a "that sucks!" from someone <g>
OK, here's one: "that sucks!" I really miss this feature. Like Don said Norbert Nemec wrote a proposal quite a long time ago and I don't think it was that bad, nothing that Walter couldn't fix himself if he really wanted to get the feature in the language. If I remember correctly there was also a version rectangular array class that Ben wrote that could do strides and all the other cool stuff (if I remember correctly :))
 
 I'm pretty sure the syntax has been proposed before, but not the same 
 implementation ideas.
 

 relatively low hanging and juicy fruit (but Walter would have to tell us 
 how low hanging it is for sure, of course).
Me too, been missing rectangular arrays in D from the very beginning because they are an extremely useful data type. D's rectangular arrays just suck, with their lengths being compile time constants, and not to mention other problems with static arrays.
Aug 10 2006
parent Dave <Dave_member pathlink.com> writes:
Ivan Senji wrote:
 Dave wrote:
 What, not even a "that sucks!" from someone <g>
OK, here's one: "that sucks!"
<g> Thanks! Sometimes silence is not golden <g>
 I really miss this feature. Like Don said Norbert Nemec wrote a proposal 
 quite a long time ago and I don't think it was that bad, nothing that 
 Walter couldn't fix himself if he really wanted to get the feature in 
 the language. If I remember correctly there was also a version 
 rectangular array class that Ben wrote that could do strides and all the 
 other cool stuff (if I remember correctly :))
 
I'll check that out too. IMHO, this is something that needs to be built in (and not just a template hack or something like that in the background) for speed reasons. If a new, expanded struct (like Array) is introduced, then we have slow function parameter passing and maybe more cache issues, etc. So the trick as I see it is to try and make it usable w/ the current compiler internals at least for phase 1 (not version 1 of D, phase 1 of MD arrays ;)).
 I'm pretty sure the syntax has been proposed before, but not the same 
 implementation ideas.


 relatively low hanging and juicy fruit (but Walter would have to tell 
 us how low hanging it is for sure, of course).
Me too, been missing rectangular arrays in D from the very beginning because they are an extremely useful data type. D's rectangular arrays just suck, with their lengths being compile time constants, and not to mention other problems with static arrays.
Totally agree - I bet they are one of the least used features of D right now.
Aug 10 2006
prev sibling parent reply Mikola Lysenko <mclysenk mtu.edu> writes:
I agree that a multi-dimensional array structure would be extremely
useful, however there are a few questions that must be answered before the
syntax gets changed.

1.  How should foreach work?

There are two main possibilities, either foreach iterates over each
element, or else it iterates over arrays of one less rank. Unfortunately,
these behaviors are mutually exclusive so it is important to choose
carefully.  I personally prefer the view that a multi-array is like an
associative array of tuples of ints. Under this perspective, the first
option is more sensible, but the second approach is more consistent with
existing dynamic array semantics.

2.  How should array concatenation or resizing be applied?

Concatenating to a multi-dimensional array seems difficult, since it is
inevitable that a user will attempt to grow an array along any of its
dimensions.  This must trigger a large and costly memory recopy if it is
not along the last rank.  A similar issue could happen if a user attempts
to change one of the dimensions in the middle ranks.  The memory layout
would become dramatically altered, and the entire array would need to be
copied/shifted.

3.  Should it be possible to dynamically change the rank of a multi-array?

This can present many hazards, since there is no safe way to retain the
contents of an array across such a transformation.  One solution is to
embed the rank into the type of the array, making it immutable.

4.  How should the new types memory be laid out?

In the current specification for D, a dynamic array's memory looks like
this:

struct DynArray(T)
{
	size_t len;
	T * arr;
}

In a multi-array, there are 2 possible scenarios:

struct MultiArray(T)
{
	size_t rank;
	size_t * dimensions;
	T * arr;
}

In this situation, we can dynamically adjust the rank and dimension of the
multi-array, at the expense of allocating 2 blocks of dynamic memory.  If
we make rank static, we get the following:

struct MultiArray(T, RANK)
{
	size_t dims[RANK];
	T * arr;
}

This is slightly simpler, but rank is fixed.  It also has the advantage
that a rank-1 multi-array is byte for byte equal to a dynamic array.

Finally, we need to decide on row major or column major layout.  This is a
tricky issue because there is no "best" answer.


5.  How do slices work?

You can't just slice a random chunk from the middle of an array in place
like a regular array, since the layout will be incorrect.  By necessity,
the memory will have to be copied, which is transforms the copy-on-write
idiom into a dangerous new copy-on-read situation.


Before the language gets changed, there needs to be more discussion of the
fundamental issues surrounding multi-arrays.
Aug 10 2006
next sibling parent Dave <Dave_member pathlink.com> writes:
Mikola Lysenko wrote:
 I agree that a multi-dimensional array structure would be extremely
 useful, however there are a few questions that must be answered before the
 syntax gets changed.
 
I don't think this has to be overly complicated, even to "get it (mostly) right". If you look at the [,] syntax as just another way of expressing [][] (with a different allocation strategy) then what is built-in to the compiler internals already might work just fine. It's really easy to allocated MD arrays out of a contiguous pool and that's where the speed and ease of implementation benefits come from (not only in D but probably Fortran as well).
 1.  How should foreach work?
 
 There are two main possibilities, either foreach iterates over each
 element, or else it iterates over arrays of one less rank. Unfortunately,
 these behaviors are mutually exclusive so it is important to choose
 carefully.  I personally prefer the view that a multi-array is like an
 associative array of tuples of ints. Under this perspective, the first
 option is more sensible, but the second approach is more consistent with
 existing dynamic array semantics.
The original post demo'd the first because if they want the 2nd they can use the jagged array syntax.
 
 2.  How should array concatenation or resizing be applied?
 
 Concatenating to a multi-dimensional array seems difficult, since it is
 inevitable that a user will attempt to grow an array along any of its
 dimensions.  This must trigger a large and costly memory recopy if it is
 not along the last rank.  A similar issue could happen if a user attempts
 to change one of the dimensions in the middle ranks.  The memory layout
 would become dramatically altered, and the entire array would need to be
 copied/shifted.
 
What does Fortran do now? If it's not offered built-in in other high-performance, statically compiled languages then don't do it. If it is, then this actually sounds like a great place for library support because it will usually be an expensive single operation and can probably not be done more efficiently "built-in".
 3.  Should it be possible to dynamically change the rank of a multi-array?
 
 This can present many hazards, since there is no safe way to retain the
 contents of an array across such a transformation.  One solution is to
 embed the rank into the type of the array, making it immutable.
I would say no, not built-in to start with.
 
 4.  How should the new types memory be laid out?
 
 In the current specification for D, a dynamic array's memory looks like
 this:
 
 struct DynArray(T)
 {
 	size_t len;
 	T * arr;
 }
 
The original post suggested a way to lay them out "flat" in memory and then use the internal representation to access the elements the same way as jagged arrays. So, no new internal structure is used (large jagged arrays are slow because of their memory layout, not because of how the references to the elements are calculated, etc.).
 In a multi-array, there are 2 possible scenarios:
 
 struct MultiArray(T)
 {
 	size_t rank;
 	size_t * dimensions;
 	T * arr;
 }
 
I've tried this... It is slower w/ both DMD and GDC - apparently 'fragments' the memory used to lookup and then access the elements. Whatever the case the current compiler implementations don't do this efficiently.
 In this situation, we can dynamically adjust the rank and dimension of the
 multi-array, at the expense of allocating 2 blocks of dynamic memory.  If
 we make rank static, we get the following:
 
 struct MultiArray(T, RANK)
 {
 	size_t dims[RANK];
 	T * arr;
 }
 
 This is slightly simpler, but rank is fixed.  It also has the advantage
 that a rank-1 multi-array is byte for byte equal to a dynamic array.
 
Tried this too. It is potentially pretty expensive - passing "large" structs by val. Using a class internally means another thing to allocate, slower member access and more complexity internal to the compiler.
 Finally, we need to decide on row major or column major layout.  This is a
 tricky issue because there is no "best" answer.
 
 
 5.  How do slices work?
 
 You can't just slice a random chunk from the middle of an array in place
 like a regular array, since the layout will be incorrect.  By necessity,
 the memory will have to be copied, which is transforms the copy-on-write
 idiom into a dangerous new copy-on-read situation.
 
 
 Before the language gets changed, there needs to be more discussion of the
 fundamental issues surrounding multi-arrays.
 
 
Slices on the last dimension could be done like so for example: int arr[,] = new int[10,100], ar2 = new int[10,10]; ar2[2,0..$] = arr[9,0..10]; // internally converted to ar2[2][0..$] = arr[9][0..10]; int[] ia = arr[5,0..10].dup; // internally converted to int[] ia = arr[5][0..10].dup; Obviously that doesn't cover all of the possibilities. Thanks, - Dave
Aug 10 2006
prev sibling parent reply Oskar Linde <olREM OVEnada.kth.se> writes:
Mikola Lysenko wrote:

 
 5.  How do slices work?
 
 You can't just slice a random chunk from the middle of an array in place
 like a regular array, since the layout will be incorrect.  
Yes you can. This is exactly what strides are for. For each dimension, you keep a stride as well as a length. Walking up the dimension moves a stride of units of memory. This even allows things like transposing a large matrix without moving a single byte. /Oskar
Aug 10 2006
parent reply Dave <Dave_member pathlink.com> writes:
Oskar Linde wrote:
 Mikola Lysenko wrote:
 
 5.  How do slices work?

 You can't just slice a random chunk from the middle of an array in place
 like a regular array, since the layout will be incorrect.  
Yes you can. This is exactly what strides are for. For each dimension, you keep a stride as well as a length. Walking up the dimension moves a stride of units of memory. This even allows things like transposing a large matrix without moving a single byte.
Can you pass along some syntax / usage for that? Thanks.
 /Oskar
 
 
Aug 10 2006
parent Reiner Pope <reiner.pope REMOVE.THIS.gmail.com> writes:
Dave wrote:
 Oskar Linde wrote:
 Mikola Lysenko wrote:

 5.  How do slices work?

 You can't just slice a random chunk from the middle of an array in place
 like a regular array, since the layout will be incorrect.  
Yes you can. This is exactly what strides are for. For each dimension, you keep a stride as well as a length. Walking up the dimension moves a stride of units of memory. This even allows things like transposing a large matrix without moving a single byte.
Can you pass along some syntax / usage for that? Thanks.
 /Oskar
I think he was talking about Norbert Nemec's proposal, which was referred to earlier: http://homepages.uni-regensburg.de/~nen10015/documents/D-multidimarray.html Cheers, Reiner
Aug 10 2006