True multidimensional arrays
My #1 wish for Mustang is simple: "int[2,3] matrix". I was once in favor of JSR-83 (Multiarray package), but now that the Java language is more open to syntax improvements, we can just drop that JSR. We don't need a full-blown Fortran clone (BLAS libraries, etc.) bundled with every JRE, less than 1% of Java apps need this kind of functionality. We need only the most fundamental feature: multidimensional arrays in the core typesystem.
Sophisticated numerical APIs like JSR83's, Jakarta Commons Math's and others, could then be implemented in PureJava with top performance, without any further JVM support, for those needing such APIs. But the core array feature is useful for ALL non-trivial Java apps, even those not doing any numerical work -- MD arrays are better than square arrays-of-arrays, even for non-numerical content.
Now, a more concrete tentative specification.
Java's current arrays have this layout:
[header, size, elem0, elem1, .., elemN], N=size-1.
I propose this layout for multidimensional arrays:
[header, size, elem0, elem1, .., elemN, dims, dimsize0, dimsize1, .., dimsizeM], M=dims-1
Where "dims" is the number of dimensions for the array. For example, the array "int[2,3]" would be stored as:
[header, 6, elem0, elem1, .., elem5, 2, 2, 3]
Where elem0 = [0,0], elem1 = [0,1], elem2 = [0,2], elem3 = [1,0], elem4 = [1,1], elem5 = [2,3]. An index expression such as array[a,b] would be mapped by the compiler to *(&elem0 + 3*a + b), as usual in languages with true multidimensional arrays.
The advantage of storing the new fields for #dimensions and size of each dimension in the end of the array instead of the beginning is compatibility. It's less changes to existing JVMs, reflection APIs, etc. Even the traditional "full size" field can be kept, even if redundant. The object header may need an 1-bit flag to specify if the array is traditional or multidimensional, i.e., if the new dimension/dimension-size fields are present, so we don't need to add these fieidls for 1-dimension arrays.
We could even support compatibility between MD arrays and traditional arrays:
int[2,3] mdArray = new int[2,3];
int oldArray = (int)mdArray;
oldArray = 7; // changes mdArray[1,2]
The code above is easy and safe to implement. But:
int oldArray = new int;
int[2,3] mdArray = (int[2,3])oldArray; // not allowed!
This case is not allowed because it creates problems with my next request: conformant arrays.
"Conformant" (or "open") arrays have dimensions that may be dynamically inspected. Java's current arrays are conformant: aray.length gives the size. Multidimensional arrays must be conformant too:
mdArray.dims -> 2 // reads field: dims
mdArray.length -> 3 // reads field: dimsize0
mdArray.length -> 4 // reads field: dimsize1
mdArray.length -> 1
The above is just one possible suggestion for how to access the number of dimensions and the length of each. There are other possibilities, like:
mdArray.lengths -> 3 // reads field: dimsize0
mdArray.lengths -> 4 // reads field: dimsize1
mdArray.lengths.length -> 2 // reads field: dims
In this second version, I only add one meta-field lengths, less new stuiff than the first proposal (which requires a meta-field 'dims' plus new syntax like mdArra.length to fetch the length of the second dimension). Do whatever is easier. Maybe we could keep "mdArray.length" returing the "full size" (like 3*4=12 in this example), to make some single/multi-dimensional programming tricks easier, more compatible, or more efficient, like:
int data = new int[mdArray.length]; // new 12-elem array
System.arraycopy(mdArray, 0, data, 0, data.length);
Finally, support for array sizes in the static typesystem is another very important improvement. Example:
double[4,4] matmult (double[4,4] a, double[4,4] b);
The method above implements the matrix multiplication algorithm, optimized for 4x4 matrices, which are wildly popular in 2D & 3D graphics code for example. With the specific dimensions specified in parameters and return types, the JVM doesn't need to do ANY bounds checking for constant indexes (the matmult algorithm above can be implemented using only constant indexes, or if you prefer, with two 'for' loops ranging from 0..3 so the compiler can still prove statically that all indexes are valid). The index-check would be required only at method call or at assignment of the return, and this check could be usually performed at source compilation time. The single scenario that requires dynamic checks is when using the next feature:
double[,] matmult (double[,] a, double[,] b);
The method above performs multiplication of matrices of any size. The code will use of the dimension-specific length fields, so it will do loops like
for (int x = 0; x < a.lengths; ++x)
// operate on a[x], etc.
...so the optimizer can remove bounds-checks easily, as [0..a.lengths) is precisely the valid range for a[N] and so on. It's only slightly less efficient than a version tuned for specific size, because we need loops, but we don't need any bounds checks, neither expensive optimizations to remove bounds-checks (loop unrolling, moving the checks to method header, loop versioning so an eventual exception happens exactly when required by the JLS, etc.).
This feature can get even better:
double[A,C] matmult (double[A,B] a, double[B,C] b);
In this version, the identifiers A/B/C are constraints similar to type variables in generics. The methods is constrainted to multiply only pairs of arrays such that a's second-dim length is equal to b's first-dim length. The resulting array's dimensions are also constrained by the dimensions of the arguments. The implementation of this methods can use the identifiers A,B,C (which map to 'int' values) in loop bounds, array creation expressions, etc. so we don't need any dynamic lookup of the array's dimension-length fields... and the *single* overhead of this implementation, compared to one optimized for a fixed size, is the looping structures.
The language would allow all sensible combinations of conversions, like:
int[,] b, c;
b = a; // Ok, no checks required
c = new int[9,1];
a = (int[3,4])b // Ok (with dynamic bounds-check)
a = b; // compile-time error, requires cast
a = (int[3,4])c; // Compiles, but throws index exception
I think this proposal is hugely useful. Multidimensional arrays save space and time with their much simpler memory layout and initialization (not need of nested for loops just to init all dimensions). JIT compilers can generate optimizal code with less effort (better loading time). The "flat" memory layout produces much better performance also due to CPU caches. Less overhead goes to GC too, because arays-of-arrays contain a tree of pointers to the sub-arrays, and they're split in a large number of small objects; in comparison, a multidimensional array of any size doesnt' contain any reference, and it's made of one
single big object, so in the GC, both the mark and copy steps are more efficient. Multidimensional arrays avoid virtually all the bounds checks, and all the nullpointer
checks (for nested arrays), that currently make difficult for JIT compilers to generate optimal code for arrays. Finally, full support for conformant arrays, including syntaxes for arrays with specified sizes (a[3,4]), unspecifed sizes (a[,]) and constrained sizes (a[A,B]), will do for arrays what generics do for other codes, with additional performance benefits.
The proposal can be implemented with a very backwards compatible memory layout for MD arrays; no new keywords; very modest syntax extensions (in the same ballpark of most features from JSR-201); and the new arrays can be made hugely compatible with existing APIs (expecting traditional arrays), even though some new APIs would be desirable to provide specific support for MD arrays.
And nothing here is rocket science, programming languages have been implementing multidimensional arrays for ages, even with features that go much further than this proposal (e.g. triangular or sparse arrays; group operations on entire arrays, rows or columns, and so on). In fact, the current top-notch JIT compilers, like HotSpot, have array handling code that's more complex than everything I'm requesting here, because they implement optimizations like bounds-check removal and loop transformations, that are
very difficult to do with arays-of-arrays, but much easier with MD arrays, and trival with constrained MD arrays.