[plt-scheme] build-list for large lists

Eli and I have had this long-running discussion. As Kent and Bob Hieb  
showed to me two decades ago, plain recursion usually wins in the  
context of an optimizing compiler because the compiler knows more  
about managing stacks and stuff than programmers do.

I for one am happy to see that Eli is now wrong in the context of  
mzscheme :-)

-- Matthias



On Apr 8, 2009, at 10:04 PM, Eli Barzilay wrote:

> 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!
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme