[issue37863] Speed hash(fractions.Fraction)

[Tim Peters]

New submission from Tim Peters <tim at python.org>:

Recording before I forget.  These are easy:

1. As the comments note, cache the hash code.

2. Use the new (in 3.8) pow(denominator, -1, modulus) to get the inverse instead of raising to the modulus-2 power.  Should be significantly faster.  If not, the new "-1" implementation should be changed ;-)  Will require catching ValueError in case the denom is a multiple of the modulus.

3. Instead of multiplying by the absolute value of the numerator, multiply by the hash of the absolute value of the numerator.  That changes the multiplication, and the subsequent modulus operation, from unbounded-length operations to short bounded-length ones.  Hashing the numerator on its own should be significantly faster, because the int hash doesn't require any multiplies or divides regardless of how large the numerator is.

None of those should change any computed results.

----------
messages: 349789
nosy: tim.peters
priority: low
severity: normal
stage: needs patch
status: open
title: Speed hash(fractions.Fraction)
type: performance
versions: Python 3.9

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue37863>
_______________________________________