New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: Go 2: sync: remove the Cond type #21165

Open
bcmills opened this Issue Jul 25, 2017 · 17 comments

Comments

Projects
None yet
@bcmills
Member

bcmills commented Jul 25, 2017

In the discussion on #16620, I've noticed that the majority of use-cases folks describe for sync.Cond turn out to work fine with a channel instead: (*sync.Cond).Broadcast corresponds to calling close on the channel, and (*sync.Cond).Signal corresponds to sending on the channel.

The existence of sync.Cond suggests that people might want to use it, but it is currently under-documented (#20491), incompatible with other Go synchronization patterns (e.g. select statements; see #16620), and unlike most other types in the sync package, does not have a valid zero-value (its Wait method requires a non-nil L field). It has an additional "no copy" invariant enforced through both a run-time dynamic check and special-case code in the vet tool.

On top of that, condition variables are fiendishly difficult to use: they are prone to either missed or spurious signals [citation needed — experience reports welcome].

An audit of the Go standard library shows only a handful of uses:

  • io/pipe.go: The use of sync.Cond was added in https://golang.org/cl/4252057. The previous implementation used channels and had no known bugs.
  • syscall/net_nacl.go: The comment there says "We do not use channels because we need to be able to handle writes after and during close, and because a chan byte would require too many send and receive operations in real use." It does not explain why these considerations preclude the use of channels (e.g. a separate 'chan struct{}' to signal closing, and channels of tokens or slices rather than channels of tokens or bytes).
  • net/http/h2_bundle.go: There are two sync.Conds in this file. One is is in a struct "like io.Pipe". The other is only used with Broadcast (never Signal), and can thus be replaced with a channel that is closed to broadcast readiness.
  • net/http/server.go: This sync.Cond is again only used with Broadcast, and thus easy to replace with a channel.
  • crypto/tls/conn.go: Again only used with Broadcast.

Of the above uses, only the one in syscall/net_nacl.go does not have an obvious channel equivalent. However, it appears to be used to limit the size of a buffer, and I know of at least one similar "limiter" API (x/sync/semaphore) that is implemented in terms of channels in order to support interoperation with the standard context package. (I did the Cond-to-channel conversion myself on a prototype of that package before it was open-sourced.)

In light of the above observations, I propose that we remove the Cond type from the sync package in Go 2.

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Jul 25, 2017

The main thing that sync.Cond provides that (as far as I can see) channels do not is the ability to use both Signal and Broadcast on the same synchronization point. But if nobody does that then I agree that sync.Cond is not especially useful.

cc @bradfitz since he decided to use sync.Cond in x/net/http2 in https://golang.org/cl/16310 .

@cespare

This comment has been minimized.

Contributor

cespare commented Jul 25, 2017

I don't use sync.Cond often, but when I have, I've been happy it exists. I agree that it's hard to use in other languages where you only have, say, locks and condition variables as concurrency primitives. But in Go, where we have channels, one can reserve use of sync.Cond for those specific cases where it's a good fit.

Besides the signal+broadcast case mentioned, another case where it's not obvious to me how to replace a Cond with a channel is where the mutex linked to the Cond protects some state. I typically want to lock, modify some state, and then cond.Wait -- which releases the lock. If I try to replace the Cond with a channel but keep the mutex, now I have two independent synchronization primitives, and that seems trickier to reason about.

@bcmills

This comment has been minimized.

Member

bcmills commented Jul 25, 2017

@cespare

another case where it's not obvious to me how to replace a Cond with a channel is where the mutex linked to the Cond protects some state.

Indeed, that's the trickier type of usage I've seen in practice. (It's also, in my experience, the type more likely to have deadlocks, or spurious or missed signals.) That kind of usage is illustrated in syscall/net_nacl.go, where the Mutex guards two monotonic variables (r and m) and triggers based on the difference between them.

I know of at least two techniques that can apply for that type of usage.

  1. If the state is always associated with a single condition, we can apply the technique illustrated in #16620 (comment) and store the data in the channel payload itself.

  2. Otherwise, we can replace the Cond with a list of channels instead of a single channel, and ensure that edits to that list only occur with the Mutex held. To cancel a wait, we acquire the Mutex, check whether the channel was signaled, and (if it wasn't) remove the entry from the list. This is the technique used in (*semaphore.Weighted).Acquire.

(For the latter technique, there may be something we could factor out into a library that would harmonize with the rest of Go better than sync.Cond does today, but I'm not sure that it's a common enough use case to warrant being in the standard library.)

@cznic

This comment has been minimized.

Contributor

cznic commented Jul 25, 2017

sync.Cond makes emulating pthreads simple. It seems to me semantics of sync.Cond is actually heavily inspired by pthreads.

@bcmills

This comment has been minimized.

Member

bcmills commented Jul 25, 2017

@cznic

sync.Cond makes emulating pthreads simple.

Agreed, but is pthread really a good example for Go's concurrency model to emulate?

@dsnet dsnet added the Go2 label Jul 25, 2017

@dsnet dsnet changed the title from proposal (Go 2): sync: remove the Cond type to proposal: Go 2: sync: remove the Cond type Jul 25, 2017

@gopherbot gopherbot added this to the Proposal milestone Jul 25, 2017

@gopherbot gopherbot added the Proposal label Jul 25, 2017

@bradfitz

This comment has been minimized.

Member

bradfitz commented Jul 25, 2017

I think Go2 could improve Cond but I think removing Cond is kinda crazy. Using channels is currently a super heavy replacement.

@kr

This comment has been minimized.

Contributor

kr commented Jul 26, 2017

Note that a single Cond lets multiple waiters each wait on a slightly different condition, such as an incrementing counter reaching various thresholds. I mentioned a real-life example of this in #16620 (comment). Channels seem to be a poor fit for this.

@reusee

This comment has been minimized.

reusee commented Jul 26, 2017

Channels cannot be reopened to broadcast twice.

@tombergan

This comment has been minimized.

Contributor

tombergan commented Aug 15, 2017

Since x/net/http2 was mentioned: I recently wrote a CL for x/net/http2 that was complicated by the use of Cond, because I wanted to select on set of channels or a Cond. I had to implement this by spinning a goroutine to wait on the channels, then broadcast to the Cond if one of those channels fired.
https://go-review.googlesource.com/c/53250/8/http2/transport.go#955

And FWIW, x/net/http2 uses Broadcast exclusively, never Signal.

I don't have a position on removing Cond, per se, but more than once I have been annoyed by not being able to select on a Cond and a channel simultaneously. If that could be fixed I would be happy.

@glycerine

This comment has been minimized.

glycerine commented Aug 28, 2017

I find channels easier to use than sync.Cond, but channels don't provide for efficient, repeated broadcasting of more than one bit from 1:N receivers. I suggest adding a new type of channel, a broadcast channel. It would be very similar to a channel with buffer size 1, with some extra logic:

a) if the channel has a value, then receiving on a broadcast channel doesn't consume the value in it. This allows an unlimited number of receivers to receive the same value.

b) delete on the broadcast channel removes any value in it. This allows the sender to stop broadcasting any value at all.

Notes

  1. an empty broadcast channel would still cause receivers to block, as usual.

  2. Senders then broadcast by sending into the channel, as usual. But each new send replaces the old value, and any receive after a replacement sees the new value. Just like a condition variable, receivers may miss values if a new value replaces the old before they awake. And just like a condition variable, a receiver may not receive a value at all if somebody deletes it from the broadcast channel before receipt.

Alternatives:

A2) a more general approach would be to allow the sending of values tagged as "sticky", and let sticky values be consumed an infinite number of times. This could be nice if you want the buffer of the channel to contain both sticky and non-sticky values. You would need a new operation to consume and eliminate a sticky value.

A3) allow the size of the buffer attached to a channel to be resized without being re-allocated. Then, assuming you know how many subscribers you have, the sender can send exactly that many values on a regular buffered channel. Unfortunately this requires that the sender have "register a new client" logic so it knows when to expand the queue. Corresponding de-registration logic required as well. Hence I prefer the broadcast type channels suggested first.

edit: A2 may have the advantage of being the most backwards compatible, and the advantage of having obviously novel syntax for sending sticky values. Suppose for instance that the operator <~ was chosen for sticky send. Example ch := make(chan int); ch <~ 1; would send the value 1 as a sticky value, that could be received many times. The new syntax would make the use of the sticky value very visually distinct.

@cespare

This comment has been minimized.

Contributor

cespare commented Sep 5, 2017

Over in #16620 (comment) I described taking some of my sync.Cond-using code and altering it to use a channel instead. I found it to be fairly tricky to get right (though of course it's possible that I overlooked some simpler way).

@as

This comment has been minimized.

Contributor

as commented Jan 4, 2018

On top of that, condition variables are fiendishly difficult to use: they are prone to either missed or spurious signals

This couldn't be more true, I would gladly take performance loss in favor of debugging someone else's condition variable usage. People see it in stdlib, copy it, get it wrong, and then spend late nights debugging it.

sync.Cond is a keyword in my bug comb

@gopherbot

This comment has been minimized.

gopherbot commented Feb 15, 2018

Change https://golang.org/cl/94138 mentions this issue: shiny/driver/internal/event: use a channel in Deque instead of a sync.Cond

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Mar 7, 2018

First I'll note that Go 2 should be largely if not entirely backward compatible with Go 1. sync.Cond is not actively buggy, so I don't see sufficient justification to remove it from "sync".

We could remove it from a new version of the sync package, whether that is called "sync/v2" or something else. But I don't think that removing condition variables is a sufficient reason to create a new version of the sync package.

@gdamore

This comment has been minimized.

gdamore commented Oct 3, 2018

I have used sync.Cond in a number of situations. Channels are really heavy weight, and its significant that a number of constructs that would be easy to implement as a relatively straight-forward condition variable followed by checks of several conditions can be implemented in terms of select {}, but at relatively large performance costs.

sync.Cond is harder to use than channels, and possibly more error prone, but for highly performance sensitive code there are so many constructs that are vastly more efficient with sync.Cond than select {} multiple conditions that removing sync.Cond would be devastating for projects that I work on.

Removing this construct would be devastating to me, and would be a reason to abandon to the language entirely for certain of my projects.

@gdamore

This comment has been minimized.

gdamore commented Oct 3, 2018

Let me be clear here. If an implementation using channels, and multiple channels, can be show to be roughly equivalent in terms of performance with a using a single condition variable followed by multiple if {} statements, then I'd be willing to accept that channels are an equivalent replacement. My own experience is that this is vehemently not the case, and I believe that this proposal stems from a naive understanding of the documented semantics of channels and condition variables, without sufficient experience in using either in performance critical code to make assertions about the lack of utility of one vs. the other.

@bcmills

This comment has been minimized.

Member

bcmills commented Nov 16, 2018

Channels are really heavy weight

It is true that a channel is currently larger than a sync.Cond, and requires more allocations. However, I don't believe that that is inherent to the use of channels. (#28366 describes one option to streamline both the API and implementation.)

for highly performance sensitive code there are so many constructs that are vastly more efficient with sync.Cond

Can you provide some benchmarks to demonstrate that? I'd be curious to see how well the channel alternatives can be optimized.

In my experience, even today the performance cost of untargeted wakeups can often swamp out the other performance advantages of condition variables.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment