Parallel computation and the order of evaluating array elements in array-copy[!], etc.
Bradley Lucier 12 Jan 2025 18:49 UTC
Jens Axel Søgaard pointed out the Racket's math/array library was
motivated in some sense by arrays in Haskell, as described in
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/RArrays.pdf
One emphasis of that paper is automatic parallelization of array
operations, which is A Good Thing (TM).
Automatic parallelization is inhibited if, as in SRFI 231, it is
specified that the elements of (generalized) arrays are evaluated in
lexicographical order. This makes sense for certain operations
(array->list), and is necessary for some operations (array-any,
array-every, array-for-each), but for other operations (array-copy,
array-stack, array-append, array-block, array-decurry) it is a nice
thing to have in some circumstances (e.g., when constructing an array by
reading elements from a file) but it would be good to have versions of
these operations where the order of evaluation is not specified.
We can allow parallel computations in a future array library by allowing
the non-"call/cc-safe" routines array-set!, array-assign!, array-copy!,
array-stack!, array-append!, array-block!, and array-decurry! to
evaluate elements of argument arrays in any order. If the order of
evaluation of the source argument to array-assign! is important, then
the source argument can be copied with array-copy before the assignment.
(As an aside, the notion of a single continuation to a parallel
computation seems problematic.)
So I would add this change to the list of things I'd change in a future
library.
Brad
Things to change in a future library (just for future reference):
1. (srfi 231) is "safe", with an "unsafe" library (srfi 231 unsafe);
mixing safe and unsafe arrays and operations could be accomplished by
renaming routines.
2. Get rid of array-freeze!
3. Do not fix the order of evaluation of array elements in arguments to
the "bang" (!) procedures.