16 ms·
I know the author doesn't intend this code to be "production ready", but I just wanted to point a problem that may not be completely obvious, if you are trying
by tbirdz 10y ago
I know the author doesn't intend this code to be "production ready", but I just wanted to point a problem that may not be completely obvious, if you are trying to use this structure for multithreaded communication.
The structure declares the read and write indices like so:
std::atomic<IndexT> read_idx;
std::atomic<IndexT> write_idx;
These two variables are going to be stored next to each other in memory. If IndexT is say a 32-bit int, then the read_idx and write_idx will be 4 bytes each. A cache line is 64 bytes on intel, so these two variables are going to end up on the same cache line.
The problem with this, is that cache coherence protocols work on the granularity of lines, not bytes. So when one core writes to anywhere on the line (for example the producer to write_idx), then the other core (say the consumer core) has to invalidate its cache entry for that line, and get the new value off the bus, or maybe even hit memory.
Regardless of the specifics, the point is the consumer and producer cores can no longer independently write to their respective variables. Whenever they write to their variable, it will cause some cache coherence operations to be done to update the line that variable is in, in the other core.
This is false sharing, since the producer and consumer don't actually need to access the others variable. The cores are just forced to share access to the variables because the variables are on the same cache line.
This can really have a big impact for multithreaded workloads, and bring down the overall thread throughput.
One solution is to add some padding between the variables. Something like:
std::atomic<IndexT> read_idx;
unsigned char pad[64];
std::atomic<IndexT> write_idx;
will do. That will put the variables on different cache lines. And you might want to pad out some other variables to different cache lines as well.
- danbruc 10y agoDoes this actually help? Both, producer and consumer, have to read both pointers on every operation to determine whether the buffer is full respectively empty even though each only updates one of the pointers making the buffer thread-safe. So if there is actually an advantage to not having both pointers in the same cache line, then it is not totally obvious, at least to me.
- gpderetta 10y agoThe usual trick is for each side to cache the last value of the other side index so you only need to refresh the remote value when you "catch up". Even without caching, padding is still a win as the shared to exclusive transition is less expensive than a request for ownership of an invalidated cache line (aka "single writer principle")
- deleted 10y ago[deleted]
- IanCal 10y agoIs there a way of hinting this to the compiler, rather than adding a explicit padding? Any way of saying "please don't put the following on the same cache line"?
- NotThe1Pct 10y agoYou could use the alignas(64) specifier http://en.cppreference.com/w/cpp/language/alignas http://en.cppreference.com/w/cpp/language/alignas
- IanCal 10y agoInteresting, thanks!
- NotThe1Pct 10y agoYes, it's not meant to be production ready. Still, the padding you added is particular to Intel/AMD CPUs and this article is more about constrained memory/embedded. On Intel you would not care about the missing slot when you have 256GB memory available. I've added the atomic<> in the github and updated the article as well. However with atomic<> it adds an mfence instruction which is not really necessary and might add a ton of latency.
- gpderetta 10y agoYou can specify the memory ordering of operations to get the desired fences. For an spsc queue just load aquires and store releases are sufficient and will have no overhead at all on x86. Don't use operator++ to increment ( it will use an expensive lock xadd) just code the explicit load + add + store sequence. It is safe on this specific case.
- vmarsy 10y ago> This is false sharing You probably know this is the official Computer science term for it, but for those who don't and want to learn more about it: https://en.wikipedia.org/wiki/False_sharing https://en.wikipedia.org/wiki/False_sharing
- theGimp 10y agoI'm new to systems and this is enlightening to me. Are there any books out there that enumerate pitfalls like this one?
- brandmeyer 10y agoI'm not confident that this helps. Both the read and write index must be loaded in order to write (avoid overflow) or read (avoid underflow) any value from the queue. They may as well be on the same cache line. In either the author's code or your code, one dirty cache line will be invalidated and then reloaded by the other core. IMO, it takes a detailed protocol analysis for the cache coherence protocol in use by the target processor to determine which method actually results in fewer bus transactions.