The speed of subs()
Christian Bauer
Christian.Bauer at Uni-Mainz.DE
Thu Jul 10 22:22:39 CEST 2003
Hi!
Prompted by the recent discussion I've done some timings and experiments
with subs().
Two benchmarks were used:
a) "Binary tree" constructs a binary expression tree (alternating sums
and products) of depth N with symbols as the leaves (e.g. N=3 leads to
(a1+a2)*(a3+a4)+(a5+a6)*(a7+a8)), then substitutes all 2^N symbols by
a set of new symbols (using one subs() call).
b) "Linear polynomial" constructs an expression of the form "1+a1+a1*a2+
a1*a2*a3+...+a1*...*aN" of length N and also substitutes all N symbols
by new ones.
The time measured was only the time for the subs() step, excluding the
expression and list set-up time. All tests were done on an Athlon XP 2000+
machine with 768MB of RAM.
Results:
GiNaC 1.0
---------
With default options:
Binary tree, 2^N symbols....
N: 8 9 10 11
time/s: 0.17 1.33 13.269 129.4
Linear polynomial, N symbols......
N: 100 200 300 400 500 600
time/s: 0.13 1.39 6.32 18.539 49.429 109.64
With no_pattern = true:
Binary tree, 2^N symbols....
N: 8 9 10 11
time/s: 0.17 1.31 12.29 129.629
Linear polynomial, N symbols......
N: 100 200 300 400 500 600
time/s: 0.08 1.03 4.879 15.429 41.77 99.43
GiNaC 1.0 wastes its time in the inefficient lst::op(). no_pattern isn't
of much help here.
GiNaC 1.1
---------
With default options:
Binary tree, 2^N symbols.....
N: 8 9 10 11 12
time/s: 0.01 0.05 0.17 0.739 5.06
Linear polynomial, N symbols......
N: 100 200 300 400 500 600
time/s: 0.05 0.4 1.34 3.149 6.15 10.92
With subs_options::subs_no_pattern:
Binary tree, 2^N symbols.....
N: 8 9 10 11 12
time/s: 0 0 0.029 0.17 2.25
Linear polynomial, N symbols......
N: 100 200 300 400 500 600
time/s: 0 0.04 0.1 0.25 0.479 0.81
Much better. subs_no_pattern significantly speeds up the second case.
GiNaC 1.2 (i.e. what's currently in CVS)
---------
Performs about 5% better than GiNaC 1.1 but shows the same scaling behavior,
so I've omitted the results.
GiNaC 1.2 with basic::subs() using a map<ex,ex,ex_is_less> instead of two lists
---------
Default options:
Binary tree, 2^N symbols.....
N: 8 9 10 11 12
time/s: 0.01 0.029 0.13 0.55 3.899
Linear polynomial, N symbols......
N: 100 200 300 400 500 600
time/s: 0.059 0.39 1.29 3.12 5.919 10.46
With subs_options::subs_no_pattern:
Binary tree, 2^N symbols.....
N: 8 9 10 11 12
time/s: 0 0.01 0.029 0.13 1.53
Linear polynomial, N symbols......
N: 100 200 300 400 500 600
time/s: 0 0.02 0.04 0.059 0.1 0.149
A significant speedup, especially with subs_no_pattern. In the general case,
subs() still has to iterate through the list of substitutions to apply
match() to every single one. Only with subs_no_pattern can it use map::find().
But wait, there's more: I've noticed that expairseq::subschildren() scans
the substitution list and uses a different algorithm depending on whether
the list contains products or not. This step should be done only once, and
the result passed on as a subs_options flag. Preliminary tests indicate that
doing so speeds up the "binary tree" test by two orders of magnitude, and
the "linear polynomial" test by 10%).
Should these changes go into GiNaC 1.2? basic::normal() should then
probably also be altered to take a map<> instead of two lists. What about
match(), to_rational() and to_polynomial()?
Also, this will break the API for class implementors (again), and Stefan
Weinzierl will beat me. :-) (ok, it's broken in 1.2 anyway since basic::copy()
and basic::destroy() are gone)
Bye,
Christian
--
/ Physics is an algorithm
\/ http://www.uni-mainz.de/~bauec002/
More information about the GiNaC-list
mailing list