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: |

### Description (last modified by )

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

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

### comment:2 Changed 7 years ago by

Commit: | → b2af8aa130f6d386c6a163971f37dc4ba98e4bf6 |
---|---|

Status: | new → needs_review |

### comment:3 Changed 7 years ago by

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

Description: | modified (diff) |
---|

### comment:5 Changed 7 years ago by

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

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

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

Resolution: | → fixed |

Status: | positive_review → closed |

**Note:**See TracTickets for help on using tickets.

New commits:

`test whether sorting is needed in topological iteration`