[plt-scheme] build-list for large lists

I was doing some benchmarking of my random-access list package and found 
that its build-list often outperformed scheme/base's build-list function 
for constructing large lists, which seemed curious.

My data representation for a list is a list of complete binary trees, 
and build-list boils down to build-tree, which is defined by recursion 
on the size of the tree.

I thought perhaps the performance boost was due to using recursion 
rather than iteration and reverse as done in scheme/base build-list, so 
I did some comparisons with a recursive definition of build-list, which 
indeed does better on large lists.

Finally, the tree-based version still outperforms both the recursive 
build-list and the iterative build-list for really large lists.  I'm not 
sure why.

Anyway, I thought these numbers might be of interest.

David

#lang scheme
(require (prefix-in ra: (planet dvanhorn/ralist:1:6)))
(require (prefix-in mz: scheme/base))

(define (my:build-list i f)
   (let recr ([j 0] [i i])
     (cond [(zero? i) empty]
           [else (cons (f j)
                       (recr (add1 j) (sub1 i)))])))

(define id (lambda (i) i))

(define-syntax times
   (syntax-rules ()
     ((times n e)
      (begin (collect-garbage)
             (time (for ([i (in-range n)]) e))))))

(let ((n 500000))
   (times 5 (mz:build-list n id))
   (times 5 (ra:build-list n id))
   (times 5 (my:build-list n id)))

;; cpu time: 5482 real time: 5490 gc time: 5267
;; cpu time: 836 real time: 858 gc time: 76
;; cpu time: 392 real time: 429 gc time: 76

(let ((n 10000000))
   (times 1 (mz:build-list n id))
   (times 1 (ra:build-list n id))
   (times 1 (my:build-list n id)))

;; cpu time: 7241 real time: 7271 gc time: 6367
;; cpu time: 4920 real time: 4959 gc time: 1953
;; cpu time: 5248 real time: 5283 gc time: 3305