Re: [boost] Multi Array Review vs. Budd

From: Larry Evans (jcampbell3_at_[hidden])
Date: 2002-01-08 13:06:58

Larry Evans wrote:

> John Maddock wrote:

[snip]

>
> Could someone compare this method for accessing subarrays with the one in:
>
>       _An APL Compiler_
>      Timothy Budd
>       Springer-Verlag(1988)
>
> Budd did a lot of analysis of the speed and memory requirements and
> his methods included very simple ways to do transposes and slices and
> rotations and other transforms.  Using some of his ideas might improve
> multi_array and enable it to be better optimized by some compilers.

The following is a short comparison between Budd's book and
multi_array:

  Page 60 of _An APL Compiler_ by Timothy Budd contains a description
  of the shape vector, s[i], and expansion vector, e[i], of an array.
  The correspondence of these vectors and the data in multi_array are
  (as far as I can tell):

    s[i] = const_multi_array_ref::extent_list_[i]
    e[i] = const_multi_array_ref::stride_list_[i]

  Page 83 of Budd's book contains a description of the Stepper, which
  the footnote says is from Leo Guibas and Douglas Wyatt in
  "Compilation and Delayed Evalutaion in APL," _Conference Record of
  the 5th ACM Symposium on Principles of Programming Languages, 1978_.
  This description is of 3 vectors whose length is the rank of the
  array.  The correspondence of these vectors and the data in
  multi_array are as follows:

    q[i] == general_storage_order::_ordering[i]
    d[i] == general_storage_order::_ascending[i]?+1:-1
    t[i] == ?

  The ? above indicates I couldn not find any corresponding
  multi_array data.  t[i] in Budd's book is used when an dimension (or
  axis in apl nomenclature) is "reversed", i.e. index 0 actually
  corresponds to s[i]-1.  However, the base.hpp:346 line defines
  calculate_descending_dimension_offset, which looks like it does
  something related, but I'm not sure.

I would recommend NOT accepting into boost until some methods for
reversing axes and other methods for transposing axes are provided.
In particular, it's unclear from the code how to get a false entry
into ascending_.  Only adding a method for reversing the axes would
make this necessary.  Also, I would have to see some justification for
not using Budd's method to take care of "descending" dimensions
(i.e. the t[i] above).

Also, in addition to the concerns about memory management of the data,
as reflected in http://groups.yahoo.com/group/boost/message/22396, I
think there's a concern about management of the "configuration" of the
array.  For example, in base.hpp:129, the call to Reference seems to
pass pointers to the extents and strides.  I assume, then that
Reference is a multi_array_ref, but then multi_array_ref doesn't own
the extents or strides either.  Right?  On the other hand, some other
operations may require the result to copy all or part of the
"configuration".  For example, wouldn't slicing the array require
this?

Budd's book might also serve as a guide for template metaprogramming
of multi_array, since it analyzes how how the stepper is modified from
the bottom of and expression tree to the top.  This book might also be
helpful to any optimizing compiler writers.