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!

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

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...

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.

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 :)

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

> 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".

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