First, DefaultRectangular has to support arbitrary dimension.
Is it important to support arbitrary dimension "column-major"
layouts? What about a 3D layout, where only the middle dimension
is stored differently from how it works now? As far as I know,
people interested in "column major" arrays are talking
about 2D arrays / matrices.
I use row-major and column-major as shorthands for whether the innermost
or outermost dimensions are closer together in memory, so I think it
extends naturally to higher-dimensional arrays. As far as I know, this is
how others use the terms as well (e.g., I think people say Fortran is a
column-major order language even though it also supports
higher-dimensional arrays). We could use less 2D-centric terms for this
decision if that seemed more palatable.
Second, I'm not so sure it's a good precedent to put it in
to DefaultRectangular. Won't we prefer to make any new layout a
configurable option in DefaultRectangular for to "minimize software
layers and complexity"? I think it would be preferably to allow
other layouts to exist separately and to solve whatever software
engineering/complexity problems come up. (E.g. giving Block
the ability to select the layout used).
I think that's a reasonable argument. But for the specific case of row-
vs. column-major order, I think that this is a natural and simple choice
for a default rectangular array to expose and that there's more code in
common between the two choies than there is differentiated code. I think
your objection here is more relevant to my suggestion that perhaps
DefaultRectangular might support a tiled layout down the road, and I think
I agree with your point if that was what we were discussing. I.e., I
think I overspoke in opening DefaultRectangular up to more complex layouts
yesterday -- sorry.
Couldn't we view a Column-major layout as an array that is
similar to an array view? That is, it is not really storing
the array as much as adjusting the mapping from indices
to elements. Isn't that similar to a rank-change array view,
in particular? Didn't we just decide that it was better
to make a rank-change array view a different type, rather
than folding it in to DefaultRectangular? Why is this different?
I believe that what you're proposing here is what Apan has prototyped. I
think the difference is that rank-change array views are more different
and arbitrary than simply reversing the order in which dimensions are
considered in computing offsets (so again, a case of the amount of code
that needs to change to support either case).
Also, recall that we had to special-case rank-change views on default
rectangular in order to retain our historical performance and compress the
translation out of the view. This suggests to me that we'd need to do
similar point-optimizations to make a view-based column-major
implementation perform competitively with a native row-major array.
So, my assertion is that it does not add much code complexity to
DefaultRectangular to support a switch between row and column major order
(while also reusing a lot of existing code) and that it's the cleanest /
best way to maintain similar performance between the two. I'd be happy to
take a quick stab at the implementation to see if I'm correctly estimating
the small number of places that would need to change, but don't want to
take Apan's exploration away from him if he wants to pursue it (that said,
I also hesitate to send anyone down into DefaultRectangular.chpl... :(
Here's an example of one of the key places that would need to change -- it
sets up the per-dimension multipliers, blk():
proc initialize() {
...
blk(rank) = 1:idxType;
for param dim in 1..(rank-1) by -1 do
blk(dim) = blk(dim+1) * dom.dsiDim(dim+1).length;
computeFactoredOffs();
const size = blk(1) * dom.dsiDim(1).length;
...
}
For the column-major case, this would need to be something like:
proc initialize() {
...
blk(1) = 1:idxType;
for param dim in 2..rank do
blk(dim) = blk(dim-1) * dom.dsiDim(dim-1).length;
computeFactoredOffs();
const size = blk(rank) * dom.dsiDim(rank).length;
...
}
With some minor refactoring, I suspect that we could write a version of
this code that would work in either case.
From there, in cases where we consider all dimensions symmetrically,
nothing else would need to change. For example this code should work in
either case:
proc computeFactoredOffs() {
factoredOffs = 0:idxType;
for param i in 1..rank do {
factoredOffs = factoredOffs + blk(i) * off(i);
}
}
But other cases that would need to change are those that optimize away the
multiplication by blk(rank) in cases where we know the value to be '1' (as
it typically is). Such cases would want to symmetrically avoid the
multiplication by blk(1).
-Brad
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Chapel-developers mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/chapel-developers
