[r6rs-discuss] Multiple returns from higher-order procedures

From: William D Clinger <will>
Date: Sun, 24 Jun 2007 19:27:42 -0400

As a public service to those who may be worried about the
efficiency of correct versus buggy vector-map, I wrote a
little benchmark that evaluates

    (vector-map truth v1000)
 or (vector-map truth2 v1000 v1000)

one million times, where truth and truth2 ignore their
arguments and return #t, and v1000 is a vector of length
1000. (For those who appreciate appeals to authority,
that's a billion invocations of truth in each benchmark.)
Elapsed timings in seconds on a 32-bit Mac mini, with
peak space in bytes (including the result but not the
inputs):

                                     truth truth2 peak space

vector-map (consing) 38.8 43.2 12000
rec-vector-map (recursive) 40.6 46.0 36000
rec4-vector-map (unrolled 4 times) 28.4 29.3 18000 (*)
rec8-vector-map (unrolled 8 times) 24.5 28.8 11000
buggy-vector-map 25.5 30.1 4000

(*) The peak space for the 4x unrolling was higher than
expected, because the compiler allocated stack slots to
preserve computed vector indexes across the calls. For
the 8x loop unrolling, I used a trick to defeat CSE on
those indexes.

This benchmark makes the correct versions look as bad
as they can look, because most real uses of vector-map
will perform more computation per vector element.

Correctness definitely has its price, mainly in space.
In terms of time, the cost is less than what you'd pay
if you didn't unroll the obvious recursion or weren't
in the habit of examining the machine code produced by
your compiler.

Will
Received on Sun Jun 24 2007 - 19:27:42 UTC