digitalmars.D - Flat multi-dim arrays.
- Dave (32/32) Aug 07 2006 A current thread delved into "deep" copy for multidim arrays, but maybe ...
-
Dave
(7/72)
Aug 10 2006
What, not even a "that sucks!" from someone
- Don Clugston (10/91) Aug 10 2006 Have you read Norbert Nemec's original multi-dim array proposal (you can...
- Dave (7/100) Aug 10 2006 Thanks - that's great feedback (obviously I'm coming at it from the POV ...
- =?iso-8859-1?q?Knud_S=F8rensen?= (5/15) Aug 10 2006 Walters comment to Nemec's proposal where that it where 2.0 stuff.
- Ivan Senji (12/21) Aug 10 2006 OK, here's one: "that sucks!"
- Dave (8/34) Aug 10 2006 I'll check that out too. IMHO, this is something that needs to be built ...
- Mikola Lysenko (57/57) Aug 10 2006 I agree that a multi-dimensional array structure would be extremely
- Dave (29/108) Aug 10 2006 I don't think this has to be overly complicated, even to "get it (mostly...
- Oskar Linde (6/11) Aug 10 2006 Yes you can. This is exactly what strides are for.
- Dave (3/19) Aug 10 2006 Can you pass along some syntax / usage for that?
- Reiner Pope (6/26) Aug 10 2006 I think he was talking about Norbert Nemec's proposal, which was
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
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
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
Dave <Dave_member pathlink.com> Don Clugston wrote:Dave wrote: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. - DaveWhat, 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
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
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
Ivan Senji wrote:Dave wrote:<g> Thanks! Sometimes silence is not golden <g>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'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 ;)).Totally agree - I bet they are one of the least used features of D right now.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
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
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
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
Oskar Linde wrote:Mikola Lysenko wrote:Can you pass along some syntax / usage for that? Thanks.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
Dave wrote:Oskar Linde wrote: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, ReinerMikola Lysenko wrote:Can you pass along some syntax / usage for that? Thanks.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