[racket-dev] Speeding up sequence->list

The performance of `sequence->list' came up on this thread:

   http://thread.gmane.org/gmane.comp.lang.racket.user/16384

`sequence->list' uses the sequence API to make a copy of its input. This 
can dominate the running time of functions that look like this:

   (define (f xs)
     (let ([xs  (sequence->list xs)])
       ... simple O(n) computation using xs ...))

Also, it seems wasteful to make a copy if `xs' is already a list.

I'd like to change the definition of `sequence->list' from this:

   (define (sequence->list s)
     (for/list ([v s]) v))

to this, to handle the two most common sequences specially:

   (define (my-sequence->list s)
     (cond [(list? s)  s]
           [(vector? s)  (vector->list s)]
           [else  (for/list ([v s]) v)]))

For vectors, I measure a 3x speedup. For lists, it's of course O(1).

It's a semantic change, but I can't imagine anyone relying on this fact:

   (not (eq? xs (sequence->list xs)))

If someone does, [(list? s)  (map values s)] would preserve that fact, 
and is 3x faster in my measurements.

Thoughts?

Neil ⊥