Things that make Go channels expensive to implement

January 26, 2017

Recently, fchan: Fast Channels in Go made the rounds (via). I read it with some interest, because I'm always interested in interesting high-performance concurrent things like this, but my first reaction was that they'd started with an artificially inexpensive scenario. That got me thinking about what features make Go channels expensive (ie slower), regardless of the specifics of the implementation.

Generally, what makes concurrent operations intrinsically expensive is the need for cross-thread locking and coordination. So we can look for all of the places that require coordination or locks, as opposed to simple operations:

  • A sender may have to suspend, as opposed to either the channel being unbounded or sends failing immediately if the channel is full. Suspending means enqueuing, scheduling, and coordination to make sure that wakeups are not lost.

    (The mere potential of even a single waiting sender means that receivers must be prepared to wake senders, as opposed to passively pulling messages from a queue and possibly suspending until some show up.)

  • There may be multiple senders and thus multiple suspended senders. A new receiver and the overall runtime must insure that exactly one of them is woken to continue on (no more, no less).

  • There may be multiple receivers and thus multiple suspended receivers. A new sender must insure that exactly one of them is woken to receive its message.

    (You can cover all of this waiting sender and receiver stuff with a single lock on the channel as a whole, but now you have a single lock that everyone who touches the channel will be contending over, and it may be held over more than very short lengths of code.)

  • A receiver may be waiting in a select for multiple channels to become ready. A sender that wants to wake this receiver must insure that its send is the single event that wakes the receiver; all other channel events must be locked out and prevented from happening.

  • A sender may be waiting in a select for multiple channels to become ready. A receiver that wants to wake this sender to get its message must insure that its event is the one that wins the race; all other channel events must be locked out and prevented from happening.

  • When a goroutine performs a select on multiple channels, it must initially lock all the channels before determining their readiness because the language spec specifically says that the winning channel is chosen via a uniform pseudo-random selection. The Go runtime is not free to lock channels one after another until it finds the first ready one, take that, and stop there; it must lock everything before picking one ready channel.

    (This channel locking must also be performed in a consistent order so that selects in different goroutines with overlapping or identical channel lists don't deadlock against each other.)

In the fully general case you have one goroutine sleeping in select on multiple channels and another running goroutine starting a select that could succeed immediately by waking the first goroutine. The running goroutine must take some pains to insure that the sleeping goroutine is not actually woken out from underneath it by a third goroutine. There are quite a few locks and atomic operations flying around in the process.

(Part of the result of this is that the implementation of select in the runtime is reasonably involved. select.go is actually surprisingly readable, although it's not easy going. It's best read along with chan.go. As a bonus it contains at least one neat hack.)

PS: The implementation of select is so complicated that recently a long-standing and extremely intricate race deep inside the runtime was fixed in this commit (the commit discussion has an illuminating explanation of what the code is doing in general). The fix was rather simple but the journey there was clearly an epic one.

Written on 26 January 2017.
« I think docstrings in Python are for everything, not just public things
Conversations, conversational units, and Twitter »

Page tools: View Source, Add Comment.
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Thu Jan 26 01:07:04 2017
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.