[issue22464] Speed up fractions implementation

[Roundup Robot]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Serhiy Storchaka]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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 following change shaves off almost 30% of the 
calls to PyNumber_InPlaceFloorDivide() in the telco benchmark during Fraction 
instantiation according to callgrind, thus saving 20% of the CPU instructions 
that go into tp_new().

Instead of always executing

numerator //= g
denominator //= g

this avoids unnecessary divisions:

if g is not 1:
if g is -1:
numerator = -numerator
denominator = -denominator
else:
numerator //= g
denominator //= g

Using the is operator here is CPythonish, but doing the same with != and == 
should also be an improvement already, although not as cheap. Now, given that 
CPython caches small integers internally, I would suggest actually not adding 
these two special cases to the fractions module but more generally to the 
division routines in longobject.c.

--
status: closed - open

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Roundup Robot]

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 tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Georg Brandl]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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 
extension type with Cython. For the benchmark, it currently gives me a 10x 
speedup over the original fractions module in Py3.4. I uploaded my initial 
attempt to PyPI and it's on github:

https://pypi.python.org/pypi/quicktions

https://github.com/scoder/quicktions

That makes a C implementation of Fraction generally worth considering for 
CPython.

--
resolution:  - fixed
status: open - closed

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Raymond Hettinger]

Changes by Raymond Hettinger raymond.hettin...@gmail.com:


--
nosy: +rhettinger

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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 small enough.
cdef long long ai, bi
while b:
try:
ai, bi = a, b
except OverflowError:
pass
else:
# switch to C loop
while bi:
ai, bi = bi, ai%bi
return ai
a, b = b, a%b
return a

It tries to drop the two numbers into C long-long-ints as soon as possible, and 
only runs the calculation in Python space until they are small enough to fit. 
In most cases, this will be either right from the start or fairly quickly after 
only a few iterations.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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__() and a simplistic gcd based normalisation. Here is a profiling run 
from the benchmark proposed in issue 22458 (which matches more or less the 
results with my own code):

 6969671 function calls (6969278 primitive calls) in 4.835 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   5196441.3240.0002.9280.000 fractions.py:73(__new__)
   5196320.6540.0000.6540.000 fractions.py:17(gcd)
   3197440.6370.0002.6940.000 fractions.py:400(_add)
  10392600.5070.0000.9500.000 abc.py:178(__instancecheck__)
40.4590.1154.8211.205 bm_telco_fractions.py:38(run)
  10393000.4430.0000.4430.000 _weakrefset.py:70(__contains__)
   5196160.3010.0004.3290.000 fractions.py:373(forward)
   1998720.2720.0001.3350.000 fractions.py:416(_mul)
  15987200.1170.0000.1170.000 fractions.py:278(denominator)
   9592320.0740.0000.0740.000 fractions.py:274(numerator)

The instantiation itself takes twice as much time as the gcd calculations, and 
both dominate the overall runtime of the benchmark by about 60%. Improving the 
instantiation time would thus bring a substantial benefit.

--
components: Library (Lib)
messages: 227284
nosy: scoder
priority: normal
severity: normal
status: open
title: Speed up fractions implementation
versions: Python 3.5

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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: +mark.dickinson

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

Changes by Stefan Behnel sco...@users.sourceforge.net:


--
type:  - performance

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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.

--
Added file: http://bugs.python.org/file36688/special_case_int2.patch

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Serhiy Storchaka]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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 patch, deselecting after applying should be easy 
enough.

--
Added file: http://bugs.python.org/file36690/special_case_int4.patch

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Serhiy Storchaka]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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 fractions.py:17(gcd)
   5196440.8060.0001.7000.000 fractions.py:73(__new__)
   3197440.6300.0001.9830.000 fractions.py:408(_add)
40.3930.0983.7350.934 bm_telco_fractions.py:38(run)
   5196160.2770.0003.3160.000 fractions.py:381(forward)
   1998720.2750.0000.9010.000 fractions.py:424(_mul)
  15987200.1610.0000.1610.000 fractions.py:285(denominator)
   5202570.1550.0000.1550.000 {built-in method isinstance}
   9592320.1180.0000.1180.000 fractions.py:281(numerator)
   5196570.0660.0000.0660.000 {built-in method __new__ of type 
object at 0x9d1c40}

Note that the gcd() call inside of __new__() now takes about as much time as 
the rest of the __new__() itself. It's clearly still worth optimising that.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22464] Speed up fractions implementation

[Stefan Behnel]

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  tottime  percall  cumtime  percall filename:lineno(function)
   5196320.8430.0000.8430.000 fractions.py:17(gcd)
   5196440.8000.0001.7090.000 fractions.py:73(__new__)
   3197440.5200.0001.8160.000 fractions.py:408(_add)
40.4010.1003.5820.896 bm_telco_fractions.py:38(run)
   5196160.2910.0003.1560.000 fractions.py:381(forward)
   1998720.2740.0000.9040.000 fractions.py:424(_mul)
   5202570.1450.0000.1450.000 {built-in method isinstance}
   9592320.1080.0000.1080.000 fractions.py:285(denominator)
   9592320.1080.0000.1080.000 fractions.py:281(numerator)
   5196570.0660.0000.0660.000 {built-in method __new__ of type 
object at 0x9d1c40}

--
Added file: 
http://bugs.python.org/file36691/avoid_redundant_property_lookups.patch

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22464
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com