[plt-scheme] Making a fast list like sequence

From: Eli Barzilay (eli at barzilay.org)
Date: Tue Apr 7 19:23:52 EDT 2009

On Apr  7, David Van Horn wrote:
> 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

I get comparable results for the car/cdr/pair? version.  Actually, the
surprising thing is that I get a significant improvement if I use
`void' for the redundant predicates:

  #lang scheme
  (define ls (build-list 100000 (lambda (i) i)))
  (define (ls->seq ls)
      (lambda ()
  (define seq (ls->seq ls))
  (time (for* ([n (in-range 100)] [i seq]) (void i)))
  ;; cpu time: 493 real time: 494 gc time: 0
  (time (for* ([n (in-range 100)] [i ls])  (void i)))
  ;; cpu time: 716 real time: 716 gc time: 0

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

Posted on the users mailing list.