# 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/

```