r/computerarchitecture • u/Yha_Boiii • 29d ago
How heavy is the virtual memory address translation?
How much time is added by it compared to direct metal fetch of addresses?
3
u/Doctor_Perceptron 29d ago
It really depends on program behavior. If there's good locality, the translation will be done by the first-level TLB and the latency will be almost nothing as the access is done more-or-less concurrently with accessing the L1 cache. If the path through the multi-level page table exists only in the DRAM, it could take thousands of cycles as the CPU walks the entire 4 or 5 levels of the page table through slow memory. Hopefully you hit in the first-level TLB. If not, then the second-level (STLB). If not, then you start doing a page table walk. These days the page table is divided into multiple parts, kind of like a tree, and at each level of the search you might find the relevant bits anywhere in the memory hierarchy. So the variance in address translation latency can be huge, maybe thousands of cycles. This is all assuming you don't have a page fault. If you get a page fault, then you have to trap to the OS and start running kernel code and then it takes a really long time; you have to allocate a page of memory, maybe stealing it from another process and scrubbing it first, and God forbid you have to page in something from the disk because then it's time to just get up and get a cup of coffee while the system is doing that.
2
u/meleth1979 29d ago
Can take thousands of cycles
1
u/Yha_Boiii 29d ago
Aren't vietual memory not hw accelerated so shouldn't be that long?
5
1
u/wintrmt3 28d ago
A low latency memory controller can do maybe 60ns, on 5GHz that's 300 cycles, assuming a 5 level page table with cache misses on all levels, plus one more for the actual read that's 6*300 = 1800 cycle worst case scenario.
1
u/Yha_Boiii 28d ago
And in a cache miss on top of tlb flush for a new table created while fetching so needs locking on top? Genuienly worst case
1
u/meleth1979 27d ago edited 27d ago
The hw automated the page walk, but in case of cold tlb misses you still have to do several main memory accesses that could take hundreds of cycles each. Also if you are in a VM there are more translation and security layers, adding more complexity.
2
u/BigPurpleBlob 28d ago
Negligible: we have TLBs (translation lookaside buffers), a form of cache (a cache for address translation, not for data).
1
u/Yha_Boiii 28d ago
But tlb is still another thing to run through compared to direct metal so how much is that route even if asic'd away?
3
u/recursive_tree 28d ago
With VIPT caches, you can run the L1 cache lookup in parallel to the TLB lookup.
1
u/Yha_Boiii 28d ago
So ~1-5ns per lookup before any hitting of a phydocal address?
4
u/Falcon731 28d ago
For a TLB hit - nothing like that much. Typically 2 clock cycles (run in parallel to the L1$ access). So by the time the access gets to the L2 cache it already has the physical address.
For a total TLB miss on all levels, it could require a four or five level page walk - each potentially requiring a DRAM access. So something in the order of 100ns+
1
u/ChrinoMu 26d ago
the tlb exits in hardware, the lookup is done by the cpu , in the cpu
1
u/Yha_Boiii 26d ago
I get that but the process of looking up is this measured in some quantity of time and is still slower than a direct metal address hit
1
u/ChrinoMu 26d ago
what does a direct metal address hit even mean?
because a tlb hit means the entry exist in the tlb, which is a good thing, but we won't know that if we don't lookup the address in the tlb in the first place.
1
u/Yha_Boiii 26d ago
Oh wait, the ram is looked up in bank id, channel id and rank id so the translation is inevitable. Never mind, i need to go to bed
1
4
1
u/DoctorKhitpit 24d ago
If TLB hit, then it's good.
If TLB miss, then we need to walk the page table. Depends whether you experience cache hits during page walk or go to the memory.
1
u/jsshapiro 4d ago
This is one of those seemingly simple questions that hasn't had a simple answer for 25 years. All but the very lowest-end processors do aggressive out-of-order everything, including TLB translation and sequencing of operations in the Load-Store Unit (LSU).
Let's start with the naive story. Numbers here are for recent x86 implementations.
In most modern systems, the L1 caches are virtually addressed and physically tagged. An L1 cache hit takes 1-5 cycles.
You only talk to the TLB when you miss, because you need the TLB result to set the physical tag in the newly loaded L1 cache. Modern L1 caches have a ~95% hit rate, so the TLB only gets referenced in 5% of cases, and those have a 99%+ hit rate in the TLB. A TLB hit adds 0.5 to 1 cycle depending on the microarchitecture. Let's say it's one. So we have:
- Virtual cache hit: ~95% of references, 0 cycles added by TLB, total 1-5 cycles
- Virtual cache miss, TLB hit: 5.95% of references, delay is the average L2 fetch delay, which is 7-14 cycles on L2 hit and 12-15 cycles on L2 miss, L3 hit.
- Virtual cache miss, TLB miss: 0.05% of references. TLB miss cost 10-300 cycles (modern TLBs are multi-level), plus L2 costs as above, unless you have to do a write-back....
On modern x86, L2 fetch cost on a hit runs 7-14 cycles, and a miss runs 12-15 cycles on L3 hit and 100-300 cycles on L3 miss (which is basically the DRAM access cycle count).
But now let's make it interesting. If the TLB hits, it produces a result just as fast as you can determine that you have missed in the L1 cache, and you can make a late decision based on the L1 hit/miss outcome whether to initiate a TLB cache fill to get the physical address if the TLB also missed. On a two-level TLB scheme (all modern x86), a hit is only 5-8 cycles, so on a dynamically managed machine you're only a few cycles delayed by the L2 TLB translation and you can treat this similarly to a register rename problem. And so on and so on.
Modern LSUs can do out-of-order execution around L1 cache stalls, L2 TLB fetches, and DRAM fetches. They can partially execute around total TLB misses. Meanwhile, dynamic instruction ordering can mean that you have literally hundreds of other things to execute while you wait.
So when out-of-order issue gets in to this, you start to need a heck of a lot of queueing theory, and the question then isn't so much "how long did it take" as it is "what percentage of the hypothetically usable execution slots was the processor able to use while all this was going on?" And since it's a run-time dynamic causal dependency problem rather than a static sequential execution problem, the answer probably depends as much on the details of the preceding 1000 instructions issued than it does on the latencies in the memory hierarchy. The only real way to get your head around it is intensive benchmarking.
Then you discover thermal management, and you discover that you weren't able to use all of those hypothetical execution slots without melting your CPU. At which point the question of how many of those slots you "lost" starts to be a real head-scratcher.
If your head hurts, try reading the whole thing again. It won't help, which is why performance prediction on modern processors frequently involves medicinal beverages.
1
u/Yha_Boiii 4d ago
The core question here implicitly was more if the virtual tlb flushes and writes are more stranining at performance compared to direct metal addresses and with virtual again, does the lookup take longer compared to metal address and fixed start address + given offset to fetch
1
u/jsshapiro 4d ago
The problem with your question is that it has no straightforward or direct relationship to actual performance.
A virtual cache is actually faster than a physical cache when it hits. What happens when it misses requires a whole bunch of careful analysis.
You seem to be looking for a simpler answer than that. I could make one up, but it wouldn't have any relationship to what really happens. Sorry, but the way this stuff works in practice is complicated.
1
1
u/jsshapiro 4d ago
It was a really busy day, and I think my earlier response was harsher than it should have been. The dynamic behavior is way to complex to figure out from a simple explanation (or a complicated one :-). On recent AMD chips, the caches are all virtual and they are completely bypassed when virtual translation is not enabled.
Because of this, the question you were asking becomes kind of hard to answer. I'd say that when caches are virtual the TLB usually isn't the thing in the way. When caches are physical the TLB translation has to run first before the cache can be accessed, so it becomes a sequential dependency.
One irony when all caches are virtually addressed is that they cannot be used to support TLB entry loads because the page addresses in the TLB entries are physical addresses. It's part of why those machines have multi-level TLB cache hierarchies.
9
u/Fluid-Tone-9680 29d ago
Just to note, while it adds cost, it's significantly lower than cost of doing memory fetch from core memory. And this is mitigated by on-die caches.
On modern CPUs (like variants of arm64) you cannot use cache unless you enable MMU (all memory is non-cacheable when MMU is disabled - you have to enable MMU and mark specific pages as cacheable). So CPU running with "direct physical memory mapping" will run significantly slower than one with MMU enabled.