How Much Linear Memory Access Is Enough? (probably less than 128 kB)
Posted by PhilipTrettner@reddit | programming | View on Reddit | 26 comments
Typical performance advice for memory access patterns is "keep your data contiguous". When you think about it, this must have diminishing returns.
I tried to experimentally find generalizable guidelines and it seems like 128 kB is enough for most cases. I wasn't able to find anything needing more than 1 MB really (within the rules).
wannaliveonmars@reddit
Isn't 4kb the page size anyway? So even if data is contiguous in your address space, it probably won't be contiguous in physical memory.
Ameisen@reddit
The cache and the prefetcher operate on logical addresses, not physical.
The only real benefit to contiguous physical pages is that you could potentially use huge or large pages, thus reducing pressure on the TLB.
And even then, your memory can scramble its addresses, so even the physical addresses as per your CPU aren't necessarily the same as on the RAM module.
WoodyTheWorker@reddit
Where logical address in Intel parlance is pretty close to physical, and not to be confused with virtual.
Ameisen@reddit
Good point; should have said virtual to be more careful.
Qweesdy@reddit
For most 80x86; L2 & L3 and hardware prefetcher/s work on physical addresses; and hardware prefetcher takes a break at 4 KiB boundaries even when you're using larger pages "just in case" (because hardware prefetcher isn't aware of MMU at all and can't know what the page size is or whether paging is enabled).
Don't forget there's a whole pile of cache coherency involved (including "same physical page mapped at different virtual addresses" situations); where writes done by any CPU to a completely unrelated virtual address have to appear in the correct order by a different CPU looking at a different virtual address. In other words; caches must operate on physical address to ensure that cache coherency doesn't become a performance disaster.
Another real benefit is that it uses cache evenly, with no risk of (e.g.) everything fighting to use one half of the cache while the other half of the cache isn't used. Essentially, you avoid the problems that cache colouring (see https://en.wikipedia.org/wiki/Cache_coloring ) fixes if you're using an OS that is too crappy to do cache colouring (e.g. Linux).
In practice: there's always a logical reasoned mapping from physical addresses to RAM module locations, because the memory controller has to route accesses as fast as possible based on physical address.
In theory: anything "could" happen (but idiotic fantasy crap doesn't have a place in the real world).
Ameisen@reddit
There are basically four patterns that you can use for caches. Generally, x86 processors use VIPT (virtually indexed/physically tagged) caches for the L1, and the L2/L3 use PIPT (most ARM chips do as well).
So, you're right in this regard, though I'm not really sure that it matters - even if your contiguous logical address space isn't contiguous in physical address space, that won't effect the L2/L3 cache too much - there's a slight possibility that contiguous logical accesses in that case will result in unwanted cache eviction, but with cache associativity I don't see that being as much of an issue either.
On Intel, they can't operate out of 4 KiB pages at all as said (unless that's changed) whereas on current AMD chips they can operate within the page size that that address is mapped within (AMD chips project some logical information - like the page size - to higher caches, as I recall). I believe that those only support huge pages rather than large pages, though.
But... it doesn't really matter if the prefetcher uses physical or logical addresses - they don't operate outside of the page anyways, so the result is effectively identical. Whether your logical addresses are contiguous in physical space doesn't matter when you're working within a page regardless.
And, as I'm sure you know since you didn't include it, but the L1d prefetcher uses logical addresses (though that makes sense).
AMD chips propagate this information down, I believe. At least for large pages.
As far as I know, pretty much all modern memory modules have address scramblers. The fact that they have that, though, doesn't really matter much to the CPU or the programmer.
wannaliveonmars@reddit
Thank you for the great comment, that kind of insight is what I was looking for!
lood9phee2Ri@reddit
Well, not exactly, these days you may be using a mix of classic 4kiB and 2MiB "huge" pages (typically, on x86-64, other cpu with mmu architectures may support and/or require some other page size(s)).
Long ago applications used to have to specifically use hugepages, but nowadays transparent hugepages is probably on by default in your distro, and will be used if your cpu hardware supports hugepages.
https://kernel-internals.org/mm/thp/ - transparent hugepage usage.
https://docs.kernel.org/admin-guide/mm/hugetlbpage.html - old explicit way, beware old documentation pointing you to doing things this way (there are special cases where you might still want to, but the transparent hugepages facility covers a lot).
Ameisen@reddit
I see that you just ignored 1 GiB large pages :( .
lood9phee2Ri@reddit
Yes, sorry, though usable in the "special cases" as they ARE supported by explicit hugepages on linux ...just not transparent hugepages.
Though I do wonder if we'll see transparent hugepage support for them some time fairly soon, with server-class and ai-bullshit-engine hardware existing with 100s of GiB to TiBs of ram, if a single 1GiB page is still only 1/1024th of the addressable memory and apps are allocating multi-GiB multidimentional arrays the "but fragmentation" argument may be weaker.
Ameisen@reddit
I just wish that I could manually use large pages in an application without requiring the user to go through hoops.
antiduh@reddit
At that point, I think you can just call it Page.
lood9phee2Ri@reddit
The x86-64 1GiB huge pages are sometimes called "gigantic pages", hah.
afl_ext@reddit
A whole book
wannaliveonmars@reddit
They should be called books at that point. Or at least scrolls. ;)
Qweesdy@reddit
For 80x86, minimum page size is 4 KiB, but modern operating systems can/do auto-promote to a larger (2 MiB) page size; and AMD Zen (e.g. the Ryzen 9 7950X3D used) has a "four compatible/contiguous 4 KiB pages act like one 16 KiB page" feature that an OS can deliberately exploit (but I don't know if the OS that was used supports that).
For the Macbook Air M4 that was also tested, I believe the minimum page size is 16 KiB.
braaaaaaainworms@reddit
The CPU's MMU in Apple Silicon can do 4KiB pages just fine, just don't expect DMA to work because IOMMU does only 16KiB pages
PhilipTrettner@reddit (OP)
The prefetcher works on the virtual address space. There's some TLB effects at 4k boundaries but that's mostly it. And you see in the graphs that there's a clear benefit beyond 4k.
Dineshvk18@reddit
Performance tuning always comes down to tiny details like this, pretty interesting read runnable.
ShinyHappyREM@reddit
If you're interested in this stuff you should also look at cache lines and how they can be fitted into the caches.
levodelellis@reddit
I don't know if I can believe in any of this. One program was looking up data in a table because compilers (I tried more than one) thought it was a good idea. With one thread it worked fine, with 4+ my code was waiting on ram and I needed to rewrites parts of it so compilers wouldn't generate lookup tables
Ameisen@reddit
So, this is effectively telling me (though different CPUs will differ) that chunked arrays with 256 KiB chunks are the optimal approach to large sets of data?
RegisteredJustToSay@reddit
Isn't the article's data and graphs actually showing that 256kb is the point of diminishing marginal returns? The second derivative of the normalized throughput is still positive at 128kb. 'Enough' is also a really hard to apply for throughput IMO since that's almost entirely context dependent. Either way with this data I'd probably just pick 1MB since that's when the marginal returns are almost negligible (assuming the dip for scalar_stats is due to measurement error).
gimpwiz@reddit
I think one interesting consideration is that the workloads running on different CPUs are different, because different CPUs go into different products with different needs and software gets optimized differently.
For a silly example, consider the ubiquitous mobile phone SOC versus a server chip. What workloads are on a smartphone? Tons of browser-related workloads, which vary wildly in scope and length (see: 15 megabyte javascript webpages that scrape all your info and keep reloading ads for eternity, versus tightly optimized webpages serving static content), and tons of app-type workloads of which many optimized for "hurry up and go to sleep" but others are much more liberal with your resources treating themselves as a first-class citizen under the theory of "no matter how much battery we burn you'll never uninstall me," and then lots of OS-level tasks that tend to be tightly optimized, take a short time, etc. On the flip side, consider the server chip that needs to be optimized for long-term high-performance workloads doing number crunching, running four low-utilization VMs per core, running a peaky-load webserver, etc.
Even more granularly, look at a server chip sold as one of a hundred thousand in a supercomputer versus a server chip sold to amazon to run AWS. They sound pretty similar, but the former is going to be used with a ton of wide instructions (SIMD-extensions out to forever) and need tons of optimization for scientific compute, but you can generally trust the people writing code to tune it to the architecture of the chip, whereas the latter is going to involve a ton of VM work, but probably less number crunching... especially because these days if it's going to do a ton of vector math there's a good chance that the VM will be spending most of its time communicating with and orchestrating one or multiple GPUs or other accelerators.
So it's not just that (eg) an Intel x86-64 core is somewhat different from an Apple ARMv8 mobile phone core in terms of how they'll run a workload like you are talking about, but also that people might actually want to run pretty significantly different workloads between the two.
So chip vendors spend a lot of time figuring out the workloads that will be run on their product and doing a ton of simulation and testing to make sure that they'll be delivering a good chip for that set of workloads. And vice versa, the higher-tier software shops writing the actual workload will tune the workload to work with the chip they're running on. And there are middle layers (compiler optimizations, VMs, interpreters and bytecode interpreters like the JVM, etc) that do the heavy work of tuning workloads to CPUs allowing the people writing the actual software to write more simply and agnostically.
funtimes-forall@reddit
Okay, I've been holding on to my 80286 from 1982. This is its moment to shine!
gimpwiz@reddit
Intel, AMD, ARM and various architecture licensees, etc all did a lot of work studying this sort of question. Given the workloads expected to be run, how much L2 cache lets you have a really good hit rate?
This is really evident with stuff like the Xeon Phi, which had a shitload of cores with pairs sharing L2 but no L3. The workloads for a chip like that were pretty well understood and optimized, and it lacked L3 as a potential confounding factor. Being a design intended for a lot of wide parallelism, they found that 1MB/2core was a good number. So 512KB/core. But each corr was quad-threaded round robin, so you got....... yep. 128KB/hardware thread.
I worked on the little fucker. Referring to KNL specifically.