Exposing the stride and offset John Cowan 11 Aug 2015 21:17 UTC Re: Exposing the stride and offset Pierpaolo Bernardi 11 Aug 2015 21:48 UTC Re: Exposing the stride and offset Bradley Lucier 26 Sep 2015 18:28 UTC

Exposing the stride and offset John Cowan 11 Aug 2015 21:17 UTC

This is a proposal for a substantive (and substantial) change to SRFI 122.
(I accidentally sent it to the SRFI-112 list the first time.)  It's based
on NumPy and Julia, and provides a powerful new capacity to fixed-arrays.

The normal algorithm for converting an index tuple to a single integer
is as follows.  Let L_k (k <= 0 < the rank) to be the lower bound of
dimension k, let U_k be the upper bound of dimension k, let I_k be the
kth element of the index vector.  Furthermore, let R_k be U_k - L_k for
every , and let O_k be I_k - L_k for every k.  If the invariant L_k <
I_k <= U_k fails for any k, it is an error.  Then, we compute the index
as the sum of factors of the form O_k * R_k-1 * ... * R_0 for every k.
We can optimize away the repeated multiplications, of course.

But we can do a much more thorough job of factoring by precomputing a
vector of *strides*.  S_k is the kth stride, and represents the number
of storage elements between successive elements that differ in the kth
index by 1.  So in a 3 x 4 zero-based matrix, S is #(4 1); note that
the highest value of S is always 1.  The offset V represents the index
of the storage element whose index tuple is (0) or (0, 0) or (0, 0, 0)
or ...  Now the algorithm is simply V + \sigma S_k * I_k.

If the stride-offset representation were purely internal, it wouldn't
matter to this SRFI.  But the ability to specify an array using the body
of an existing array but with different strides and offset makes a huge
difference to what can be done to the array.  For example, transposing
a matrix just requires reversing the stride: with a stride vector of
#(1 4) instead of #(4 1), we have effectively exchanged the roles of
the row index and the column index without further ado.  Similarly, we
can reverse a zero-based vector whose V is 0 and whose stride is #(1),
by letting V be the vector length and S be #(-1).  There are a lot more
transformations we can do on an array by returning the same body with
new values of S and V.

(It is also possible for S_k to be an exact rational: this allows us to
create, for example, a vector with five elements of backing store with
V = 2 and S = #(1/100), meaning that the valid values of I_0 are -200,
-100, 0, 100, 200.  I am not sure that this is useful enough to require
support, however.)

I realize that this is not the clearest explanation, so I'll be
happy to answer questions on it.  Commenters should also look at
<http://docs.scipy.org/doc/numpy/reference/arrays.ndarray.html>.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
The work of Henry James has always seemed divisible by a simple dynastic
arrangement into three reigns: James I, James II, and the Old Pretender.
--Philip Guedalla