[plt-scheme] build-list for large lists

Matthew Flatt wrote:
> I've committed your `my:build-list' as `build-list'.

What is the value in having build-list being specified to apply its 
function in order?  If you drop that requirement, then an iterative 
version substantially outperforms all the other options.

I can't think of a case where I've depended on build-list being applied 
in order.

Anyway, here's a comparison with that option included.  It also 
benchmarks building smaller lists.

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 (it:build-list i f)
   (let loop ([i (sub1 i)] [a empty])
     (cond [(< i 0) a]
           [else (loop (sub1 i)
                       (cons (f i) a))])))

(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 5000))
   (times 500 (mz:build-list n id))
   (times 500 (ra:build-list n id))
   (times 500 (my:build-list n id))
   (times 500 (it:build-list n id)))

;; cpu time: 843 real time: 853 gc time: 640
;; cpu time: 764 real time: 794 gc time: 14
;; cpu time: 184 real time: 209 gc time: 11
;; cpu time: 133 real time: 136 gc time: 11

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

;; cpu time: 873 real time: 880 gc time: 674
;; cpu time: 806 real time: 836 gc time: 50
;; cpu time: 297 real time: 323 gc time: 28
;; cpu time: 147 real time: 155 gc time: 22

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

;; cpu time: 6421 real time: 6484 gc time: 5604
;; cpu time: 7360 real time: 7452 gc time: 4420
;; cpu time: 5426 real time: 5475 gc time: 3640
;; cpu time: 3765 real time: 3818 gc time: 3233