Is Python Code Sensitive to CPU Caching? (2024)

https://lukasatkinson.de/2024/python-cpu-caching/

by leonry • 1 year ago

81 33 1 year ago

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.

stingraycharles• 1 year ago

It should be, as most interpreted code uses a JIT native compiler at this point, which implies the branch prediction is native as well.

I would be happy to stand corrected if someone knows more about this, though!

tarruda• 1 year ago

AFAIK CPython doesn't JIT compile.

pansa22• 1 year ago

most interpreted code uses a JIT native compiler at this point

I suspect most JavaScript code is JIT-compiled - but most Python, Ruby etc is interpreted (via bytecode).

vlovich1232• 1 year ago

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?

almostgotcaught• 1 year ago

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.

exyi6• 1 year ago

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. For comparison, in a compiled language, the difference is 4x

ammar22• 1 year ago

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

cma2• 1 year ago

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?

LPisGood• 1 year ago

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.

eulgro• 1 year ago

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.

adgjlsfhk1• 1 year ago

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

saagarjha• 1 year ago

Yep, this is why Spectre mitigations are applied to browsers.

PaulHoule• 1 year ago

"Mechanical sympathy" effects are so strong on modern CPUs you feel them even in languages like Python that are far from the metal.

davvid• 1 year ago

The article didn't mention Python's atomic refcounts. They're very bad for cache usage as they're constantly invalidating cache.

quotemstr• 1 year ago

The only version of Python that uses atomic reference counting is the very new free threaded version.

senderista• 1 year ago

Non-atomic refcounts invalidate cache as well, they're just not as expensive.

Delk2• 1 year ago

I really don't see why you wouldn't expect to find cache-sensitivity in Python, or in some other similarly high-level language.

Python sequences are defined as "support[ing] efficient element access using integer indices" [1]. Python lists are sequences and thus must support random access. In practice that means the implementation is a (dynamically resizing) array allocated contiguously. That means spatial locality is relevant.

If the list type were defined simply as an iterable collection, with no requirement of constant-time random access, the definition would be abstract enough that an implementation might end up being something else than a contiguous array. But if you define the type so that it supports constant-time random access [2], you pretty much end up with cache-friendly sequential access as well.

If you don't define the list type as supporting random access, you also sacrifice asymptotic algorithmic efficiency for lookups by index. Any language that cares about efficiency at all separates collections that support efficient random access from those that don't. (For example, Python has lists and dicts/sets for different access patterns. The Java standard library has separate types for contiguous arrays/lists, hashtable-backed collections and tree-backed collections because the three have different algorithmic efficiencies for different access patterns. In practice it leads to different properties in terms of cache-friendliness as well.)

[1] https://docs.python.org/3/glossary.html#term-sequence

[2] As usual, the Python documentation is a bit vague on the details. It doesn't really say random access has to be constant-time, only that it has to be "efficient". So you might be able to have a non-constant time implementation such as an indexable skiplist while arguing that it's efficient, but you'd have to go out of your way to do that.

zahlman• 1 year ago

I really don't see why you wouldn't expect to find cache-sensitivity in Python, or in some other similarly high-level language... Python lists are sequences and thus must support random access. In practice that means the implementation is a (dynamically resizing) array allocated contiguously.

The contents of the dynamically allocated array, in the C implementation, are pointers (PyObject), since the lists are heterogeneous and must be able to store any Python object. That entails indirection, which defeats spatial locality. Even if you iterate over cached data, you have to jump around to retrieve the actual objects to do anything* with them.

Delk2• 1 year ago

Sure. But that's one less level of indirection than if you also had to jump around to get the reference to the object in the first place.

Is Python Code Sensitive to CPU Caching? (2024)

Related Stories