Safely and unambiguously manipulating atomic variables in C++11

Question

I have to read some data (which is coming at a blinding speed - upto 5000 messages per second) from a multicast (UDP) stream. Because the stream is multicast (and the data is quite critical) the data provider has provided two streams that send identical data (their logic being that the possibility of the same packet dropping in both streams is very close to zero). All data packets are tagged with a sequence number to keep track.

Also, the application is so time critical that I am forced to listen to both streams in parallel and pick up the next sequence number from whichever multicast stream it was received on first - When the same packet comes on the mirror stream, I simply drop it.

I am planning to implement this drop feature using a common "sequence_number" variable between the two functions - which by the way run in different threads. The sequence number is atomic as it is going to be read and updated from two different threads.

The obvious algorithm that comes to mind is

if (sequence number received from the stream > sequence_number)
{
   process packet;
   sequence_number = sequence number received from the stream;
}

(The above algorithm needs to be modified for times when sequence numbers come out of order - and they can as it is a UDP stream - but lets forget about it for the time being)

My question is this:

From the time I std::load my sequence_number, check if it is smaller than the sequence number I have received from the stream, accept the packet, and finally std::store the new sequence number to sequence_number; if the other stream receives the same packet (with the same sequence number) and performs the same operations (before the first stream finishes std::store on that sequence number), I will essentially end up with the same packet twice in my system. What is a way to overcome this situation ?

Answer 1

Don't put off worrying about handling out of order packets until later, because solving that also provides the most elegant solution to synchronizing threads.

Elements of an array are unique memory locations for the purposes of data races. If you put each packet (atomically via pointer write) into a different array element according to its sequence number, you'll get rid of most of the contention. Also use compare-exchange to detect whether the other thread (other stream) has already seen that packet.

Note that you won't have the retry loop normally associated with compare-exchange, either you have the first copy of the packet and compare-exchange succeeds, or the packet already exists and your copy can be discarded. So this approach is not only lock-free but also wait-free :)