It depends how you define "TLB miss". Read it as "paging table reads" if that's clearer. If you have a 64-entry TLB and 4kB pages, then you can do random memo

It depends how you define "TLB miss". Read it as "paging table reads" if that's clearer. If you have a 64-entry TLB and 4kB pages, then you can do random memory accesses (aka hash table accesses) up to 256 kB without any paging table reads; up to ~16 MB with one paging table read per operation; and up to ~1GB with two paging table reads per operation. (This, of course, is why large databases use superpages when possible; but while that pushes the limits back it doesn't eliminate them.) In virtual machines there's further overhead since you have "virtual physical" addresses...