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 UTCThis 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