Yes, You Have Been Writing SPSC Queues Wrong • Hacker News Board

Re: Yes, You Have Been Writing SPSC Queues Wrong

#31

Post by gpderetta » Fri, Dec 16, 2016, 1:29 AM UTC

NotThe1Pct wrote: post #26

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 t…

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

Re: Yes, You Have Been Writing SPSC Queues Wrong

#32

Post by gpderetta » Fri, Dec 16, 2016, 1:32 AM UTC

gpderetta wrote: post #23

ashtuchkin wrote: post #20

Earlier quoted context omitted.

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 2 31 everything works fine as long as computation is done with unsigned integers.

(too late to edit)

HN ate my asterisks. s/231/2^31/

Re: Yes, You Have Been Writing SPSC Queues Wrong

#33

Post by NotThe1Pct » Fri, Dec 16, 2016, 1:38 AM UTC

decker wrote: post #15

I didn't see the referenced article and initially thought this was going to be a post about not using volatile instead of atomic load / store. I suppose this could be a useful implementation, however, it's not clear how useful it would be since the main place it has an impact is if you have a large number of very small queues. The overhead associated with the unused element is sizeof(T) / (sizeof(T) * n + sizeof(Ring…

Quite frankly I wrote this more like an exercise. I have never used it in practice other than the github test. I saw people picking up on the other post and didn't really like the indices going unbounded. Then I spent a few minutes thinking how to solve it.

While I think the implementation per se is not that useful (I agree with you), I believe the actual trick can be reused in a different situation or type of container.

Check out the github repo now, I added a choice of allocator. That is nice because the main use of this kind of tool is when you have a slab of mapped memory that you go partitioning.

Re: Yes, You Have Been Writing SPSC Queues Wrong

#34

Post by theGimp » Fri, Dec 16, 2016, 4:03 AM UTC

vmarsy wrote: post #29

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

I'm new to systems and this is enlightening to me. Are there any books out there that enumerate pitfalls like this one?

Re: Yes, You Have Been Writing SPSC Queues Wrong

#35

Post by IanCal » Fri, Dec 16, 2016, 1:26 PM UTC

NotThe1Pct wrote: post #27

IanCal wrote: post #25

Earlier quoted context omitted.

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

Interesting, thanks!