[plt-scheme] Iterator performance

From: Mark Engelberg (mark.engelberg at gmail.com)
Date: Fri Jul 4 18:09:11 EDT 2008

I've noticed that iterators are fast.  So fast, in fact, that I can't
seem to approach their speed with any Scheme-written loopy version.
I've tested both vectors and lists, and gotten similar results.

Here is some sample benchmarking on vector iteration:
#lang scheme
(define v (build-vector 500000 (λ (i) i)))

(collect-garbage)
(define list1 (time (for/list ([item (in-vector v)]) item)))
(set! list1 #f)
(collect-garbage)
(define list2 (time (for/list ([index (in-range (vector-length v))])
(vector-ref v index))))
(set! list2 #f)
(collect-garbage)
(define (v->l v i)
  (if (= i (vector-length v)) empty
      (cons (vector-ref v i) (v->l v (add1 i)))))
(define list3 (time (v->l v 0)))
(set! list3 #f)
(define (v->l2 v i l)
  (if (= i (vector-length v)) (reverse l)
      (v->l2 v (add1 i) (cons (vector-ref v i) l))))
(define list4 (time (v->l2 v 0 empty)))

On my computer:
cpu time: 16 real time: 16 gc time: 0
cpu time: 78 real time: 78 gc time: 0
cpu time: 500 real time: 500 gc time: 156
cpu time: 250 real time: 250 gc time: 0

Is all iteration done on the C side?  If not, what wizardry makes it
so much faster?

It's enough of a difference to make me want to do iteration all the
time.  Forget this recursion stuff :) ...

Speaking of which, if I make a data structure into a sequence using
prop:sequence, it works great in for loops, but what do I need to do
to make it behave like the superfast iterators, such as in-list,
in-vector, etc.?

--Mark

Posted on the users mailing list.