Re: Loop optimization

[Andy Wingo]

On Mon 07 Mar 2011 22:01, Michael Ellis <address@hidden> writes:

> (let loop ((i 0) (j 1e7))
>   (set! i (+ i 1))
>   (if (< j i)
>     (begin (display i) (newline))
>     (loop i j)))

Note that if you avoid a set!, this gets faster:

  (let loop ((i 0) (j 1e7))
    (if (<= j i)
        (begin (display i) (newline))
        (loop (1+ i) j)))

On my machine this goes down from 1.5 seconds to 0.91 seconds.  See
"Variables and the VM" in the manual, for more.

You get better if you actually use an int as the boundary condition:

  (let loop ((i 0) (j 10000000))
    (if (<= j i)
        (begin (display i) (newline))
        (loop (1+ i) j)))

0.62 seconds here.

In fact that is the deal:

> (let loop ((i 0))
>   (set! i (+ i 1))
>   (if (< 1e7 i)
>     (begin (display i) (newline))
>     (loop i)))

Here we are loading up a float (which conses) at every iteration.  Oddly
enough this would work better in a procedure, because procedures have
constant tables (again, "Variables and the VM").

So:

 (define (proc)
   (let loop ((i 0))
     (set! i (+ i 1))
     (if (< 1e7 i)
       (begin (display i) (newline))
       (loop i))))
 (proc)
  
1.19 seconds here.

But the real thing is again to avoid the float<->int compare.  By way of
comparison:

  (let loop ((i 0))
    (if (<= 10000000 i)
        (begin (display i) (newline))
        (loop (1+ i))))

0.56 seconds here.

Regards,

Andy
-- 
http://wingolog.org/