[plt-scheme] List loop timing

There's this common Scheme (and Lisp) idiom for looping over a list
and collecting the results:

  (let loop ([l l] [r '()])
    (if (null? l)
      (reverse! r)
      (loop (cdr l) (cons ... r))))

When switching to v4, the natural thing to do is to simply change the
`reverse!' to `reverse', and hope that somehow mzscheme manages to
make it as fast as (or close enough to) the above.  But there's also
the `foldr' option:

  (let loop ([l l] [r '()])
    (if (null? l)
      '()
      (cons ... (loop (cdr l)))))

and I knew that it is "obviously" worse, since it's not tail-calling
itself.

To check that, I wrote some toy benchmark -- a function that simply
copies a given list.  I used four versions of the function:

  - f1: tail-loop with a final `reverse'
  - f2: tail-loop with my own definition of `reverse' (might be faster
        since it doesn't check that its input is a list)
  - f3: non-tail-loop (and no `reverse', of course)
  - f4: tail-loop with a final `reverse!' (available in pre-v4 only)

The results were surprising.  My conclusions are:

* As expected, my `reverse' definition was doing a little better than
  the built in, especially noticeable on long lists

* in 371, `reverse!' always outperform the `reverse' versions

* surprise #1: the non-tail-recursive version is always faster than
  the `reverse' versions, and sometimes even faster than the
  `reverse!' in 371.  The difference is very noticeable on short lists
  (10 and 1000 items below), and a little less noticeable on 1m-long
  lists

* surprise #2: on short lists (10 and 1000), v4 is much faster than
  371.

----

The numbers:

  length=10; iterations=10000000
  371  [f1] cpu time: 4537 real time: 4543 gc time: 1506
       [f2] cpu time: 4738 real time: 4751 gc time: 1547
       [f3] cpu time: 2582 real time: 2585 gc time:  752
       [f4] cpu time: 2729 real time: 2736 gc time:  761
  3.99 [f1] cpu time: 2458 real time: 2464 gc time:  501
       [f2] cpu time: 2389 real time: 2393 gc time:  460
       [f3] cpu time: 1376 real time: 1376 gc time:  238

  length=1000; iterations=100000
  371  [f1] cpu time: 4535 real time: 4540 gc time: 1581
       [f2] cpu time: 4525 real time: 4532 gc time: 1536
       [f3] cpu time: 2717 real time: 2720 gc time:  771
       [f4] cpu time: 2631 real time: 2633 gc time:  805
  3.99 [f1] cpu time: 2367 real time: 2369 gc time:  496
       [f2] cpu time: 2209 real time: 2216 gc time:  448
       [f3] cpu time: 1412 real time: 1414 gc time:  222

  length=1000000; iterations=50
  371  [f1] cpu time: 11678 real time: 11696 gc time: 9301
       [f2] cpu time: 10336 real time: 10381 gc time: 7859
       [f3] cpu time:  6935 real time:  6949 gc time: 3976
       [f4] cpu time:  7762 real time:  7775 gc time: 5542
  3.99 [f1] cpu time: 10236 real time: 10250 gc time: 7892
       [f2] cpu time:  8684 real time:  8697 gc time: 6335
       [f3] cpu time:  7222 real time:  7232 gc time: 4317

The functions:

  
  (define (f1 l)
    (let loop ([l l] [r '()])
      (if (null? l)
        (reverse r)
        (loop (cdr l) (cons (car l) r)))))
  
  (define (rev l)
    (let loop ([l l] [r '()])
      (if (null? l)
        r
        (loop (cdr l) (cons (car l) r)))))
  (define (f2 l)
    (let loop ([l l] [r '()])
      (if (null? l)
        (rev r)
        (loop (cdr l) (cons (car l) r)))))
  
  (define (f3 l)
    (let loop ([l l])
      (if (null? l)
        '()
        (cons (car l) (loop (cdr l))))))
  
  (define (f4 l)
    (let loop ([l l] [r '()])
      (if (null? l)
        (reverse! r)
        (loop (cdr l) (cons (car l) r)))))

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