logoalt Hacker News

amiga386 • yesterday at 10:03 PM • 2 replies • view on HN

I call shenanigans on this.

    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
    for n in [1000, 2000, 4000, 8000, 16000]:
        print(f"M=2^61-1, {n=:5d} ->", timeit.timeit(lambda: test(M,n), number=3))
    for n in [1000, 2000, 4000, 8000, 16000]:
        print(f"M=1,      {n=:5d} ->", timeit.timeit(lambda: test(1,n), number=3))
Magically, when you stop using BIGINTS as the set members and just use regular ints, there is no such quadratic explosion.

    M=2^61-1, n= 1000 -> 0.13144792200182565
    M=2^61-1, n= 2000 -> 0.48016051898594014
    M=2^61-1, n= 4000 -> 2.058760045998497
    M=2^61-1, n= 8000 -> 7.843778470996767
    M=2^61-1, n=16000 -> 40.01485426299041
    M=1,      n= 1000 -> 0.000748768012272194
    M=1,      n= 2000 -> 0.0015750699967611581
    M=1,      n= 4000 -> 0.003037029004190117
    M=1,      n= 8000 -> 0.006664915999863297
    M=1,      n=16000 -> 0.012693285010755062
The runtime is being spent hashing bigints, comparing candidate bigint(s) against reference bigints, and summing bigints. And there's also some set lookups.

Replies

nilslindemann • today at 1:06 AM

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.__...

➕ show 1 reply
mitxela • today at 5:15 AM

So why is it quadratic? Hashing 1<<61-1 should be a constant factor slower than hashing 1.

I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI?

➕ show 1 reply