Fractions instantiation revisited #72902
Comments
|
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. CHANGES TO INSTANTIATION FROM STRINGS:
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: scientific notation (e.g., '1.234E-7'): integer strings (e.g. '123456'): from other Fractions (to test effect on instantiation of numbers.Rational): from int subclass (as another numbers.Rational): 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
CHANGES TO INSTANTIATION FROM FLOAT AND DECIMAL:
Resulting performance changes: standard constructor with float: from_float: standard constructor with decimal: from_decimal: SUMMARY of this part:
I hope at least some of this is interesting. |
|
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? |
|
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 usDECIMALS (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 us |
|
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? |
|
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. |
|
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. |
This would allow the numpy As far as I can tell, Perhaps an |
|
Not sure if it's relevant for this specific change, but here's a benchmark that you could use for Fractions: bpo-22458 |
|
Just FYI and as further motivation, I reimplemented this dedicated parser for quicktions (in Cython, so the timings and speedups are not comparable). 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.) 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")' [regex] $ python3.7 -m timeit -s 'from quicktions import Fraction as F' 'F("15.3456789E+4")' 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. |
|
[Eric Wieser]
I'm confused: as far as I can tell, the NumPy floating-point types don't implement |
Yes, exactly. Conversely, there's little gain in implementing it until |
|
FYI, adding int.as_integer_ratio() is being taken care in a separate issue: https://bugs.python.org/issue33073 . I've set it aside for a beginning core-dev mentee to work on because it is simple and self-contained. Pretty much all the related work can be done here. |
|
See https://discuss.python.org/t/pep-3141-ratio-instead-of-numerator-denominator/2037/24?u=jdemeyer for a proposal to define a new dunder __ratio__ (instead of as_integer_ratio) for this. |
|
@wm75, here is a pr to speedup Let me know if you wish to continue your work on the Fraction constructor. Or I can prepare a patch and mention you as co-author. IIUIC, at this point relevant parts of your proposal are: 1) move "str" case up (over numbers.Rational), 2) reimplement string parsing without regexps. Below my simple benchmarks. The patch1 just do 1), the patch2 (included below) - solves also 2).
# bench.py
import pyperf
from fractions import Fraction as F
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"
Integral.register(myint)
for v in [myint(), "123", "1/3", "1.2e-3", "-.2"]:
r = s + '(' + repr(v) + ')'
runner.bench_func(r, F, v)diff --git a/Lib/fractions.py b/Lib/fractions.py
index fa722589fb..55d1113b4a 100644
--- a/Lib/fractions.py
+++ b/Lib/fractions.py
@@ -53,20 +53,6 @@ def _hash_algorithm(numerator, denominator):
result = hash_ if numerator >= 0 else -hash_
return -2 if result == -1 else result
-_RATIONAL_FORMAT = re.compile(r"""
- \A\s* # optional whitespace at the start,
- (?P<sign>[-+]?) # an optional sign, then
- (?=\d|\.\d) # lookahead for digit or .digit
- (?P<num>\d*|\d+(_\d+)*) # numerator (possibly empty)
- (?: # followed by
- (?:\s*/\s*(?P<denom>\d+(_\d+)*))? # an optional denominator
- | # or
- (?:\.(?P<decimal>\d*|\d+(_\d+)*))? # an optional fractional part
- (?:E(?P<exp>[-+]?\d+(_\d+)*))? # and optional exponent
- )
- \s*\Z # and optional whitespace to finish
-""", re.VERBOSE | re.IGNORECASE)
-
# Helpers for formatting
@@ -238,11 +224,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'))):
@@ -252,31 +233,56 @@ def __new__(cls, numerator=0, denominator=None):
elif isinstance(numerator, str):
# Handle construction from strings.
- m = _RATIONAL_FORMAT.match(numerator)
- if m is None:
+ fraction_literal = numerator
+ num, _, denom = fraction_literal.partition('/')
+ try:
+ num = num.strip()
+ denom = denom.strip()
+ if _ == '':
+ # Numerator-only form allows for optional fractional
+ # and exponent parts.
+ # Partition the fraction literal on the exponent sign,
+ # while ignoring leading and trailing whitespace
+ # and the case of the exponent sign.
+ num, _, exp = num.replace('e', 'E').partition('E')
+ if _ and not exp:
+ # No exponent notation without value!
+ raise ValueError
+ num, _, decimal = num.partition('.')
+ shift = 0
+ if decimal:
+ # Zero-pad integer-less fraction literals.
+ if num == '' or num == '+':
+ num = '0'
+ elif num == '-':
+ num += '0'
+ # Joining literal parts by underscores ensures
+ # that result strings can only be parsed as ints
+ # if there parts were parseable.
+ num = f'{num}_{decimal}'
+ shift -= len(decimal)-decimal.count('_')
+ if exp:
+ shift += int(exp)
+ numerator = int(num)
+ denominator = 1
+ if shift > 0:
+ numerator *= 10 ** shift
+ elif shift < 0:
+ denominator = 10 ** -shift
+
+ elif num and denom and num[-1].isdigit() and denom[0].isdigit():
+ numerator = int(num)
+ denominator = int(denom)
+ else:
+ raise ValueError
+ except ValueError:
raise ValueError('Invalid literal for Fraction: %r' %
- numerator)
- numerator = int(m.group('num') or '0')
- denom = m.group('denom')
- if denom:
- denominator = int(denom)
- else:
- denominator = 1
- decimal = m.group('decimal')
- if decimal:
- decimal = decimal.replace('_', '')
- scale = 10**len(decimal)
- numerator = numerator * scale + int(decimal)
- denominator *= scale
- exp = m.group('exp')
- if exp:
- exp = int(exp)
- if exp >= 0:
- numerator *= 10**exp
- else:
- denominator *= 10**-exp
- if m.group('sign') == '-':
- numerator = -numerator
+ fraction_literal)
+
+ 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 " |
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:
bugs.python.org fields:
Linked PRs
The text was updated successfully, but these errors were encountered: