Opened 4 years ago

Closed 4 years ago

#19577 closed enhancement (fixed)

performance improvement of mutable poset used for univariate asymptotic expansions

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

Description (last modified by 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).

Change History (7)

comment:1 Changed 4 years ago by dkrenn

  • Branch set to u/dkrenn/asy/speed-topo-iter

comment:2 Changed 4 years ago by dkrenn

  • Commit set to b2af8aa130f6d386c6a163971f37dc4ba98e4bf6
  • Status changed from new to needs_review

New commits:

b2af8aatest whether sorting is needed in topological iteration

comment:3 Changed 4 years ago by dkrenn

  • Summary changed from performance improvment of mutable poset used for univariate asymptotic expansions to performance improvement of mutable poset used for univariate asymptotic expansions

comment:4 Changed 4 years ago by dkrenn

  • Description modified (diff)

comment:5 Changed 4 years ago by dkrenn

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 4 years ago by cheuberg

  • Milestone changed from sage-6.10 to sage-7.1
  • Reviewers set to Clemens Heuberger
  • Status changed from needs_review to positive_review

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

comment:7 Changed 4 years ago by vbraun

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