Monday, May 19, 2014

Fast, lock-free, non-blocking queue

In my copious spare time (insert laugh-track here), I have developed a fairly simple queue that features:
  • Fixed size (size specified at queue creation time).
  • Non-blocking (enqueuing to a full queue returns immediately with status; dequeuing from an empty queue returns immediately with status).
  • Single Producer, Single Consumer (SPSC).
  • No dynamic memory allocates or frees during enqueue and dequeue operations.  Messages are void pointers (null pointers not allowed).
  • High performance.  On my Macbook Air, streaming data through a queue averages 11 ns per message (queue size=32), while ping-pong latency is 69 ns (one-way).
  • Tested on Mac OSX 10.9 (Mavericks) and Linux 2.6 and 3.5 kernels.  At present, I only recommend the 64-bit x86 processor family, due to the fact that I take advantage of its programmer-friendly memory model.  In the future I hope to generalize it to be efficient on other processor types.
I'm making it available as public domain (or more-accurately, as CC0), which means you can use it for any purpose without restriction.

You can get the module and its documentation here:

In addition to the queue itself, I produced semi-literate internals documentation  I'm rather proud of my semi-literate documentation system.

No comments: