Re: [boost] Try out a multi-dimensional adapter class template?

Subject: Re: [boost] Try out a multi-dimensional adapter class template?
From: Daryle Walker (darylew_at_[hidden])
Date: 2013-10-09 06:00:48

> From: ramey_at_[hidden]
> Date: Tue, 8 Oct 2013 21:25:44 -0800
> 
> Daryle Walker wrote:
>>> From: ramey_at_[hidden]
>>> Date: Tue, 8 Oct 2013 08:50:54 -0800
>>>
>>> Daryle Walker wrote:
>>>> I added a new class template for my library at
>>>> <https://github.com/CTMacUser/ArrayMD>. It's called "multiarray,"
>>>> and it's an adapter class like stack and queue. But the new
>>>> interface is only for accessing elements. Besides the element and
>>>> container types, the template header for the class takes the number
>>>> of dimensions. The class uses at, operator [] and operator () to
>>>> access an element. It has methods to read/write the shape of the
>>>> array and the priority of each index. There are no methods to
>>>> change the number of elements stored; you have to either use a
>>>> fixed-size container or sub-class the multi-array to add methods to
>>>> change the size. (The container sub-object is protected, like the
>>>> Standard adapters.) I split the main code into two base class
>>>> templates, because the code for computing the offset from an index
>>>> tuple and the code for referencing an element were nearly distinct.
>>>> This really screws up my attempt at Doxygen comments. Any ideas?
>>>> Or is my case too complex for what Doxygen's author thought could
>>>> be handled.
>>>
>>> I've looked at the document above. It would seem to me that this
>>> is similar or equivalent to boost.multi-array with extents set at
>>> compile time rather than at runtime. Is my understanding of this
>>> correct? If not how is it wrong.
>>
>> Both templates get the number of dimensions as a compile-time
>> parameter and the actual extent values at run-time. The Boost
>> version can take the extents and priorities in the constructor, while
>> my version has to change those attributes in separate call(s). But
>> it seems that construction time is the only opportunity for the Boost
>> version to use a different index priority; it can't be changed later,
>> unlike mine.
> 
> Hmm- I'm not sure what "index priority" refers to.

That's row-major vs. column-major vs. scrambled.  Let's look at a 3x4 array:

  1  2  3  4
  5  6  7  8
  9 10 11 12

In row-major order, the elements are stored as {1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12} in memory.  Given coordinates <a, b>, you can find the offset
(zero-based) from the start of the memory block to the desired element as:
a * 4 + b.  For column-major order, the elements are stored as {1, 5, 9, 2,
6, 10, 3, 7, 11, 4, 8, 12} in memory and the offset formula is a + 3 * b.

In other words, the offset is "DOT_PRODUCT( <a, b>, StrideArray )," where
the stride array is {4, 1} for row-major order and {1, 3} in column-major
order.  The stride array is calculated from the index extents, the product
of those extents, and the index priority list.

The priority list is the same length as the extents list, and contains the
numbers 0 through Rank - 1.  Each number appears once; the value at element
0 is that of the index that is the most major, next major at element 1,
down to the least-major index at element Rank - 1.  The stride array has the
same length as the others.  The stride of the most-major index is the total
size divided by the extent for that index.  The stride of the next major
index is the previous stride divided by the extent of the next major index.
Eventually, we go down to the least-major index getting a stride of 1.

The priorities are my terminology for the storage order.

[SNIP]
>> Neither version provides methods to directly change the number of
>> elements. The Boost version can change its element count through its
>> resize method.
> 
> Hmm - These statements seem to conflict - It seems to me that
> multi-array can have all the extents adjusted at run time. I can
> see that this facility could imply extra coding and loss of runtime
> efficiency. That was the motivation for my original question -
> it seemed to me there might be a motivation to have the same
> thing with more stuff fixed at compile time to make it faster
> at the cost of runtime configurability.

Yeah, it didn't look right after I wrote it.  If you want fixed extents,
then you would have a fixed-sized container, and Boost.MultiArray is a
dynamic one.  If you want said fixed-sized container, then use something
like Boost.Array or my array_md type, and use an adapter like my multiarray
or the Boost (const_)multi_array_ref types if you don't like the default
storage order (or other choices for the Boost adapters).

>> My version can't at all, except through derived
>> classes. But my version decouples the elements stored and what's
>> needed. You only crash when referencing an element beyond the
>> container's bounds. It was designed with std::array as a base
>> container. It should be efficient when the desired size stays close
>> to the array's fixed size.
> 
> Hmm - doesn't one fix the array size to the "desired size" at
> compile time? Aren't they equal. I'm not getting this.

My multiarray adapter holds two sizes.  One is the desired size, which is
the product of the last submitted set of extents.  The other is the actual
size, which calls "size()" of the inner protected container.  They don't
have to match.

If they don't match, then you get either unused container elements which
can't be addressed or missing ones you shouldn't address.  The constructors
set the desired size to be the current size (or 1 if the container starts
off empty), and the priority to be row-major order.  The default constructor
works right for std::array, but using a std::vector or deque will start off
with an empty container.  You can use the other constructors to start the
container with elements.

>> My version indexes only elements; sub-arrays are not supported. It
>> wouldn't be efficient, since elements would not be contiguous in
>> general.
> 
> To me this is an absolutly essential feature and one reason I
> love this library.

C spoiled us with their multidimensional arrays actually being nested linear
arrays.  So subsets was really easy (as long as you followed row-major
order).  I think it's more of a secondary action of the Multi-Array concept,
rather than primary (like element indexing).

>>Create a new array object of the smaller size and use
>> (c)apply to copy over what you want.

Which is probably what Boost.Multiarray does in the background of its
slicing methods (that return a copy).

> You have to walk all the elements to create the new
> contiguous array. It's not clear how you would do this
> in your library. The current one does it all automatically
> taking care of strides and all that. Your scheme just
> ignores the utility of this feature.

The automatically-defined copy constructor and assignment work if all the
template parameters are the same.  But for other combinations, do you
want to follow in-memory order, or match index-tuple to (mapped) index-tuple?
That's why I didn't pick a default.

If you're doing copying, you should call (c)apply for the smaller container.
Make sure to pass the non-applying container as a lambda argument.

[SNIP]
>> Another class in that GitHub
>> repository, array_md, does do that. However, it's a variadic
>> extension of std::array, and so does not have any of the storage or
>> indexing options that Boost.Multi-Array has. My multiarray adapter
>> was started from so many complaints that array_md doesn't support
>> anything besides row-major order, making it less desirable for all
>> the math & science junkies that wanted column-major (or
>> scrambled-priority) storage.
> 
> All this is supported by the current multi-array. Why not just
> focus your efforts in enhancing multi-array to include compile
> time setting of array extents. Note that the multi-array library
> includes multi_array_ref which is designed to provide the
> multi-array interface to an array which has already been allocated.
> Natually in this case it doesn't do any allocation on it's own.
> 
> It seemst to me that the mult-array has everything we need
> and that very little is to be gained by trying to replace it.

array_md is designed to be an upgrade of boost::array, not compete with
Boost.MultiArray.  My multiarray adapter is a first draft at something
new for me.  They're both made to be possible additions to the Standard,
which wouldn't have Boost.Multiarray, i.e. they have to be stand-alone.

Daryle W.