Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Myths Programmers Believe about CPU Caches (2018)

software.rajivprab.com

Post reply on HN
Print view View original

131–140 of 143 posts

Re: Myths Programmers Believe about CPU Caches (2018)

#131

Post by gpderetta »

throwawaylinux wrote: post #130
gpderetta wrote: post #127

Earlier quoted context omitted.

Sorry, I'm losing track of what you are proposing. I guess you mean MOESI plus an additional Stale state? Can you describe all the transitions and when they are performed?

It seems to be a state that can send stale data to loads, but will get invalidated if the CPU performs a barrier. It doesn't work of course, obviously because there is no forward progress. CPU1 can order all previous stores, then later store some flag or lock variable, and that will never propagate to CPU2 spinning on that waiting for the value. But also because CPU2 and CPU3 can see different values depending on the…

Yes, saw that flaw, but I think in their model, barriers are always associated with stores (so atomic_thread_fence is not implementable but store_release is), which fixes your first example. I agree that in any case you end up doing more work that in the typical model to make other scenarios work.

Re: Myths Programmers Believe about CPU Caches (2018)

#133

Post by ComputerGuru »

ggm wrote: post #5

My favourite myth is that I still believe it's possible to write code which operates totally out of L1 and L2 cache. Not just tight ASM on bare metal: C code or similar, compiled down, to run under a modern UNIX/POSIX os on a multi-core host. I have never explored HOW this would work, or WHAT I would do to achieve it, but I believe it, implicitly. For it to be true I would have to understand the implications of every…

Some SoCs will let you directly/explicitly use the cache as (ostensibly secondary) RAM, remapping your configuration from

    [cpu] -- [cache] -- ram
to

          [   cpu    ]
            |      |
        [cache]  [ram]
Here's TI's documentation on doing just that CC13x2/CC26x2 family of MCUs: [0]. In this case, it's a seemingly paltry 8K of "RAM" but that's a lot for microcontroller developers! In this configuration and for this particular MCU, the CPU will actually run at a reduced speed (60% of its norm), probably because it needs to synchronize directly against the RAM. If you were to use it in CaR-only mode (which I don't think TI exposes), i.e. with the cache being used instead of rather than in addition to any RAM, you probably wouldn't need to run at those reduced speeds (and might even be able to run at higher clock speeds!).

[0]: https://software-dl.ti.com/simplelink/esd/simplelink_cc13x2_...

Re: Myths Programmers Believe about CPU Caches (2018)

#134

Post by ComputerGuru »

monocasa wrote: post #19
ninepoints wrote: post #3

Hmm, I think the discussion is missing a few things needed for a complete picture of the situation. First, ARM and x86 coherency models differ, so a big disclaimer is needed regarding the protocol. Most ARM processors use the MOESI protocol instead of the MESI protocol. Second, synchronization isn't just because of register volatility and such. Synchronization is needed in general because without the appropriate lock…

> First, ARM and x86 coherency models differ, so a big disclaimer is needed regarding the protocol. Most ARM processors use the MOESI protocol instead of the MESI protocol. MOESI is called out. > The above are just some of the possible scenarios that can occur. In reality, there are numerous variations of the above design, and no 2 implementations are the same. For example, some designs have an O/F state. However tha…

I didn't immediately find a first-party source but according to these COMP522 lecture notes from Rice, AMD still uses MOESI for Zen [0].

[0]: https://www.cs.rice.edu/~johnmc/comp522/lecture-notes/COMP52...

Re: Myths Programmers Believe about CPU Caches (2018)

#135

Post by ComputerGuru »

chasil wrote: post #4

SQLite database locks can be more quickly obtained and released if CPU affinity is set for the database processes, allowing all I/O activity to share the same cache(es). I have read (but cannot remember where) that this can increase performance by thousands of DML operations per second.

This is really going to be hardware- and OS-dependent. Most schedulers try to avoid changing CPU affinity for active processes, so you're likely looking at the delta for the worst-case scenario rather than the average case. But yes, affinity definitely helps!

Re: Myths Programmers Believe about CPU Caches (2018)

#136

Post by [deleted] »

gpderetta wrote: post #85
jcranmer wrote: post #80

Earlier quoted context omitted.

The data-race-free theorem states that, in the absence of data races, acquire/release is indistinguishable from sequential consistency. Define data races to be UB, as C/C++ do, and you get to the state that acquire/release lets you pretend everything (except atomic operations themselves) is sequentially consistent.

My understanding is that that only applies to programs that use mutex lock/unlock operations (which do have acquire/release semantics), but not to programs that use acq/rel memory operations in general. For example: https://www.hboehm.info/c++mm/sc_proof.html which contains the the SC proof for lock operations that you mention, but also a counterexample for acq/rel atomics.

[deleted]

Re: Myths Programmers Believe about CPU Caches (2018)

#137

Post by ComputerGuru »

gpderetta wrote: post #49
klabb3 wrote: post #44

Earlier quoted context omitted.

I’m nowhere near as deep in this rabbit hole. But I recall running/seeing some benchmarks on different memory orderings and the differences were not.. that big, on x86 I believe. Obviously there’s a lot that can go wrong with micro-benchmarks in these incredibly complex systems, but I still got the feeling that memory orderings are perhaps not worth the immense complexity that they introduce, for let’s say the majori…

At leas on x86, acq/rel load/stores vs relaxed is basically free. Seq/cst loads are also free. Seq/cst are relatively fast, but at around 20-30 clock cycles still measurably slower thant everything else. The catch is that x86 only has seq/cst atomic RMW so even if you ask for, say, a relaxed CAS or XADD, you will still get an expensive one. So the c++11 memory model allows you to more easily maintain correctness (and…

> At leas on x86, acq/rel load/stores vs relaxed is basically free.

The corollary to this is that using them doesn't buy you any performance (under x86).

(Also it makes it difficult to test that your code itself synchronizes correctly if you're developing on x86, since bugs may only show up under ARM or RISC or whatever, and even there, only some of the time... and that's why project loom, tsan, and miri exist.)

Re: Myths Programmers Believe about CPU Caches (2018)

#138

Post by ComputerGuru »

winstonprivacy wrote: post #103
CyberDildonics wrote: post #92

Earlier quoted context omitted.

Ok, that's the latency of the L1 cache and that isn't shared between threads, so you might not want to count on being able to do this.

Exactly. I was referring to that bit at the end of the article: "In the case of Java volatiles, part of the solution is to force all reads/writes to bypass the local registers, and immediately trigger cache reads/writes instead. As soon as the data is read/written to the L1 cache, the hardware-coherency protocol takes over and provides guaranteed coherency across all global threads. Thus ensuring that if multiple thr…

That last sentence can be pedantically true, if you look at in a very strict context. It doesn't say the variable can be returned in 1ns - but even if it did, it says the inter-thread coordination can take place in "as little as" 1ns. If a L1 cache immediately returning it's cached value for a memory address because it has the data in E or M state, that's technically a form of inter-thread coordination, just using already-coordinated state.

Re: Myths Programmers Believe about CPU Caches (2018)

#139

Post by Dylan16807 »

throwawaylinux wrote: post #130
gpderetta wrote: post #127

Earlier quoted context omitted.

Sorry, I'm losing track of what you are proposing. I guess you mean MOESI plus an additional Stale state? Can you describe all the transitions and when they are performed?

It seems to be a state that can send stale data to loads, but will get invalidated if the CPU performs a barrier. It doesn't work of course, obviously because there is no forward progress. CPU1 can order all previous stores, then later store some flag or lock variable, and that will never propagate to CPU2 spinning on that waiting for the value. But also because CPU2 and CPU3 can see different values depending on the…

I can't say that spinning without a barrier is doing things wrong?

I guess if I need an emergency fix I can make those lines invalidate themselves every thousand cycles.

> But also because CPU2 and CPU3 can see different values depending on the state of their caches. If one had no such line and the other had a valid-stale line, then they will end up seeing different values.

But only if there's no memory barriers, so it shouldn't be a big deal. And the valid-stale lines can't be used as the basis for new writes.

> And the writeback out of CPU1's cache needs to write back and invalidate all possible older such written-to lines.

The only such lines are in this new state that's halfway between S and I. They don't need to be marked any more invalid. Zero bus traffic there.

Re: Myths Programmers Believe about CPU Caches (2018)

#140

Post by Dylan16807 »

throwawaylinux wrote: post #129
Dylan16807 wrote: post #123

Earlier quoted context omitted.

When I talk about how the cache protocol has to do XYZ to implement a barrier, you complain that that isn't what a barrier is. When I talk about what memory barriers do in pure terms, you complain that I'm not mentioning the cache protocol. When I give an example of a cache protocol in isolation, you start talking about which memory barriers I'm missing. I don't know what you want. > Coherency is not about ordering,…

> I don't know what you want. I don't want anything, I was correcting your misconceptions. > Well, if I go by "if it's part of the memory model then it's not stale", then you can allow a relaxed ordering on single addresses without having stale data. I don't know what you're talking about. Memory ordering is not about ordering of a single address. That's cache coherency. [snip] > I'm pretty sure the entire point of a…

> I don't know what you're talking about. Memory ordering is not about ordering of a single address. That's cache coherency.

The ordering of a single address is relevant to both the cache protocol and the memory model.

That section is describing a cache protocol.

> And you're still wrong. Acquire barrier can be required even if you receive coherency updates in a sequential order.

I agree. How does that make my statement wrong in any way?

> Real cache coherency protocols are verified with formal proofs, and not because they are easy. I guarantee if you handwave a new coherency state or give up some property of coherency, you will have bugs.

Do you think my description is impossible to fix, or are you just trying to impress on me that it's hard?

I don't feel like spending hours finding and editing a concurrency simulator today.

Post reply on HN