[plt-scheme] tree-recursion vs explicit stack tail-recursive

On Fri, Apr 23, 2010 at 10:04 AM, Richard Cleis <rcleis at mac.com> wrote:
> On Apr 23, 2010, at 6:18 AM, Joe Marshall <jmarshall at alum.mit.edu> wrote:
> ...
>>
>> In real life I *did* find a program that was spending an inordinate
>> amount of time counting the elements in a list --- a good 20%!
>> The performance dramatically improved
>
> ...
>
> It improved more than 20% ?

It didn't improve *more* than the wasted time, if that's what you are asking.
It improved close to 20%, though.

It was a complex program and everyone thought that naturally
it will take a good chunk of time to compute things, so no one suspected
anything was wrong.  Then I ran the profiler and found that LENGTH was
the number 1 function.  One of the core routines had a boner in it like this:
(do ((i 0 (+ i 1))
      ....
      ((>= i (length l)) ....))

Which isn't a problem for small lists, but a huge problem for medium-sized
or long lists.

The point being that avoiding computation altogether outperforms any
other improvement.

-- 
~jrm