Opened 3 months ago

Last modified 3 months ago

#1620 new defect

Some let bindings are not replaced resulting in unnecessary CPS calls

Reported by: sjamaan Owned by:
Priority: major Milestone: 5.2
Component: compiler Version: 5.0.0
Keywords: Cc:
Estimated difficulty: hard

Description (last modified by sjamaan)

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.

Change History (2)

comment:1 Changed 3 months ago by sjamaan

Description: modified (diff)

comment:2 Changed 3 months ago by sjamaan

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.

Note: See TracTickets for help on using tickets.