Thread-Safe Lock Free Priority Queues in Golang

These queues are thread safe and lock-free, but they are far from efficient. My biggest issue here is that the runtime evaluations are wrong. The insert operation is definitely an average runtime of N (where N is the number of elements in the queue) and a worst case of infinity(since the insert operation is restarted if a race condition occurs, an insert operation could be repeated forever). I don't know if I missed anything, so I could be wrong, but this implementation seems incredibly flawed.

That said, it is always nice to see new data-structures and I really wish there were more posts like this. I always like to see the different ways that people try to solve these problems.

Re: Thread-Safe Lock Free Priority Queues in Golang

#6

Post by slobdell » Fri, Sep 30, 2016, 7:16 PM UTC

theaustinseven wrote: post #5

These queues are thread safe and lock-free, but they are far from efficient. My biggest issue here is that the runtime evaluations are wrong. The insert operation is definitely an average runtime of N (where N is the number of elements in the queue) and a worst case of infinity(since the insert operation is restarted if a race condition occurs, an insert operation could be repeated forever). I don't know if I missed…

I agree, these are currently far from efficient (I hope to resolve this). My suspicion right now is that a lot of time is being spent somewhere in spinning loops waiting for progress to be made.

Average runtime of insertion is constant time because the size of the linked list does not grow beyond a certain size, and inserting into the priority queue is constant. The worst case is not infinity because there is always at least one goroutine making progress.

Thank you for the comment about wanting to see posts like this :)

I do not think this implementation is flawed from the standpoint that at least one goroutine is making progress, there are no locks, and results are returned in order if dequeues are not saturated

This is not something that would make it to a white paper because the implementation does not return deterministic results, and I could not explain from a mathematical standpoint how flawed the results are returned because they're not guaranteed to be in order.

I should have also included the profiling results. Currently 25% of time is spent garbage collecting, which is expected because the priority queues effectively use multi-version concurrency control, but this will come in handy when I want to persist data to the hard drive with as little locking as possible (and for general simplicity in avoiding corruption)

Another 15% or so is spent sleeping, which would be the spinning loop part.

Re: Thread-Safe Lock Free Priority Queues in Golang

#7

Post by fmstephe » Fri, Sep 30, 2016, 7:18 PM UTC

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.

Here's a very quick alternative

    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.

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.

https://gist.github.com/fmstephe/4fdc930ff180be3e92c693ad5a2...

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.

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.

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.

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.

Re: Thread-Safe Lock Free Priority Queues in Golang

#8

Post by jalfresi » Fri, Sep 30, 2016, 7:30 PM UTC

Hats off, this is a GREAT post! Lots of detail and I'm way out of my depth but lots to dig into and learn from!

Thanks for posting!

Re: Thread-Safe Lock Free Priority Queues in Golang

#9

Post by jalfresi » Fri, Sep 30, 2016, 7:31 PM UTC

fmstephe wrote: post #7

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. Here's a very quick alternative 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. This is a pretty mediocre implementation. But I…

That's a really interesting approach, thanks for posting

Re: Thread-Safe Lock Free Priority Queues in Golang

#10

Post by jasonwatkinspdx » Fri, Sep 30, 2016, 7:32 PM UTC

theaustinseven wrote: post #5

These queues are thread safe and lock-free, but they are far from efficient. My biggest issue here is that the runtime evaluations are wrong. The insert operation is definitely an average runtime of N (where N is the number of elements in the queue) and a worst case of infinity(since the insert operation is restarted if a race condition occurs, an insert operation could be repeated forever). I don't know if I missed…

Yeah, something's up with the OP's numbers/design. I didn't dig into it further because I found the writing style off-putting. A basic lock free queue or linked list in golang should run at 10+ million ops per second. I suspect even with the parallelization the priority queue implementation is spending too much time reorganizing. A skiplist of 64 byte or 4KB buckets would probably be both simpler and faster.