View mode: basic / threaded / horizontal-split · Log in · Help
October 25, 2011
Multidimensional arrays for D
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!
October 25, 2011
Re: Multidimensional arrays for D
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
October 26, 2011
Re: Multidimensional arrays for D
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...
November 02, 2011
Re: Multidimensional arrays for D
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.
November 29, 2012
Re: Multidimensional arrays for D
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 :)
November 29, 2012
Re: Multidimensional arrays for D
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
November 29, 2012
Re: Multidimensional arrays for D
> 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".
December 03, 2012
Re: Multidimensional arrays for D
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
Top | Discussion index | About this forum | D home