Comment by fmstephe | Hacker News Reader

Comment by fmstephe | Hacker News Reader

Parent Full thread

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.

I don't think that the implementation here performs correctly...

For example, the following:

    q := NewPrioq()
    q.In <- timestamp(20)
    q.In <- timestamp(10)
    q.In <- timestamp(30)
    o := <-q.Out
    fmt.Println("Read", o)

Prints "Read 20" rather than "Read 30".

Furthermore, this input:

    q := NewPrioq()
    for i := 0; i < 202; i++ {
        q.In <- timestamp(i)
    }
    o := <-q.Out
    fmt.Println("Read", o)

will result in a deadlock.

As far as I can tell, this code behaves like a FIFO queue with capacity 201. Each iteration of the loop in Prioq.run() will read once from the input channel, insert into the empty tree, remove the "max" element from the single item tree, and then insert into the output channel.

Reading from the input channel and writing to the output channel are performed in lockstep rather than as needed. A correct implementation of this pattern would need to use a select block and to avoid the deadlock and would need a way for writes to the output channel to be signaled as needed so to avoid the stale max value problem.

You are right.

But the purpose of that code was just to indicate the rough performance that was possible using much less sophisticated parts, compared to a lock-free linked list with sorting built in.

But, thinking about it further it does seem like solving the 'stale max value' problem would be non-trivial.

If I was implementing this for a real system I would side-step that problem by redefining the requirements (which could be seen as cheating).

We can agree that the Out channel is full of stale max values and isn't really well sorted. But it will only have len(out) many stale values, and the values which replace them as Out drains are reasonably well ordered. At any time we have at most len(out) out of order tasks.

I am thinking of the queue in two different scenarios.

1: Workers are keeping up with new tasks - this queue provides FIFOish semantics and no effective priority ordering. But it doesn't matter, workers are keeping up prio is irrelevant.

2: Workers are falling behind. The red-black tree fills up as Out is filled to max capacity. As Out drains new tasks are in priority order (roughly).

Because of the vagueness of the guarantees given above you'd need to think hard about whether that provides enough. But I would strongly prefer something along these lines (i.e. avoid lock-free linked list with built in sorting) if I thought I could live with it.

What do you think?

thanks for posting...I will try the implementation you linked to and see the effects on performance.

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.

Locking isn't the problem. Contention is the problem.

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.

If you want to push the performance of that approach (a single goroutine prioritising your messages for you a queue in and a queue out) I have built a set of lock-free queues on a ringbuffer.

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.

My experience is that you can lock and unlock a golang mutex in around 130ns, do a cas in around 60ns, and a fetch and increment in around 30ns. So building something atop the atomic primitives is potentially faster, but the difference is not so dramatic that you shouldn't try a simple implementation first.

Lock free structures typically have worse average or even uniformly worse performance. The issue is what happens under contention or predictability. Lock freedom guarantees that at least one process makes progress whereas with locks a process can acquire a lock and get switched between cores or get GC paused or whatever.

That's a really interesting approach, thanks for posting

Reply on news.ycombinator.com