Comment by nilslindemann

Actually, as the Google AI just taught me [1], the bad performance results from hash _collisions_, not from using bigints (which the author also mentions):

    import timeit
    
    def test(M, n):
        values = [i * M for i in range(1, n + 1)]
        s = set(values)
        sum(v in s for v in values)
    
    M = (1 << 61) - 1   # This is a bigint and also a Mersenne prime number
    N = (1 << 61) + 42  # This is a bigint, but not a Mersenne prime number
    
    # This runs slow
    for n in [1000, 2000, 4000, 8000, 16000]:
        print(f"M=2^61-1, {n=:5d} ->", timeit.timeit(lambda: test(M,n), number=3))
    
    # This runs with normal performance
    for n in [1000, 2000, 4000, 8000, 16000]:
        print(f"N=2^61+42, {n=:5d} ->", timeit.timeit(lambda: test(N,n), number=3))

(1 << 61) - 1 is a Mersenne prime number, which Python uses internally on 64-bit systems for the hash algorithm for big integers. When multiplying numbers with this prime number, hash collisions become common, and this slows down the performance.

This is not completely theoretical; hash-DoS attacks make use of that. For this reason, there is hash salting since Python 3.3 for strings, bytes, and datetime objects [2], but not for integers, because the most common attack surface is JSON, but JSON keys are strings, and hash salting would slow down the performance of math operations.

[1] https://share.google/aimode/cXQyw0SDPr5FnhBc5, available for seven days

[2] See the grey info box here: https://docs.python.org/3/reference/datamodel.html#object.__...