I get that this is dry subject matter and some humor helps to lighten it up, but I found the writing style distracting. Some paragraphs are dense with algorithm details, others just have a picture of a tech office, a story about running into someone on BART, or descriptions of data structures as "lame" or "losers". Made it really tough to retrace my steps and get context from the preceding section.
Thread-Safe Lock Free Priority Queues in Golang
11–20 of 32 posts
Re: Thread-Safe Lock Free Priority Queues in Golang
#12It 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.
Re: Thread-Safe Lock Free Priority Queues in Golang
#13I get that this is dry subject matter and some humor helps to lighten it up, but I found the writing style distracting. Some paragraphs are dense with algorithm details, others just have a picture of a tech office, a story about running into someone on BART, or descriptions of data structures as "lame" or "losers". Made it really tough to retrace my steps and get context from the preceding section.
thanks!
Re: Thread-Safe Lock Free Priority Queues in Golang
#14I get that this is dry subject matter and some humor helps to lighten it up, but I found the writing style distracting. Some paragraphs are dense with algorithm details, others just have a picture of a tech office, a story about running into someone on BART, or descriptions of data structures as "lame" or "losers". Made it really tough to retrace my steps and get context from the preceding section.
Yes. I'm starting to call this "neckbeard writing".
Re: Thread-Safe Lock Free Priority Queues in Golang
#15Can you write lock-free code in Go without assembly language support? Sometimes you need fence instructions or hardware compare-and-swap.
Re: Thread-Safe Lock Free Priority Queues in Golang
#16It 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.
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.
Re: Thread-Safe Lock Free Priority Queues in Golang
#17I get that this is dry subject matter and some humor helps to lighten it up, but I found the writing style distracting. Some paragraphs are dense with algorithm details, others just have a picture of a tech office, a story about running into someone on BART, or descriptions of data structures as "lame" or "losers". Made it really tough to retrace my steps and get context from the preceding section.
Yes. I'm starting to call this "neckbeard writing".
I don't think neckbeards have 24" arms (as per OP's site).
Re: Thread-Safe Lock Free Priority Queues in Golang
#18Can 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.
Re: Thread-Safe Lock Free Priority Queues in Golang
#19It 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.
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.
Re: Thread-Safe Lock Free Priority Queues in Golang
#20Earlier quoted context omitted.
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.
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.