Summary

Some let bindings are not replaced resulting in unnecessary CPS calls

Metadata

Description

We've seen in #1604 that this is a performance killer:

This code is fast when compiled with `-O5 -strict-types -fixnum-arithmetic`:

 (define (fib n)
   (if (or (eq? n 0) (eq? n 1))
       n
       (+ (fib (- n 1)) (fib (- n 2)))))
 
 (let loop ((n 0))
   (when (< n 35)
     (print "n=" n " => " (fib n))
     (loop (+ n 1))))

This code is slow when compiled with the same options, even though the generated intermediate Scheme code is equivalent:

 (define (fib n)
   (if (or (= n 0) (= n 1))
       n
       (+ (fib (- n 1)) (fib (- n 2)))))
 
 (let loop ((n 0))
   (when (< n 35)
     (print "n=" n " => " (fib n))
     (loop (+ n 1))))

The reason is that in the first case, the `eq?` calls get replaced by `(##core#inline "C_eqp" a b)` while in the second case, the `=` calls get replaced by `(let ((x a) (y b)) (##core_inline "C_eqp" x y))` and the `let` is not considered `replacable` even though (I think?) it should be.

That's because `fib`'s arguments are marked by `analyze-expression` in `core.scm` as `captured`.

Fixing this could potentially make a lot of code a lot faster! We definitely should run the benchmarks with and without the fix to find out how dramatic the improvement is.

Changes and comments

[2019-05-29 16:45:54 UTC] sjamaan changed description

[2019-05-29 16:49:46 UTC] sjamaan wrote:

Note: The `let` bindings are actually necessary when the arguments of `=` are impure; you want side-effects or exceptions to happen before calling `=`. The expanded generated code contains a shortcutting `C_and` call introduced by `fold-boolean` and each of the arguments except the first and the last are repeated twice, so if we got rid of the `let` completely, the resulting code would not be semantically equivalent.

However, if they just alias other variables, I think they should always be replacable.

[2019-10-13 16:25:41 UTC] sjamaan changed status from new to closed

[2019-10-13 16:25:41 UTC] sjamaan set resolution to fixed

[2019-10-13 16:25:41 UTC] sjamaan wrote:

Fixed by 27dbbc02d32f91712b83f6b11ffa325da6454df8