[plt-scheme] Making a fast list like sequence

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

On Apr  7, Matthew Flatt wrote:
> At Tue, 7 Apr 2009 18:55:40 -0400, Carl Eastlund wrote:
> > 
> > I can certainly see why pair? will be faster than (compose not
> > empty?), but why would car/cdr/pair?/null? be significantly faster
> > than first/rest/cons?/empty? ?  Is there extra contract wrapping
> > or something?
> The `first' and `rest' functions work only on lists, so there's an
> extra test. The test is constant-time due to immutable pairs, but
> it's still extra compared to `car' and `cdr'.

You can also see the effect of amortizing the `list?'-ness of a list.
When I try out David's example I get the car/cdr version about 3.5
faster than the first/rest one, but when I run it 20 times, it's only
2.3 times faster.

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

Posted on the users mailing list.