Re: Compiling multidimensional arrays

[Per Bothner <per at bothner dot com>]

On 09/12/2013 05:51 PM, Charles Turner wrote:
> I've spent today trying to get multidimensional array
> subscripting/generalised setting to work. It works from the REPL, but
> not when compiling. That is, I've fixed the various ArrayGet/ArraySet
> reflectors, ApplyToArgs, SetArray and various compilation helpers, but
> I'm currently having fun trying to fix the code in CompileArrays.
>
> Currently, CompileArrays only handles 1d arrays correctly. I want to
> make it handle nd arrays. It seems fairly straightforward: just emit
> N-1 aaload instructions, followed by the appropriate *aload
> instruction to retrieve the value.

No, that does not work for true multi-dimensional arrays.

Emitting n-1 aaload instructins works for *nested* arrays - i.e.
an array each of whose elements is another array.  Java does not
have (and the JVM does not support) multi-dimensional arrays,
only nested arrays.

You can mostly simulate multi-dimensional arrays with nested
arrays, but you get into problems.  Consider matrixes: You can
have a 10*0 matrix as well as a 0*10 matrix - and they're different.
You can't represent this with nested arrays.  Even 1*10 column
matrix is painful, because you need 10 1-element arrays.

Also consider a 4*5 matrix.  This is implemented as a single
GeneralArray object, and a single 20-element Object[].
Using nested arrays each row is 5-element Object[], and there
are 4 rows, so there is a 4-element array, each of which is a
pointer to other array (i.e. another object). This extra indirection
does not exist if using GeneralArray.

Another bonus of using GeneralArray that various transpose-like
operations are cheap.

> I'm still swimming around in
> CodeAttr getting myself familiarised with the code generator, but I
> noticed something very weird in CodeAttr#emitNewArray.
>
> The branching order is an instanceof ObjectType test, and if that
> fails, an instanceof ArrayType test. What? ArrayType is a subclass of
> ObjectType! How can that branch be taken?

Indeed, that appears to be a bug.

> Because of that, it seems
> Kawa will never emit the multianewarray instruction even if it
> correctly handled md arrays in the first place. In r1378, Per made the
> following comment:
>
> (emitNewArray):  Use anewarray even if element type is ArrayType.
>
> I assume that's because md arrays don't work anyway, so it makes sense
> to use the faster anewarray when creating arrays of one dimension, but
> why keep the old instanceof ArrayType branch around and not even
> comment why it's there? Am I missing something?
>
> I'm going to take a crack at implementing my above scheme after some
> rest. I'll special case the 1d array to use anewarray of course. I'm
> also special casing 1d arrays in the reflectors and friends because I
> measured a 10x time speedup as opposed to the way you get at arbitrary
> arrays using java.lang.reflect.Array#get and a loop. Not sure if it's
> worth special casing 2d arrays as well, how much do people use them? I
> often find myself simulating them on a vector anyway :/

For people who do Fortran-like numerical calculations it might be
very worthwhile to optimize 2d arrays.  But it seems far from trivial,
and includes a bit of API design - for example an Array2 class.
I think unless you personally care about 2d arrays and their
performance (or your employer cares) I don't think it's high priority.
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/