GeezerVison is showing github.com — Fractions instantiation revisited · Issue #72902 · python/cpython
Fractions instantiation revisited #72902Description
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = None
closed_at = None
created_at = <Date 2016-11-16.18:06:27.650>
labels = ['3.8', 'type-bug', 'library']
title = 'Fractions instantiation revisited'
updated_at = <Date 2019-08-05.09:04:19.247>
user = 'https://github.com/wm75' bugs.python.org fields:
activity = <Date 2019-08-05.09:04:19.247>
actor = 'jdemeyer'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2016-11-16.18:06:27.650>
creator = 'wolma'
dependencies = []
files = ['45507']
hgrepos = []
issue_num = 28716
keywords = ['patch']
message_count = 13.0
messages = ['280977', '280981', '280995', '280997', '280998', '280999', '305611', '310470', '313208', '313741', '313753', '313786', '349037']
nosy_count = 9.0
nosy_names = ['rhettinger', 'mark.dickinson', 'scoder', 'steven.daprano', 'serhiy.storchaka', 'jdemeyer', 'Eric.Wieser', 'wolma', 'josh.r']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'open'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue28716'
versions = ['Python 3.8'] Linked PRs
Activitywm75 commented on Nov 16, 2016 MannequinAuthor More actions I've spent a bit of time lately trying to optimize the instantiation of Fractions. This is related to bpo-22464, but instead of focusing on constructing Fractions from ints, my attempts revolve around improving instantiation from strings, floats and decimals.
I'm attaching a patch with all my changes for discussion, but here's an overview of what's in it:
CHANGES TO INSTANTIATION FROM STRINGS:
-
isinstance checking for str is performed before the more expensive check for numbers.Rational (which has to go through abc)
-
instantiation from strings doesn't use a regex pattern anymore for parsing; this is faster in many cases (and never slower) than the current version
-
while reimplementing string parsing I added PEP-515 support (this is the only behavior change in the patch)
combined this gives me the following performance changes for instantiation of Fractions from different arguments (profiled with 1,000,000 random inputs each):
'x/y'-type of strings:
----------------------
ncalls tottime percall cumtime percall filename:lineno(function)
old:
1000000 12.162 0.000 27.778 0.000 fractions.py:84(new)
new:
1000000 9.619 0.000 12.428 0.000 frc.py:68(new)
scientific notation (e.g., '1.234E-7'):
---------------------------------------
ncalls tottime percall cumtime percall filename:lineno(function)
old:
1000000 18.209 0.000 37.341 0.000 fractions.py:84(new)
new:
1000000 15.509 0.000 21.252 0.000 frc.py:68(new)
integer strings (e.g. '123456'):
--------------------------------
ncalls tottime percall cumtime percall filename:lineno(function)
old:
1000000 11.272 0.000 26.201 0.000 fractions.py:84(new)
new:
1000000 9.347 0.000 12.425 0.000 frc.py:68(new)
from other Fractions (to test effect on instantiation of numbers.Rational):
ncalls tottime percall cumtime percall filename:lineno(function)
old:
1000000 4.708 0.000 10.093 0.000 fractions.py:84(new)
new:
1000000 4.835 0.000 10.572 0.000 frc.py:68(new)
from int subclass (as another numbers.Rational):
ncalls tottime percall cumtime percall filename:lineno(function)
old:
1000000 3.446 0.000 8.044 0.000 fractions.py:84(new)
new:
1000000 3.795 0.000 8.836 0.000 frc.py:68(new)
SUMMARY of this part
====================
+ very significant speedup for instatiation from strings of different forms with (near) negligible effects on instantiation from numbers.Rational.
+ correct parsing of PEP-515-like number strings
- possibly slower error bubbling with invalid input (untested)
CHANGES TO INSTANTIATION FROM FLOAT AND DECIMAL:
-
no explicit check for float and decimal in standard constructor; instead, simply try to call as_integer_ratio as last resort (even after checking for numbers.Rational)
-
speed up alternate from_float and from_decimal constructor class methods by rearranging type checks and making use of _normalize flag
-
import decimal only on demand (when using from_decimal)
Resulting performance changes:
standard constructor with float:
--------------------------------
ncalls tottime percall cumtime percall filename:lineno(function)
old:
1000000 4.362 0.000 12.452 0.000 fractions.py:84(new)
new:
1000000 6.693 0.000 16.020 0.000 frc.py:68(new)
from_float:
-----------
ncalls tottime percall cumtime percall filename:lineno(function)
old:
1000000 3.146 0.000 17.769 0.000 fractions.py:193(from_float)
new:
1000000 2.544 0.000 7.591 0.000 frc.py:205(from_float)
standard constructor with decimal:
--------------------------------
ncalls tottime percall cumtime percall filename:lineno(function)
old:
1000000 4.672 0.000 20.795 0.000 fractions.py:84(new)
new:
1000000 7.097 0.000 24.526 0.000 frc.py:68(new)
from_decimal:
-------------
ncalls tottime percall cumtime percall filename:lineno(function)
old:
1000000 5.054 0.000 34.473 0.000 fractions.py:207(from_decimal)
new:
1000000 2.942 0.000 16.013 0.000 frc.py:220(from_decimal)
SUMMARY of this part:
- standard constructor becomes a bit slower for floats and Decimals
specialized class methods become a lot faster (for Decimal the benchmarks are based on _pydecimal - with the C implementation the percent differences would be even larger)
- eliminates decimal from regularly imported modules
- allows Fraction instantiation from duck-typing classes that provide as_integer_ratio
I hope at least some of this is interesting. serhiy-storchaka commented on Nov 16, 2016 Profiling give you only approximate results. In normal execution the effect of your changes can be opposite. Could you please provide benchmarks without using profiling? wm75 commented on Nov 16, 2016 MannequinAuthor More actions sure, I just happened to have the profiling available since I used it to optimize things. Here's similar microbenchmarks using perf:
STRINGS
=======
$ python -m perf timeit -s "from fractions import Fraction" "Fraction('1.23456e-7')"
.....................
Median +- std dev: 17.0 us +- 0.3 us
$ python -m perf timeit -s "from frc import Fraction" "Fraction('1.23456e-7')"
.....................
Median +- std dev: 8.95 us +- 0.16 us
$ python -m perf timeit -s "from fractions import Fraction" "Fraction('234/567')"
.....................
Median +- std dev: 12.6 us +- 0.1 us
$ python -m perf timeit -s "from frc import Fraction" "Fraction('234/567')"
.....................
Median +- std dev: 5.45 us +- 0.16 us
$ python -m perf timeit -s "from fractions import Fraction" "Fraction('123456')"
.....................
Median +- std dev: 12.4 us +- 0.6 us
$ python -m perf timeit -s "from frc import Fraction" "Fraction('123456')"
.....................
Median +- std dev: 5.77 us +- 0.12 us
$ python -m perf timeit -s "from fractions import Fraction; f=Fraction(3/4)" "Fraction(f)"
.....................
Median +- std dev: 4.36 us +- 0.06 us
$ python -m perf timeit -s "from frc import Fraction; f=Fraction(3/4)" "Fraction(f)"
.....................
Median +- std dev: 4.59 us +- 0.07 us
$ python -m perf timeit -s "from fractions import Fraction" -s "class myInt(int): pass" -s "i=myInt(123456)" "Fraction(i)"
.....................
Median +- std dev: 4.04 us +- 0.07 us
$ python -m perf timeit -s "from frc import Fraction" -s "class myInt(int): pass" -s "i=myInt(123456)" "Fraction(i)"
.....................
Median +- std dev: 4.27 us +- 0.06 usFLOATS
======
$ python -m perf timeit -s "from fractions import Fraction" "Fraction(1.23456e-7)"
.....................
Median +- std dev: 6.30 us +- 0.28 us
$ python -m perf timeit -s "from frc import Fraction" "Fraction(1.23456e-7)"
.....................
Median +- std dev: 8.64 us +- 0.13 us
$ python -m perf timeit -s "from fractions import Fraction" "Fraction.from_float(1.23456e-7)"
.....................
Median +- std dev: 8.68 us +- 0.14 us
$ python -m perf timeit -s "from frc import Fraction" "Fraction.from_float(1.23456e-7)"
.....................
Median +- std dev: 3.37 us +- 0.17 us DECIMALS (using C implementation this time)
===========================================
$ python -m perf timeit -s "from fractions import Fraction; from decimal import Decimal; d=Decimal('123456')" "Fraction(d)".....................
Median +- std dev: 6.95 us +- 0.21 us
$ python -m perf timeit -s "from frc import Fraction; from decimal import Decimal; d=Decimal('123456')" "Fraction(d)"
.....................
Median +- std dev: 8.43 us +- 0.17 us
$ python -m perf timeit -s "from fractions import Fraction; from decimal import Decimal; d=Decimal('123456')" "Fraction.from_decimal(d)"
.....................
Median +- std dev: 11.6 us +- 0.2 us
$ python -m perf timeit -s "from frc import Fraction; from decimal import Decimal; d=Decimal('123456')" "Fraction.from_decimal(d)"
.....................
Median +- std dev: 4.14 us +- 0.28 usMojoVampire commented on Nov 16, 2016 Might it make sense to make instantiation from numbers.Rational duck typing based as well? Just try to get the numerator and denominator attributes, on AttributeError, skip it and move on. Unless there is some concern that a non-Rational type might have both attributes and not intend them to mean it's a Rational? MojoVampire commented on Nov 16, 2016 Similarly, type checking for int might be replaced with calling operator.index on the input and handling the TypeError; that way, anything that has declared itself logically int-like is handled without explicit type checking at all. wm75 commented on Nov 16, 2016 MannequinAuthor More actions No, I don't think the numeric tower ABC should be replaced by duck-typing. One of the very reasons the fractions module exists is that it showcases how to use the numeric tower. If you want a class to be picked up as a Rational it should be registered as such. Pretty much the same goes for integer-like things. The direct type check for ints only exists to speed up the most obvious case, but anything integer-like should be registered as a numbers.Integral and it will just work with fractions. Beautiful stuff!
This is not the case for as_integer_ratio because that method is not defined in the numeric tower and this is why I think duck-typing could be of interest here (I'm not sure though whether its worth the somewhat decreased performance). My reasoning is that the standard constructor is anyway slower for floats and ints than the specialized classmethods for the two so people who really care about speed here (probably not too many) can just use the classmethods. eric-wieser commented on Nov 5, 2017
allows Fraction instantiation from duck-typing classes that provide as_integer_ratio
This would allow the numpy np.floating types to take part in Fraction conversion as well, which would be great.
As far as I can tell, Decimal already follows this duck-typing, so it would be a shame for other modules not to.
Perhaps an num, den = operator.rational(x) is needed to unify this code across the places that coerce rational numbers. scoder commented on Jan 23, 2018 Not sure if it's relevant for this specific change, but here's a benchmark that you could use for Fractions: bpo-22458 scoder commented on Mar 4, 2018 Just FYI and as further motivation, I reimplemented this dedicated parser for quicktions (in Cython, so the timings and speedups are not comparable).
scoder/quicktions@cc034e0
I was able to get another quite visible improvement by caching the values of "10 ** shift" for 0 <= shift < 58 in a tuple. Higher values are very unlikely in practice, and the memory size of a tuple with 58 values gives a nice multiple of the usual cache line size. (I originally stored 64 values in my commit but then cut it down later.)
scoder/quicktions@c20add5
I suspect that the difference won't be as big for the Python implementation, but it still seems worth a try.
The overall speedup that I got, compared to the initial regex implementation, is 50-70%.
[regex] $ python3.7 -m timeit -s 'from quicktions import Fraction as F' 'F("153456/789344")'
200000 loops, best of 5: 1.19 usec per loop
[native] $ python3.7 -m timeit -s 'from quicktions import Fraction as F' 'F("153456/789344")'
500000 loops, best of 5: 593 nsec per loop
[regex] $ python3.7 -m timeit -s 'from quicktions import Fraction as F' 'F("15.3456789E+4")'
100000 loops, best of 5: 2.3 usec per loop
[native] $ python3.7 -m timeit -s 'from quicktions import Fraction as F' 'F("15.3456789E+4")'
500000 loops, best of 5: 667 nsec per loop
It could be even higher if I additionally moved the int() integer parsing into Cython. Might try that at some point. But that's also not something that concerns the implementation in CPython. mdickinson commented on Mar 13, 2018 [Eric Wieser]
This would allow the numpy np.floating types to take part in Fraction conversion as well, which would be great.
I'm confused: as far as I can tell, the NumPy floating-point types don't implement as_integer_ratio. (Except for np.float64, which subclasses float and so inherits is_integer_ratio from it.) Or are you suggesting that if they were to implement as_integer_ratio at some point in the future, then they'd become compatible with Fraction? serhiy-storchaka commented on May 19, 2025
@serhiy-storchaka, but what about other change, i.e. moving down numbers.Rational check? Maybe I should factor out this to a separate pr? See benchmarks (third column) and my arguments for this.
First, benchmark how it would affect Fraction -> Fraction conversion. While it looks meanless, Fractions() can be applied to a collection of numbers -- integers, floating point, rational... We can also move down the as_integer_ratio check, but we need to benchmark Deciaml -> Fraction conversion. The float check can be left, and it can be simplified to type(numerator) is float if there is a benefit. Just for the case, benchmark conversion from int and float subclasses -- I do not think this is an important use case, but we should know how large the impact. skirpichev commented on May 20, 2025 @serhiy-storchaka, here are more extended tests on top of #133994 (at e383bdb):
| Benchmark |
ref |
patch |
move-abc |
| Fraction(myint) |
5.67 us |
7.10 us: 1.25x slower |
7.02 us: 1.24x slower |
| Fraction(Fraction(1, 2)) |
5.86 us |
4.87 us: 1.20x faster |
4.85 us: 1.21x faster |
| Fraction(Decimal('0.25')) |
11.1 us |
8.05 us: 1.38x faster |
8.01 us: 1.39x faster |
| Fraction(IntSubclass(123)) |
6.03 us |
5.08 us: 1.19x faster |
5.06 us: 1.19x faster |
| Fraction(FloatSubclass(0.25)) |
7.71 us |
4.28 us: 1.80x faster |
4.27 us: 1.81x faster |
| Fraction('123') |
19.3 us |
12.2 us: 1.58x faster |
15.9 us: 1.21x faster |
| Fraction('1/3') |
19.6 us |
9.49 us: 2.07x faster |
16.4 us: 1.20x faster |
| Fraction('1.2e-3') |
26.2 us |
16.9 us: 1.55x faster |
23.1 us: 1.13x faster |
| Fraction('-.2') |
23.4 us |
15.1 us: 1.55x faster |
20.3 us: 1.15x faster |
| Geometric mean |
(ref) |
1.41x faster |
1.21x faster |
Details
move-abc patch:
diff --git a/Lib/fractions.py b/Lib/fractions.py
index 8163e3bb59..063f28478c 100644
--- a/Lib/fractions.py
+++ b/Lib/fractions.py
@@ -238,11 +238,6 @@ def __new__(cls, numerator=0, denominator=None):
self._denominator = 1
return self
- elif isinstance(numerator, numbers.Rational):
- self._numerator = numerator.numerator
- self._denominator = numerator.denominator
- return self
-
elif (isinstance(numerator, float) or
(not isinstance(numerator, type) and
hasattr(numerator, 'as_integer_ratio'))):
@@ -278,6 +273,11 @@ def __new__(cls, numerator=0, denominator=None):
if m.group('sign') == '-':
numerator = -numerator
+ elif isinstance(numerator, numbers.Rational):
+ self._numerator = numerator.numerator
+ self._denominator = numerator.denominator
+ return self
+
else:
raise TypeError("argument should be a string or a Rational "
"instance or have the as_integer_ratio() method")# bench.py
import pyperf
from fractions import Fraction as F
from decimal import Decimal as D
from numbers import Integral
runner = pyperf.Runner()
s = 'Fraction'
class MyInt:
numerator = 123
denominator = 1
def __int__(self):
return 123
def __repr__(self):
return "myint"
class IntSubclass(int):
def __repr__(self):
return 'IntSubclass('+super().__repr__()+')'
class FloatSubclass(float):
def __repr__(self):
return 'FloatSubclass('+super().__repr__()+')'
Integral.register(MyInt)
for v in [MyInt(), F(1, 2), D("0.25"),
IntSubclass(123), FloatSubclass(0.25),
"123", "1/3", "1.2e-3", "-.2"]:
r = s + '(' + repr(v) + ')'
runner.bench_func(r, F, v)Reacted by Serhiy Storchaka serhiy-storchaka commented on May 20, 2025 Well, it looks that the only slowed down case is for rational numbers without as_integer_ratio(). I think that from a practical point of view it is worth it. Reacted by Sergey B Kirpichev skirpichev commented on May 20, 2025 Ok, I split out this change to #134320 scoder commented on Jun 26, 2026 The instantiation fast paths make the general assumption that the .as_integer_ratio() method returns its ratio in lowest terms. This is certainly true for the builtin types, but subtypes and other types (e.g. arbitrary other Rational types) might not follow this constraint. The .as_integer_ratio() method is only 'formally' documented for the builtin types that provide it, not as a general protocol. The numbers module of ABCs does not mention the method.
Therefore, I wonder if we should generally assume that all types obey this constraint, including builtin subtypes and user provided types, or whether we should restrict optimisations to the exact builtin types and otherwise assume (potentially) non-normalised return values, bailing to the regular GCD-normalisation paths.
For performance reasons, assuming a builtin-like implementation that returns lowest terms ratios is obviously attractive, but optimisations should only be applied within safe assumptions, not forfeit correctness. And I would generally expect the large majority of cases (those that merit optimisation) to actually pass the exact builtin types and nothing else, so we shouldn't lose much by playing it safe.
Opinions? skirpichev commented on Jun 27, 2026
The instantiation fast paths make the general assumption that the .as_integer_ratio() method returns its ratio in lowest terms.
And this is correct in the merged pr #133251, as it affects only float/Decimal subclasses. Someone can override contract from the parent class method to return None and blow up a nuke instead. I see no way to play nicely with such morons.
other types (e.g. arbitrary other Rational types) might not follow this constraint.
That's true, just invalid for builtin subtypes. It was my concern as well:
#120271 (comment)
Notably, that numpy types doesn't document such constraint (despite it seems to be valid):
>>> help(np.float128.as_integer_ratio)
Help on method descriptor as_integer_ratio:
as_integer_ratio(self, /) unbound numpy.longdouble method
longdouble.as_integer_ratio() -> (int, int)
Return a pair of integers, whose ratio is exactly equal to the original
floating point number, and with a positive denominator.
Raise `OverflowError` on infinities and a `ValueError` on NaNs.
>>> np.longdouble(10.0).as_integer_ratio()
(10, 1)
>>> np.longdouble(0.0).as_integer_ratio()
(0, 1)
>>> np.longdouble(-.25).as_integer_ratio()
(-1, 4)(Some canonicalization was mentioned, however.)
This affects following cases:
|
elif (isinstance(numerator, float) or |
|
(not isinstance(numerator, type) and |
|
hasattr(numerator, 'as_integer_ratio'))): |
|
# Exact conversion |
|
self._numerator, self._denominator = numerator.as_integer_ratio() |
|
return self |
and:
|
elif (isinstance(number, float) or |
|
(not isinstance(number, type) and |
|
hasattr(number, 'as_integer_ratio'))): |
|
return cls._from_coprime_ints(*number.as_integer_ratio()) |
This assumption was introduced in c8d2630. CC @serhiy-storchaka.
My opinion is that this is API similar to numerator/denominator pairs, it's for interoperation with the Rational type and should be mentioned in the numbers ABC as an optional method for Real types and mandatory for Rational's. It should return a canonicalized fraction.
BTW, there could be a more generic API, limit_denominator()-like. With infinite max_denominator - this should provide same value as as_integer_ratio() for Rational types and for some Real types (e.g. floating-point numbers). Though, in certain cases (e.g. for interval arithmetic) - infinite max_denominator doesn't make any sense.
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|