Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Is Python Code Sensitive to CPU Caching? (2024)

lukasatkinson.de

Post reply on HN
Print view View original

21–30 of 39 posts

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

#21

Post by exyi »

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.

It corresponds to a way more than one branch at instruction level. The branch prediction AFAIK does not care based on what are you branching, it just assumes branches will go in similar sequences as they did last time. If the Python 'if' is never taken, the instruction-level predictor will learn that after the comparison operation, there is an 'if' operation and then another array access operation. If the Python 'if' is unpredictable unpredictable, CPU predictor can't be sure which opcode are we processing after 'if', so there will be penalty.

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

#22

Post by bgwalter »

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?

That seems very likely. The benchmark should probably use a range that is guaranteed to be outside of the cached smallint range.

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

#23

Post by mardifoufs »

exyi wrote: post #21
almostgotcaught wrote: post #15

Earlier quoted context omitted.

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.

It corresponds to a way more than one branch at instruction level. The branch prediction AFAIK does not care based on what are you branching, it just assumes branches will go in similar sequences as they did last time. If the Python 'if' is never taken, the instruction-level predictor will learn that after the comparison operation, there is an 'if' operation and then another array access operation. If the Python 'if'…

Is there any public documentation on modern branch prediction algorithms? I know branch prediction is very important to modern CPU so SOTA techniques are probably not public... But it's really amazing what it can do especially considering the "limited" cache sizes that branch predictors have .

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

#25

Post by adgjlsfhk1 »

eulgro wrote: post #17
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.

the counterpoint is that a lot of those 20 instructions are also branches

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

#26

Post by cma »

exyi wrote: post #19
cma wrote: post #16

Earlier quoted context omitted.

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…

How big is the pointed to small integer? With alignment etc. I'm seeing some stuff saying 256 of them would fill an 8KB L1. Plus other stuff for the interpreter might overfill it. Sorted that would be less of an issue.

Larger range one being slower unsorted yes makes sense because of allocation order no longer matching the iteration order.

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

#27

Post by exyi »

cma wrote: post #26
exyi wrote: post #19

Earlier quoted context omitted.

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…

How big is the pointed to small integer? With alignment etc. I'm seeing some stuff saying 256 of them would fill an 8KB L1. Plus other stuff for the interpreter might overfill it. Sorted that would be less of an issue. Larger range one being slower unsorted yes makes sense because of allocation order no longer matching the iteration order.

I don't know how large are those boxes, but normal CPU L1 cache has 32 or 48KB which should be plenty for this. Python opcodes for this program are going to be tiny, and the interpreter itself uses the instruction-L1 cache (which is another 32-48KB). I hope the sequential scan of the big array won't flush the L1 cache (there should be 12-way associativity with LRU, so I don't see how it could).

Anyway, there is no need to have 256 integers, just 2 is enough. When I try that, the results are similar: 17.5 ms (unsorted) / 12.5 ms (sorted)

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

#28

Post by exyi »

mardifoufs wrote: post #23
exyi wrote: post #21

Earlier quoted context omitted.

It corresponds to a way more than one branch at instruction level. The branch prediction AFAIK does not care based on what are you branching, it just assumes branches will go in similar sequences as they did last time. If the Python 'if' is never taken, the instruction-level predictor will learn that after the comparison operation, there is an 'if' operation and then another array access operation. If the Python 'if'…

Is there any public documentation on modern branch prediction algorithms? I know branch prediction is very important to modern CPU so SOTA techniques are probably not public... But it's really amazing what it can do especially considering the "limited" cache sizes that branch predictors have .

I guess it depends on how deep you want to go, I think the real predictors are based on publicly known algorithms such as TAGE. This seems to be nice overview: https://comparch.net/2013/06/30/why-tage-is-the-best/ (it's 2013, so definitely not SOTA, but advanced enough for my taste :) )

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

#29

Post by exyi »

bgwalter wrote: post #22
cma wrote: post #16

Earlier quoted context omitted.

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?

That seems very likely. The benchmark should probably use a range that is guaranteed to be outside of the cached smallint range.

Then you are back to what the article discusses. Each integer is in a separate box, those boxes are allocated in one order, sorting the array by value will shuffle it by address and it will be much slower. I tested this as well, see the other comment.
Post reply on HN