[issue43420] Optimize rational arithmetics

Sergey B Kirpichev added the comment: > I'll have to see if the slowdown can be mitigated somehow. Yes, for small components this is a known slowdown. I'm trying to mitigate that case in https://github.com/python/cpython/pull/25518. Except for the mixed mode (Fraction's+int) - this match

[issue43420] Optimize rational arithmetics

Stefan Behnel added the comment: Just FYI, I applied the same changes to the quicktions [1] module, a Cython compiled (and optimised) version of fractions.Fraction. [1] https://github.com/scoder/quicktions/ The loss in performance for small values is much higher there, almost 2x for the

[issue43420] Optimize rational arithmetics

Tim Peters added the comment: This report is closed. Please open a different report. We've already demonstrated that, as predicted, nothing can be said here without it being taken as invitation to open-ended discussion. So it goes, but it doesn't belong on _this_ report anymore. --

[issue43420] Optimize rational arithmetics

Sergey B Kirpichev added the comment: On Mon, Mar 22, 2021 at 04:34:32AM +, Tim Peters wrote: > For example, setting up a module global `_gcd` name for `math.gcd` Looking on the stdlib, I would just import gcd. > default `_gcd=math.gcd` arguments to the methods? Then it's > even faster

[issue43420] Optimize rational arithmetics

Tim Peters added the comment: If experience is any guide, nothing about anything here will go smoothly ;-) For example, setting up a module global `_gcd` name for `math.gcd` is a very standard, widespread kind of micro-optimization. But - if that's thought to be valuable (who knows? maybe

[issue43420] Optimize rational arithmetics

Sergey B Kirpichev added the comment: On Mon, Mar 22, 2021 at 02:35:59AM +, Tim Peters wrote: > Thanks, all! This has been merged now. If someone wants to > continue pursuing things left hanging, I'd suggest opening > a different BPO report. Tim, if you are about micro-optimizations for

[issue43420] Optimize rational arithmetics

Tim Peters added the comment: Thanks, all! This has been merged now. If someone wants to continue pursuing things left hanging, I'd suggest opening a different BPO report. -- resolution: -> fixed stage: patch review -> resolved status: open -> closed

[issue43420] Optimize rational arithmetics

Tim Peters added the comment: New changeset 690aca781152a498f5117682524d2cd9aa4d7657 by Sergey B Kirpichev in branch 'master': bpo-43420: Simple optimizations for Fraction's arithmetics (GH-24779) https://github.com/python/cpython/commit/690aca781152a498f5117682524d2cd9aa4d7657 --

[issue43420] Optimize rational arithmetics

Sergey B Kirpichev added the comment: > a short paragraph or section on alternative implementations There are no alternative implementations. SymPy's PythonRational (AFAIR, this class not in the default namespace) is an internal fallback solution, for case when no gmpy2 is available.

[issue43420] Optimize rational arithmetics

Tim Peters added the comment: Terry, we could do that, but the opposition here isn't strong, and is pretty baffling anyway ;-) : the suggested changes are utterly ordinary for implementations of rationals, require very little code, are not delicate, and are actually straightforward to see

[issue43420] Optimize rational arithmetics

Terry J. Reedy added the comment: A possible resolution to this issue might be augmenting https://docs.python.org/3/library/fractions.html#module-fractions with a short paragraph or section on alternative implementations noting that there is a tradeoff between speed and complexity (and

[issue43420] Optimize rational arithmetics

Tim Peters added the comment: Issue 21922 lists several concerns, and best I know they all still apply. As a practical matter, I expect the vast bulk of core Python developers would reject a change that sped large int basic arithmetic by a factor of a billion if it slowed down basic

[issue43420] Optimize rational arithmetics

Sergey B Kirpichev added the comment: On Tue, Mar 09, 2021 at 05:11:09AM +, Tim Peters wrote: > those for + and - are much subtler In fact, these optimizations will payoff faster (wrt denominators size), esp. due to gcd==1 branch. Sorry for off-topic: > WRT which, I added Python's

[issue43420] Optimize rational arithmetics

Tim Peters added the comment: I agree with everyone ;-) That is, my _experience_ matches Mark's: as a more-or-less "numeric expert", I use Fraction in cases where it's already fast enough. Python isn't a CAS, and, e.g., in pure Python I'm not doing things like computing or composing power

[issue43420] Optimize rational arithmetics

Sergey B Kirpichev added the comment: On Sun, Mar 07, 2021 at 12:16:36PM +, Mark Dickinson wrote: > but not the "incompatible denominators" part. :-) The typical use there is > that those fractions have been converted from floats But there is no limits to use Fraction's for input, e.g.

[issue43420] Optimize rational arithmetics

Sergey B Kirpichev added the comment: On Sun, Mar 07, 2021 at 10:34:24PM +, Aaron Meurer wrote: > I'm surprised to hear that the "typical use-case" of Fraction > is fractions converted from floats. For statistics module - that may be true. Unfortunately, no (other) practical

[issue43420] Optimize rational arithmetics

Aaron Meurer added the comment: I'm surprised to hear that the "typical use-case" of Fraction is fractions converted from floats. Do you have evidence in the wild to support that? I would expect any application that uses fractions "generically" to run into the same sorts of problems SymPy

[issue43420] Optimize rational arithmetics

Mark Dickinson added the comment: > There is one exception I've found: stdlib's statistics module uses > Fraction's in the _sum() helper, exactly in a paradigm "sum a lot > of values". That's an interesting example: it does indeed satisfy the "sum of a lot of values" part, but not the

[issue43420] Optimize rational arithmetics

Sergey B Kirpichev added the comment: > I'd prefer to keep the code simplicity It's not going to be complicated so much and algorithms are well known, but I see your point. > and the speed for small inputs here Speed loss is not so big, 10-20%. > Python's needs aren't the same as SymPy's

[issue43420] Optimize rational arithmetics

Mark Dickinson added the comment: Personally, I'd prefer to keep the code simplicity, and the speed for small inputs here. Python's needs aren't the same as SymPy's needs or SAGE's needs, and not all of the fractions.Fraction use-cases involve summing lots of values with incompatible

[issue43420] Optimize rational arithmetics

Raymond Hettinger added the comment: > 1 loop, best of 11: 257 msec per loop > $ ... from patched ... > 10 loops, best of 11: 33.2 msec per loop Looks worth it :-) -- ___ Python tracker

[issue43420] Optimize rational arithmetics

Change by Aaron Meurer : -- nosy: +asmeurer ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue43420] Optimize rational arithmetics

Change by Sergey B Kirpichev : -- pull_requests: +23544 stage: -> patch review pull_request: https://github.com/python/cpython/pull/24779 ___ Python tracker ___

[issue43420] Optimize rational arithmetics

Sergey B Kirpichev added the comment: I have similar timings (for a draft version of PR, see f.patch) as for the last comment, though the small-dens overhead seems to be bigger(~20%): $ python3.10 -m timeit -r11 -s 'from fractions import Fraction as F' -s 'a=F(10,3)' -s 'b=F(6, 5)' 'a * b'

[issue43420] Optimize rational arithmetics

Raymond Hettinger added the comment: Without the guards the incremental cost drops to 10%. $ python3.10 -m timeit -r11 -s 'from patched_noguards import Fraction as F' -s 'a=F(10,3)' -s 'b=F(6, 5)' 'a * b' 10 loops, best of 11: 2.02 usec per loop --

[issue43420] Optimize rational arithmetics

Raymond Hettinger added the comment: The cost to the common case for small components is about 20%: $ python3.10 -m timeit -r11 -s 'from fractions import Fraction as F' -s 'a=F(10,3)' -s 'b=F(6, 5)' 'a * b' 20 loops, best of 11: 1.8 usec per loop $ python3.10 -m timeit -r11 -s 'from

[issue43420] Optimize rational arithmetics

Raymond Hettinger added the comment: Note that Fraction arithmetic has a huge administrative overhead. The cost of the underlying multiplications and divisions won't dominate the total time until the numerators and denominators are very large. For the proposed optimization, this implies

[issue43420] Optimize rational arithmetics

Change by Mark Dickinson : -- nosy: +mark.dickinson ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue43420] Optimize rational arithmetics

Raymond Hettinger added the comment: Here's some code to try out: from math import gcd from fractions import Fraction import operator import math class Henrici(Fraction): 'Reformulate _mul to reduce the size of intermediate products' # Original has 2 multiplications, 1 gcd calls,

[issue43420] Optimize rational arithmetics

New submission from Sergey B Kirpichev : fractions.py uses naive algorithms for doing arithmetics. It may worth implementing less trivial versions for addtion/substraction and multiplication (e.g. Henrici algorithm and so on), described here: