[plt-scheme] Iterator performance

At Fri, 4 Jul 2008 15:09:11 -0700, "Mark Engelberg" wrote:
> 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? 

None.

> If not, what wizardry makes it
> so much faster?

I think you're just seeing different levels of instrumentation for
DrScheme's debugging. Since more of the implementation of `v->l' and
`v->l2' is exposed in the source, then there's more for DrScheme to
instrument.

If you turn off debugging in DrScheme (via the "Choose Language"
dialog, then the "Show Details" panel), then the last one runs almost
as fast as the `for/list' version. If you lift the `vector-length'
calculation out of the `v->l2' loop, then it should be essentially the
same as the expansion of `for/list'.

> 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.?

See `define-sequence-syntax'.


Matthew