[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Axiom-developer] A terrible bug: romberg+simplify/expand: slowdown
From: |
William Sit |
Subject: |
Re: [Axiom-developer] A terrible bug: romberg+simplify/expand: slowdownof 125/300 times |
Date: |
Mon, 17 Jan 2005 18:30:49 -0500 |
Vladimir Bondarenko wrote:
> -----------------------
> -- even worse
> -----------------------
>
> -> romberg(z+->simplify(%i^2), 0, 1, 0.1, 0.1, 10, 12)
>
> [value= - 1.0,error= 0.0,totalpts= 2049,success= true]
> Time: 3.07 (IN) + 2.25 (EV) + 0.18 (OT) + 0.48 (GC) = 5.98 sec
>
> .........................................................................
>
> A bloodcurdling guesswork, Does AXIOM each time call simplify/expand ?!
>
> Or... or what causes this user's nightmare?
I tried the above,
[snipped]
Function Selection for ^
Arguments: (COMPLEX INT,PI)
[1] signature: (COMPLEX INT,PI) -> COMPLEX INT
implemented: slot $$(PositiveInteger) from COMPLEX INT
[2] signature: (COMPLEX INT,PI) -> COMPLEX INT
implemented: slot $$(PositiveInteger) from COMPLEX INT
----- This is the cause of the problem: Complex arithmetic
Function Selection for simplify
Arguments: COMPLEX INT
Target type: FLOAT
[1] signature: EXPR COMPLEX INT -> EXPR COMPLEX INT
implemented: slot (Expression (Complex (Integer)))(Expression (Complex (In
eger))) from TRMANIP(COMPLEX INT,EXPR COMPLEX INT)
----- The only simplify is from EXPR Complex Integer
Function Selection for map by coercion facility (map)
Arguments: ((COMPLEX INT -> INT),EXPR COMPLEX INT)
Target type: EXPR INT
[1] signature: ((COMPLEX INT -> INT),EXPR COMPLEX INT) -> EXPR INT
implemented: slot (Expression (Integer))(Mapping (Integer) (Complex (Integ
r)))(Expression (Complex (Integer))) from EXPR2(COMPLEX INT,INT)
----- which requires the answer to stay in EXPR Complex Integer after
----- "simplification", which then require ti to be converted
and found that the interpreter printed out 2049 (or thereabout)
Function Selection for map by coercion facility (map)
Arguments: ((COMPLEX INT -> INT),EXPR COMPLEX INT)
Target type: EXPR INT
[1] signature: ((COMPLEX INT -> INT),EXPR COMPLEX INT) -> EXPR INT
implemented: slot (Expression (Integer))(Mapping (Integer) (Complex
(Integer)))(Expression (Complex (Integer))) from EXPR2(COMPLEX INT,INT)
which means that it is applying the map function to evaluate the
z+->simplify(%i^2) function 2049 times. Of course, evaluating is not the
problem, the problem is how the function is evaluated. In Axiom, the appearance
of %i means it has to convert the value to Float because romberg requires the
first argument to be a function: Float -> Float.
To understand what is happening and indeed it is troubling to find out, try the
following:
(3) -> g:Float->Float
Type: Void
(4) -> g(z)==simplify(%i^2)::Float
Type: Void
(5) -> g(5)
Compiling function g with type Float -> Float
(5) - 1.0
Type: Float
(6) -> )time on
(6) -> romberg(g, 0, 1, 0.1, 0.1, 10, 12)
(6) [value= - 1.0,error= 0.0,totalpts= 2049,success= true]
Type: Record(value: Float,error: Float,totalpts: Integer,success: Boolean)
Time: 2.78 (IN) + 2.18 (EV) + 0.27 (OT) + 0.60 (GC) = 5.83 sec
there is no improvement at all! The interpreter DID use the compiled version of
g but the code reflects faithfully the definition of g, not what it simplifies
to! Notice below, g has been compiled at (5).
(7) -> g(7)
Function Selection for g
Arguments: FLOAT
[1] signature: FLOAT -> FLOAT
implemented: local function *1;g;1;initial
Function Selection for map by coercion facility (map)
Arguments: ((COMPLEX INT -> INT),EXPR COMPLEX INT)
Target type: EXPR INT
[1] signature: ((COMPLEX INT -> INT),EXPR COMPLEX INT) -> EXPR INT
implemented: slot (Expression (Integer))(Mapping (Integer) (Complex (Integ
er)))(Expression (Complex (Integer))) from EXPR2(COMPLEX INT,INT)
(7) - 1.0
Type: Float
Time: 0.02 (OT) = 0.02 sec
The issue is therefore one of mathematical optimization in the compiler, but
compilers are only built to optimize code, not mathematics.
So the moral is: Do not expect compiler to simplify (mathematically) your code.
Incidentally, timing in Axiom, and also in Maple, may not be very reliable.
Running Maple 5, starting from scratch, I got different timing for below (Maple
may cache values), but the worst time is the simplest code on first run in the
order given:
restart; time(evalf(Int(expand(sqrt(-1)^2), z=0..1)));
>
.015
> restart; time(evalf(Int((sqrt(-1)^2), z=0..1)));
>
.016
> restart; time(evalf(Int(simplify(expand(sqrt(-1)^2)), z=0..1)));
>
.015
> restart; time(evalf(Int(expand(simplify(sqrt(-1)^2)), z=0..1)));
.016
> restart; time(evalf(Int(1, z=0..1)));
.032
When the last command is repeated, time becomes .016.
In Mathematica, there are two ways to define a function: Set and SetDelayed and
SetDelayed will also exhibit a big penalty:
Set[g[z_], Simplify[I^2]];
SetDelayed[h[z_], Simplify[I^2]];
Timing[Table[g[z],{z,1,10000}];]
{0.04 Second, Null}
Timing[Table[h[z],{z,1,10000}];]
{0.55 Second, Null}
I think there is no equivalent to Set in Axiom. So the more you try to coax
Axiom to "simplify", the worse it becomes:
(8) -> g(z) == eval(simplify(%i^2)::Float)
Compiled code for g has been cleared.
1 old definition(s) deleted for function or rule g
Type: Void
(9) -> g(5)
Compiling function g with type Float -> Float
(9) - 1.0
Type: Float
(10) -> romberg(z+->g(z), 0, 1, 0.1, 0.1, 10, 12)
(10) [value= - 1.0,error= 0.0,totalpts= 2049,success= true]
Type: Record(value: Float,error: Float,totalpts: Integer,success: Boolean)
Time: 3.08 (IN) + 2.87 (EV) + 0.28 (OT) + 0.35 (GC) = 6.58 sec
The only way I found that can simulate Set is to do this in two steps (and you
must include the coercion to Float):
(19) -> a:= simplify(%i^2)::Float
(20) -> g(z)==a
(21) -> romberg(g, 0, 1, 0.1, 0.1, 10, 12)
Time: 0.03 (EV) + 0.03 (OT) = 0.07 sec
William