chicken-hackers
[Top][All Lists]
Advanced

[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.



reply via email to

[Prev in Thread] Current Thread [Next in Thread]