Channels end up locking under the hood as well, so from a purity standpoint I wanted to avoid those...if channels are indeed faster, then clearly I need to rework my approach.
Even "lock free" algorithms can still not scale due to contention. Read this paper for a good summary:
http://queue.acm.org/detail.cfm?id=2991130
In short, a queue is made up of a linked list, where each entry is itself a circular buffer. Insertions go into a circular buffer... unless there's contention, in which case the next circular buffer is used.
The result is that insertions are mostly not contented. Removals are mostly not contented. And it scales very well.
https://github.com/fmstephe/flib/tree/master/queues/spscq
Those are only single producer single consumer (spsc) so not flexible enough for your needs right now, but I am working on expanding into multiproducer/multiconsumer variants which could be a good fit.
The single producer/consumer queues get up to 100 million messages per second (on microbenchmarks) and I expect the multi variants to be above 10-20 million per second.
I also have a handbuilt redblack tree which does around 10 million inserts/pops per second
https://github.com/fmstephe/matching_engine/tree/master/matc...
Although that is very specialised for another purpose, I would be happy to try stripping it down if you wanted that. But, start with the LLRB in that gist.