[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Chicken-hackers] [PATCH] Mostly fix #1604
From: |
megane |
Subject: |
Re: [Chicken-hackers] [PATCH] Mostly fix #1604 |
Date: |
Sat, 18 May 2019 20:46:40 +0300 |
User-agent: |
mu4e 1.0; emacs 25.1.1 |
Peter Bex <address@hidden> writes:
> Hi all,
>
> Attached is a patch to restore rewrites for the common arithmetic
> operators when in fixnum arithmetic mode.
>
Interesing stuff!
[snip]
>
> Finally, I ran into this head scratcher: I tried to replace = with eq? in
> the code and it sped up the code by a *lot*. However, in fixnum
> arithmetic mode, = gets rewritten to C_eqp. The difference in the C
> output is that the code that uses eq? directly gets this completely
> inlined in the same C function as the following subtractions. The code
> that uses = will get the comparisons in a C function and then call a CPS
> function which does the subtractions. Any ideas why this is? It makes
> a massive difference, so I think it's worthwhile to at least understand
> what's going on here.
>
Here's what I figured out fwiw:
This is the program from #1604:
(define (fib n)
(if (or (= n 0) (= n 1))
n
(+ (fib (- n 1)) (fib (- n 2)))))
(time (let loop ((n 0))
(when (< n 35)
(fib n)
(loop (+ n 1)))))
Relevant output from compiling this with your your patch:
$ csc -f -debug 5 -O5 fib-orig.scm
...
(if r145 (k147 r145) (scheme#= k147 n10 1))
...
(scheme#= k144 n10 0)
...
[optimized-iteration]
...
(if r145
(k147 r145)
(let ((g232 n10))
(let ((g233 1))
(k147 (##core#inline "C_eqp" g232 g233)))))
...
(let ((g234 n10))
(let ((g235 0))
(k144 (##core#inline "C_eqp" g234 g235))))
...
This transformation comes from this rewrite rule:
(rewrite 'scheme#= 9 "C_eqp" "C_i_equalp" #t #t)
I don't know why the temporary variables are needed here. They seem to
be the source of the sub-optimal optimization.
Compare this with the output from the fast version where '='s are
replaced with 'eq?':
$ csc -f -debug 5 -O5 fib-eq.scm
...
(if r145 (k147 r145) (scheme#eq? k147 n10 1))
...
(scheme#eq? k144 n10 0)
...
[optimized-iteration]
...
(k147 (##core#cond r145 r145 (##core#inline "C_eqp" n10 1)))
...
(k144 (##core#inline "C_eqp" n10 0))
...
This transformation probably comes from this rewrite rule:
(rewrite 'scheme#eq? 1 2 "C_eqp")
This is the step where the optimization diverges for these two versions.
The optimizer never gets rid of the temporary variables in the '='
version.