More power to constant folding :)

jpellegrini commented 1 year ago

Hi @egallesio ! Still kind of erratic (got no time for long hacking sessions), but I managed to do this...

This patch does constant folding to all math expressions, even using transcendentals etc.
Creates a compiler option to turn this on and off (compiler:open-math -- not a good name... Is there a better one?)
It also creates a more compact way to create the inline table
And, well, it's not large at all :)

Do you think it's interesting?

(exp (sqrt 5)) will end up generating:

000:  CONSTANT             0

Constants:
0: 9.35646901660115

Another example, with a nested expression:

stklos> (disassemble-expr '(cos (+ 3 (tan 2))) #t)
000:  CONSTANT             0

Constants:
0: 0.685897402427631

I did this because it's not unusual to write (expt 2 10) or other powers of two... But then, why only optimize powers of two? We can do that to all math functions! :)

jpellegrini commented 1 year ago

(This will conflict with #543, since it reformats the inline table. Easy to fix.)

jpellegrini commented 1 year ago

Maybe in the future we can also do more general code transformations? Like this:

    (when (and (compiler:some-compiler-option)
               (eq? fct 'log)
               (pair? (car actuals))       ; (log (...) ...)
               (eq? (caar actuals) 'expt)) ; (log (expt ...) ...)

      ;; (log (expt b e) z) => (/ e (log b z))
      (let ((e (caddar actuals))       ; (log (expt b e) ...) => e
            (b (cadar actuals)))       ; (log (expt b e) ...) => b
        (case len
          ((1) (compile `(/ ,e (log ,b)) env epair #f))
          ((2) (let ((z (cadr actuals)))        ; (log (expt b e) z) => z
                 (compile `(/ ,e (log ,b ,z)) env epair #f)))))

(because computing $$\frac{e}{log _z b}$$ is faster than $$log_z(b^e)$$ -- one log and one division is faster than one log and one expt -- at least for non-bignums)

jpellegrini commented 1 year ago

~In a separate PR, later~ (already included in this one!) I have something that will do constant folding of commutative math operations (+ and * in STklos), so that (+ 2 b a 3 c 5) turns into (+ 10 b a c).

jpellegrini commented 1 year ago

This PR can get much better. I'm working on it.

jpellegrini commented 1 year ago

I think it makes sense now.

There are some cases where this won't do the complete constant folding I was hoping to get done, but it already does a lot:

stklos> (disassemble-expr '(+ (sin 2) (log (expt 2 3) 4)) #T)

000:  CONSTANT             0
002:

Constants:
0: 2.40929742682568

stklos> (compiler:inline-common-functions #f)               ;; turn it off so we can see how much code we saved
stklos> (disassemble-expr '(+ (sin 2) (log (expt 2 3) 4)) #T)

000:  PREPARE-CALL        
001:  INT-PUSH             2
003:  GREF-INVOKE          0 1
006:  PUSH-PREPARE-CALL   
007:  PREPARE-CALL        
008:  INT-PUSH             2
010:  INT-PUSH             3
012:  GREF-INVOKE          1 2
015:  PUSH                
016:  INT-PUSH             4
018:  GREF-INVOKE          2 2
021:  IN-ADD2             
022:

Constants:
0: sin
1: expt
2: log
stklos>

Should compiler:inline-common-functions be used only to inlining, and some other parameter for constant folding? Currently this PR uses one single parameter for both.

jpellegrini commented 1 year ago

One thing that this PR does is to change uses of memq into assq. This is because it simplifies the code, and both are primitives, so there doesn't seem to be too much of a difference in speed (differently from assoc, which is not primitive...)

egallesio commented 1 year ago

I have not yet looked at the details, but this seems really impressive!

jpellegrini commented 1 year ago

It's not complex at all... Just implemented some rules (the two new procedures in the compiler): maybe-fold-constant and fold-commutative-args. I'll include the code comments for them here, reformatted for clarity:

maybe-fold-constant takes the current environment, a list of arguments and tries to math-fold them into constants.

Example:

(maybe-fold-constant '( 2.0 (log (sin 2)) (f 5) )) => ( 2.0  -0.0950830360951606  (f 5) )

The number 2.0 remains unchanged;
The expression (log (sin 2)) is evaluated;
The expression (f 5) remains unchanged.

(maybe-fold-constant #f '(expt 2 (expt 2 3))) => 256
(maybe-fold-constant #f '(expt x (expt 2 3))) => (expt x 8)
(maybe-fold-constant #f '(expt 2 (expt 2 x))) => (expt 2 (expt 2 x))

fold-commutative-args will do constant folding in the arguments as much as possible, and return a new argument list. This of course should be used only for commutative operations.

(fold-commutative-args + '(a 2 3 b -1)) => (4 a b)
(fold-commutative-args * '(a 2 3 b -1)) => (-6 a b)

egallesio commented 6 months ago

Hi @jpellegrini,

I have finally managed to merge this PR. I have also simplified the inline tables, now that the SCHEME module is immutable.
Sorry for the long delay. I hope to be more productive soon. Anyway, thanks a lot for this PR.

jpellegrini commented 6 months ago

Great!!!

And... This, along with your recent enhancements to the equivalence predicates, seems to have boosted STklos' speed considerably. The test suite last week took ~8.2 seconds to run, and not it runs in ~7.1 seconds! :smile:

egallesio commented 6 months ago

And... This, along with your recent enhancements to the equivalence predicates, seems to have boosted STklos' speed considerably. The test suite last week took ~8.2 seconds to run, and not it runs in ~7.1 seconds! 😄

Oh, I had great expectations about that but didn't see such improvements (on an old i5). Happy, if it works for you

egallesio / STklos

More power to constant folding :) #550