Flat multi-dim arrays.

Mikola Lysenko mclysenk at mtu.edu
Thu Aug 10 12:29:49 PDT 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.





More information about the Digitalmars-d mailing list