[theaustinseven]

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.

[jasonwatkinspdx]

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.

[slobdell]

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.

[theaustinseven]

The insert is still an N operation since N in this case is the number of nodes in the list. It would only be O(1) if the list was of constant size(and even that would be misleading). The worst case is still infinity, because you are concerned with a single insert operation, and not that there are some making progress. We are merely concerned with the progress that a given insert operation makes, and there could potentially be an infinite loop. You can reduce the probability of this happening by shortening the loop between repeating the CAS operation.

Otherwise I think it would be awesome to see profiling results, I suspect that the garbage collection time can be reduced significantly. I have recently been implementing a locking thread-safe queue, and I think it would be interesting to compare the differences in speed and garbage produced, just to get a better idea of the pros and cons. I suspect if you shortened the retry loop you have, your implementation would be faster.

When I said flawed, I meant that it was not really enforcing order on insertion, but for many applications, this doesn't matter that much. Close enough is often good enough(and the probability of this going wrong is fairly small, except in extreme cases).