Skip to content
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: sync: mechanism to select on condition variables #16620

Open
bradfitz opened this issue Aug 5, 2016 · 42 comments

Comments

@bradfitz
Copy link
Member

commented Aug 5, 2016

Sometimes condition variables are the best fit for a problem, and sometimes channels are. They don't compose well, though.

I've increasingly been finding myself in a position where I would like to select on both channel(s) and a condition variable. This has come up a few times in http2, where I use condition variables for flow control, but there are plenty of channels (including the net/http.Request.Cancel channel) in play too. Sometimes I need to both wait for flow control, or wait for a user to cancel their request, or the peer side to close their connection, etc.

I would love to be able to select on a condition variable, like if the sync.Cond type had a method:

// WaitChan returns a channel which receives a value when awoken
// by Broadcast or Signal. Unlike Wait, WaitChan does not unlock
// or lock the c.L mutex.
func (c *Cond) WaitChan() <-chan struct{} {
     // ....
}

The semantics would be the receiving from it acts like a runtime_Syncsemacquire on c.sema. We'd need to define what happens if another case in the select fires first. (does the semacquire get canceled?).

Thoughts?

@bradfitz bradfitz added the Proposal label Aug 5, 2016

@bradfitz bradfitz changed the title sync: mechanism to select on conditional variables proposal: sync: mechanism to select on conditional variables Aug 5, 2016

@bradfitz

This comment has been minimized.

Copy link
Member Author

commented Aug 5, 2016

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Aug 5, 2016

It seems to me that you can turn a condition variable into a channel by writing

c := make(chan struct{})
go func() {
    cond.L.Lock()
    cond.Wait()
    c <- struct{}{}
}()

I'm sure I'm missing something, but what?

@bradfitz

This comment has been minimized.

Copy link
Member Author

commented Aug 5, 2016

Yeah, except then I can leak goroutines if I'm not careful. I also pay the additional 4+ KB cost per select, which can be blocking for some time.

@josharian

This comment has been minimized.

Copy link
Contributor

commented Aug 5, 2016

Stupid question, but why would it be ok for WaitChan not to lock or unlock c.L? Relatedly, for Ian's code sample, why isn't a loop checking condition required?

@bradfitz

This comment has been minimized.

Copy link
Member Author

commented Aug 5, 2016

I would still reacquire the mutex afterwards.

Instead of this example from our docs:

c.L.Lock()
for !condition() {
    c.Wait()
}
... make use of condition ...
c.L.Unlock()

I would write:

c.L.Lock()
for !condition() {
    c.L.Unlock()
    select {
    case <-ctx.Done():
    case <-c.WaitChan():
    }
    c.L.Lock()
}
... make use of condition ...
c.L.Unlock()
@josharian

This comment has been minimized.

Copy link
Contributor

commented Aug 5, 2016

My expertise in this area is very limited, but as I understand it, it is important that Wait atomically unlock c.L and suspends execution. Maybe in your sample code this will occur, in that Unlock is immediately followed by select, and we always have cooperative scheduling, but in the event that someone added other code just before the select in order to prepare for the select (e.g. calling a function to decide whether to nil out a channel), then we have a race. Seems like a footgun. And if we moved to pre-emptive scheduling (or used another toolchain), then there might be no way to write the code correctly.

I might be wrong about all of this, though.

@bradfitz

This comment has been minimized.

Copy link
Member Author

commented Aug 5, 2016

There's nothing atomically special about the Cond.Wait method. It's just an unlock, wait, and lock:

https://github.com/golang/go/blob/release-branch.go1.7/src/sync/cond.go#L53

I don't see how this is any more of a footgun than anybody using the sync package in general. Or anybody using two goroutines and sharing global state without the sync package. Bad Go code is full of data races.

I'm proposing this as a mechanism for people who do know what they're doing. Not as some recommended high-level mechanism.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Aug 5, 2016

@josharian I think what you are thinking of is that it is critical that a condition variable not miss a signal/broadcast in between the unlock and the goroutine suspension. Other than that there is no implied atomicity. A simple implementation of condition variables can easily make that mistake--unlock, check signal, (receive unnoticed signal), suspend. Our implementation doesn't have that problem. The required atomicity is in runtime.notifyListWait, via the internal lock it acquires.

@minux

This comment has been minimized.

Copy link
Member

commented Aug 5, 2016

@bradfitz

This comment has been minimized.

Copy link
Member Author

commented Aug 5, 2016

Kinda. Really I want a magic type of hchan (sentinel value of hchan.elemtype) which makes hchan.buf mean it's a pointer to a notifyList, and have the select implementation on entry to select do the notifyListAdd, and then if separate case fires in select, we do something like a notifyListRemove, and unregister that waiter.

Otherwise I'm afraid of the leaks where my condition variable is woken up (because, say, I selected on my context.Done()), but then I find that my condition is satisfied and I exit the function, and never wait on the condition variable again. I need to tell the cond.Wait running in the goroutine to stop. Which makes me think it's better done in the implementation of select with a special channel type.

This wouldn't be a language change. But it would involve modifying the runtime to support an API addition.

@minux

This comment has been minimized.

Copy link
Member

commented Aug 5, 2016

could you design a user facing sync.Cond API for this?

we need to automatically lock cond.L when the channel
unblocks and the unlock needs to happen for the goroutine
that is actually winning the race. This seems too magical
to me. Maybe I'm missing something.

@bradfitz

This comment has been minimized.

Copy link
Member Author

commented Aug 5, 2016

@minux, I covered all this above.

@quentinmit quentinmit added this to the Proposal milestone Aug 8, 2016

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Sep 1, 2016

Something that has come to trouble me about this: channels are level-triggered. A channel has a value or it does not, and values do not disappear until somebody reads them.

Condition variables are edge-triggered. A call to the Signal method is a trigger that wakes up anything that is waiting right now. If nothing is waiting, nothing happens.

If we turn an edge-triggered mechanism into a level-triggered mechanism, then we either do something laborious to drain the level (read the value from the channel) if nothing needs it, or we have too many triggers.

This is particularly obvious when we consider the Broadcast method. The Broadcast method is easy to understand in terms of edge-triggering: everything that is waiting right now is alerted. Implementing that was level-triggering, without race conditions, is much more complex. Do we wake all select statements waiting on the channel right now? What value do we hand them?

The select statement, unlike channels, can be either edge-triggered or level-triggered. It would be meaningful to design some way to attach an edge trigger to a select statement. It just wouldn't go through a channel.

So I think this is a fairly subtle change.

@bcmills

This comment has been minimized.

Copy link
Member

commented Sep 8, 2016

@ianlancetaylor

channels are level-triggered. A channel has a value or it does not, and values do not disappear until somebody reads them.

default cases convert between "edge-triggered" and "level-triggered" events on channels. (For example, consider the usage of time.Ticker.C.)

In particular, a send-with-default converts an edge-triggered event into a level-triggered event by "latching" on the first edge-crossing. A receive-with-default converts a level-triggered event to an edge-triggered event by "unlatching" the channel when the edge-trigger no longer applies.

The Broadcast method is easy to understand in terms of edge-triggering: everything that is waiting right now is alerted. Implementing that was level-triggering, without race conditions, is much more complex. Do we wake all select statements waiting on the channel right now? What value do we hand them?

On a Broadcast, we would wake all select statements that have evaluated the case to receive it (and reacquire the lock before unblocking the case, which would either require a language change or a very deep runtime hook).

With the "channel as cond-var" pattern we can implement without such a hook, Broadcast corresponds to close (and unfortunately you end up needing to allocate a new channel every time you Broadcast).

With a built-in mechanism, we could do even better: we could have the Signal and Broadcast operations receive values, and the Wait operation return the value from the corresponding signal. (If we want something compatible with sync.Cond, I would propose that we send c.L as the value.) You could imagine using the same (or a similar) mechanism for implementing futures natively: a future is a selectable that can be sent to exactly once but received from any number of times. And there are also some interesting possibilities involving Broadcast with a channel (or another Cond) as a parameter...

The tricky part, I think, is constructing the API such that either the sender or the receiver can abandon a case after it has marked the other side as "ready".

@funny-falcon

This comment has been minimized.

Copy link
Contributor

commented Oct 16, 2016

I add proposal for "future" internal type #17466 , and it looks similar (in spirit) to this proposal.

@rsc

This comment has been minimized.

Copy link
Contributor

commented Nov 7, 2016

After implementation of #8898 we'd necessarily have the runtime support for alternate kinds of channels. At that point it might make sense to try this.

@josharian

This comment has been minimized.

Copy link
Contributor

commented Dec 4, 2016

If we do this, we might also want to extend it to sync.Lockers. I'm working with some code now where I have a sync.Mutex that might be held by someone else for a long time and a context.Context to respect. For the same reasons as Brad already outlined, I'd like to be able to use a select to either acquire the mutex or read from ctx.Done().

select {
case <-mu.C():
	// do work
	mu.Unlock()
case <-ctx.Done():
	// clean up, mu is not locked
}
@funny-falcon

This comment has been minimized.

Copy link
Contributor

commented Dec 4, 2016

I'd like to be able to use a select to either acquire the mutex or read from ctx.Done().

@josharian Looks like channel with buffer of size 1:

  • Lock() is write to channel,
  • Unlock() is read from.

we'd necessarily have the runtime support for alternate kinds of channels.

Then, why not implement "future"?

But, perhaps I didn't quite understand it. Excuse me then.

@rsc rsc changed the title proposal: sync: mechanism to select on conditional variables proposal: sync: mechanism to select on condition variables Apr 10, 2017

@eaburns

This comment has been minimized.

Copy link

commented Jun 29, 2017

Sorry to stumble in, but this edge/level-trigger goroutine leak issue reminds me of an old golang-dev thread [1] about "non-parallel channels". On that thread, I (admittedly without much thought) proposed a new way to make a channel/goroutine pair where the two are intimately tied, such that when all receivers are garbage collected, the goroutine can also be garbage collected. It's a language change, and not fully-thought-out, but perhaps some such thing could present a more general solution to this type of goroutine leak without needing special handling for select or timer-specific channels.

[1] https://groups.google.com/d/msg/golang-dev/VoswK7OBckY/-4ZPi3XoSI4J

@cespare

This comment has been minimized.

Copy link
Contributor

commented Jul 22, 2017

I keep running into this when plumbing context through things.

For example, I have an implementation of a connection pool which is cleanly expressed with a mutex and a sync.Cond. If there are no available connections nor capacity to create new ones, a caller waits to borrow with cond.Wait. I want to be able to pass a context.Context through and cancel the wait, so it would be nice to select on both cond.Wait and ctx.Done().

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 24, 2017

@cespare Are you running into significant cases where you can't easily replace the sync.Cond with a channel (for example, due to too much overhead from allocating the channel)? If so, could you describe them in a bit more detail?

@zombiezen

This comment has been minimized.

Copy link
Contributor

commented Jul 24, 2017

IIUC, @bcmills, you are proposing that folks do something like https://play.golang.org/p/zyi-LBlyBN?

That would solve the use-case I stumbled upon this issue for. But I wouldn't say it's obvious. :) I have no idea about the runtime efficiency.

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 24, 2017

@zombiezen Provided that you can keep the locked:unlocked ratio low (to reduce contention), I would only use a mutex for the Cond, not for the Mutex itself.

But I think the example you linked is a bit too simple anyway: the Cond usage you're showing there looks more like Signal than Broadcast, and for that kind of usage the channel can function as both the Mutex and the Cond: https://play.golang.org/p/beoQFQEx0e

@rogpeppe

This comment has been minimized.

Copy link
Contributor

commented Jul 24, 2017

@zombiezen I don't get how your example is different from https://play.golang.org/p/pqyJScFA2X.
@bcmills We overlapped with slightly different implementations! :)

FWIW I have found sync.Cond particularly useful when dealing with one-to-many
goroutine topologies (for example when one goroutine is changing state and wants to
broadcast the fact of the changed state to many listeners but without blocking
or maintaining per-listener state).

Here's an example of a package that uses sync.Cond and where I'd like to be able to
be able to interrupt the Wait: http://godoc.org/github.com/juju/utils/voyeur

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 24, 2017

@rogpeppe

It looks like you're only calling Broadcast and not Signal, which makes the conversion from a sync.Cond to a channel pretty straightforward.

Something like (not tested): https://play.golang.org/p/76i_EgBLCf
(Further simplifications may be possible.)

Is there a reason you can't / don't want to use a channel there?

@rogpeppe

This comment has been minimized.

Copy link
Contributor

commented Jul 25, 2017

@bcmills
You're right - I could use a channel there, although it's a pity to have
to allocate a channel for every message send. I suspect there would
be a significant performance hit in a micro-benchmark, but it's probably
negligible compared to other work.

@cespare

This comment has been minimized.

Copy link
Contributor

commented Jul 25, 2017

@bcmills I already need a mutex to protect other internal state. It's very natural and clean to express my code with a sync.Cond that piggybacks on that mutex. The changes required to change the Cond to a channel aren't immediately obvious to me, but I'll give it some thought and provide some sample code in a few weeks when I'm back at a computer.

@kr

This comment has been minimized.

Copy link
Contributor

commented Jul 26, 2017

If you're looking for cases where this would be helpful, see https://github.com/chain/chain/blob/1351422fd4c23991feea239fb6e5c2eca6432804/protocol/protocol.go#L257-L292.

It would be a considerable improvement, both in readability and runtime resource use, if this could select on a channel and a Cond together. Currently, that code allocates a new channel plus one or two goroutines for every waiter, which is a big waste.

Note that we use a single Cond here, but each waiter is waiting on a slightly different condition. They each want to know when the incrementing counter reaches a particular threshold, but the threshold can vary for each waiting goroutine. This is a poor fit for channels, as you can see from the code. We could modify this code to make a different efficiency tradeoff (one channel per threshold rather than one channel per waiting goroutine), but it would not improve readability.

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 26, 2017

We could [use] one channel per threshold rather than one channel per waiting goroutine[,] but it would not improve readability.

@kr The code you linked to seems like it leaks the BlockWaiter and BlockSoonWaiter goroutines for an arbitrarily long time (forever, if the condition never holds but the caller cancels their Context). That seems much more severe than a readability issue, and it wouldn't obviously change if you could select on the sync.Cond.

@kr

This comment has been minimized.

Copy link
Contributor

commented Jul 26, 2017

Indeed, the BlockWaiter goroutine exists until its condition is satisfied. That's part of what I was referring to by "wasteful". (Note that, in context, this is a reasonable behavior because we expect the counter to make steady progress and eventually to satisfy any threshold.)

If we could select on a Cond, there'd be no need for us to create these one-off goroutines in the first place.

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 26, 2017

If we could select on a Cond, there'd be no need for us to create these one-off goroutines in the first place.

I guess that's part of my point? It looks like you'd already be better off without creating these one-off goroutines.

A heap that associates thresholds with channels would let you register and wake up each waiter in O(log n) for a maximum queue depth of n waiters. With a selectable sync.Cond, each threshold is O(n) due to spurious wakeups. That's the difference between O(n log n) and O(n^2) total running time.

I don't know what kind of constant factors you're dealing with, but to me, O(n log n) with n extra allocations seems a lot less wasteful than O(n^2), especially when you factor in the extra cache contention from each of those spurious wakeups locking and unlocking the mutex.

@jba

This comment has been minimized.

Copy link
Contributor

commented Jul 26, 2017

@bcmills According to this thread, sync.Cond is not subject to spurious wakeups.

@kr

This comment has been minimized.

Copy link
Contributor

commented Jul 26, 2017

It looks like you'd already be better off without creating these one-off goroutines.

A heap that associates thresholds with channels would let you register and wake up each waiter in O(log n) for a maximum queue depth of n waiters.

Yeah, that would be the tradeoff I mentioned above. If anything, it would make the code even more complicated. It would certainly not improve readability beyond what we have already, so we wouldn't be better off. As for resource use, our current code is efficient enough in practice, it's not a problem. If we could select on a Cond, the code would become both more readable and more efficient.

Here I'm primarily concerned with code complexity and readability. In other scenarios, the efficiency improvement could be make-or-break; for us, it would be a nice bonus.

(Maybe don't focus too much on efficiency at the expense of complexity. Readability is extremely important!)

I don't know what kind of constant factors you're dealing with, but to me, O(n log n) with n extra allocations seems a lot less wasteful than O(n^2).

I couldn't answer that without measuring both options. But it seems like either one could benefit to some degree from selecting on a Cond.

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 26, 2017

@jba sync.Cond itself is not subject to spurious wakeups, but if you're using the same Cond to signal crossings of many independent thresholds, each waiter gets signaled for potentially many threshold crossings that aren't the one it is interested in.

@cespare

This comment has been minimized.

Copy link
Contributor

commented Sep 5, 2017

@bcmills following up on my July comments:

@cespare Are you running into significant cases where you can't easily replace the sync.Cond with a channel (for example, due to too much overhead from allocating the channel)? If so, could you describe them in a bit more detail?

Let's set aside efficiency for now (though in some cases, as others have pointed out, that's definitely a relevant concern).

I took one of my sync.Cond use cases, which is a connection pool that I mentioned over in #21165 (comment), and extracted out some the interesting stuff into an example that I can share. (The example does not include the full complexity, but I think it's interesting enough to discuss.)

Check it out here: https://github.com/cespare/misc/tree/master/condchan

I included the sync.Cond-based implementation (which is what we use in our real code) and I also wrote a channel-based implementation modeled on your demo code at https://play.golang.org/p/beoQFQEx0e.

I'd be interested in what you think about the code. Do you see simplifications that preserve the desired properties that I listed?

I found that writing the channel-based version was a fun and interesting exercise, and I had to think pretty hard to come up with something that works (and to convince myself that it's correct). I had a bunch of previous iterations that had fairly subtle bugs. I'm sure that the cond-based solution is also bug-prone in this way, but on balance, I feel like the channel-based version is significantly trickier/subtler.

@bcmills

This comment has been minimized.

Copy link
Member

commented Sep 6, 2017

I'd be interested in what you think about the code. Do you see simplifications that preserve the desired properties that I listed?

Yes: cespare/misc#1

I found that writing the channel-based version was a fun and interesting exercise, and I had to think pretty hard to come up with something that works

Agreed: a typical CS education covers the usage of condition variables, so using channels instead can make it harder to map the problems we find to known patterns.

@EdSchouten

This comment has been minimized.

Copy link

commented Oct 4, 2018

Also running into this issue, where I have a gRPC call that waits for a state transformation on a server and reports changes. If clients cancel these blocking/waiting RPCs, I currently leave goroutines behind, waiting on the condition variable.

What about having a func (c *Cond) WaitWithContext(context.Context) error? By using context objects, support for timeouts comes for free.

@bcmills

This comment has been minimized.

Copy link
Member

commented Oct 4, 2018

@EdSchouten, is there a reason you can't replace the condition variable with a channel?

See my talk on Rethinking Classical Concurrency Patterns: the section on condition variables starts on slide 37, and there is more detail on patterns for broadcast events in the backup slides (101-105).

@virtuald

This comment has been minimized.

Copy link

commented Oct 11, 2018

I just found an implementation of a condition variable using channels at https://github.com/anacrolix/missinggo/blob/master/chancond.go . It's similar to some of the backup slides in @bcmills talk referenced above. While it seems useful for event notifications, because of its locking behaviors it would be prone to race conditions if you tried to use it for some of the things one might traditionally use a condition variable for.

@jasajona

This comment has been minimized.

Copy link

commented Jan 28, 2019

Cancellable Cond package that implements all sync.Cond methods and passes all sync.Cond tests.
https://gitlab.com/jonas.jasas/condchan

Please write your comments about it.

@rogpeppe

This comment has been minimized.

Copy link
Contributor

commented Jan 28, 2019

@jasajona I'm not convinced, I'm afraid. It can panic when Signal is called at the same time as Broadcast.

For example, this code panics immediately on my machine:

package main

import (
	"gitlab.com/jonas.jasas/condchan"
)

func main() {
	var cond condchan.CondChan
	go func() {
		for {
			cond.Signal()
		}
	}()
	go func() {
		for {
			cond.Broadcast()
		}
	}()
	select {}
}

Concurrency code is tricky!

@jasajona

This comment has been minimized.

Copy link

commented Jan 28, 2019

Thank you for pointing out a bug! Fixed it and made additional test:
https://gitlab.com/jonas.jasas/condchan/commit/96de89d3cf0e4cd6b14e519d06ddc87fc4c365cf
That was a small optimization that caused this bug. Please share if you have any other ideas how to break CondChan lib!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
You can’t perform that action at this time.