You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Shouldn't set_intersection use _PyObject_HashFast()? #137759
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).
changed the title [-]Shouldn't `set_intersection` use `_PyObjectHashFast()`?[/-][+]Shouldn't `set_intersection` use `_PyObject_HashFast()`?[/+]on Aug 14, 2025
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:
_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.
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).
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.
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:
_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.
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).
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.
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).
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.
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?
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 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.
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.
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)?
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.
Activity
[-]Shouldn't `set_intersection` use `_PyObjectHashFast()`?[/-][+]Shouldn't `set_intersection` use `_PyObject_HashFast()`?[/+]StanFromIreland commentedon Aug 14, 2025
cc @aisk (294e724)
aisk commentedon Aug 14, 2025
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_intersectionwas already just calling thePyObject_Hashinstead 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_HashFastis not faster thanPyObject_Hash, I'm not very familiar with assembly or C compilers, but I guess it may be caused by these reasons:_PyObject_HashFastis 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.JasonMendoza2008 commentedon Aug 14, 2025
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_HashFasthere.aisk commentedon Aug 14, 2025
Hi, I built current main branch on Debian12 with
--enable-optimizations, and I can ensure that_PyObject_HashFastis inlined (at least in_PySet_AddTakeRef).aisk commentedon Aug 14, 2025
I guess maybe the set comparisons in
set_intersectionmay use most of the time, so the optimization by_PyObject_HashFastis 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_HashFastdoesn't introduce performance regression or break the tests, we should do that, at least for code consistency.JasonMendoza2008 commentedon Aug 14, 2025
Here are the results of some benchmarks (3.13.6).
Code used:
Sets of integers (shouldn't be faster)
Sets of strings (should be faster)
Results (ran twice code above) without _PyObject_HashFast() (compiled with .\PCbuild\build.bat -e -p x64 --pgo):
Ints:
Strs:
Results (ran twice code above) with _PyObject_HashFast() (compiled with .\PCbuild\build.bat -e -p x64 --pgo):
Ints:
Strs:
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?aisk commentedon Aug 14, 2025
I'm not sure, maybe we can wait for a core dev to do the decision.
ZeroIntensity commentedon Aug 14, 2025
Try the benchmark on some string objects.
_PyObject_HashFastsimply uses the cached hash for string objects, and falls back toPyObject_Hashif 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_HashFasthas no fast-path for them.18 remaining items
serhiy-storchaka commentedon Aug 14, 2025
Don't add more code in
PyObject_Hash(). This will only make the general case slower.ZeroIntensity commentedon Aug 14, 2025
I agree in general, but a very common case for
PyObject_Hashis to hash a string. I don't think that a simplePyUnicode_CheckExactwill regress performance in any noticeable way for non-strings, and users will probably be happy about the speedup.pythonGH-137759:Limit _PyObject_HashFast dicts keys, rename it, and m…
pythonGH-137759:Limit _PyObject_HashFast to dicts keys, rename it, an…
vstinner commentedon Dec 8, 2025
@aisk:
I agree. Just use
_PyObject_HashFast()inset_intersection()to make it consistent withsetobject.c.vstinner commentedon Dec 8, 2025
cc @rhettinger
MojoVampire commentedon May 18, 2026
@vstinner:
Shouldn't it be the other way around?
_PyObject_HashFastshould only be used indictcode because that's the case wherestrkeys are considered unusually common (because every namespace in Python is astrkeyeddict). It's not a fast hash, it's just faster forstr(at the expense of code bloat and slower for everything else). Inset, we don't specialize for any given type, becauseset[str]is no more common than any otherset, and optimizing forset[str]slows all the others.I'm having a hard time coming up with a reason why we would use
_PyObject_HashFastinsetthat wouldn't immediately imply we should just make literally every call toPyObject_Hashbecome_PyObject_HashFastacross the entire codebase (and then make it public to replacePyObject_Hash, cause if it's good for every hash-based thing, why not have everyone use it instead)?pythonGH-137759: Limit _PyObject_HashFast to dict keys
Added reference to pythongh-137759 in the comments
pythonGH-137759: Limit _PyObject_HashFast to dict keys
pythonGH-137759: Limit _PyObject_HashFast to dict keys
gh-137759: Replace _PyObject_HashFast() with PyObject_Hash() in setob…
vstinner commentedon Jun 15, 2026
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.
pythongh-137759: Replace _PyObject_HashFast() with PyObject_Hash() in…