www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Rectangular multidimensional arrays for D

reply Denis Shelomovskij <verylonglogin.reg gmail.com> writes:
I accidentally discovered Andrei wrote [1] multidimensional array 
implementation is needed. If it really is, I will work to revise the API 
and prepare my implementation [2] for review if nobody is doing it already.

Also as Kenji's "multidimensional indexing and slicing" pull [3] still 
not merged the only way is to use hacks like this:
---
// first two rows and three columns of the second matrix
array2d = matrices[1, R[0 .. 2], R[0 .. 3]];
---

[1] http://forum.dlang.org/post/kivkp0$csp$1 digitalmars.com
[2] 
http://denis-sh.bitbucket.org/unstandard/unstd.multidimensionalarray.html
[3] https://github.com/D-Programming-Language/dmd/pull/443


--- Previous related topics ---

At least the ones I participated in:

* October 09, 2011: Kenji Hara proposes "Matrix-type-friendly syntax and 

     http://forum.dlang.org/thread/j6sp68$2a7k$1 digitalmars.com
     https://github.com/D-Programming-Language/dmd/pull/443

* October 25, 2011: Original "Multidimensional arrays for D" post. No 
response from Phobos developers.
     http://forum.dlang.org/thread/j864es$2gi0$1 digitalmars.com

* June 17, 2012: A request for "template that can simulate a rectangular 
array".
     http://forum.dlang.org/thread

* June 30, 2012: A request for "fixed size multidimensional array at 
runtime".
     http://forum.dlang.org/thread/ldjzfqvnjltbbiovqdmy forum.dlang.org

-- 
Денис В. Шеломовский
Denis V. Shelomovskij
Oct 08 2013
next sibling parent reply "Stefan Frijters" <sfrijters gmail.com> writes:
On Tuesday, 8 October 2013 at 14:41:47 UTC, Denis Shelomovskij 
wrote:

 I accidentally discovered Andrei wrote [1] multidimensional 
 array implementation is needed. If it really is, I will work to 
 revise the API and prepare my implementation [2] for review if 
 nobody is doing it already.

 Also as Kenji's "multidimensional indexing and slicing" pull 
 [3] still not merged the only way is to use hacks like this:
 ---
 // first two rows and three columns of the second matrix
 array2d = matrices[1, R[0 .. 2], R[0 .. 3]];
 ---

 [1] http://forum.dlang.org/post/kivkp0$csp$1 digitalmars.com
 [2] 
 http://denis-sh.bitbucket.org/unstandard/unstd.multidimensionalarray.html
 [3] https://github.com/D-Programming-Language/dmd/pull/443


 --- Previous related topics ---

 At least the ones I participated in:

 * October 09, 2011: Kenji Hara proposes "Matrix-type-friendly 

     http://forum.dlang.org/thread/j6sp68$2a7k$1 digitalmars.com
     https://github.com/D-Programming-Language/dmd/pull/443

 * October 25, 2011: Original "Multidimensional arrays for D" 
 post. No response from Phobos developers.
     http://forum.dlang.org/thread/j864es$2gi0$1 digitalmars.com

 * June 17, 2012: A request for "template that can simulate a 
 rectangular array".
     http://forum.dlang.org/thread

 * June 30, 2012: A request for "fixed size multidimensional 
 array at runtime".
     
 http://forum.dlang.org/thread/ldjzfqvnjltbbiovqdmy forum.dlang.org


I don't normally post here a lot (though I'm a regular reader), 
but I wanted to say I for one would really appreciate an official 
solution for proper rectangular arrays. A bit of background: I'm 
a numerical physicist focusing on the lattice Boltzmann 
method[1], where most physical quantities live on a (3D) lattice. 
Currently I'm using a Fortran code with is very feature-rich, but 
has grown organically over a decade or so and the features have 
come at the cost of maintainability and performance. As I'm very 
much interested in the D language (though I cannot devote much 
time to it at the moment) I've had plans of writing my own 
smaller D code which would contain the features I need. It would 
be nice to be able to use Phobos for my 3D array needs. Slicing 
will also be much valued to make it easier to communicate 
sections of the lattice through MPI. I would aim to undertake 
this project after I've finished my PhD thesis, in ~2 months. I 
don't assume an official Phobos version would be available at 
that time, but even having a good idea of the API that is being 
aimed for would save me a lot of time I think.

Cheers,

Stefan

[1] http://en.wikipedia.org/wiki/Lattice_Boltzmann_methods
Oct 08 2013
parent reply "Nick B" <nick.barbalich gmail.com> writes:
On Tuesday, 8 October 2013 at 17:26:46 UTC, Stefan Frijters wrote:
andrei wrote:

* We need to have a battery of multidimensional array shapes 
along with
simple iteration and access primitives, at least for interfacing 
with
scientific libraries that define and expect such formats. I'm 
thinking
rectangular (generally hyperrectangular) matrices, triangular 
matrices,
sparse matrices, and band matrices.

I too are interesteed in this area as well. Dennis do you only 
plan to focus on multidimensional arrays only, or will you 
incorporate the above matrices as well  ??

What features are you proposing ?

Nick
Oct 08 2013
parent reply Denis Shelomovskij <verylonglogin.reg gmail.com> writes:
09.10.2013 7:55, Nick B пишет:

 On Tuesday, 8 October 2013 at 17:26:46 UTC, Stefan Frijters wrote:
 andrei wrote:

 I too are interesteed in this area as well. Dennis do you only plan to
 focus on multidimensional arrays only, or will you incorporate the above
 matrices as well  ??

 What features are you proposing ?


I propose stuff for "multidimensional arrays only" as you noted. And I 
plan just to revise my existing API [1] without cardinal changes.

I.e. all I propose is rectangular multidimensional arrays slicing and 
iterating. For matrix and math specific tasks see DScience [2] and SciD 
[3]. The latter started as a fork of DScience but became a separate 
project and is in development. See its wiki [4]. Also such math oriented 
libraries have to be partially (and the are) wrapper around LAPACK.

Also it will be interest to see features you (Stefan and Nick) need e.g. 
as examples of code you want to compile with comments if needed. Write 
down at least basic features for now.

[1] 
http://denis-sh.bitbucket.org/unstandard/unstd.multidimensionalarray.html
[2] https://github.com/dscience-developers/dscience
[3] https://github.com/kyllingstad/scid
[4] https://github.com/kyllingstad/scid/wiki

-- 
Денис В. Шеломовский
Denis V. Shelomovskij
Oct 09 2013
parent "Stefan Frijters" <sfrijters gmail.com> writes:
On Wednesday, 9 October 2013 at 08:30:11 UTC, Denis Shelomovskij 
wrote:

 09.10.2013 7:55, Nick B пишет:

 On Tuesday, 8 October 2013 at 17:26:46 UTC, Stefan Frijters 
 wrote:
 andrei wrote:

 I too are interesteed in this area as well. Dennis do you only 
 plan to
 focus on multidimensional arrays only, or will you incorporate 
 the above
 matrices as well  ??

 What features are you proposing ?


 I propose stuff for "multidimensional arrays only" as you 
 noted. And I plan just to revise my existing API [1] without 
 cardinal changes.

 I.e. all I propose is rectangular multidimensional arrays 
 slicing and iterating. For matrix and math specific tasks see 
 DScience [2] and SciD [3]. The latter started as a fork of 
 DScience but became a separate project and is in development. 
 See its wiki [4]. Also such math oriented libraries have to be 
 partially (and the are) wrapper around LAPACK.

 Also it will be interest to see features you (Stefan and Nick) 
 need e.g. as examples of code you want to compile with comments 
 if needed. Write down at least basic features for now.

 [1] 
 http://denis-sh.bitbucket.org/unstandard/unstd.multidimensionalarray.html
 [2] https://github.com/dscience-developers/dscience
 [3] https://github.com/kyllingstad/scid
 [4] https://github.com/kyllingstad/scid/wiki


Ok, off the top of my head, here are some of the points that 
would be great for me to have. I apologize in advance if any of 
them are trivial / irrelevant or out of scope; I have not had 
time to get my hands dirty on this subject. Even if they are not 
to be part of the generic multidimensional array (MDA) module, 
these are things that I would then like to build my own 
implementation of without having to work with instead of against 
the things that will be in Phobos.

- Many of my operations involve looping over the array in no 

will be very useful.
- Another very common operation is accessing a lattice site and 
looking at its neighbours to determine the outcome of the 
operation. Of course this is easy for nested for-loops as I can 
just nest one deeper and pre-calculate the neighbour offsets in 
another array, but I don't know if there's a canonical way to do 
this in terms of a foreach loop, and if this would add 
requirements to the MDA. As an example, Python's numpy seems to 
have 'generic_filter' for tasks like this[1]. In my testing it 
was very slow though.
- I will have multiple MDAs, containing information like local 
densities and velocities. These will affect each other in 
calculations and thus being able to use zip and friends would be 
very useful. This would require the MDA to be a range I guess?
- My code will use wrapped MPI[2] and HDF5[3] calls for 
parallelism and parallel IO, respectively, and because of that I 
will need some control over the memory layout. Nothing fancy, but 
the usual C-style pointer arithmetic would need to work I think, 
unless there's a nicer mechanism.

I hope these comments can be of some help.

Cheers,

Stefan

[1] 
http://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.filters.generic_filter.html#scipy.ndimage.filters.generic_filter
[2] http://en.wikipedia.org/wiki/Message_Passing_Interface
[3] http://www.hdfgroup.org/HDF5/
Oct 09 2013
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Oct 08, 2013 at 06:42:12PM +0400, Denis Shelomovskij wrote:

 I accidentally discovered Andrei wrote [1] multidimensional array
 implementation is needed. If it really is, I will work to revise the
 API and prepare my implementation [2] for review if nobody is doing
 it already.
 
 Also as Kenji's "multidimensional indexing and slicing" pull [3]
 still not merged the only way is to use hacks like this:
 ---
 // first two rows and three columns of the second matrix
 array2d = matrices[1, R[0 .. 2], R[0 .. 3]];
 ---


[...]

What's the reason Kenji's pull isn't merged yet? As I see it, it does
not introduce any problematic areas, but streamlines multidimensional
indexing notation in a nice way that fits in well with the rest of the
language. I, for one, would push for it to be merged.

In any case, I've seen your multidimensional array implementation
before, and I think it would be a good thing to have it in Phobos. In
fact, I've written my own as well, and IIRC one or two other people have
done the same. Clearly, the demand is there.

See also the thread about std.linalg; I think before we can even talk
about having linear algebra code in Phobos, we need a solidly-designed
rectangular array API. As I said in that other thread, matrix algebra
really should be built on top of a solid rectangular array API, and not
be yet another separate kind of type that's similar to, but incompatible
with rectangular arrays. A wrapper type can be used to make a
rectangular array behave in the linear algebra sense (i.e. matrix
product instead of per-element multiplication).


T

-- 
Debian GNU/Linux: Cray on your desktop.
Oct 11 2013
parent reply "Laeeth Isharc" <laeethnospam nospamlaeeth.com> writes:
On Friday, 11 October 2013 at 22:41:06 UTC, H. S. Teoh wrote:

 What's the reason Kenji's pull isn't merged yet? As I see it, 
 it does
 not introduce any problematic areas, but streamlines 
 multidimensional
 indexing notation in a nice way that fits in well with the rest 
 of the
 language. I, for one, would push for it to be merged.

 In any case, I've seen your multidimensional array 
 implementation
 before, and I think it would be a good thing to have it in 
 Phobos. In
 fact, I've written my own as well, and IIRC one or two other 
 people have
 done the same. Clearly, the demand is there.

 See also the thread about std.linalg; I think before we can 
 even talk
 about having linear algebra code in Phobos, we need a 
 solidly-designed
 rectangular array API. As I said in that other thread, matrix 
 algebra
 really should be built on top of a solid rectangular array API, 
 and not
 be yet another separate kind of type that's similar to, but 
 incompatible
 with rectangular arrays. A wrapper type can be used to make a
 rectangular array behave in the linear algebra sense (i.e. 
 matrix
 product instead of per-element multiplication).



Hi.

I wondered how things were developing with the rectangular arrays 
(not sure who is in charge of reviewing, but I guess it is not HS 
Teoh).  It would be interesting to see this being available for 
D, and I agree with others that it is one of the key foundation 
blocks one would need to see in place before many other useful 
libraries can be built on top.

Let me know if anything I can help with (although cannot promise 
to have time, I will try).


Laeeth.
Dec 22 2014
next sibling parent reply "aldanor" <i.s.smirnov gmail.com> writes:
A gap in multi-dimensional rectangular arrays functionality in D 
is sure a huge blocker when trying to use it for data science 
tasks. Wonder what's the general consensus on this?
Dec 22 2014
parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Mon, Dec 22, 2014 at 11:35:17AM +0000, aldanor via Digitalmars-d wrote:

 A gap in multi-dimensional rectangular arrays functionality in D is
 sure a huge blocker when trying to use it for data science tasks.
 Wonder what's the general consensus on this?


Kenji's PR has been merged in the meantime, so now we have the tools to
build a solid multi-dim array library. Somebody just needs to do the
work, that's all.


T

-- 
Debian GNU/Linux: Cray on your desktop.
Dec 22 2014
prev sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Mon, Dec 22, 2014 at 08:49:45AM +0000, Laeeth Isharc via Digitalmars-d wrote:

 On Friday, 11 October 2013 at 22:41:06 UTC, H. S. Teoh wrote:

What's the reason Kenji's pull isn't merged yet? As I see it, it does
not introduce any problematic areas, but streamlines multidimensional
indexing notation in a nice way that fits in well with the rest of
the language. I, for one, would push for it to be merged.




FYI, Kenji's merge has since been merged. So now the stage is set for
somebody to step up and write a nice multidimensional array
implementation.



In any case, I've seen your multidimensional array implementation
before, and I think it would be a good thing to have it in Phobos. In
fact, I've written my own as well, and IIRC one or two other people
have done the same. Clearly, the demand is there.

See also the thread about std.linalg; I think before we can even talk
about having linear algebra code in Phobos, we need a
solidly-designed rectangular array API. As I said in that other
thread, matrix algebra really should be built on top of a solid
rectangular array API, and not be yet another separate kind of type
that's similar to, but incompatible with rectangular arrays. A
wrapper type can be used to make a rectangular array behave in the
linear algebra sense (i.e. matrix product instead of per-element
multiplication).


 
 
 Hi.
 
 I wondered how things were developing with the rectangular arrays (not
 sure who is in charge of reviewing, but I guess it is not HS Teoh).
 It would be interesting to see this being available for D, and I agree
 with others that it is one of the key foundation blocks one would need
 to see in place before many other useful libraries can be built on
 top.
 
 Let me know if anything I can help with (although cannot promise to
 have time, I will try).


[...]

Well, just like almost everything in D, it just takes somebody to step
up to the plate and do the work. :-) Now that language support is there,
all that's left is for a good, solid design to be made, a common API
that all (multi-dimensional) rectangular arrays will conform to, and a
nice Phobos module to go along with it.

What I envision is a set of traits for working generically with
multidimensional arrays, plus some adaptors for common operations like
subarrays (rectangular "windows" or "views"), and a concrete
implementation that serves both as a basic packed rectangular array
container and also an example of how to use the traits/adaptors.

The traits would include things like determining the dimensionality of a
given array, the size(s) along each dimension, and element type. Common
operations include a subarray adaptor that does index remappings,
iteration (in various orderings), etc.. 

The concrete implementation provides a concrete multidimensional
rectangular array type that implements the aforementioned traits. It
supports per-element operators via overloading, but not matrix algebra
(which belongs in a higher-level API).

Along with this, I have found in my own experiments that it is helpful
to include a standard 1-dimensional "short array" type that serves as a
common type for storing index sets, representing array dimensions, for
use in representing (sub)regions, etc.. This "short array" type, perhaps
we can call it a Vector, is basically an n-tuple of array indices
(whatever the array index type is -- usually size_t, but in some
applications it might make sense to allow negative array indices). A
rectangular range of array indices can then be represented as a pair of
Vectors (the n-dimensional equivalent of upperleft and lowerright
corners). Index remappings for subarrays can then be implemented via a
simple subtraction and bound on the incoming index (e.g., subarray[i1]
gets remapped to originalArray[i1 - subarray.upperleft], where i1 and
upperleft are Vectors). To allow convenient interoperability with
explicit index lists (e.g., array[i,j,k,l]), Vectors should easily
expand into argument tuples, so that writing array[v1] is equivalent to
writing array[v1[0], v1[1], v2[2], ...].

None of this is groundbreaking new territory; somebody just has to sit
down and sort out the API and write the code for it.


T

-- 
Why are you blatanly misspelling "blatant"? -- Branden Robinson
Dec 22 2014
parent reply "aldanor" <i.s.smirnov gmail.com> writes:
On Monday, 22 December 2014 at 22:36:16 UTC, H. S. Teoh via 
Digitalmars-d wrote:

 FYI, Kenji's merge has since been merged. So now the stage is 
 set for
 somebody to step up and write a nice multidimensional array
 implementation.


One important thing to wish for, in my opinion, is that the 
design of such implementation would allow for (future potential) 
integration with linear algebra libraries like blas/lapack 
without having to be rewritten from scratch (e.g. so it doesn't 
end up like Python's array module which got completely superceded 
by numpy).
Dec 22 2014
parent reply "Laeeth Isharc" <Laeeth.nospam nospam-laeeth.com> writes:
On Monday, 22 December 2014 at 22:46:57 UTC, aldanor wrote:

 On Monday, 22 December 2014 at 22:36:16 UTC, H. S. Teoh via 
 Digitalmars-d wrote:

 FYI, Kenji's merge has since been merged. So now the stage is 
 set for
 somebody to step up and write a nice multidimensional array
 implementation.


 One important thing to wish for, in my opinion, is that the 
 design of such implementation would allow for (future 
 potential) integration with linear algebra libraries like 
 blas/lapack without having to be rewritten from scratch (e.g. 
 so it doesn't end up like Python's array module which got 
 completely superceded by numpy).


You mean especially for sparse matrices ?  What is it that needs 
to be borne in mind for regular matrices ?
Dec 22 2014
parent reply "uri" <uri.grill gmail.com> writes:
On Tuesday, 23 December 2014 at 03:11:20 UTC, Laeeth Isharc wrote:

 On Monday, 22 December 2014 at 22:46:57 UTC, aldanor wrote:

 On Monday, 22 December 2014 at 22:36:16 UTC, H. S. Teoh via 
 Digitalmars-d wrote:

 FYI, Kenji's merge has since been merged. So now the stage is 
 set for
 somebody to step up and write a nice multidimensional array
 implementation.


 One important thing to wish for, in my opinion, is that the 
 design of such implementation would allow for (future 
 potential) integration with linear algebra libraries like 
 blas/lapack without having to be rewritten from scratch (e.g. 
 so it doesn't end up like Python's array module which got 
 completely superceded by numpy).


 You mean especially for sparse matrices ?  What is it that 
 needs to be borne in mind for regular matrices ?


The layout in lapck/blas is column major so it can be handy using 
a wrapper around arrays to provide the FORTRAN indexing.

Also you need to pass the .ptr property of the array or &a[0]. D 
arrays are fat and include their length.

Cheers,
uri
Dec 22 2014
parent "jmh530" <john.michael.hall gmail.com> writes:
It might make sense to take a look at Armadillo (another C++ 
linear algebra library) for inspiration on multidimensional 
arrays.
Jan 14 2015
prev sibling parent "ilya-stromberg" <ilya-stromberg-2009 yandex.ru> writes:
On Tuesday, 8 October 2013 at 14:41:47 UTC, Denis Shelomovskij 
wrote:

 I accidentally discovered Andrei wrote [1] multidimensional 
 array implementation is needed. If it really is, I will work to 
 revise the API and prepare my implementation [2] for review if 
 nobody is doing it already.

 Also as Kenji's "multidimensional indexing and slicing" pull 
 [3] still not merged the only way is to use hacks like this:


+1
Oct 13 2013