[plt-scheme] Making a fast list like sequence

Matthew Flatt wrote:
> At Tue, 07 Apr 2009 18:32:33 -0400, David Van Horn wrote:
>> I see dramatic differences in running times between the built-in list 
>> sequence and a naive implementation of list sequencing.  What can I do 
>> to make this naive implementation run faster?
> 
> If you use use `car', `cdr', and `pair? instead of `first', `rest', and
> `(compose not empty?)', you should get the same performance as for
> lists.

This didn't improve the running time very much.  It's still not nearly 
as fast as just a direct list value.

Here are the timings for a list sequence built with car/cdr/pair?, a 
list-like structure sequence, a direct list, and an list in in-list:

cpu time: 2036 real time: 2327 gc time: 0
cpu time: 2179 real time: 2387 gc time: 0
cpu time: 686 real time: 720 gc time: 0
cpu time: 690 real time: 694 gc time: 0

David


#lang scheme
(define ls (build-list 100000 (lambda (i) i)))

(define-struct kons (first rest))
(define (ks->seq ks)
   (make-do-sequence
    (lambda ()
      (values
       kons-first
       kons-rest
       ks
       kons?
       (lambda (p) true)
       (lambda (p v) true)))))

(define ks (foldr make-kons empty ls))

(define (ls->seq ls)
   (make-do-sequence
    (lambda ()
      (values
       car
       cdr
       ls
       pair?
       (lambda (p) true)
       (lambda (p v) true)))))

(define lseq (ls->seq ls))
(define kseq (ks->seq ks))

(collect-garbage)
(time (for ([i lseq]) i))

(collect-garbage)
(time (for ([i kseq]) i))

(collect-garbage)
(time (for ([i ls]) i))

(collect-garbage)
(time (for ([i (in-list ls)]) i))