Shouldn't `set_intersection` use `_PyObject_HashFast()`?

[JasonMendoza2008]

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

cpython/Objects/setobject.c

Line 1453 in 2a6888e

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

• GH-137759:Limit _PyObject_HashFast to dicts keys, rename it, and mark it as Py_ALWAYS_INLINE #137828

[StanFromIreland]

cc @aisk (294e724)

[aisk]

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.

[JasonMendoza2008]

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.

[aisk]

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);
...

[aisk]

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.

[JasonMendoza2008]

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?

[aisk]

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

[ZeroIntensity]

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.