[plt-scheme] List loop timing

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Thu Feb 14 12:15:28 EST 2008

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.


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

* 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

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

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

-- Matthias

Posted on the users mailing list.