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

Yes, You Have Been Writing SPSC Queues Wrong

vitorian.com

Post reply on HN
Print view View original

21–30 of 35 posts

Re: Yes, You Have Been Writing SPSC Queues Wrong

#21

Post by gpderetta »

danbruc wrote: post #18
tbirdz wrote: post #17

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 read_idx; std::atomic write_idx; These two variables are going to be stored next to each other in memory. If IndexT is say a 32-bit in…

Does 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.

The 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")

Re: Yes, You Have Been Writing SPSC Queues Wrong

#22

Post by tcbawo »

jstapels wrote: post #11

I honestly don't see how any of these implementations are better than simply using a bool to track whether the queue is empty or not (as suggested in one of the comments on the original article). You could even use the highest bit of the write index to store the bool value if memory was an issue.

Another approach gives each element a 'data ready' flag (ie the real element type inherits from T). This flag is set by a producer and cleared by the consumer. This would give you an empty/full indication.

Re: Yes, You Have Been Writing SPSC Queues Wrong

#23

Post by gpderetta »

ashtuchkin wrote: post #20
loeg wrote: post #8

Earlier quoted context omitted.

Yeah. Just requires power of 2 sizes and handling of write_idx < read_idx.

AFAIK write_idx Power of 2 requirement stands, though.

Yes, this exact trick is used for tcp sequence numbers, for example, which are allowed to overflow, and as long as the unack'd bytes are less than 231 everything works fine as long as computation is done with unsigned integers.

Re: Yes, You Have Been Writing SPSC Queues Wrong

#24

Post by [deleted] »

gpderetta wrote: post #21
danbruc wrote: post #18

Earlier quoted context omitted.

Does 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.

The 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]

Re: Yes, You Have Been Writing SPSC Queues Wrong

#25

Post by IanCal »

tbirdz wrote: post #17

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 read_idx; std::atomic write_idx; These two variables are going to be stored next to each other in memory. If IndexT is say a 32-bit in…

Is 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"?

Re: Yes, You Have Been Writing SPSC Queues Wrong

#26

Post by NotThe1Pct »

tbirdz wrote: post #17

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 read_idx; std::atomic write_idx; These two variables are going to be stored next to each other in memory. If IndexT is say a 32-bit in…

Yes, 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.

Re: Yes, You Have Been Writing SPSC Queues Wrong

#27

Post by NotThe1Pct »

IanCal wrote: post #25
tbirdz wrote: post #17

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 read_idx; std::atomic write_idx; These two variables are going to be stored next to each other in memory. If IndexT is say a 32-bit in…

Is 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"?

You could use the alignas(64) specifier

http://en.cppreference.com/w/cpp/language/alignas

Re: Yes, You Have Been Writing SPSC Queues Wrong

#29

Post by vmarsy »

tbirdz wrote: post #17

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 read_idx; std::atomic write_idx; These two variables are going to be stored next to each other in memory. If IndexT is say a 32-bit in…

> 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

Re: Yes, You Have Been Writing SPSC Queues Wrong

#30

Post by brandmeyer »

tbirdz wrote: post #17

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 read_idx; std::atomic write_idx; These two variables are going to be stored next to each other in memory. If IndexT is say a 32-bit in…

I'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.

Post reply on HN