21–30 of 32 posts
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…
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.
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.
Can you write lock-free code in Go without assembly language support? Sometimes you need fence instructions or hardware compare-and-swap.
Yes. Portable primitives are provided in the sync.atomic package. They've been careful about the details (eg, inserting fences on architectures like arm). Most applications shouldn't touch this stuff but it's there if you want to try to write a lock free data structure or algorithm.
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…
For example, the following:
q := NewPrioq()
q.In Furthermore, this input:
q := NewPrioq()
for i := 0; i 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.
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…
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).
I didn't make it past the bar pic :(
Comments like this are NOT appreciated on Hacker News, especially if you haven't taken the time to read the article.
Oh, you've meant the comment police from the ministry of truth will kill his karma, yes they surely will. They always do.
PS: Down voting below zero is not moderation it's punishment, and yes, I know they enjoy it.
I didn't make it past the bar pic :(
Comments like this are NOT appreciated on Hacker News, especially if you haven't taken the time to read the article.
I notice that in about 80% of your comments on your comment history you mention how old you are. Maybe you're just getting grumpy?
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…
I don't think that the implementation here performs correctly... For example, the following: q := NewPrioq() q.In Prints "Read 20" rather than "Read 30". Furthermore, this input: q := NewPrioq() for i := 0; i 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…
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?
Earlier quoted context omitted.
Yes. Portable primitives are provided in the sync.atomic package. They've been careful about the details (eg, inserting fences on architectures like arm). Most applications shouldn't touch this stuff but it's there if you want to try to write a lock free data structure or algorithm.
There are some interesting caveats to using sync.atomic. Some working code on x86_64 did panic on x86_32 since the target struct member was no longer 64-bit aligned.
I would be interested if you did. I have a repo that provides a set of packages for doing things like that. If that is a real need I would be interested to add it to the library.
Earlier quoted context omitted.
Yes. Portable primitives are provided in the sync.atomic package. They've been careful about the details (eg, inserting fences on architectures like arm). Most applications shouldn't touch this stuff but it's there if you want to try to write a lock free data structure or algorithm.
There are some interesting caveats to using sync.atomic. Some working code on x86_64 did panic on x86_32 since the target struct member was no longer 64-bit aligned.