From: Larry Evans (jcampbell3_at_[hidden])
Date: 2002-01-08 13:06:58
Larry Evans wrote:
> John Maddock wrote:
> Could someone compare this method for accessing subarrays with the one in:
> _An APL Compiler_
> Timothy Budd
> 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
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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk