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/