Opened 7 years ago

Closed 7 years ago

#19577 closed enhancement (fixed)

performance improvement of mutable poset used for univariate asymptotic expansions

Reported by: Daniel Krenn Owned by:
Priority: major Milestone: sage-7.1
Component: asymptotic expansions Keywords:
Cc: Benjamin Hackl, Clemens Heuberger Merged in:
Authors: Daniel Krenn Reviewers: Clemens Heuberger
Report Upstream: N/A Work issues:
Branch: b2af8aa (Commits, GitHub, GitLab) Commit: b2af8aa130f6d386c6a163971f37dc4ba98e4bf6
Dependencies: Stopgaps:

Status badges

Description (last modified by Daniel Krenn)

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).

Change History (7)

comment:1 Changed 7 years ago by Daniel Krenn

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

comment:2 Changed 7 years ago by Daniel Krenn

Commit: → b2af8aa130f6d386c6a163971f37dc4ba98e4bf6
Status: new → needs_review

New commits:

​b2af8aatest whether sorting is needed in topological iteration

comment:3 Changed 7 years ago by Daniel Krenn

Summary: performance improvment of mutable poset used for univariate asymptotic expansions → performance improvement of mutable poset used for univariate asymptotic expansions

comment:4 Changed 7 years ago by Daniel Krenn

Description: modified (diff)

comment:5 Changed 7 years ago by Daniel Krenn

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

comment:6 Changed 7 years ago by Clemens Heuberger

Milestone: sage-6.10 → sage-7.1
Reviewers: → Clemens Heuberger
Status: needs_review → positive_review

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

comment:7 Changed 7 years ago by Volker Braun

Branch: u/dkrenn/asy/speed-topo-iter → b2af8aa130f6d386c6a163971f37dc4ba98e4bf6
Resolution: → fixed
Status: positive_review → closed
Note: See TracTickets for help on using tickets.