Introducing lunchbox::LFQueue< T >

The second installment on Lunchbox introduces the lock-free queue.

Lunchbox uses two naming schemes when implementing containers which have a STL pendant, ‘LF’ and ‘MT’. In both cases the containers are thread-safe, in contrast to their STL counterparts. These classes carefully document what types of multi-threaded access are allowed, and which methods might only be accessed from a certain thread or in a certain state, if any.

‘MT’ stands for multi-threaded and typically uses synchronization primitives and blocking access. More on ‘MT’ classes in a later post.

‘LF’ stands for lock-free and uses atomic variables and non-blocking access. Lunchbox provides an Atomic class, which is derived from a library which recently got accepted as boost::lock_free. Atomic variables are a standard concept, google it if you’re not familiar with it.

Implementing lock-free containers is a very tricky business. Smart minds spend a lot of time on it, and still get it wrong quite often. For that reason, the functionality of the LFQueue is limited. To begin with, it has a fixed-size storage allocated at construction time. For that reason, a push might fail if the queue is full. Furthermore, only a single thread may write and (another) single thread might read at the same time, that is, at most two threads can access the LFQueue at the same time.

All these restrictions seem severe, but they allow for a fast and simple implementation. A quick test on my laptop yields:

[roku Release master]% ./Lunchbox/tests/mtQueue
193.339 reads/ms
193.34 writes/ms
[roku Release master]% ./Lunchbox/tests/lfQueue
12288.8 reads/ms, 6629.31 empty/ms
6145.42 writes/ms, 2031.51 full/ms

Collage uses the LFQueue in its multicast implementation. The RSPConnection uses a protocol thread handling the sending of data, acknowledgment, negative acknowledgement and retransmissions. Each connection has a fixed set of data buffers, which are constantly shuffled around between the application and protocol thread. At high wire speed (10GigE), more than 100.000 buffers need to be shifted each second. From the protocol thread to the application thread this is blocking, using an MTQueue, and in the other direction it’s non-blocking using a LFQueue. Since the queue size (number of buffers) is fixed, and only two threads are involved, the LFQueue is well suited here. For the curious, here is more background on the RSP implementation.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: