[racket-dev] Speeding up sequence->list

No one should rely on eq? of lists..... especially not in code that didn't
exist in the pre-immutable cons days.


On Mon, Feb 11, 2013 at 12:17 PM, Neil Toronto <neil.toronto at gmail.com>wrote:

> The performance of `sequence->list' came up on this thread:
>
>   http://thread.gmane.org/gmane.**comp.lang.racket.user/16384<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 ⊥
> _________________________
>  Racket Developers list:
>  http://lists.racket-lang.org/**dev <http://lists.racket-lang.org/dev>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/dev/archive/attachments/20130211/7da0f41c/attachment.html>