Array processing without error checks Bradley Lucier 16 Apr 2025 02:01 UTC

TL;DR:

Nearly all checks that arrays' getters and setters make to ensure that
their arguments are valid are unnecessary when those arrays are passed
as arguments to the bulk array processing procedures; these checks will
be removed in an upcoming pull request.

With this change in the sample implementation on Gambit on my
10-year-old Linux box, I see up to a 30% speedup in early tests.

================================

One of the goals of this SRFI is to:

Encourage bulk processing of arrays rather than word-by-word operations.

The array routines that operate on all elements of an array are

array-copy, array-assign!, array-stack, array-decurry, array-append,
array-block, array-fold-left, array-fold-right, array-reduce,
array-for-each, array-every, and array-any

And, in fact, all the multi-indices that these routines pass to their
argument arrays' getters are within the domain of the array, i.e., they
are all valid multi-indices for the argument arrays.

Because all the multi-indices passed as arguments to the array getters
are known to be valid,  there is no need for the argument array's
getters to check the validity of the multi-indices passed to them, in
contrast to the checking needed for (array-ref A i j k l), which is:

Is A an array?
Is it four-dimensional?
Does the multi-index (i j k l) consist of exact integers within the
domain of the array?

Additionally, once the routines array-map, array-outer-product, and
array-inner-product check the compatibility of the domains of their
array arguments, there is again no need for the bulk processing
procedures to check the individual indices for correctness.

For example, one sees this in the routine neighbor-count as part of
Conway's Game of Life implementation in the SRFI document:

(define (neighbor-count a)
   (let* ((big-a      (array-copy (array-pad-periodically a 1)
                                  (array-storage-class a)))
          (domain     (array-domain a))
          (translates (map (lambda (translation)
                             (array-extract (array-translate big-a
translation)
                                            domain))
                           '(#(1 0) #(0 1) #(-1 0) #(0 -1)
                             #(1 1) #(1 -1) #(-1 1) #(-1 -1)))))
     ;; Returns a generalized array that contains the number
     ;; of 1s in the 8 cells surrounding each cell in the original array.
     (apply array-map + translates)))

Here there are eight different translates of an array as arguments to
array-map; there is no reason for each of the eight different argument
array getters to check that their multi-index arguments are valid once
the array result of (neighbor-count a) does so.

I'll soon submit a pull request implementing these ideas, by adding two
hidden fields to the array structure, %%array-unsafe-getter and
%%array-unsafe-setter, which do not check the validity of their
arguments.  These are the routines that array-copy, array-fold-left,
etc., will use.

If someone calls (array-getter A), then (%%array-unsafe-getter A) will
be wrapped in code that checks its arguments; similarly for
(array-setter A).

As a practical matter, removing these argument checks in the bulk array
procedures makes the idea of "safe" and "unsafe" arrays unnecessary to
some extent.  For now the "unsafe" versions of an array's getter and
setter will remain hidden.