Skip to content

Shouldn't set_intersection use _PyObject_HashFast()? #137759

Closed

Description

@JasonMendoza2008

While doing something else, I ended up reading parts of setobject.c and I noticed that set_intersection doesn't use _PyObject_HashFast():

hash = PyObject_Hash(key);

Is there a reason for it? I tried replacing it (no unit test fails), and benchmarking both versions (with --pgo enabled) but I couldn't see a difference (probably too much noise, or maybe I didn't try hard enough, probably should try on really big big sets to call that operation many a times). In theory though, it should make sets faster when they have strings (and maybe sets of other types slightly slightly slower but _PyObject_HashFast() is used everywhere else in setobject.c so I think that that tradeoff was considered already).

Linked PRs

Activity

  1. changed the title [-]Shouldn't `set_intersection` use `_PyObjectHashFast()`?[/-] [+]Shouldn't `set_intersection` use `_PyObject_HashFast()`?[/+] on Aug 14, 2025
  2. StanFromIreland commented on Aug 14, 2025

    @StanFromIreland
    Member
  3. aisk commented on Aug 14, 2025

    @aisk
    Member

    In 294e74, I just extracted the always used code snippet which does the fast path for a unicode object into an inline function which turns out to be the _PyObject_HashFast.

    Before that, the set_intersection was already just calling the PyObject_Hash instead of using the code snippet which does the fast path for a unicode. So I just have no idea why this doesn't use the fast path and didn't touch it.

    As for why the _PyObject_HashFast is not faster than PyObject_Hash, I'm not very familiar with assembly or C compilers, but I guess it may be caused by these reasons:

    1. _PyObject_HashFast is not inlined by the C compiler so the function call may eat up the performance benefit of the fast path. I'll check this and if so, we should change it to a macro.
    2. The modern compiler is smart enough to do the inline optimization, so maybe it can inline the function calls in the slow path for unicode objects (it's just a memory read, with extra function calls).
    3. The hash part is not the bottleneck of the running code if you test it in Python, because the Python interpreter's eval loop or other runtime costs may be slower than the hash part, so the performance difference will be hard to observe.
  4. JasonMendoza2008 commented on Aug 14, 2025

    @JasonMendoza2008
    ContributorAuthor

    In 294e74, I just extracted the always used code snippet which does the fast path for a unicode object into an inline function which turns out to be the _PyObject_HashFast.

    Before that, the set_intersection was already just calling the PyObject_Hash instead of using the code snippet which does the fast path for a unicode. So I just have no idea why this doesn't use the fast path and didn't touch it.

    As for why the _PyObject_HashFast is not faster than PyObject_Hash, I'm not very familiar with assembly or C compilers, but I guess it may be caused by these reasons:

    1. _PyObject_HashFast is not inlined by the C compiler so the function call may eat up the performance benefit of the fast path. I'll check this and if so, we should change it to a macro.
    2. The modern compiler is smart enough to do the inline optimization, so maybe it can inline the function calls in the slow path for unicode objects (it's just a memory read, with extra function calls).
    3. The hash part is not the bottleneck of the running code if you test it in Python, because the Python interpreter's eval loop or other runtime costs may be slower than the hash part, so the performance difference will be hard to observe.

    Just to clarify, I only tested on small sets, I hadn't had time to test on sets with $> 10^3$ elements, I will try on sets with $10^6$ elements, they should hopefully call that function enough times to observe a difference. I'll do more extensive benchmarks soon, but as far as I can tell from a correctness standpoint, there is no reason not to call _PyObject_HashFast here.

  5. aisk commented on Aug 14, 2025

    @aisk
    Member

    Hi, I built current main branch on Debian12 with --enable-optimizations, and I can ensure that _PyObject_HashFast is inlined (at least in _PySet_AddTakeRef).

    00000000001ef060 <_PySet_AddTakeRef>:
    {
      1ef060:	41 57                	push   %r15
      1ef062:	41 56                	push   %r14
        if (PyUnicode_CheckExact(op)) {
      1ef064:	4c 8d 35 b5 a5 33 00 	lea    0x33a5b5(%rip),%r14        # 529620 <PyUnicode_Type>
      1ef06b:	41 55                	push   %r13
      1ef06d:	49 89 f5             	mov    %rsi,%r13
      1ef070:	41 54                	push   %r12
      1ef072:	55                   	push   %rbp
      1ef073:	48 89 fd             	mov    %rdi,%rbp
      1ef076:	53                   	push   %rbx
      1ef077:	48 83 ec 38          	sub    $0x38,%rsp
      1ef07b:	4c 39 76 08          	cmp    %r14,0x8(%rsi)
      1ef07f:	0f 84 f2 01 00 00    	je     1ef277 <_PySet_AddTakeRef+0x217>
        return PyObject_Hash(op);
    ...
  6. aisk commented on Aug 14, 2025

    @aisk
    Member

    I guess maybe the set comparisons in set_intersection may use most of the time, so the optimization by _PyObject_HashFast is hard to observe. If you want to dig into it, maybe you can use some perf tools to generate a flamegraph to ensure that.

    And I guess we just forgot to use the fast path in set_intersection, so I think if changing it to use _PyObject_HashFast doesn't introduce performance regression or break the tests, we should do that, at least for code consistency.

  7. JasonMendoza2008 commented on Aug 14, 2025

    @JasonMendoza2008
    ContributorAuthor

    Here are the results of some benchmarks (3.13.6).

    Code used:

    Sets of integers (shouldn't be faster)

    import statistics
    import timeit
    
    my_set: set[int] = set(range(1, 1000))
    
    other_has: set[int] = set()
    other_miss: set[int] = set()
    
    other_has: set[int] = set()
    for i in range(1, 1000):
        other_has.add(i)
    other_miss: set[int] = set()
    for i in range(1, 1000):
        other_miss.add(i + 1<<10)
    
    
    N: int = 10_000
    R: int = 100
    
    times = timeit.repeat(
        stmt="my_set & other_has",
        globals=globals(),
        number=N,
        repeat=R
    )
    avg = statistics.mean(times)
    std_dev = statistics.stdev(times)
    
    print("Intersection (elements present)")
    print(f"Average: {avg:.6f} s")
    print(f"Std Dev: {std_dev:.6f} s")
    
    times = timeit.repeat(
        stmt="my_set & other_miss",
        globals=globals(),
        number=N,
        repeat=R
    )
    avg = statistics.mean(times)
    std_dev = statistics.stdev(times)
    
    print("Intersection (elements not present)")
    print(f"Average: {avg:.6f} s")
    print(f"Std Dev: {std_dev:.6f} s")

    Sets of strings (should be faster)

    import statistics
    import timeit
    
    my_set: set[str] = set()
    for i in range(1, 1000):
        my_set.add('a'*i)
    
    other_has: set[str] = set()
    for i in range(1, 1000):
        other_has.add('a'*i)
    other_miss: set[str] = set()
    for i in range(1, 1000):
        other_miss.add('b'*i)
    
    N: int = 10_000
    R: int = 100
    
    times = timeit.repeat(
        stmt="my_set & other_has",
        globals=globals(),
        number=N,
        repeat=R
    )
    avg = statistics.mean(times)
    std_dev = statistics.stdev(times)
    
    print("Intersection (elements present)")
    print(f"Average: {avg:.6f} s")
    print(f"Std Dev: {std_dev:.6f} s")
    
    times = timeit.repeat(
        stmt="my_set & other_miss",
        globals=globals(),
        number=N,
        repeat=R
    )
    avg = statistics.mean(times)
    std_dev = statistics.stdev(times)
    
    print("Intersection (elements not present)")
    print(f"Average: {avg:.6f} s")
    print(f"Std Dev: {std_dev:.6f} s")
    Results (ran twice code above) without _PyObject_HashFast() (compiled with .\PCbuild\build.bat -e -p x64 --pgo):

    Ints:

    Intersection (elements present)
    Average: 0.123058 s / 0.123549 s
    Std Dev: 0.002149 s
    Intersection (elements not present)
    Average: 0.041472 s / 0.041177 s
    Std Dev: 0.000676 s

    Strs:

    Intersection (elements present)
    Average: 0.419300 s / 0.427943 s
    Std Dev: 0.009181 s
    Intersection (elements not present)
    Average: 0.061348 s / 0.063373 s
    Std Dev: 0.001024 s
    Results (ran twice code above) with _PyObject_HashFast() (compiled with .\PCbuild\build.bat -e -p x64 --pgo):

    Ints:

    Intersection (elements present)
    Average: 0.122205 s / 0.122734 s
    Std Dev: 0.000860 s
    Intersection (elements not present)
    Average: 0.047335 s / 0.047299 s
    Std Dev: 0.000556 s

    Strs:

    Intersection (elements present)
    Average: 0.414650 s / 0.416520 s
    Std Dev: 0.009340 s
    Intersection (elements not present)
    Average: 0.059868 s / 0.058166 s
    Std Dev: 0.001212 s

    tl;dr that works. Not sure why intersection of sets that are vastly different is so much faster, probably PGO linked but that's out of scope for this issue (EDIT: I used my brain and I realize it makes sense).

    Since it improves code consistency and seems to have small performance benefits (although, as expected it (can) degrade the performance of set[int], but that's for any function that uses _PyObject_HashFast()), should I open a PR?

  8. removed
    pendingThe issue will be closed if no feedback is provided
    on Aug 14, 2025
  9. aisk commented on Aug 14, 2025

    @aisk
    Member

    I'm not sure, maybe we can wait for a core dev to do the decision.

  10. ZeroIntensity commented on Aug 14, 2025

    @ZeroIntensity
    Member

    Try the benchmark on some string objects. _PyObject_HashFast simply uses the cached hash for string objects, and falls back to PyObject_Hash if it's not a string object or the hash hasn't been computed on it already. It makes sense that you don't see any speedup for integers, because _PyObject_HashFast has no fast-path for them.

  11. 18 remaining items

  12. serhiy-storchaka commented on Aug 14, 2025

    @serhiy-storchaka
    Member

    Don't add more code in PyObject_Hash(). This will only make the general case slower.

  13. ZeroIntensity commented on Aug 14, 2025

    @ZeroIntensity
    Member

    I agree in general, but a very common case for PyObject_Hash is to hash a string. I don't think that a simple PyUnicode_CheckExact will regress performance in any noticeable way for non-strings, and users will probably be happy about the speedup.

  14. added 2 commits that reference this issue on Aug 15, 2025
  15. vstinner commented on Dec 8, 2025

    @vstinner
    Member

    @aisk:

    And I guess we just forgot to use the fast path in set_intersection, so I think if changing it to use _PyObject_HashFast doesn't introduce performance regression or break the tests, we should do that, at least for code consistency.

    I agree. Just use _PyObject_HashFast() in set_intersection() to make it consistent with setobject.c.

  16. vstinner commented on Dec 8, 2025

    @vstinner
    Member
  17. MojoVampire commented on May 18, 2026

    @MojoVampire
    Contributor

    @vstinner:

    I agree. Just use _PyObject_HashFast() in set_intersection() to make it consistent with setobject.c.

    Shouldn't it be the other way around? _PyObject_HashFast should only be used in dict code because that's the case where str keys are considered unusually common (because every namespace in Python is a str keyed dict). It's not a fast hash, it's just faster for str (at the expense of code bloat and slower for everything else). In set, we don't specialize for any given type, because set[str] is no more common than any other set, and optimizing for set[str] slows all the others.

    I'm having a hard time coming up with a reason why we would use _PyObject_HashFast in set that wouldn't immediately imply we should just make literally every call to PyObject_Hash become _PyObject_HashFast across the entire codebase (and then make it public to replace PyObject_Hash, cause if it's good for every hash-based thing, why not have everyone use it instead)?

  18. added a commit that references this issue on May 31, 2026
  19. added 3 commits that reference this issue on Jun 14, 2026
  20. added a commit that references this issue on Jun 15, 2026
  21. vstinner commented on Jun 15, 2026

    @vstinner
    Member

    At the end, it was decided to only use the hash function specialized for (Unicode) strings on dictionaries, and replace it with generic PyObject_Hash() in setobject.c.

  22. added a commit that references this issue on Jun 17, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    interpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usagetype-refactorCode refactoring (with no changes in behavior)

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions