[fricas-devel] [PATCH] get inline optimization for some Integer functions

[oldk1331]

I said before that the following test takes too much time to run:
testIntegrate("sqrt(tan(x)^2 + 2*tan(x) + 2)", "x", "alg")

I did some profiling, and found that 40% time is spent in
symmetricRemainder:

Callers
Total. Function
Count % Count % Callees
------------------------------------------------------------------------
3 0.0 |MODRING;reduce;RMod$;6| [76]
13 0.1 |INS-;symmetricRemainder;3S;27| [1]
3431 39.3 |IDPO;map;M2$;6| [5]
1104 12.7 3451 39.6 |INS-;symmetricRemainder;3S;27| [1]
13 0.1 |INS-;symmetricRemainder;3S;27| [1]
160 1.8 |INT;=;2$B;30| [4]
149 1.7 |ABELMON-;*;Pi2S;2| [14]
67 0.8 SB-VM::ALLOC-TRAMP [15]
228 2.6 |ORDSET-;>;2SB;4| [7]
173 2.0 |ORDSET-;<=;2SB;6| [20]
73 0.8 |INT;+;3$;34| [9]
160 1.8 |INT;*;3$;37| [6]
180 2.1 |ABELGRP-;*;Nni2S;3| [11]
366 4.2 |INT;rem;3$;44| [16]
369 4.2 IDENTITY [2]
407 4.7 |INT;<;2$B;31| [3]


We can see that "=$INT, +$INT, *$INT, <$INT" are not inlined, and
"*$ABELMON, *$ABELGRP, >, <=" are not defined in INT, thus impossible
to get inlined.

So I want to add inline optimization for these functions.
(I also add inline support for "positive?, even?, ^")

=========== test case
)time on
)lisp (require :sb-sprof)

f := sqrt(tan(x)^2 + 2*tan(x) + 2)
g := integrate(f, x)

f2 := D(g, x)

)lisp (sb-sprof:start-profiling)
normalize(f-f2)
)lisp (sb-sprof:stop-profiling)

)lisp (sb-sprof:report)
===========

Benchmark result:
D(g, x) normalize(f-f2)
before patch 40.3 s 87.4 s
after patch 28.4 s 57.3 s

So it's 30% faster, saves 40 seconds in testing.

diff --git a/src/algebra/integer.spad b/src/algebra/integer.spad
index 0e619c2f..35f673b2 100644
--- a/src/algebra/integer.spad
+++ b/src/algebra/integer.spad
@@ -59,7 +59,6 @@
ZP ==> SparseUnivariatePolynomial %
ZZP ==> SparseUnivariatePolynomial Integer
x, y : %
- n : NonNegativeInteger

writeOMInt(dev : OpenMathDevice, x : %) : Void ==
if x < 0 then
@@ -87,6 +86,7 @@
dec x == x - 1
hashUpdate!(hs, s) == update!(hs, SXHASH(s)$Lisp)$HashState
negative? x == MINUSP(x)$Lisp
+ positive? x == PLUSP(x)$Lisp
coerce(x) : OutputForm == outputForm(x pretend Integer)
coerce(m : Integer) : % == m pretend %
convert(x : %) : Integer == x pretend Integer
@@ -125,15 +125,21 @@
random(x) == RANDOM(x)$Lisp
x = y == EQL(x, y)$Lisp
x < y == (x<y)$Lisp
+ x > y == (x>y)$Lisp
-- critical for coercions to NonNegativeInteger
x >= y == (x >= y)$Lisp
+ x <= y == (x <= y)$Lisp
- x == (-x)$Lisp
x + y == (x+y)$Lisp
x - y == (x-y)$Lisp
x * y == (x*y)$Lisp
(m : Integer) * (y : %) == (m*y)$Lisp -- for subsumption problem
- x ^ n == EXPT(x, n)$Lisp
+ (m : PositiveInteger) * (y : %) == (m*y)$Lisp
+ (m : NonNegativeInteger) * (y : %) == (m*y)$Lisp
+ (x : %) ^ (n : NonNegativeInteger) == EXPT(x, n)$Lisp
+ (x : %) ^ (n : PositiveInteger) == EXPT(x, n)$Lisp
odd? x == ODDP(x)$Lisp
+ even? x == EVENP(x)$Lisp
max(x, y) == MAX(x, y)$Lisp
min(x, y) == MIN(x, y)$Lisp
divide(x, y) == DIVIDE2(x, y)$Lisp
@@ -196,6 +200,17 @@
zero?(n := shift(n, -1)) => return y
z := mulmod(z, z, p)

+ -- copied from IntegerNumberSystem to get inline optimization
+ symmetricRemainder(x, n) ==
+ r := x rem n
+ r = 0 => 0
+ if n < 0 then n := -n
+ r > 0 =>
+ 2 * r > n => r - n
+ r
+ 2 * r + n <= 0 => r + n
+ r
+
)abbrev domain NNI NonNegativeInteger
++ Author:
++ Basic Operations:

[Waldek Hebisch]

Post by oldk1331
testIntegrate("sqrt(tan(x)^2 + 2*tan(x) + 2)", "x", "alg")
I did some profiling, and found that 40% time is spent in
Callers
Total. Function
Count % Count % Callees
------------------------------------------------------------------------
3 0.0 |MODRING;reduce;RMod$;6| [76]
13 0.1 |INS-;symmetricRemainder;3S;27| [1]
3431 39.3 |IDPO;map;M2$;6| [5]
1104 12.7 3451 39.6 |INS-;symmetricRemainder;3S;27| [1]
13 0.1 |INS-;symmetricRemainder;3S;27| [1]
160 1.8 |INT;=;2$B;30| [4]
149 1.7 |ABELMON-;*;Pi2S;2| [14]
67 0.8 SB-VM::ALLOC-TRAMP [15]
228 2.6 |ORDSET-;>;2SB;4| [7]
173 2.0 |ORDSET-;<=;2SB;6| [20]
73 0.8 |INT;+;3$;34| [9]
160 1.8 |INT;*;3$;37| [6]
180 2.1 |ABELGRP-;*;Nni2S;3| [11]
366 4.2 |INT;rem;3$;44| [16]
369 4.2 IDENTITY [2]
407 4.7 |INT;<;2$B;31| [3]
We can see that "=$INT, +$INT, *$INT, <$INT" are not inlined, and
"*$ABELMON, *$ABELGRP, >, <=" are not defined in INT, thus impossible
to get inlined.
So I want to add inline optimization for these functions.
(I also add inline support for "positive?, even?, ^")
=========== test case
)time on
)lisp (require :sb-sprof)
f := sqrt(tan(x)^2 + 2*tan(x) + 2)
g := integrate(f, x)
f2 := D(g, x)
)lisp (sb-sprof:start-profiling)
normalize(f-f2)
)lisp (sb-sprof:stop-profiling)
)lisp (sb-sprof:report)
===========
D(g, x) normalize(f-f2)
before patch 40.3 s 87.4 s
after patch 28.4 s 57.3 s
So it's 30% faster, saves 40 seconds in testing.

OK, good. But I see some funny formatting below, which may be
due tabs. Please make sure there are no tabs when you commit.

Post by oldk1331
diff --git a/src/algebra/integer.spad b/src/algebra/integer.spad
index 0e619c2f..35f673b2 100644
--- a/src/algebra/integer.spad
+++ b/src/algebra/integer.spad
@@ -59,7 +59,6 @@
ZP ==> SparseUnivariatePolynomial %
ZZP ==> SparseUnivariatePolynomial Integer
x, y : %
- n : NonNegativeInteger

^^^^^^
Would be indentation error if real.