Is Python Code Sensitive to CPU Caching? (2024) • Hacker News Board

Re: Is Python Code Sensitive to CPU Caching? (2024)

#11

Post by ammar2 » Sat, Apr 05, 2025, 2:43 PM UTC

exyi wrote: post #10

PhilipRoman wrote: post #2

IME CPU caches can be observed in almost all languages, regardless of how detached they are from the machine. What I'm really wondering is, if branch prediction can be observed from interpreted code.

It is! Although my test case is probably an unrealistically bad scenario: It's the classic, why is processing sorted array faster than unsorted one def f(arr): r = True for x in arr: if x > 128: r = not r return r arr = [ random.randint(0, 255) for i in range(0, 1000_000) ] arr_sorted = list(sorted(arr)) %timeit f(arr) %timeit f(arr_sorted) Results are (on my machine): 17.5 ms for unsorted, and 13.5 ms for sorted. Fo…

Edit: Analyzed the wrong thing earlier.

This depends on the Python version, but if it has the specializing interpreter changes, the `COMPARE_OP` comparing the integers there is probably hitting a specialized `_COMPARE_OP_INT` [1].

This specialization has a ternary that does `res = (sign_ish & oparg) ? PyStackRef_True : PyStackRef_False;`. This might be the branch that ends up getting predicted correctly?

Older versions of Python go through a bunch of dynamic dispatch first and then end up with a similar sort of int comparison in `long_richcompare`. [2]

[1] https://github.com/python/cpython/blob/561965fa5c8314dee5b86...

[2] https://github.com/python/cpython/blob/561965fa5c8314dee5b86...

Re: Is Python Code Sensitive to CPU Caching? (2024)

#12

Post by GBhpkmY » Sat, Apr 05, 2025, 2:52 PM UTC

exyi wrote: post #10

PhilipRoman wrote: post #2

IME CPU caches can be observed in almost all languages, regardless of how detached they are from the machine. What I'm really wondering is, if branch prediction can be observed from interpreted code.

It is! Although my test case is probably an unrealistically bad scenario: It's the classic, why is processing sorted array faster than unsorted one def f(arr): r = True for x in arr: if x > 128: r = not r return r arr = [ random.randint(0, 255) for i in range(0, 1000_000) ] arr_sorted = list(sorted(arr)) %timeit f(arr) %timeit f(arr_sorted) Results are (on my machine): 17.5 ms for unsorted, and 13.5 ms for sorted. Fo…

[dead]

Re: Is Python Code Sensitive to CPU Caching? (2024)

#13

Post by dzaima » Sat, Apr 05, 2025, 2:52 PM UTC

ammar2 wrote: post #11

exyi wrote: post #10

Earlier quoted context omitted.

It is! Although my test case is probably an unrealistically bad scenario: It's the classic, why is processing sorted array faster than unsorted one def f(arr): r = True for x in arr: if x > 128: r = not r return r arr = [ random.randint(0, 255) for i in range(0, 1000_000) ] arr_sorted = list(sorted(arr)) %timeit f(arr) %timeit f(arr_sorted) Results are (on my machine): 17.5 ms for unsorted, and 13.5 ms for sorted. Fo…

Edit: Analyzed the wrong thing earlier. This depends on the Python version, but if it has the specializing interpreter changes, the `COMPARE_OP` comparing the integers there is probably hitting a specialized `_COMPARE_OP_INT` [1]. This specialization has a ternary that does `res = (sign_ish & oparg) ? PyStackRef_True : PyStackRef_False;`. This might be the branch that ends up getting predicted correctly? Older versio…

This isn't actually timing the sorting, but just the (dumb) function f.

Re: Is Python Code Sensitive to CPU Caching? (2024)

#14

Post by ammar2 » Sat, Apr 05, 2025, 3:07 PM UTC

dzaima wrote: post #13

ammar2 wrote: post #11

Earlier quoted context omitted.

Edit: Analyzed the wrong thing earlier. This depends on the Python version, but if it has the specializing interpreter changes, the `COMPARE_OP` comparing the integers there is probably hitting a specialized `_COMPARE_OP_INT` [1]. This specialization has a ternary that does `res = (sign_ish & oparg) ? PyStackRef_True : PyStackRef_False;`. This might be the branch that ends up getting predicted correctly? Older versio…

This isn't actually timing the sorting, but just the (dumb) function f.

Oh whoops, that's right. I totally missed that.

Re: Is Python Code Sensitive to CPU Caching? (2024)

#15

Post by almostgotcaught » Sat, Apr 05, 2025, 3:08 PM UTC

vlovich123 wrote: post #9

PhilipRoman wrote: post #2

IME CPU caches can be observed in almost all languages, regardless of how detached they are from the machine. What I'm really wondering is, if branch prediction can be observed from interpreted code.

Why would you think that branch prediction wouldn’t be? Do you think the interpreter is adding too much false sharing to the branch predictor to render it worthless?

you do realize that the Python

  if x > 128: 
     r = not r

doesn't necessarily correspond to one branch at the ASM instruction level right? in fact, a priori, it doesn't even correspond to absolutely any branches at the ASM instruction level.

Re: Is Python Code Sensitive to CPU Caching? (2024)

#16

Post by cma » Sat, Apr 05, 2025, 3:10 PM UTC

exyi wrote: post #10

PhilipRoman wrote: post #2

IME CPU caches can be observed in almost all languages, regardless of how detached they are from the machine. What I'm really wondering is, if branch prediction can be observed from interpreted code.

It is! Although my test case is probably an unrealistically bad scenario: It's the classic, why is processing sorted array faster than unsorted one def f(arr): r = True for x in arr: if x > 128: r = not r return r arr = [ random.randint(0, 255) for i in range(0, 1000_000) ] arr_sorted = list(sorted(arr)) %timeit f(arr) %timeit f(arr_sorted) Results are (on my machine): 17.5 ms for unsorted, and 13.5 ms for sorted. Fo…

Python speed up is probably from small integer caching, a sorted array will have runs of pointers to the same integers adjacent. The compiled language one is probably branch prediction right?

Re: Is Python Code Sensitive to CPU Caching? (2024)

#17

Post by eulgro » Sat, Apr 05, 2025, 3:43 PM UTC

PhilipRoman wrote: post #2

IME CPU caches can be observed in almost all languages, regardless of how detached they are from the machine. What I'm really wondering is, if branch prediction can be observed from interpreted code.

My guess would be that branch misprediction does have an impact on interpreted language, but much less. If bytecode instructions take on average 20 CPU cycles to execute, and the branch misprediction penalty is 50 CPU cycles, the relative cost of a misprediction is much smaller than in compiled code.

Re: Is Python Code Sensitive to CPU Caching? (2024)

#18

Post by vlovich123 » Sat, Apr 05, 2025, 4:05 PM UTC

almostgotcaught wrote: post #15

vlovich123 wrote: post #9

Earlier quoted context omitted.

Why would you think that branch prediction wouldn’t be? Do you think the interpreter is adding too much false sharing to the branch predictor to render it worthless?

you do realize that the Python if x > 128: r = not r doesn't necessarily correspond to one branch at the ASM instruction level right? in fact, a priori, it doesn't even correspond to absolutely any branches at the ASM instruction level.

Yes I do and that’s neither here nor there. There almost certainly ASM instruction level branches to implement the conditional and the branch predictor isn’t tied to a single instruction - the rough high level mental model is a cache of a few of the least significant digits of the CPU to the prediction although in practice it’s far more complicated. Since the predictor is right like 80% of the time, it means that even when there’s false sharing of a lot of branches, the CPU does a good job predicting. It’s performance is primarily impacted when execution takes both branches closer to 50/50 than to 100/0.

That’s why I asked about false sharing specifically as that’s the main way I can think of that Python code wouldn’t be able to observe the branch predictor performance - because the interpreter has so many branches internally that it dominates any branches that might be caused by the Python code itself.

Re: Is Python Code Sensitive to CPU Caching? (2024)

#19

Post by exyi » Sat, Apr 05, 2025, 4:37 PM UTC

cma wrote: post #16

exyi wrote: post #10

Earlier quoted context omitted.

It is! Although my test case is probably an unrealistically bad scenario: It's the classic, why is processing sorted array faster than unsorted one def f(arr): r = True for x in arr: if x > 128: r = not r return r arr = [ random.randint(0, 255) for i in range(0, 1000_000) ] arr_sorted = list(sorted(arr)) %timeit f(arr) %timeit f(arr_sorted) Results are (on my machine): 17.5 ms for unsorted, and 13.5 ms for sorted. Fo…

Python speed up is probably from small integer caching, a sorted array will have runs of pointers to the same integers adjacent. The compiled language one is probably branch prediction right?

I intentionally stayed in the small integer range to avoid benchmarking the cache. 256 distinct values should fit into L1 just fine in both cases.

I'm now thinking that the difference might be even larger if we instead avoid small integers and let the CPU get stuck chasing pointers. The idea is that it gets stuck on a memory access, which forces it to speculate much further, which in turn makes it backtrack a longer path if a branch was mispredicted. I'm obviously no expert on this, feel free to correct me

The results for 1B range instead of 255 are 17.6 ms for unsorted / 68.2 ms for sorted! We are back to what the original article observed and it's a way stronger effect than what branch prediction can offer. So don't sort your arrays, keep them in the order the boxed values were allocated ;)

Re: Is Python Code Sensitive to CPU Caching? (2024)

#20

Post by LPisGood » Sat, Apr 05, 2025, 4:40 PM UTC

exyi wrote: post #10

PhilipRoman wrote: post #2

IME CPU caches can be observed in almost all languages, regardless of how detached they are from the machine. What I'm really wondering is, if branch prediction can be observed from interpreted code.

It is! Although my test case is probably an unrealistically bad scenario: It's the classic, why is processing sorted array faster than unsorted one def f(arr): r = True for x in arr: if x > 128: r = not r return r arr = [ random.randint(0, 255) for i in range(0, 1000_000) ] arr_sorted = list(sorted(arr)) %timeit f(arr) %timeit f(arr_sorted) Results are (on my machine): 17.5 ms for unsorted, and 13.5 ms for sorted. Fo…

This is a really good example. It is more like branch prediction than standard data/instruction caching.

I wonder if you could do Spectre type vulnerabilities in python. You would need some way to leak micro-architectural state, so without being particularly clever maybe python code could only be used as a gadget or something.