www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Multidimensional arrays for D

reply Denis Shelomovskij <verylonglogin.reg gmail.com> writes:
What does D already have: build-in rectangular static arrays, dynamic 
arrays of arrays, std.range.frontTransversal, std.range.transversal.

Some time ago I was told that "FORTRAN is good for its arrays" and heard 
me saying "it is easy to implement in C++ or D, but in D it will have 
more convenient syntax". But than I have understood that I 
underestimated the problem and it isn't easy to implement in D and looks 
much more harder to implement in C++. In spite of this I decided to 
implement it in D. So, my implementation is ready for test/use but still 
has some TODO-s because it is just a straightforward implementation of 
basic multidimensional array operations with no optimisations. And I 
think it is valuable enough to be added in Phobos in future (tell me if 
it isn't).

Documentation and sources:
http://deoma-cmd.ru/d/docs/src/my/rarray.html

Sources will be at GitHub as soon as I am asked for it.

I have some questions about my array:
* Should such array be a part of Phobos or Druntime?
* Now my array has CT dimensions and RT lengths, should there be a 
version with RT dimensions (or maybe it is the only needed version)?
* Some (or most) of element names should be changed (like 
RectangularArray, because is isn't a rectangular array in the general 
case). So if one knows better names, tell me please (at least 
RectangularArray -> MultidimensionalArray, rectArray -> multiArray?).
* Have I misused some terminology (top dimension etc.)?
* What `Throwable` types should be thrown and when? Currently I use 
`AssertError` for my own mistakes and user incorrect ranges using and 
`Exception` for user incorrect array using, all are in debug mode only.
And I don't understand Druntime exceptions: it uses `Exception` for 
"lengths don't match for array copy" and `core.exception.RangeError` if 
array index is out of bounds and calls it "Range violation" (all are in 
debug mode only). It looks inconsistent.
* For `int a = b / c, d = b % c;` will compiler optimize it or should I 
add there an inline assembly to get `d` from `EDX` on x86 after division?

I also have some questions about other files (my.typetuple and my.traits):
* I was confused with Phobos TypeTuple because it isn't a type tuple. 
Should it be replaced with some modification of my variant?
* Have any additions in my.traits a general use? IMHO ArrayElementType, 
isType and staticRange have.

I also have some ideas (TODO-s) for my array which looks good:
* opSliceAssign with an array or a RectangularArray as its operand 
should use array copy for as much tail dimensions as possible (if data 
has no copy constructor because of dmd bug 6470).
* byElementRandomAccess should also look at all packed tail dimensions 
if they are one dimension for faster indexing.
* Special optimized case for 2^^n-lengths.


Thanks everybody for reading such a big post!
Oct 25 2011
next sibling parent Zardoz <luis.panadero gmail.com> writes:
On Tue, 25 Oct 2011 14:52:04 +0300, Denis Shelomovskij wrote:

Looks interesting. This summer I did a small lib around vectors and matrices,
at same time that I was 
learning D. Perhaps you can borrow some idea or not. It's focused for using it
with OpenGL so they are 
limited to squared matrices of 2 to 4 dimension and column major ordered  : 
https://github.com/Zardoz89/zmath


 What does D already have: build-in rectangular static arrays, dynamic
 arrays of arrays, std.range.frontTransversal, std.range.transversal.
 
 Some time ago I was told that "FORTRAN is good for its arrays" and heard
 me saying "it is easy to implement in C++ or D, but in D it will have
 more convenient syntax". But than I have understood that I
 underestimated the problem and it isn't easy to implement in D and looks
 much more harder to implement in C++. In spite of this I decided to
 implement it in D. So, my implementation is ready for test/use but still
 has some TODO-s because it is just a straightforward implementation of
 basic multidimensional array operations with no optimisations. And I
 think it is valuable enough to be added in Phobos in future (tell me if
 it isn't).
 
 Documentation and sources:
 http://deoma-cmd.ru/d/docs/src/my/rarray.html
 
 Sources will be at GitHub as soon as I am asked for it.
 
 I have some questions about my array: * Should such array be a part of
 Phobos or Druntime? * Now my array has CT dimensions and RT lengths,
 should there be a version with RT dimensions (or maybe it is the only
 needed version)? * Some (or most) of element names should be changed
 (like RectangularArray, because is isn't a rectangular array in the
 general case). So if one knows better names, tell me please (at least
 RectangularArray -> MultidimensionalArray, rectArray -> multiArray?). *
 Have I misused some terminology (top dimension etc.)? * What `Throwable`
 types should be thrown and when? Currently I use `AssertError` for my
 own mistakes and user incorrect ranges using and `Exception` for user
 incorrect array using, all are in debug mode only. And I don't
 understand Druntime exceptions: it uses `Exception` for "lengths don't
 match for array copy" and `core.exception.RangeError` if array index is
 out of bounds and calls it "Range violation" (all are in debug mode
 only). It looks inconsistent. * For `int a = b / c, d = b % c;` will
 compiler optimize it or should I add there an inline assembly to get `d`
 from `EDX` on x86 after division?
 
 I also have some questions about other files (my.typetuple and
 my.traits): * I was confused with Phobos TypeTuple because it isn't a
 type tuple. Should it be replaced with some modification of my variant?
 * Have any additions in my.traits a general use? IMHO ArrayElementType,
 isType and staticRange have.
 
 I also have some ideas (TODO-s) for my array which looks good: *
 opSliceAssign with an array or a RectangularArray as its operand should
 use array copy for as much tail dimensions as possible (if data has no
 copy constructor because of dmd bug 6470). * byElementRandomAccess
 should also look at all packed tail dimensions if they are one dimension
 for faster indexing. * Special optimized case for 2^^n-lengths.
 
 
 Thanks everybody for reading such a big post!






-- 
Yep, I'm afraid that I have a blog : zardoz.es
Oct 25 2011
prev sibling next sibling parent Norbert Nemec <Norbert Nemec-online.de> writes:
Excellent! I have toying around with similar ideas for years. Never 
found the time to really get into it. :-(

Some ideas below inline.

On 25.10.2011 13:52, Denis Shelomovskij wrote:

 What does D already have: build-in rectangular static arrays, dynamic
 arrays of arrays, std.range.frontTransversal, std.range.transversal.

 Some time ago I was told that "FORTRAN is good for its arrays" and heard
 me saying "it is easy to implement in C++ or D, but in D it will have
 more convenient syntax".


Certainly not easy in C++.
After trying it in C++, surprisingly easy in D...


 But than I have understood that I
 underestimated the problem and it isn't easy to implement in D and looks
 much more harder to implement in C++. In spite of this I decided to
 implement it in D. So, my implementation is ready for test/use but still
 has some TODO-s because it is just a straightforward implementation of
 basic multidimensional array operations with no optimisations. And I
 think it is valuable enough to be added in Phobos in future (tell me if
 it isn't).


The question about adding it to Phobos is not just whether it is 
valuable enough, but whether it is generic enough to be *the* library 
for numerical arrays. Numerical arrays are foremost the interface 
between numerical libraries.

I have not had a close look at your code to form an opinion about this.



 Documentation and sources:
 http://deoma-cmd.ru/d/docs/src/my/rarray.html

 Sources will be at GitHub as soon as I am asked for it.

 I have some questions about my array:
 * Should such array be a part of Phobos or Druntime?


Ultimately, yes.


 * Now my array has CT dimensions and RT lengths, should there be a
 version with RT dimensions (or maybe it is the only needed version)?


As terminology, I find the following convenient:
	"rank" - the number of dimensions
	"shape" - the collection of lengths of all dimensions

In those terms, I believe that CT rank is good for most relevant 
purposes. I don't know of any use for RT ranks except to overcome 
limitations of other languages. D't powerful variadic functions should 
deal with that nicely.

CT shapes on the other hand can become relevant, but these would be a 
different kind of arrays. Some comparable C++ libraries offer 
"TinyArrays" which have a CT shape. I myself made heavy use of those in 
one project, where I had to handle myriads of complex 3x3 matrices.

However, TinyArrays are conceptually quite different from the more 
commonly used numerical arrays with RT shape.



 * Some (or most) of element names should be changed (like
 RectangularArray, because is isn't a rectangular array in the general
 case). So if one knows better names, tell me please (at least
 RectangularArray -> MultidimensionalArray, rectArray -> multiArray?).


Better put it in a module with a descriptive name and keep the names of 
individual elements inside short.


 * Have I misused some terminology (top dimension etc.)?


I don't know what "top" means here. Isn't "first" or "last" clearer?

For the remaining questions I have nothing smart to add, so I leave 
those to others...
Oct 26 2011
prev sibling next sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
This looks nice. I like how much is possible with the foreach delegates.  
For the most part when I need a matrix, it is for 2D rotation and  
translation or OpenGL. It would be nice if one day OpenGL bindings would  
have overloads that accept your matrices. The row/coumn order is different  
there and I bet most realtime gfx fanatics would want optimized versions  
for the common 4x4 or 3x3 matrix types. Close to handwritten assembler so  
to say. But even without top-notch performance some nice demo code could  
show up.
Nov 02 2011
prev sibling next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Tuesday, 25 October 2011 at 10:53:16 UTC, Denis Shelomovskij 
wrote:

 Sources will be at GitHub as soon as I am asked for it.


I'm asking :)
Nov 29 2012
parent Denis Shelomovskij <verylonglogin.reg gmail.com> writes:
29.11.2012 15:59, John Colvin пишет:

 On Tuesday, 25 October 2011 at 10:53:16 UTC, Denis Shelomovskij wrote:

 Sources will be at GitHub as soon as I am asked for it.


 I'm asking :)


Sorry for the delay.

You are welcome! And it is already there. You need 
unstd.multidimensionalarray from phobos-additions project:

http://denis-sh.github.com/phobos-additions/

It is already alive, but there is absolutely no progress in including 
any of its parts in phobos just like with all other my pull requests. 
But I will support and improve phobos-additions project.


-- 
Денис В. Шеломовский
Denis V. Shelomovskij
Dec 03 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Denis Shelomovskij:


 Documentation and sources:
 http://deoma-cmd.ru/d/docs/src/my/rarray.html


Something like this will be good to have in Phobos.

Bye,
bearophile
Nov 29 2012
prev sibling parent "deed" <none none.none> writes:
 Documentation and sources:
 http://deoma-cmd.ru/d/docs/src/my/rarray.html


In RectangularArray there's an alias named "dimention", which 
probably should be "dimension".
Nov 29 2012