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. JasonMendoza2008 commented on Aug 14, 2025

    @JasonMendoza2008
    ContributorAuthor

    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.

    I did though? I just also tried it on ints to make sure it doesn't degrade performance too much, but that was just a "negative control".

  2. ZeroIntensity commented on Aug 14, 2025

    @ZeroIntensity
    Member

    Oh, sorry, where? The benchmark here contains integers.

  3. JasonMendoza2008 commented on Aug 14, 2025

    @JasonMendoza2008
    ContributorAuthor

    Oh, sorry, where? The benchmark here contains integers.

    There are two benchmarks here: #137759 (comment)

  4. serhiy-storchaka commented on Aug 14, 2025

    @serhiy-storchaka
    Member

    I suppose that all uses of _PyObject_HashFast() are in dict? Dicts are specially optimized for string keys, because dicts are used to save class and instance attributes. This is essential to performance of Python in general. On other hand, string-only sets are not so omnipresent.

  5. JasonMendoza2008 commented on Aug 14, 2025

    @JasonMendoza2008
    ContributorAuthor

    I suppose that all uses of _PyObject_HashFast() are in dict? Dicts are specially optimized for string keys, because dicts are used to save class and instance attributes. This is essential to performance of Python in general. On other hand, string-only sets are not so omnipresent.

    Everywhere else in setobject.c _PyObject_HashFast() is used. I agree that the argument for _PyObject_HashFast() is less relevant for sets but then why are we using it here for example

    Py_hash_t hash = _PyObject_HashFast(key);

  6. ZeroIntensity commented on Aug 14, 2025

    @ZeroIntensity
    Member

    @serhiy-storchaka Do we need _PyObject_HashFast at all? I think it would be fine to move the fast path to PyObject_Hash. Users will enjoy the speed up.

  7. JasonMendoza2008 commented on Aug 14, 2025

    @JasonMendoza2008
    ContributorAuthor

    @serhiy-storchaka Do we need _PyObject_HashFast at all? I think it would be fine to move the fast path to PyObject_Hash. Users will enjoy the speed up.

    Agreed although we do not need the fast path present in _PyObject_HashFast for hashsets. As seen above, although it improves set[str] by 2-8% it makes set[int] 14% slower if we look at the case where we intersect two sets that are completely different.

  8. serhiy-storchaka commented on Aug 14, 2025

    @serhiy-storchaka
    Member

    I would say that using _PyObject_HashFast for anything that is not a __dict__ key is misuse.

    I am not even sure that moving the code into inline function was right. Inline function is not always inlined, and we should be sure that the fast path for string is inlined in the dict code, otherwise it is a pessimization rather than an optimization.

  9. serhiy-storchaka commented on Aug 14, 2025

    @serhiy-storchaka
    Member

    I suggest to rename _PyObject_HashFast, its name is misleading. It is not just a "better PyObject_Hash", it should only be used for keys in dicts with string-only keys -- or, more narrowly, only for attribute names.

  10. ZeroIntensity commented on Aug 14, 2025

    @ZeroIntensity
    Member

    Agreed, I think we should do two things here:

    1. Rename _PyObject_HashFast to _PyObject_HashAttribute or _PyObject_HashDictKey, and then mark it as Py_ALWAYS_INLINE.
    2. Include a fast path for strings in PyObject_Hash, but not inline the whole function. At a glance, we could probably add a fast path for integers as well?

    I'll work on this if you aren't already.

  11. JasonMendoza2008 commented on Aug 14, 2025

    @JasonMendoza2008
    ContributorAuthor

    -- or, more narrowly, only for attribute names.

    I'd assume a lot of dict usage is with JSON string keys as well, so probably not limited to class and instance attributes.

  12. JasonMendoza2008 commented on Aug 14, 2025

    @JasonMendoza2008
    ContributorAuthor

    At a glance, we could probably add a fast path for integers as well?

    The more fast paths for certain types, the slower it gets for other types, right? Is adding a fast path worth it for integers?

  13. ZeroIntensity commented on Aug 14, 2025

    @ZeroIntensity
    Member

    I don't think that a fast path for integers would add any noticeable overhead, but I'm speculating anyway.

  14. JasonMendoza2008 commented on Aug 14, 2025

    @JasonMendoza2008
    ContributorAuthor

    Agreed, I think we should do two things here:

    1. ...
    2. Include a fast path for strings in PyObject_Hash, but not inline the whole function. At a glance, we could probably add a fast path for integers as well?

    I think serhiy-storchaka was suggesting to leave the fast paths out of PyObject_Hash and just use them in dictobject.c.

  15. ZeroIntensity commented on Aug 14, 2025

    @ZeroIntensity
    Member

    Why not? Hashing strings is pretty common. We don't want people relying on the private API to get speedups.

  16. JasonMendoza2008 commented on Aug 14, 2025

    @JasonMendoza2008
    ContributorAuthor

    Why not? Hashing strings is pretty common. We don't want people relying on the private API to get speedups.

    That's a design decision, I'm probably not the right person to have an opinion. But I see the point of adding a fast path for strings and integers since they're likely to constitute most of hashing usage.


    and then mark it as Py_ALWAYS_INLINE.

    Also, https://peps.python.org/pep-0670/ mentions:

    Previous attempts to use Py_ALWAYS_INLINE didn’t show any benefit, and were abandoned. See for example bpo-45094 “Consider using __forceinline and attribute((always_inline)) on static inline functions (Py_INCREF, Py_TYPE) for debug build”.


    I'm down to work on this if that's ok

  17. ZeroIntensity commented on Aug 14, 2025

    @ZeroIntensity
    Member

    PEP 670 is talking very generally about force-inlining every static inline function we have (which is a lot). For something extremely hot (in this case, attribute access), we definitely want it to be inlined.

    I'm down to work on this if that's ok

    Go for it, but keep in mind that this isn't a trivial change.

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

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

  20. added 2 commits that reference this issue on Aug 15, 2025
  21. 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.

  22. vstinner commented on Dec 8, 2025

    @vstinner
    Member
  23. 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)?

  24. added a commit that references this issue on May 31, 2026
  25. added 3 commits that reference this issue on Jun 14, 2026
  26. added a commit that references this issue on Jun 15, 2026
  27. 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.

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