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

61–70 of 143 posts

Re: Myths Programmers Believe about CPU Caches (2018)

#61

Post by re-thc »

jcranmer wrote: post #30
hashmash wrote: post #29

Earlier quoted context omitted.

> Java doesn't have the weaker atomics support that C++ added Yes it does, but it doesn't have first-class keywords to represent these modes. You have to use the VarHandle class, which is a bit kludgy. https://docs.oracle.com/en/java/javase/20/docs/api/java.base...

Okay, it looks like those were added in Java 9, which was after I stopped following Java (and well after the C++ memory model was largely settled, in 2007).

Before Java 9 it could have been done using Unsafe. VarHandle just provides a slightly higher level construct.

Re: Myths Programmers Believe about CPU Caches (2018)

#62

Post by gpderetta »

anonymousDan wrote: post #56

On the related topic of store buffers and write coalescing, can anyone point me to some good articles discussing how this works in practice for merging small writes to the same cache line? I have a workload where we are appending different size payloads (of sizes between 1 and 64 bytes) to an in memory log. One option is to just store each entry in its own cache line. A more space efficient option is to pack each wri…

On a typical write back cache, the cache line is written back to memory (or to a lower hierarchy) only when needed: either some other core wants it or it needs to be evicted to make space for other data. For a write mostly task, if you write to the same line again, it is likely to be still in the M state and data can be written to it immediately. Later, when the line is written back, the separate writes are effectively coalesced. But if some other core is concurrently reading from the head of the log, it can be suboptimal as the cacheline will keep bouncing between M and S state generating coherence traffic. This is still more scalable than two threads writing to the same cacheline of course.

Re: Myths Programmers Believe about CPU Caches (2018)

#63

Post by p_l »

Tuna-Fish wrote: post #9
edrxty wrote: post #6

Earlier quoted context omitted.

Modern CPUs are pushing 1MB L1 and 8MB L2 or more. You can fit a dozen FreeRTOS instances in that space. It would be pretty cool to see someone build a system that used a high end CPU but didn't have any installed ram, though I'm not sure if the CPU microcode would be ok with that.

Those numbers are for all cores. No modern CPU has anywhere near that of L1 and L2 per core.

Modern, no.

Some used to, however.

PA-RISC PA-8200 (1997) had 2MB iCache and dCache, up from 1MB of PA-8000. The last two PA-RISC models did 768kB L1 per core, with 32MB or 64MB of L2

Re: Myths Programmers Believe about CPU Caches (2018)

#64

Post by vmfunction »

Dylan16807 wrote: post #10

This article gives the impression that everything is the compiler's fault when you end up with conflicting reads in different cores, but that's not right. From the point of view of someone outside the CPU, yes you can say that simultaneous reads might never give different answers. But everything happening at that level barely resembles the original software. Dozens of instructions are happening at any moment, overlap…

> From the point of view of the software, running a bunch of instructions in sequence, you do get stale values. You can have two threads wait for a signal, then both read a value, and both get different results. You can have a thread set a flag after it's done editing some values, have another thread wait for the flag, and then after waiting it sees the edits as still incomplete.

Isn't that implementation of semaphore? I would imagine that should already being done in the CPU implementation?

Re: Myths Programmers Believe about CPU Caches (2018)

#65

Post by gpderetta »

re-thc wrote: post #61
jcranmer wrote: post #30

Earlier quoted context omitted.

Okay, it looks like those were added in Java 9, which was after I stopped following Java (and well after the C++ memory model was largely settled, in 2007).

Before Java 9 it could have been done using Unsafe. VarHandle just provides a slightly higher level construct.

Was the behavior of more relaxed operations fully formalized in the way it fits with the rest of the memory model?

Re: Myths Programmers Believe about CPU Caches (2018)

#66

Post by pjc50 »

vmfunction wrote: post #64
Dylan16807 wrote: post #10

This article gives the impression that everything is the compiler's fault when you end up with conflicting reads in different cores, but that's not right. From the point of view of someone outside the CPU, yes you can say that simultaneous reads might never give different answers. But everything happening at that level barely resembles the original software. Dozens of instructions are happening at any moment, overlap…

> From the point of view of the software, running a bunch of instructions in sequence, you do get stale values. You can have two threads wait for a signal, then both read a value, and both get different results. You can have a thread set a flag after it's done editing some values, have another thread wait for the flag, and then after waiting it sees the edits as still incomplete. Isn't that implementation of semaphor…

Only if you use the special instructions for that purpose. If you're just doing a regular read/write, you're vulnerable to this kind of problem.

If you do use the atomic instructions, you're guaranteed a consistent view across threads for that location. Check your platform documentation as to whether this is also a memory barrier, affecting ordering between the atomic instruction and other non-atomic instructions.

Re: Myths Programmers Believe about CPU Caches (2018)

#67

Post by throwawaylinux »

Dylan16807 wrote: post #53
throwawaylinux wrote: post #42

Earlier quoted context omitted.

Well no, if you don't have a coherent system then your memory operations aren't reliable. You can lose updates or read stale data. Look at what software has to do in incoherent systems, specific flush and invalidate points which is not the same as ordering barriers. Your CPU guarantees a lot, cache coherency to start with. But also a very well defined ordering model and ordering instructions. It's not necessarily tri…

> You can lose updates A system without cache coherency can still promise that updates won't be lost. There are lots of way to write rules around update propagation, and cache coherency is just one of them. > or read stale data Cache coherency doesn't protect you from stale data unless you only read one memory address ever. > Look at what software has to do in incoherent systems, specific flush and invalidate points…

> A system without cache coherency can still promise that updates won't be lost. There are lots of way to write rules around update propagation, and cache coherency is just one of them.

Not without coherency performed in software though, which is the point.

> Cache coherency doesn't protect you from stale data unless you only read one memory address ever.

It does. Observing updates to different locations in other than sequential order does not mean the data is stale. I guess that's also colloquial language issue. The data is up to date according to the constraints of the memory model.

> That depends on the memory model. You could have a system that doesn't guarantee cache coherency in general but works fine if you put in ordinary memory barriers.

What property of cache coherency could you lose and still have it working?

Re: Myths Programmers Believe about CPU Caches (2018)

#68

Post by [deleted] »

p_l wrote: post #63
Tuna-Fish wrote: post #9

Earlier quoted context omitted.

Those numbers are for all cores. No modern CPU has anywhere near that of L1 and L2 per core.

Modern, no. Some used to, however. PA-RISC PA-8200 (1997) had 2MB iCache and dCache, up from 1MB of PA-8000. The last two PA-RISC models did 768kB L1 per core, with 32MB or 64MB of L2

[deleted]

Re: Myths Programmers Believe about CPU Caches (2018)

#69

Post by throwawaylinux »

gpderetta wrote: post #50
throwawaylinux wrote: post #38

Earlier quoted context omitted.

It never presents an incoherent view to software. I'm using coherency as in the term of art, not a colloquial meaning. Every agent observes stores to a location in the same order[*]. Cache coherency says nothing about observed ordering of stores to different locations. [*] Although store forwarding throws a bit of a spanner in that definition, there can still be reordering occurring absent that local reordering.

Hum I don't see how store forwarding breaks the illusion of total order of stores on a single memory location, at least in 5 minutes of thinking I can't come up with a litmus that would demonstrate it. In fact even c++ relaxed stores and loads preserve this ordering. I think your definition is correct without the asterisk. edit: tweaked working

Oh yes that must be right, I wasn't thinking (or thinking about consistency ordering). Good catch.

Re: Myths Programmers Believe about CPU Caches (2018)

#70

Post by klabb3 »

gpderetta wrote: post #55
klabb3 wrote: post #54

Earlier quoted context omitted.

> Seq/cst are relatively fast, but at around 20-30 clock cycles Did you mean to say seq/cst store ? Also, what operation is “set the value to X unconditionally and return me the previous value”? Is that possible with a store or something different? (Golang calls this op atomic swap) In either case, sounds like the room for optimizing for performance with granular memory models on x86 is even narrower than I thought.

> Did you mean to say seq/cst store? Indeed! > set the value to X unconditionally and return me the previous value That would be atomic::exchange that maps to XCHG on x86, which, as all atomic RMW is sequentially consistent. Incidentally seq-cst stores are also typically lowered to XCHG on x86 as opposed to the more obvious MFENCE+MOV. There is still room for optimization, as if you can implement your algos with just…

Thanks a ton!

This matches my own micro-benchmarks in golang ish. I see basically either ~4ns for any write op, including store, swap, add, etc. And ~1ns for loads. I assume it’s all seq-cst.

Post reply on HN