Is Python Code Sensitive to CPU Caching? (2024)

Summary

Cache-aware programming can make a huge performance difference, especially when writing code in C++ or Rust. Python is a much more high-level language, and doesn't give us that level of control over memory layout of our data structures. So does this mean that CPU caching effects aren't relevant in Python? In this post, we'll conduct some basic experiments to answer this question, by accessing list element either in sequental order or in a random order. Results indicate that randomized access is consistently slower in Python. Especially as soon as problem sizes outgrow the CPU cache sizes, random access is multiple times slower. Thus, some degree of cache-aware programming may be relevant in interpreted environments like CPython 3.12 as well. Disclaimers: Results may vary on different software and hardware. The software used for these tests is CPython 3.12. The CPU uses the x86-64 (amd64) architecture, Zen 2 microarchitecture. This CPU generation had a fairly complex cache hierarchy due to grouping cores in separate "core complexes" that partially share some of their cache. Each core should see up to 32KB L1, 512KB L2, 16MB L3. Background Programs store data in memory (RAM), but this is slow. CPU caches are faster, but much smaller. The CPU has to decide which parts of the RAM to load into the caches. Of course explicitly accessed memory addresses will be loaded into the cache. But the act of loading data is comparatively slow, so the CPU will try to pre-load relevant data. For example, we can expect the CPU to detect linear array access patterns and automatically pre-load the next chunks of an array. So foreach style loops over an array where all relevant data is directly inside the array can be quite cache-friendly, whereas random access cannot be predicted. In practice, many arrays contain pointers instead. We must dereference the pointer to a different memory location in order to get to the actual data. Maybe the pointed-to location is already in the cache, maybe...