►Math Library
▼6 Arrays
►6.5 Nonstrict Arrays
On this page:
6.5.1 Caching Nonstrict Elements
6.5.2 Performance Considerations
  top  ← prev  up  next → 

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.

This conservative default often wastes time and space. In functional code that operates on arrays, the elements in most intermediate arrays are referred to exactly once, so allocating and filling storage for them should be unnecessary. For example, consider the following array:
> (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

- : (Array String)

(array #["Hello Ada!" "Hallo Edsger!" "Jó napot John!"])

By default, the result of the inner array-map has storage allocated for it and filled with strings such as "Hello Ada", even though its storage will be thrown away at the next garbage collection cycle.

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)

A solution is to construct nonstrict arrays*, which are arrays whose procedures can do more than simply look up elements. Setting the parameter array-strictness to #f causes almost all math/array functions to return nonstrict arrays:
> (define arr (parameterize ([array-strictness #f])
                (make-hellos)))
> (array-strict? arr)

- : Boolean

#f

> arr

- : (Array String)

(array #["Hello Ada!" "Hallo Edsger!" "Jó napot John!"])

In arr, the first element is the computation (string-append (string-append "Hello " "Ada") "!"), not the value "Hello Ada!". The value "Hello Ada!" is recomputed every time the first element is referred to.

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.

To compute and store an array’s elements, use array-strict! or array-strict:
> (array-strict? arr)

- : Boolean

#f

> (array-strict! arr)
> (array-strict? arr)

- : Boolean

#t

> (array-strict arr)

- : (Array String)

(array #["Hello Ada!" "Hallo Edsger!" "Jó napot John!"])

If the array is already strict, as in the last example above, array-strict! and array-strict do nothing.

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.

Having to name an array is a good indicator that it should be strict. In the following example, which computes (+ (expt x x) (expt x x)) for x from 0 to 2499, each element in xrr is computed twice whenever its corresponding element in res is referred to:
(define xrr (array-map expt
                       (index-array #(50 50))
                       (index-array #(50 50))))
(define res (array+ xrr xrr))
Having to name xrr means we should make it strict:
(define xrr (array-strict
             (array-map expt
                        (index-array #(50 50))
                        (index-array #(50 50)))))
(define res (array+ xrr xrr))
Doing so halves the time it takes to compute res’s elements.

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.

When writing library functions that may be called with either (array-strictness #t) or (array-strictness #f), operate on nonstrict arrays and wrap the result with array-default-strict to return what the user is expecting. For example, if make-hellos is a library function, it should be written as
(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.

  top  ← prev  up  next →