No, Donald Knuth, Half the TLB is Not “Wasted”

Donald Knuth is a genius. If he suffered significant head trauma, was sleep-deprived for days, and then pounded 10 shots of Jager in 10 minutes while holding his breath, his pinky toe could still beat me at Scrabble. I mean, the man is so smart that I am legally retarded by comparison. I should be arrested for even speaking his name.

Donald Knuth apparently gave a Valentine’s Day lecture, and at least one fella came away with this in his notebook:

He talked about how most userland programs were still 32-bit and how operating systems and processors had moved on to 64-bits and made the point that in this scenario, half of the bits in the TLB were being wasted.

Hmm, no. That just sounds wrong.

A TLB is this pretty wicked gizmo that performs address translations literally in one nanosecond via the magic of caching and SRAM. I’m not a hardware guy, but I know that this SRAM crap doesn’t come cheap. Would anyone ever waste it? I think not.

AMD64 chips employ a simple canonical address rule which limits the effective virtual address space to 48-bits while allowing for future expansion. It seems that current implementations map these virtual addresses into a 52-bit physical address space.

It’s pretty clear that we didn’t invent this idea. The MMU on the DEC Alpha, for example, left the upper 21 address bits unused.

So, sure, the page tables themselves hold 64-bits, but the hardware need only map subsets — and I’ll bet you lunch that the TLB’s SRAM structures are sized for this requirement.


%d bloggers like this: