performance improvement of mutable poset used for univariate asymptotic expansions

[dkrenn]

Reduce the evaluation time of the topological iterator.

As a result the time evaluating

k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)

(see #19306) dramatically decreases (see comment below for some timings).

CC: @behackl @cheuberg

Component: asymptotic expansions

Author: Daniel Krenn

Branch/Commit: b2af8aa

Reviewer: Clemens Heuberger

Issue created by migration from https://trac.sagemath.org/ticket/19577

[dkrenn]

Branch: u/dkrenn/asy/speed-topo-iter

[dkrenn]

New commits:

b2af8aa

test whether sorting is needed in topological iteration

[dkrenn]

Commit: b2af8aa

[dkrenn]

comment:5

Before this patch:

sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)
/local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/structure/unique_representation.py:1021: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
See http://trac.sagemath.org/17601 for details.
  instance = typecall(cls, *args, **options)
/local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/rings/asymptotic/growth_group_cartesian.py:305: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
See http://trac.sagemath.org/17601 for details.
  GenericGrowthGroup.__init__(self, sets[0], Vars, self.category(), **kwds)
1 loops, best of 1: 1.95 s per loop
sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)
1 loops, best of 1: 1.45 s per loop
sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)
1 loops, best of 1: 1.48 s per loop
sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)
1 loops, best of 1: 1.46 s per loop

After this patch:

sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)
/local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/structure/unique_representation.py:1021: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
See http://trac.sagemath.org/17601 for details.
  instance = typecall(cls, *args, **options)
/local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/rings/asymptotic/growth_group_cartesian.py:305: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
See http://trac.sagemath.org/17601 for details.
  GenericGrowthGroup.__init__(self, sets[0], Vars, self.category(), **kwds)
1 loops, best of 1: 1.12 s per loop
sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)
1 loops, best of 1: 543 ms per loop
sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)
1 loops, best of 1: 546 ms per loop
sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)
1 loops, best of 1: 514 ms per loop

[cheuberg]

comment:6

I can reproduce the speed-up in this particular instance and I cannot imagine bad side effects.

[cheuberg]

Reviewer: Clemens Heuberger

[vbraun]

Changed branch from u/dkrenn/asy/speed-topo-iter to b2af8aa