[issue22464] Speed up fractions implementation

Roundup Robot added the comment: New changeset 6c8e2c6e3a99 by Yury Selivanov in branch '3.5': whatsnew/3.5: Mention issue 22464 https://hg.python.org/cpython/rev/6c8e2c6e3a99 -- ___ Python tracker

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: I tried it, but it seems better to open a new ticket for this as there are behavioural changes. See #22501. -- status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22464

[issue22464] Speed up fractions implementation

Serhiy Storchaka added the comment: Please do not use is for number comparison. This can be broken unexpectedly in future or on alternative implementation. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22464

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: Sorry for reopening this, but I found one more thing. Division is pretty heavy on PyLong objects and there doesn't seem to be an internal optimisation for division by 1 and -1. Since many Fraction input values can already be normalised for some reason, the

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: BTW, the last two patches (int4 and redundant_property) are ready to be applied. Anyone? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22464 ___

[issue22464] Speed up fractions implementation

Roundup Robot added the comment: New changeset 646bc7d3544b by Georg Brandl in branch 'default': #22464: Speed up common Fraction operations by special-casing several https://hg.python.org/cpython/rev/646bc7d3544b -- nosy: +python-dev ___ Python

[issue22464] Speed up fractions implementation

Georg Brandl added the comment: Left this open in case you have additional patches coming. -- nosy: +georg.brandl ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22464 ___

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: I created issue 22486 about the gcd() performance. I think we can close this ticket - I don't see any more obvious low hanging fruit and future findings can have their own ticket. Out of interest, I modified the fractions module to compile Fraction into an

[issue22464] Speed up fractions implementation

Changes by Raymond Hettinger raymond.hettin...@gmail.com: -- nosy: +rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22464 ___ ___

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: This simple Cython variant of gcd() is substantially faster for me (you may consider it pseudo-code for a C implementation): def _gcd(a, b): # Try doing all computation in C space. If the numbers are too large # at the beginning, retry until they are

[issue22464] Speed up fractions implementation

New submission from Stefan Behnel: Fractions are an excellent way to do exact money calculations and largely beat Decimal in terms of simplicity, accuracy and safety. Clearly not in terms of speed, though. The current implementation does some heavy type checking and dispatching in __new__()

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: Adding Mark Dickinson to the noisy list who mentioned having worked on a C implementation for gcd(). I think this would be a good thing to try. However, the most important part would be to restructure and specialise Fraction.__new__(). -- nosy:

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: Here is a straight forward patch that special cases int values in the constructor. It gives me a 35% speedup in the benchmark. -- keywords: +patch Added file: http://bugs.python.org/file36687/special_case_int.patch

[issue22464] Speed up fractions implementation

Changes by Stefan Behnel sco...@users.sourceforge.net: -- type: - performance ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22464 ___ ___

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: Updated patch - there is a somewhat hidden attempt in the code to keep nominator and denominater plain int values, not subtypes. That means that it's safer to restrict the optimisation to plain ints as well, which should still hit 95% of the use cases.

[issue22464] Speed up fractions implementation

Changes by Stefan Behnel sco...@users.sourceforge.net: Added file: http://bugs.python.org/file36689/special_case_int3.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22464 ___

[issue22464] Speed up fractions implementation

Serhiy Storchaka added the comment: What speedup give you second change? -- nosy: +serhiy.storchaka ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22464 ___

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: The second isn't a big difference because it only hits plain instantiations from integers. They are less likely to be performance critical than those from a quotient, which happen for all calculations. It's more for symmetry, I guess. --

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: I found one more place where special casing helps: equal comparisons to integers, e.g. f == 0 or f == 1 or so. timeit shows me a speedup by a factor of three for this, with only a tiny slow-down when comparing fractions on both sides. I put all of them in one

[issue22464] Speed up fractions implementation

Serhiy Storchaka added the comment: Microbenchmarks show about 2x speedup in both cases. The patch LGTM. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22464 ___

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: Benchmark profile after the patch: 5930670 function calls (5930288 primitive calls) in 3.748 seconds Ordered by: internal time ncalls tottime percall cumtime percall filename:lineno(function) 5196320.8280.0000.8280.000

[issue22464] Speed up fractions implementation

Stefan Behnel added the comment: Here is another little optimisation that removes the redundant property lookups for the denominator in __add__() and __sub__(). New profile: 5291182 function calls (5290800 primitive calls) in 3.596 seconds Ordered by: internal time ncalls