Coherence
We have explored memory in isolation. But modern computers are not isolated. They have multiple Cores.
Each Core has its own L1 Cache. This creates a terrifying problem: Disagreement.
If Core A loads "Variable X" and Core B loads "Variable X", they now have two independent copies. If Core A writes to X, Core B holds a lie.
To fix this, the cores talk. They scream at each other over a shared fabric. Usually, they use a language called MESI.
The Protocol from Hell
MESI stands for the states a cache line can be in:
- M (Modified): I changed this. It is dirty. You cannot have it.
- E (Exclusive): I have it. I haven't changed it yet. But you don't have it.
- S (Shared): We both have it. Read-only.
- I (Invalid): My copy is trash. I must re-fetch.
1. Core A Read: Gets 'E' (Exclusive).
2. Core B Read: A downgrades to 'S'. B gets 'S'. Both Shared.
3. Core A Write: A invalidates B. A gets 'M'. B gets 'I'.
The Cost of Sharing
Look at the simulator. Every time one core writes, the other is forced to Invalidate. Its cache line dies.
This is why multi-threaded programming is slow if you share data. If two threads fight over the same atomic integer, they are playing "Ping Pong" with the cache line. The data spends more time on the Bus than in the CPU.
This is called False Sharing if the variables are different but sit in the same 64-byte line. The hardware doesn't care. The line is the unit of war.
Why does every core need its own cache?
Because a shared cache would serialize access and destroy throughput. Local caches are mandatory — coherence is the price.
Is MESI optional?
No. Without coherence, multi-core systems would silently compute incorrect results.
Why does writing shared data hurt more than reading it?
Writes require ownership. Ownership requires invalidation. Invalidation triggers communication. Communication is slow.
What is false sharing in one sentence?
Different variables. Same cache line. Same war.
What programmers usually get wrong here
They think threads are independent. They are not. They are electrically coupled through cache lines.
Phase III Complete. We have seen the Machine beneath Memory. It is hostile. It hates sharing, it hates random access, and it hates pointers.
Now that we know the rules of the metal, we can look at our high-level tools with fresh eyes. It is time to dissect Data Structures.