[plt-scheme] build-list for large lists

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Wed Apr 8 20:58:23 EDT 2009

At Wed, 08 Apr 2009 20:05:58 -0400, David Van Horn wrote:
> I thought perhaps the performance boost was due to using recursion 
> rather than iteration and reverse as done in scheme/base build-list, so 
> I did some comparisons with a recursive definition of build-list, which 
> indeed does better on large lists.

Yes. It's because the JIT builds a compact continuation (represented
mostly as an array) that the GC can traverse more quickly than a list.

> Finally, the tree-based version still outperforms both the recursive 
> build-list and the iterative build-list for really large lists.  I'm not 
> sure why.

Here's my theory: Although (deep) recursion is better than building a
list and reversing it, shallow recursion is still better than very deep

> Anyway, I thought these numbers might be of interest.

Yes, thanks!

I've committed your `my:build-list' as `build-list'.

Posted on the users mailing list.