From 29bb227a0ce6d355a2b3e5d6a25872e3702ba9bb Mon Sep 17 00:00:00 2001 From: Tim Peters Date: Fri, 16 Aug 2019 21:09:16 -0500 Subject: [PATCH] Add a minor `Fraction.__hash__()` optimization (GH-15313) * Add a minor `Fraction.__hash__` optimization that got lost in the shuffle. Document the optimizations. --- Lib/fractions.py | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-) diff --git a/Lib/fractions.py b/Lib/fractions.py index c922c38e24..2e7047a818 100644 --- a/Lib/fractions.py +++ b/Lib/fractions.py @@ -564,10 +564,25 @@ class Fraction(numbers.Rational): try: dinv = pow(self._denominator, -1, _PyHASH_MODULUS) except ValueError: - # ValueError means there is no modular inverse + # ValueError means there is no modular inverse. hash_ = _PyHASH_INF else: - hash_ = hash(abs(self._numerator)) * dinv % _PyHASH_MODULUS + # The general algorithm now specifies that the absolute value of + # the hash is + # (|N| * dinv) % P + # where N is self._numerator and P is _PyHASH_MODULUS. That's + # optimized here in two ways: first, for a non-negative int i, + # hash(i) == i % P, but the int hash implementation doesn't need + # to divide, and is faster than doing % P explicitly. So we do + # hash(|N| * dinv) + # instead. Second, N is unbounded, so its product with dinv may + # be arbitrarily expensive to compute. The final answer is the + # same if we use the bounded |N| % P instead, which can again + # be done with an int hash() call. If 0 <= i < P, hash(i) == i, + # so this nested hash() call wastes a bit of time making a + # redundant copy when |N| < P, but can save an arbitrarily large + # amount of computation for large |N|. + hash_ = hash(hash(abs(self._numerator)) * dinv) result = hash_ if self._numerator >= 0 else -hash_ return -2 if result == -1 else result -- 2.40.0