____ _ | __ )| | ___ __ _ | _ \| |/ _ \ / _` | | |_) | | (_) | (_| | |____/|_|\___/ \__, | |___/_ _ _/_| |__ ___ _ __| |_ _ _/_ / _ \ '_ \ / _ \ '__| | | | |/ _ \ __/ |_) | __/ | | | |_| | __/ \___|_.__/ \___|_| |_|\__,_|\___|
[2026-03-31][Systems]
I've always wondered how do you actually optimize memory caches. This notion seemed blury: how can you take into account machine cache with all the different hardware available today? Hearing a lot about Data Oriented Design (or Programming) was appealing but I tend to struggle understanding what it actually looked like in practice. This video introduced me to the concept, this one convinced me that I should look further than Oriented Objet Programming, and this last made my enlightenment. Jokes asides, what really helped me understanding those concepts was to expand my knowledge on computer architectures. The article What Every Programmer Should Know About Memory"]in particular is full of valuable informations, and is the topic of this post.
In the following, I provide a synthesis of my personnal notes, with more-or-less organized quotes and takeaways, but I highly encourage you to read the full article. You can jump directly to section What programmers can do if you want to take a look at optimizations.
While written in 2007, most postulates seems relevant to me:
Here follows some context about hardware and software related to memory.
There exists two types of RAM memory: SRAM (static) which is very fast but expensive due to many transistors needed, and DRAM (dynamic) is dramatically cheaper as it uses one transistor and a capacitor, but it makes it slower. Takeaways:
"Increasing the throughput of the DRAM chip is expensive since the energy consumption rises with the frequency."
For Single (or Synchronous apparently) Data Rate RAM (SDRAM): Power = Dynamic capacity x
Voltage² x Frequency Now Double Data Rate (DDR) RAM is the norm, it introduces a buffer so
that memory can be read with multiple buses.
"Instead of putting the SRAM under the control of the OS or user, it becomes a ressource which is transparently used and administered by the proccessors."
From my understanding: 1. When mentionning RAM, it usually refers to the main memory (the RAM sticks you buy and plug), it seems like it's always dynamic memory? And 2. Static memory is used for caches and registers, which are die on chip
"Realizing that locality exists is key to the concept of CPU caches as we use them today."
We can distinguish two kinds of locality:
Cores have individual level 1 caches both for data (L1d) and instructions (L1i), and today even L2 it seems. Other higher caches are shared between cores. For example on my laptop I have the following:
$ hwloc-ls
Machine (31GB total)
Package L#0
NUMANode L#0 (P#0 31GB)
L3 L#0 (12MB)
L2 L#0 (2048KB) + L1d L#0 (48KB) + L1i L#0 (64KB) + Core L#0
PU L#0 (P#0)
PU L#1 (P#1)
L2 L#1 (2048KB) + L1d L#1 (48KB) + L1i L#1 (64KB) + Core L#1
PU L#2 (P#2)
PU L#3 (P#3)
L2 L#2 (2048KB)
L1d L#2 (32KB) + L1i L#2 (64KB) + Core L#2 + PU L#4 (P#4)
L1d L#3 (32KB) + L1i L#3 (64KB) + Core L#3 + PU L#5 (P#5)
L1d L#4 (32KB) + L1i L#4 (64KB) + Core L#4 + PU L#6 (P#6)
L1d L#5 (32KB) + L1i L#5 (64KB) + Core L#5 + PU L#7 (P#7)
L2 L#3 (2048KB)
L1d L#6 (32KB) + L1i L#6 (64KB) + Core L#6 + PU L#8 (P#8)
L1d L#7 (32KB) + L1i L#7 (64KB) + Core L#7 + PU L#9 (P#9)
L1d L#8 (32KB) + L1i L#8 (64KB) + Core L#8 + PU L#10 (P#10)
L1d L#9 (32KB) + L1i L#9 (64KB) + Core L#9 + PU L#11 (P#11)
L2 L#4 (2048KB)
L1d L#10 (32KB) + L1i L#10 (64KB) + Core L#10 + PU L#12 (P#12)
L1d L#11 (32KB) + L1i L#11 (64KB) + Core L#11 + PU L#13 (P#13)
Where, PU is a Processing Unit, or hardware thread, and Core is a
physical core.
So here I have 1 CPU socket, 12 physical cores and 14 logical cores because two cores have hyper-threading enabled. L3 cache is shared among all cores. Each core have its respective L1d and L1i cache. L2 caches are shared among multiple cores, at the exception of performance cores, which have their own respective L2 caches.
Now we need to understand how data goes into the cache.
"By default all data read or written by the CPU cores is stored in the cache."
Data is stored as cache lines, which size is architecture dependant. Cache lines are pushed and evicted depending on different cache evicting methods such as LRU (Least Recently Used). When a line is pushed of a cache, it goes to the next level of cache until there is no more, then it goes to the main memory.
There is also the MESI cache coherency protocol:
They show the number of cycles to access memory on a intel pentium M, with memory type and their respective number of cycles to access memory:
When talking about instruction cache, things are less problematic:
To achieve the best performance there are only a few rules related to the instruction cache:
But compilers are so good nowadays, code size related optimizations can be directly performed by the compiler.
"If two threads are running on one hyper-threaded core the program is only more efficient than the single-threaded code if the combined runtime of both threads is lower than the runtime fo the single-threaded code."
This is because hyper-threads shares the same cache to load their data, effectively reducing its size, especially if the two threads are working on separate data. However, it is later explained that using hyper-threads with manual prefetching is actually super powerful!
"What should be clear is that if the two hyper-threads execute completely different code the cache size is indeed cut in half which means a significant increase in cache misses."
Hyper-thread usage should be situational.
"The virtual memory subsystem of a processor implements the virtual address spaces provided to each process. This makes each process think it is alone in the system. [...] Assuming all memory can be allocated contiguously is too simplistic [...] for flexibility reasons, the stack and the heap of a process are, in most cases, allocated at pretty much opposite ends fo the address space."
For security reasons, code, data, heap, stack, and Dynamic Shared Objects (shared libraries) are mapped at randomized addresses. It can be turned off at the mercy of security.
This section covers a non-exhaustive list of optimizations that I found interesting. First of all I really like this quote:
"For programmers, all these different designs mean complexity when making scheduling decisions: One has to know the workloads and the details of the machine architecture to achieve the best performance."
Sometimes, we might create data that won't be used right away. But still, it will push out of the
cache existing data in the cache. In this situation, one can use non-temporal write operations to
prevent poluting the cache by directly writing into the main memory. For example, using
void _mm_stream_si128(void *__p, __m128i __a)
/* Stores a 128-bit integer vector to a 128-bit aligned memory location.
To minimize caching, the data is flagged as non-temporal (unlikely to be used again soon).
This intrinsic corresponds to the VMOVNTPS / MOVNTPS instruction.
Parameters
__p A pointer to the 128-bit aligned memory location used to store the value.
__a A 128-bit integer vector containing the values to be stored.
*/
This works best when processing large amounts of data in one go. It seems that memset uses this for large blocks.
Optimizing L1 access gives the best results, but it also relieve some "stress" over the other caches. The goal here is to improve the locality both spatially and temporally, and align code with data.
One of the examples given is how you can improve the matrix-matrix multiplication by transposing the second term. Indeed, this improves spatiality, as it makes the second term being loop through by row, instead of doing so by column (obviously here data was represented as row-major, in column-major it would be the opposite). Though I a bit perplex of this solution as of 2026. Things have improved a lot and it seems that compilers are way better at handling matrices. It really reminds me of Im2win) though: they re-organize matrix indices so that sliding a kernel on it makes the data accesses contiguous. Anyways storing matrices differently depending on your task might be worth trying!
Next they also talk about loop unrolling, altough I think the compiler might be really good today? And doing some OpenMP is way easier. They also talk about SIMD, I won't go into further details here.
Then, we might want to optimize our structures depending on cache line sizes. First of all, to retrieve L1d cache line size, see sysconf:
sysconf(_SC_LEVEL1_DCACHE_LINESIZE)
Then with the program pahole, we can analyze the layout of our structures (this was took from the article):
struct foo {
int a; // 0 4
// XXX 4 bytes hole, try to pack
long int fill[7]; // 8 56
// --- cacheline 1 boundary (64 bytes)
int b; // 64 4
}; // size: 72, cachelines: 2
// sum members: 64, holes: 1, sum holes: 4
// padding: 4
// last cacheline: 8 bytes
Pahole can also reorganize fields automatically. Anyways, here are some takeways:
For bigger structures the goal is to pack data so that they fit correctly on multiple cache
lines. Setting alignment can also help, in gcc we can use __attribute((aligned(64))),
also it seems like there is also an attribute packed, see
gcc doc:
"This attribute, attached to an enum, struct, or union type definition, specifies that the minimum required memory be used to represent the type."
Lastly, one example clearly reminded me of ECS vs OOP (mentionned in the intro):
"While it is easier for the programmer to put all the dat which conceptually belongs together in the same data structure, this might not be the best approach for maximum performance."
For instance, given the following structure:
struct order {
double price;
bool paid;
const char* buyer[5];
long buyer_id;
}
If we mostly need to sum prices, then we might separate buyers fields so that they aren't loaded in cache. This is exactly what is explained in the beforementionned video. The problem with OOP is that it forces encapsulation of related data, while completly ignoring the reality of hardware.
"Compile time hierarchy does not need to match the domain model."
See Data Oriented Design, and Entity Component System.
On the same idea, optimizing L1i cache access is also important. As mentionned earlier, this is
mostly achieved by the compiler. Enabling -Os optimizes code size by disabling
optimizations such as unrolling and inlining.
The author says that inline should only be used on functions called just a few times: I actually though it was the opposite? For example inline a getter function that is called a lot of times. But it turns out it will create a lot of duplicated instructions (as many as different calls we have in the code).
About noinline attribute:
"Using this attribute makes sense even for small functions if they are called often from different places. If the L1i content can be reused and the overall footprint is reduced this often makes up for the additional cost of the extra function call."
Altough it is specified that this must be decided on a case-by-case basis.
Lastly on this part, even though branch prediction have gotten better and better, explicitly specifying jump likelyness can help:
#define likely(expr) __builtin__expect(!!(expr), 1)
#define unlikely(expr) __builtin__expect(!!(expr), 0)
// Then it is used as such:
if (likely(a > 1))
{
// ...
}
Last level caches are the fallback of smaller caches. Their own effective size is actually smaller as they are shared with other cores and/or hyper-threads.
"To avoid the high costs of cache misses, the working set size should be matched to the cache size. If the data is only needed onec, this obviously is not necessary since the cache would be ineffective anyway. [...] L1 cache line size is usually constant over many processors generations, even if not, differences will be small."
So assuming the largest size for L1 cache is OK, thus we can hardcode it. Although this statement is from 2007, I think dynamically getting the actual size is better than nothing. But concerning higher level caches, their sizes can vary a lot, so it must be taken into account dynamically: hardcoding a low estimation make you miss use a part of the cache, too high estimation will simply overflow on machines with tinier caches. The programmer should be able to compute (i.e. find a formula) the required memory needed, so it can be dynamically compared with cache size.
Translation lookaside buffer (TLB) makes the translation from virtual memory addresses to physical ones. It can be optimized by:
mmap +
MAP_FIXED value
On hardware prefetching:
"Prefetching has one big weakness: it cannot cross page boundaries. The reason should be obvious when one realizes that the CPUs support demand paging. If the prefetcher were allowed to cross page boundaries, the access might trigger an OS event to make the page available [...] the prefetcher does not know about the semmantic of the program or the OS itself."
Software level possibilities, we can note that gcc can insert prefetches in loops
with the compile flag -fprefetch-loop-arrays. Also we can do it ourselves:
"Programs can use the __mm_prefetch instrinsic on any pointer of the
program [...] if the passed pointer references valid memory, the prefetch unit will be instructed
to load the data into cache and, if necessary, evict other data"
Different values can be used to prefetch into specific caches:
MM_HINT_T0 into all levels of cache hierarchyMM_HINT_T1 into level 2 cache and higherMM_HINT_T2 into level 3 cache and higherMM_HINT_NTA for non-temporal aligned, minimizes cache pollution when the data will be
only used once, i.e, when data is evicted from L1d it won't be pushed to other caches. Just be
careful that the data can actually fit in L1d. Note this is implementation-dependent though.
Nevertheless, having to implement both iteration (logic) and prefetch and in the same sequential code can be tedious. The challenge is to be able to write prefetch code that comes with good timing, not too early or prefetched data will be evicted, and not too late otherwise prefetching is useless.
Another solution to avoid making sequential code where logic resides more complex is to use a **helper thread**. Its only job is to prefetch data at the correct timing. This becomes particularly interesting when using **hyper-threads**. As seen before, they do have problems if executed code is independent, as hyper-threads on the same core (pleonasm) will fight for the cache. However, this is not the case here when one of the thread is an helper thread.
"Furthemore, since the prefetch thread is mostly idle or waiting for memory, the normal operation of the other hyper-thead is not disturbed much if it does not have to access main memory itself. The latter is exactly what the prefetch helper prevents."
Attention should be paid to keep both threads synchronized though, using futex for
example. Otherwise the synergy seems really great and the idea is appealing!
There are three aspects to optimize concerning memory usage in threads:
Note: threads all share the same address space, so they can all access the same memory.
Some advices:
#define CLSIZE 64
struct {
struct al1 {
int bar;
int xyzzy;
};
char pad[CLSIZE - sizeof(struct al1)];
} rwstruct __attribute__((aligned(CLSIZE))) =
{ { .bar = 2, .xyzzy = 4 } };
-fms-exstensions.thread_local keyword (in C23)
Concerning bandwidth, we should take into account that even if threads don't cause cache contention, each processor has a maximum bandwidth, which is shared by all cores and hyper-threads. Depending on the architecture, multiple processors might share the same bus to memory or the Northbridge. If the connection to the memory cannot fulfill all load and store requests without waiting, an efficient program will still struggle.
"Programmers should be prepared to recognize problems due to limited memory bandwidth."
Front-side bus (FSB) contentions can be observed with the counter NUS_BNR_DRV, which
reports the number of cycles a core has to wait because the bus is not ready.
Note from wikipedia though:
"The original front-side bus architecture was replaced by HyperTransport, Intel QuickPath Interconnect, and Direct Media Interface, followed by Intel Ultra Path Interconnect and AMD's Infinity Fabric."
By the way HyperTransport seemed to use hyper-cubes in the beginning, which is pretty cool.
"If two threads work on a different set, having them scheduled on the same core can be a problem."
Both threads fight for the same cache, and both datasets have to be loaded in the same cache. Fixing this can be done by setting threads affinity so that threads accessing similar data are scheduled on cores that share the same caches.
Here they talk about libnuma. Altough I am more familliar with hwloc
today.
One can define NUMA memory policies:
MPOL_BIND, memory is allocated only from the given set of nodes, otherwise failsMPOL_PREFERED, prefer a given set of nodes for allocation, if fail, consider other
nodesMPOL_INTERLEAVE, memory is allocated equally on the specified nodesMPOL_DEFAULT, choose the alloction based on the default region
CPU_CLK_UNHALTED and INST_RETIRED.
"For a program which is not limited by memory bandwidth, the ratio (cycles per instruction) can be significantly bellow 1.0."
We can distinguish two kinds of page faults:
Interesting trick: in bash, using time with a backslash like \time
gives you the number of page faults!
[andrew@nixos:~]$ \time df -h
...
0.00user 0.00system 0:00.00elapsed 66%CPU (0avgtext+0avgdata 5136maxresident)k
0inputs+0outputs (0major+346minor)pagefaults 0swaps
/proc/ also gives page miss informations.
Using MAP_POPULATE with mmap let you pre-fault pages, which gives
enormous advantages if the pages are used right away. Note that by default mmap
allocates data only when read and write calls rare comming, not directly after mmap
call (MAP_POPULATE let you change this behavior).
"Large page sizes mean more waste through partially-used pages, but, in some situations, this is OK. [...] very large pages have their advantages: if huge datasets are used, storing them in 2MB pages on x86-64 would require 511 fewer page faults (per large page) than using the same amount of memory with 4K pages. **The solution is to selectively request memory allocation which, just for the requested address range, uses huge memory pages and, for all the other mappings in the same process, uses the normal page size.**"
mmap can be used with the flag MAP_HUGETLB for this case.
Altough, we should be careful of memory fragmentation when using large page sizes.
Cachegrind is a Valgrind tool that simulates cache misses (Wait, I never knew that Valgrind did is simulation??)
valgrind --tool=cachegrind command arg
The simulation retrieves the cache size values of the current machine, but you can also provide different values to try on a different (simulated) cache architecture!
Massif is also appart of Valgrind
and allows you to simulate heap memory allocations. Custom memory allocators needs to be specified
such as: --alloc-fn=xmalloc.
valgrind --tool=massif command arg
Memusage does a similar job but is not a simulation. Choosing between the two might depend on your use case.