Things that make Go channels expensive to implement
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
selectfor 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
selectfor 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
selecton 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
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
in the runtime is reasonably involved.
is actually surprisingly readable, although it's not easy going.
It's best read along with
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.