It is interesting to me how popular linked lists are for non-blocking data structures. They are often slow and always so hard to reason about and implement safely.<p>Here's a very quick alternative<p><pre><code> push all messages into a channel IN.
A goroutine reads from IN inserts into a sorted TREE.
same goroutine reads max from TREE and pushes to channel OUT.
workers read from OUT.
</code></pre>
This is a pretty mediocre implementation. But I post it because the numbers posted in this article were so low. I think we can do better with something far less sophisticated.<p><a href="https://gist.github.com/fmstephe/4fdc930ff180be3e92c693ad5a24e1b3" rel="nofollow">https://gist.github.com/fmstephe/4fdc930ff180be3e92c693ad5a2...</a><p>I timed that to write 600,000 messages concurrently and read 600,000 sequentially in 1.5 seconds. Not a perfect measurement but I'm on a train and I'm about to get to my stop.<p>If we need really high performance we can start substituting faster, and simpler, queues than Go's channels and we can very likely improve that red-black tree that is doing the sorting. Each of these components is simpler, more likely correct, and from what I can see substantially faster than the sophisticated lock-free queue described in the article.<p>I don't want to come across as snarky. But I am surprised by the popularity of linked-list based lock-free data structures like this.<p>EDIT: So the tone of my post came across nastier than I really intend. I quite enjoyed the article, I'd be interested how far the performance can be improved.