Cache the hash value of fractions

[rhettinger]

In both 3.10 and 3.11, hashing a small fraction is 20x slower than for a decimal. For fractions with large denominators, it is slower still.

We could sacrifice the space for one slot to cache the hash value:

__slots__ = ('_numerator', '_denominator', '_hash')

def __hash__(self):
    try:
        return self._hash
    except AttributeError:
        self.hash = ... # current code goes here
    return self._hash     

Another approach would be to have a single, size limited cache for the computation:

def __hash__(self):

    @lru_cache(maxsize=1 << 16)
    def current_code(numerator, denominator):
        try:
            dinv = pow(denominator, -1, _PyHASH_MODULUS)
        except ValueError:
            # ValueError means there is no modular inverse.
            hash_ = _PyHASH_INF
        else:
            hash_ = hash(hash(abs(numerator)) * dinv)
        result = hash_ if numerator >= 0 else -hash_
        return -2 if result == -1 else result

    return current_code(self._numerator, self._denominator)

Example of code that would benefit:

@lru_cache(maxsize=100_000)
def pabs(n: Fraction | int) -> Fraction:
    "P-adic absolute value"
    ...

for x, y in product(pool, repeat=2):            # pool is a set of fractions used as test values
    assert (pabs(x)==0) == (x==0)               # |x|=0 if and only if x=0
    assert pabs(x * y) == pabs(x) * pabs(y)     # |xy| = |x||y|
    assert pabs(x + y) <= pabs(x) + pabs(y)     # |x + y| ≤ |x| + |y| (Triangle Inequality)
    assert pabs(x + y) <= max(pabs(x), pabs(y)) # Strong triangle inequality
    assert pabs(x) == pabs(y) or pabs(x + y) == max(pabs(x), pabs(y)) # Lemma 2.1: If |x| ≠ |y|, |x+y| = max{|x|, |y|}

[serhiy-storchaka]

See also #58683. The similar patch for Decimal was rejected.

[gvanrossum]

Classic time vs. space trade-off. How common is hashing Fractions? (The example seems a bit special.) If we decide to do this, I'd prefer the version using an LRU cache, so that someone creating a large number of Fractions they aren't hashing doesn't have to pay the price. Did you think about the cache size much or is 65k just your go-to cache size value these days?

FWIW the Decimal patch for Python was rejected. The C version seems all right, so the problem would only affect the tiny minority of people who can't use the C Decimal version. So that's not comparable here.

[matthiasgoergens]

@rhettinger Do you have have benchmark data?

[rhettinger]

Baseline

% ~/cpython/python.exe -m timeit -s 'from fractions import Fraction as F' -s 'f = F(375, 34)' 'hash(f)'
500000 loops, best of 5: 479 nsec per loop

With caching

% git checkout fraction_hash_cache
Switched to branch 'fraction_hash_cache'
% ~/cpython/python.exe -m timeit -s 'from fractions import Fraction as F' -s 'f = F(375, 34)' 'hash(f)'
2000000 loops, best of 5: 119 nsec per loop