Lock free pub/sub queue

Back in 2008 I found myself needing a high performance queue and, in the interests of future proofing, chose to make it a pub/sub queue. To my surprise there were no lock-free pub/sub queues to be found. Ever suspicious of my Google foo I continued to search and found a plethora of lock-free queues, but nothing capable of pub/sub semantics. Seeing a wonderful opportunity to invent a new type of wheel I embarked on algorithm design.

At this point I will note to any aspiring algorithm designers who are depending on their code doing exactly what they wrote; be very, very suspicious of your compiler. Verify the assembler listing for every compiler version, optimization level and platform you intend to support. This advice comes from experiencing just how hard it is to track down a bugs in lock-free concurrent code, particularly when your code is correct and your compiler is not!

The result of my endeavours was a wait-free pub/sub queue algorithm and a lock-free implementation, the discrepancy between those performance statements due primarily to environmental issues rather than any inherent difficulty in implementation.

To my disgust at the time and my delight with the benefit of hindsight, IBM wasn't interested in patenting this algorithm. Excuse me, that should be "System for Performing <insert name of algorithm>" as algorithms aren't patentable.

To give an idea of performance, a mostly unoptimized implementation was able to throughput upwards of a million messages a second with multiple publishers and subscribers on a 4 core x86 system. I expect a wait-free implementation to improve on this.

This project is listed under the Lair rather than having a separate project page despite my strong intention of writing and releasing an implementation (IBM owning the copyright to my previous implementation) because prior to this I'm planning a concurrency verification utility that can operate on machine code with full knowledge of memory consistency. If you've never worked with a weak consistency memory model count yourself lucky!