Re: [Boost-users] Re: MultiArray questions

From: Dr Mark H Phillips (mark_at_[hidden])
Date: 2004-01-28 04:02:29

On Sun, 2004-01-25 at 04:47, garcia wrote:
> 
> Hi Mark.  Thank you for the compliments on MultiArray.  I hope that it 
> meets your needs, and if not, I hope I can be of some service.

Thanks!  Sorry my reply has been a little delayed.

> >Why can't you change the != into <?  Ie, do:
> >
> >  for(index i = 0; i < 3; ++i)
> >    for(index j = 0; j < 4; ++j)
> >      for(index k = 0; k < 2; ++k)
> >        A[i][j][k] = values++;
> >
> >or can you?  This would be more efficient I should think, and
> >requiring that index types be ordered shouldn't be too onerous
> >should it?
> >
> You can change the != into a < if you like.  I don't see any good reason 
> why one should be more efficient than the other.  I personally use != 
> because it more closely matches how I write for loops using iterators.  
> So in short, that's a matter of personal preference.

I would have thought < was more efficient.  Isn't "i != j" implemented,
at machine level, more or less by "i > j || i < j".  So one compare
would be cheaper than two.  Or have I got this wrong?

> >Question 2
> >----------
> >
> >If I use the built-in "no-frills" C array type to represent a
> >2-dimensional array in row-major order, then I would access
> >an element (i, j) by doing:
> >
> >  a[ &a[0] + i*n + j ]
> >
> >where a is my m by n array.  And if I wish to traverse a, in
> >row-major order, I can do:
> >
> >  for (int* ip=&(a[0]); ip<&(a[n*m]); ip+=n) {
> >    for (int* ijp=&(ip[0]); ijp<&(ip[n]); ++ijp) {
> >      visit(ijp);
> >    } 
> >  }
> >
> >These are a very efficient ways of doing things, but it lacks
> >somewhat in ease-of-generalization and in readbility.  This is where
> >the MultiArray library is useful.  But do I lose in efficiency by
> >going to MultiArray?  Ie, in the simple case where base is 0, stride
> >is 1, and when we traverse in row-major order, is the MultiArray
> >library smart enough to do compile-time optimizations to generate
> >code which is as efficient as the above?
> >
> >  
> >
> The MultiArray implementation doesn't currently do anything special for 
> the case that the base is 0.  I'm in the midst of doing some performance 
> analysis on the library, and so far, to be honest, it looks like there 
> is a performance hit.  I'm investigating what is happening, and I hope 
> to translate my findings into performance improvements. I would liket 
> hose to be available by May of this year.

Okay, thanks.  I think I'll have to hand code the above for now and 
perhaps change it over in May.

Also in the above I am taking advantage of being able to
do ++ijp rather than ijp+=stride where stride=1.  Is your code able to
do this?

> It is my intention that a new multi_array be constructible from an 
> existing view, but on looking back through my code and test cases, the 
> library does not currently support it.  This is an oversight on my 
> part.  I hope to have this functionality available in CVS by the end of 
> this coming week (which coincides with the end of the month).  I'm 
> afraid that the functionality won't make the upcoming Boost release however.

I'm glad it will make it in there eventually.

> >Question 4
> >----------
> >
> >Sometimes you might have an object starts off being mostly
> >accessed in row-major order, so you want a representation which works
> >efficiently for this use.  But down the track you might wish to change
> >to mostly column-major access.  Does MultiArray provide easy ways to
> >transform from one underlying representation to another?
> >
> >  
> >
> There is no direct means to change the underlying representation of an 
> existing array.  The layout of an array is determined at construction. 
> You can however assign a row-major multi_array to a column-major 
> multi_array.

Or, more efficiently, one could use multi_array_refs instead.  As
follows:

1. start with a row-major multi_array_ref, referring to internal 
consecutive storage a[]
2. use an efficient algorithm to transpose a[]
3. put this into a column-major multi_array_ref.

Am I right to think this would be a good approach?

Cheers,

Mark.