[plt-scheme] scribblings on PLT Scheme 4.0

From: Eli Barzilay (eli at barzilay.org)
Date: Mon May 28 07:07:01 EDT 2007

On May 28, Matthew Flatt wrote:
> I agree that you won't have problems, as long as you know that `f'
> doesn't capture any continuations to be applied after the `sort!' or
> `append!'.
> How much time does `append!' save you in an actual application? My
> guess is that the savings will be minor, but I'm interested in
> measurements you might be able to take.

My common !-operation is `reverse!' -- I use it very frequently to
reverse a list result.  I also use `append!', but that's less
frequent.  There are also occasions where I'd prefer some `map!' if I
had one in the code.  [I also went through a heavy !-phase (actually
that was a time when I used CL a lot, so it was an "n-phase") and gave
it up after some horrible debugging nightmares -- so now I use these
only when I know that it's safe, and reversing a locally-accumulated
list is quite common.]

Running the code below shows that there is still a significant
advantage for using `reverse!' -- I get these times:

    running list-add1-1: cpu time: 43814 real time: 45088 gc time: 35322
    running list-add1-2: cpu time: 22422 real time: 22971 gc time: 16530
    running list-add1-1: cpu time: 17737 real time: 18099 gc time: 13325
    running list-add1-2: cpu time: 9832 real time: 10058 gc time: 6488

Another fact that is relevant here is that the (relatively new) `sort'
implementation is based on pointer mutation -- it just does that on a
copy of the input list if you use `sort'.  This will be a
problem in a mostly-immutable world (unless there is a cheap way to do
things like now, and then "seal" the result in-place).

(module m mzscheme
  (define (list-add1-1 l)
    (let loop ([l l] [r '()])
      (if (null? l)
        (reverse r)
        (loop (cdr l)
              (cons (add1 (car l)) r)))))
  (define (list-add1-2 l)
    (let loop ([l l] [r '()])
      (if (null? l)
        (reverse! r)
        (loop (cdr l)
              (cons (add1 (car l)) r)))))
  (define rand-list
    (let loop ([n 10000] [r '()])
      (if (zero? n)
        (loop (sub1 n) (cons (random 1000000) r)))))
  (define (n-runs n proc)
    (unless (zero? n)
      (proc rand-list)
      (n-runs (sub1 n) proc)))
  (define (try proc)
    (n-runs 100 proc)
    (printf "running ~a: " (object-name proc))
    (time (n-runs 10000 proc)))
  (try list-add1-1)
  (try list-add1-2))

          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!

Posted on the users mailing list.