The speed of subs()

[Christian Bauer]

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/