This chapter covers different types of memory and how they interact.
The memory higherarchy works as follows, with things at the top being the fastest and smallest and most expensive per byte, to things at the bottom being the slowest and biggest, cheapest per byte.
The reason this memory higherarchy exists is simply to take advantage of spatial locality and temporal locality of reference to get fast access to large amounts of memory.
It is the programmers job to keep heavily referenced data in the registers as lon gas possible.
This higherarchy is actually quite similar to the tcp/ip model in theory(most of the time). The memory system at each layer only directly interacts with the system directly above and below it. For example, if you want to move a value from main memory into a register, the cpu asks the l1 cache if the value is there(in a previously gotten cache line). If not, l1 reaches out to l2 to grab it and update. L2 then looks and sees if it’s in one of its cache lines. If not, then the cpu reaches out to main memory. Etc. Thus, if you’re constantly reaching for stuff in RAM at different spots far away from each other, things will be way slower.
The change in access speed between different levels is not uniform. Sometimes it can be orders of magnitude(difference between level 2 cache and main memory for example), sometimes not so much(difference between level 1 and level 2 cache).
The cpu will grab one byte at a time from an L1 cache. However, below that, the cache system grabs cache lines. The L1 cache grabs a small cache line from the L2 cache, which grabs a larger cache line from main memory. This does mean that, if you have an L1 cache miss, you have to wait a while for the L1 cache to grab a line from L2 cache, assuming the data is in L2. That latency can bubble as you go down. If there is an l2 miss, you have tow ait until L2 grabs a line from main memory and also L1 to grab part of that updated line.
Caches hold cache lines. Each line of size n holds n contiguous bytes. So the first line might hold 0x10000..0x1000F. But each line does not have to hold addresses that come right after the previous line, that would be pointless. So line 2 might hold 0x21400..0x2140f for example. Thus, bytes inside a line are contiguous, but lines are not.
What happens when a cache reads a line from a lower level into itself? Where does the data go? Which line does it go into?
There are three different schemes: direct-mapped, fully associative, and n-way set associative.
Direct mapped is a one way set associative cache, a block of main memory is always loaded in the exact same line. A small number of bits in teh data’s memory address(from main memory) determines which cache line holds the data. How similar are caches to hash maps? Are hash maps just caches in some sense? This is vaguely in my mind from college.
These are fast and simple. However, they may not make efficient use of the cache space, since simplicity means addresses are essentially modulo mapped.
Most are not like this. There is no structure, the cache system can place any memory into any space. Utmost flexibility, but as usual, without constraints, and with total freedom, things don’t work well. The circuitry is slow and expensive.
In this way, the cache is broken up into sets of cache lines, each set containing n lines. Some subset of bits determines which set to use, and within that set the cache unit can throw memory in whichever slot.
You get a lot of benefits. However, remember that the more cache lines you have per set, the closer you get to fully associative so cost goes up, and complexity goes up, and performance cna go down.
For this reason, most caches are direct mapped, 2 way, or 4 way(ie 2 cache lines per set or 4 cache lines per set).
Notice that programs are sequentally accessed. The first instruction may be at address 0, but the next one will generally be at address 1 unless you jump around. Thus, a direct mapped cache works great for storing code and instructions.
What happens when a cache line that we need isn’t available in the cache and the cache is full? For direct mapped, easy. Just replace the line with new data.
For n way caches, this becomes more complex. If both are full in a 2 way cache, how do you choose?? Ideally you keep the cache line whose data will be referenced first and replace the other but we can’t know that.
Usually this is resolved by replacing the line that hasn’t been referenced in a while. In a 2 way cache system, you need to reserve a single bit somewhere to keep track of “which cache line was last accessed”. When cpu gets the first line, set the bit to 0. When it gets the second line, set the bit to one. If you need to pull in more data, replace the line at the negation of this bit.
This extra circuitry is why implementing associative caches is hard and expensive. The algorithm gets harder and harder as you go from 2 way to 4 way and up.
When writing to memory, you write to cache. However, what happens if you write to cache and the cache line you took gets replaced by another read? This obviously is unacceptable.
CPUs handle that with two approaches: write-back and write-through.
Write-through means that any time data is written to the cache, the cache immediately turns around and writes a copy of that line to main memory. The CPU does not stop unless it needs to read from that cache. Instructions can keep going.
With write-back policy, the writes are not immediately written to main memory. Instaed, teh cache controller updates main memory at a later time. This scheme si higher performance, because multiple cache writes do not necessarily mean more main memory writes. However, you now need to track whether the cache line is dirty or not(ie whether it needs writing or not). This includes a bunch of extra circuitry again. no such thing as a free lunch.
Note that a lot of the time, programmers don’t even know what the cache is doing. So they don’t think about how to organize the code. Great code is written with the behavior of the cache in mind. A great programmer attempts to put often used variables in adjacent memory cells so they they end up in the same cache lines etc.
Virtual memory gives each proceses its own 32-bit address space. CPU and OS handles this by mapping the same address for each process into a different physical address space.
Example: Program 1 ha sa virtual address 0x1000 that maps to physical address 0x215000, program 2 has a virtual address 0x1000 that maps to physical address 0x3000000. The way this is achieved is paging.
Paging is very similar to cache lines. At teh end of the day, all comp sci is just abstractions over hardware, or using the hardware itself. The physical memory space gets mapped to memory blocks of bytes called pages. Then you have a lookup table that stores the mappings, and you consult that table. The upper bits of the virtual address map to the HO bits of the physical address, and the lower bits map into the offset into that page.
Then obviously you get to the idea that pages can be huge, so you use a tiered page system, just like you may use a tiered cache system. Hilariously enough, it’s caches all the way down, and the page tables use their own cache.
You can actually think of main memory as a fully associative write-back cache with 4,096-byte cache lines which caches the data stored on the disk drive. It’s literally all caches.
Note each program has its own page table, which means that if a program crashes its space, it has no impact on others, unless it’s some massive memory leak or something.
If two programs want to cooperate, they can do so by placing data in a memory area that is shared between the two processes. The OS handles this.
Degenerate case that can cause overall performance of the system to drop to the speed of a lower level in memory higherarchy like main memory or worse. Happens when:
In the first case, you’re constantly swapping, so you’re always going slower than you’d like. This can happen when you’re running a bunch of stuff at once, using all the RAM. Then you’re constantly swapping program address spaces into the page table over and over.
The second case has been demonstrated already.
NUMA or Peripheral devices(like VRAM for example) have access times that are much slower because they are not directly connected to the bus. They are connected to a peripheral(pci) bus.
Declare variables together within a code sequence to ensure that they get allocated next to each other. Spacial and temporal locality. Allocate slocal variables inside a procedure. This makes the variables to on stack area, and that usually gets kept in cache. Declare scalars together.
I assume the compilers do thsi for you nowadays, but have to verify.
The rest of the chapter goes into memory management, garbage collection, and different types of sections in code, which I know already and also should be covered in the assembly book for linux.
One thing to notice is that OS api calls are slow because they switch from user to kernel mode and back. Thus, we want to grab big things of memory at once to reduce those calls(That’s why arenas are useful).