[plt-scheme] List loop timing

On Feb 14, Matthias Felleisen wrote:
> 
> On Feb 13, 2008, at 10:29 PM, Eli Barzilay wrote:
> 
> > I knew that it is "obviously" worse, since it's not tail-calling
> > itself.
> 
> > * surprise #1: the non-tail-recursive version is always faster
> >   than the `reverse' versions, and sometimes even faster than the
> >   `reverse!' in 371.  The difference is very noticeable on short
> >   lists (10 and 1000 items below), and a little less noticeable on
> >   1m-long lists
> 
> ELI! We have been through this exercise once before. You and I
> sat next to each other when I showed you that your TR assumption
> is plain wrong and doesn't even apply across Schemes.

Either you're confusing me with someone else, or I'm extremely
senile...  I remember that we talked about it and had a few quick
tries, nothing serious enough to learn lessons from, and the main
thing that I remember taking with me is that chez is good enough to
not make a difference which loop you're using.


> Upshot:
> 
> * the natural recursion solution is usually as good as
> some force-shaped TR version of the same function.

The behavior is highly defendant on the implementation (and according
to Matthew it might also be affected by my tests running on x86_64).
As an extreme example, Emacs won't let you copy lists of more than 100
items that way, and if you raise the limit it'll segfault away.
Obviously, Emacs is not really a player, so I tried the three random
schemes I have on my machine (disclaimer -- just running them, no
attempt at using modules, compiling, or whatever-ing):

* guile: much slower than mzscheme, user-defined-reverse version twice
  slower than built-in reverse, reverse! is a bit slower than reverse,
  foldr-style loop crashes with a stack overflow.

* Gauche: a little faster than mzscheme (7.5s for the long list
  example), user-defined-reverse is slower (9.2), reverse! is faster
  (5.3), and foldr-looping is much slower (14.9).

* Bigloo: a little slower than mzscheme, reverse! is roughly the same
  as reverse, user-defined-reverse is slower, foldr-style loop
  segfaults.

So I only see mzscheme and chez in the "doesn't matter which way you
loop" department.


> * This is especially true for compiled systems with a really
> good compiler. I showed Eli at the time that Chez was doing
> really well on the natural version for lists of say 100 - 1000
> elements.

And that still doesn't convince me to trust it with really-long
lists.  Now I am.


> * It is a COMMON misunderstanding that TR versions of a function
> do something good for your timing.
> 
>   ************************************
>   TR is a space-saving device. PERIOD.
>   ************************************
> 
> It does nothing for time.

Of course, but -- time is money^W^W^W space is time.  (And BTW, the
recent safe-for-space updates that Matthew did should help in this,
since (IIRC) the way in which mzscheme was not sfs was holding on to
values that are no longer needed.)


> * All side-effects have a seriously bad effect on conventional
> GCs and we do have a conventional GC.

(Actually, `reverse!' (in 371) was still faster than all of the
constructive versions.  I keep waiting to see the side-effects of
side-effects, but this one is not it.  Yet.  (Maybe it is in v4.))

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