last day (15 days later) » 

11:27 AM
1
A: Is there a way to "unfetch" a cache line?

Peter CordesI only know the answer for x86. This is definitely architecture-specific; different ISAs have different cache-control features. On x86, yes, clflush / clflushopt, but they only evict one single cache line per execution. (They force write-back + eviction, like you'd need for memory-mapped non...

 
Using NT stores is not beneficial in this case because buffers[i][j]++ involves a 4-byte read (assuming int is 4-byte) followed by a 4-byte write. If the read is from WB memory (most likely), the cache line containing the data will be cached. Doing an NT store now will either not flush the line or will flush it immediately and then perform a 4-byte write, but then there are other reads from the same cache line! So NT stores will actually degrade performance, not improve it.
 
@HadiBrais: My answer says to read the whole cache line before doing any stores to it, using four 16-byte vector loads. (Obviously you auto-vectorize this using paddd). The 2nd half of the 2nd-last paragraph specifically addresses the problem of evicting before the last read.
 
The cache line will be cached when read, nonetheless. This is the problem. It's not guaranteed what will happen when you do NT stores to a cached cache line. It may not get flushed or it may get flushed after or before the very first write. This is uarch dependent.
If you can do NT stores without reading the line, then you're good. Or if the target memory type is WC, then NT loads can be used and you're still good. Otherwise, it doesn't work.
 
@HadiBrais: on Intel CPUs later than Pentium-M, it is guaranteed to flush. I linked another answer where I quoted the relevant section from Intel's vol.1 manual. I didn't check AMD, though. You could use NT prefetch to minimize L2 (and L3) pollution, but IDK if that helps any (on Intel CPUs where NT stores have to evict anyway).
 
Where is that documented? AFAIK, no where in any of the Intel manuals where they say that. They only say it is uarch dependent. In addition, it does not say precisely when (and if) the flush will happen (after partial write or full write to the line).
 
11:27 AM
@HadiBrais: Like I said, the link in my answer quotes the manual What happens with a non-temporal store if the data is already in cache?. (SDM volume 1, ch 10.4.6.2 Caching of Temporal vs. Non-Temporal Data).
 
Hmm, 10.4.6.2 of V1 may be more up-to-date than 7.4.1.3 of the optimization manual. But still, it's not clear (to me at least) how the writes will be performed. Ideally, the full cache line should be written to before being evicted. This is unlikely to happen with NT stores. I think it will be evicted on (before or after) the first write.
If the cache line is already in the cache anyway, why not just write to it and then flush it using clflushopt? This is probably better and easier, and it will work on AMD processors.
 
@HadiBrais: You're not doing any non-NT stores to the line, so it's clean when the NT store needs to evict it. Ideally the progress of the NT store itself moving outward through the memory hierarchy can do the necessary evictions without needing to send a message first. But for that to happen, either the store buffer would need to merge the NT stores into one before they commit to an LFB, or the partially-written LFB would need to exist for a few cycles while the line was still in L1d. I wouldn't be surprised if it's slow (e.g. effectively triggers a clflush before putting data in the LFB).
But anyway, there's at least a possibility that this could be efficient on some microarchitectures. My understanding is that it's generally not worth it to clflushopt behind where you're writing. Maybe that's a bad assumption, and more careful cache control could be worth sending extra store-like operations down the memory hierarchy in some cases.
By avoiding a normal write, you never need to get it in MESI M state. @BeeOnRope said elsewhere that's normally cheap right after reading a line, because it will arrive in E state. I expect that's true at least for write streams, if the HW prefetchers are aware of read vs. write. So IDK if there's anything to be saved by never having a cache line in M state, just read-only + NT store.
 
It's not clear from the OP's question whether the line is clean on entering the loop. If that was the case, I'd agree that using NT stores might improve perf. But again, consider the following benefits of doing normal stores then flush: 1- it works on all Intel and AMD processors, 2- the code is maintainable; you don't have to worry about whether the read line is M state or clean, 3- you don't have to worry about the weak consistency of NT stores ever, 4- I don't remember whether NT stores inhibit hardware prefetching, but we certainly don't want that to happen.
 
@HadiBrais: I don't think I've ever read anything about NT stores inhibiting prefetch, so you'd still get normal prefetch from normal loads. NT stores don't trigger prefetch, of course. Anyway like I said, I think clflushopt is normally not worth it for this use-case. I may be wrong about that because I haven't tested. (i.e. normally best to just accept the cache pollution by using normal loads + normal stores, if this crazy NT-store idea doesn't pan out.)
 
Yes, I meant NT stores don't trigger prefetch. But the program has high locality, so prefetching is good. Using normal stores allow us to benefit from it.
 
11:27 AM
@HadiBrais: I updated the answer to be less enthusiastic about NT stores for this. More of a crazy idea than a recommendation. re: prefetching. NT stores don't trigger prefetch, but they don't stop regular loads from triggering prefetch. There are many possible problems, but lack of prefetch isn't one of them unless I'm totally mistaken. The HW prefetchers will just see a stream of normal loads. I don't see why they'd be aware of NT stores other than the forced-eviction, which should look about the same as clflushopt.
 
No, you're right. There is no need for NT stores to trigger prefetching. Doing the normal load achieves that. I want to remove reason 4 from my earlier comment; it's invalid.
There is no need to call the approach crazy :) It's certainly worth considering and discussing. Also cache pollution may not even be a perf problem in the OP's program depending on how it behaves after the loop.
Also one important note here is that each buffers[i] array should map to basically the same (small) set of cache sets. Otherwise, the normal loads can by themselves pollute the L1D or L2 cache. So it wouldn't matter whether NT stores are used or not.
 
@HadiBrais: A normal L1d (32k / 8-way) aliases at 4k strides, but good point that evicting doesn't help make room for the next if it's in a different set. Could be a problem for L2 unless you arrange for for your pages to be an even distance away from each other. (Like 32kiB or 64kiB for Intel's 256kiB 8 or 4-way L2 caches, I think.) L3 uses a non-simple hash function so there's not much you can do about it. L1d pollution is probably the least problematic (because it's small and can refill fast). Adding loop overhead just to avoid only L1 pollution is unlikely to be worth it.
 
The OP's total array size is 40KB, which I think is too small to worry about L3 pollution. The arrays have to be carefully allocated to use a small set of cache sets. This is not trivial; it depends on the L1D and L2 cache sizes and organization and may waste some memory (internal fragmentation within pages). Also the thread should ideally be pinned to the same core. Oh, and hyperthreading could be a problem because another thread might pollute the cache. What loop overhead are you thinking of?
 
@HadiBrais: loop overhead = clflushopt or using NT stores or whatever that might make the loop itself run slower in the hopes of speeding up surrounding code. I was assuming the OP's 4k buffers were page-aligned, since that's the obvious way to allocate them. Allocating but never touching memory is not usually a problem, unless you end up wasting space inside a 2M hugepage.
 
Also inclusivity matters. An eviction of a line from an inclusive lower cache can can force an eviction from all higher caches. So the arrays must map in different caches in a way that important data in lower inclusive caches don't get evicted.
The read part of buffers[i][j]++ is really problematic.
Now I'm thinking of using MOVNTDQA for the loads together with NT stores, but the memory type of the arrays must be WC. But the buffer used for NT loads are different from ones used for NT stores. So on an NT store, the NT load buffers will get evicted. Then the stores can be combined in a WC buffer.
 
11:27 AM
@HadiBrais: Interesting idea, but then lack of HW prefetch would be a problem. I guess you could prefetchnta, but with limited LFBs that probably doesn't help. Of course WC memory is not easy to get your hands on under most OSes. I'm not aware of a way to allocate WC memory under Linux; mmap doesn't have a flag for it. So it's getting into the realm of fun computer tricks that you probably can't practically use in a portable program, unlike NT stores or clflushopt.
 
Yeah, there is no easy way to allocate WC memory. NT loads don't trigger prefetching https://stackoverflow.com/questions/32103968/non-temporal-lo‌​ads-and-the-hardw‌​are‌​-prefetcher-do-they-‌​work-together/503858‌​15#50385815. So it appears there is no elegant solution. How can that be? I'm disappointed.
 
 
5 hours later…
4:29 PM
Wow, thanks for the amazing answer and the great conversation! I had no idea flushing or NT stores existed, or that there were so many factors involved! I have lots of reading ahead of me today.
 

last day (15 days later) »