6.5 Nonstrict Arrays
With few exceptions, by default, the functions exported by math/array return strict arrays, which are arrays whose procedures compute elements by looking them up in a vector.
> (define (make-hellos) (array-map string-append (array-map string-append (array #["Hello " "Hallo " "Jó napot "]) (array #["Ada" "Edsger" "John"])) (make-array #(3) "!"))) > (define arr (make-hellos)) > (array-strict? arr) - : Boolean
#t
> arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes String))
#<syntax:build/user/8.13.0.7/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.13.0.7/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.13.0.7/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #["Hello Ada!" "Hallo Edsger!" "Jó napot John!"])
An additional concern becomes even more important as Racket’s support for parallel computation improves. Allocating storage for intermediate arrays is a synchronization point in long computations, which divides them into many short computations, making them difficult to parallelize.
* Regular, shape-polymorphic, parallel arrays in Haskell, Gabriele Keller, Manuel Chakravarty, Roman Leshchinskiy, Simon Peyton Jones, and Ben Lippmeier. ICFP 2010. (PDF)
> (define arr (parameterize ([array-strictness #f]) (make-hellos))) > (array-strict? arr) - : Boolean
#f
> arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes String))
#<syntax:build/user/8.13.0.7/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.13.0.7/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.13.0.7/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #["Hello Ada!" "Hallo Edsger!" "Jó napot John!"])
To use nonstrict arrays effectively, think of every array as if it were the array’s procedure itself. In other words,
An array is just a function with a finite, rectangular domain.
Some arrays are mutable, some are lazy, some are strict, some are sparse, and most do not even allocate contiguous space to store their elements. All are functions that can be applied to indexes to retrieve elements.
The two most common kinds of operations, mapping over and transforming arrays, are compositions. Mapping f over array arr is nothing more than composing f with arr’s procedure. Transforming arr using g, a function from new indexes to old indexes, is nothing more than composing arr’s procedure with g.
6.5.1 Caching Nonstrict Elements
Nonstrict arrays are not lazy. Very few nonstrict arrays cache computed elements, but like functions, recompute them every time they are referred to. Unlike functions, they can have every element computed and cached at once, by making them strict.
> (array-strict? arr) - : Boolean
#f
> (array-strict! arr) > (array-strict? arr) - : Boolean
#t
> (array-strict arr)
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes String))
#<syntax:build/user/8.13.0.7/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.13.0.7/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.13.0.7/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #["Hello Ada!" "Hallo Edsger!" "Jó napot John!"])
To make a strict copy of an array without making the original array strict, use array->mutable-array.
6.5.2 Performance Considerations
One downside to nonstrict arrays is that it is more difficult to reason about the performance of operations on them. Another is that the user must decide which arrays to make strict. Fortunately, there is a simple rule of thumb:
Make arrays strict when you must refer to most of their elements more than once or twice.
(define xrr (array-map expt (index-array #(50 50)) (index-array #(50 50)))) (define res (array+ xrr xrr))
(define xrr (array-strict (array-map expt (index-array #(50 50)) (index-array #(50 50))))) (define res (array+ xrr xrr))
When returning an array from a function, return nonstrict arrays as they are, to allow the caller to decide whether the result should be strict.
(define (make-hellos) (array-default-strict (parameterize ([array-strictness #f]) (array-map string-append (array-map string-append (array #["Hello " "Hallo " "Jó napot "]) (array #["Ada" "Edsger" "John"])) (make-array #(3) "!")))))
If you cannot determine whether to make arrays strict, or are using arrays for so-called “dynamic programming,” you can make them lazy using array-lazy.