[plt-scheme] build-list for large lists

On Apr  8, Matthew Flatt wrote:
> 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.

I generally found that the iterate+reverse-vs-recursion costs keep
changing -- IIRC, recursion used to be much slower then iteration plus
`reverse!', then around 4.0 they were roughly the same.  It's nice to
see a big difference in favor of recursion now.


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

FWIW, in my experiments the tree-based version was slower than the
others (average of 7 runs each):

times: 100000, length: 100
  mz:build-list cpu time: 491 real time: 490 gc time: 30
  ra:build-list cpu time: 2349 real time: 2350 gc time: 23
  my:build-list cpu time: 408 real time: 408 gc time: 13

times: 5, length: 500000
  mz:build-list cpu time: 411 real time: 411 gc time: 272
  ra:build-list cpu time: 629 real time: 628 gc time: 146
  my:build-list cpu time: 159 real time: 159 gc time: 9

times: 1, length: 10000000
  mz:build-list cpu time: 3765 real time: 3765 gc time: 3221
  ra:build-list cpu time: 4238 real time: 4269 gc time: 2337
  my:build-list cpu time: 3746 real time: 3745 gc time: 2081

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