Priority cases in select?

[T L]

sometimes, I do want one case on a select block get selected even if there are multiple unblocked cases.
For example, I don't want the dataCh case is selected if the stopCh and the timer channel are unblocked:

select {
case <- stopCh:
    return
case value := <-dataCh:
}

select {
case <- time.After(time.Second):
    return
case dataCh <- value:
}

Is there a solution to satisfy my need currently?

[Jan Mercl]

On Wed, Jan 25, 2017 at 2:14 PM T L <tapi...@gmail.com> wrote:

> sometimes, I do want one case on a select block get selected even if there are multiple unblocked cases.
> For example, I don't want the dataCh case is selected if the stopCh and the timer channel are unblocked:

        select {

        case <-priorityHigh:

                ...

        default:

                select {

                case <-priorityLow:

                        ...

                default:

                        select {

                        case <- priorityLowest:

                                ...

                        }

                }

        }

--

-j

[T L]

It is really a solution. :)
Sometimes I use the following one:

select {
case <- stopCh:
    return

default:

}

select {
case <- stopCh:
    return
case value := <-dataCh:
}

But both our solutions are not less efficient than a priority select.

How about to enhance the select block syntax by assign a sort method for unblocked cases:

select (random | priority | ordered) {

case <- stopCh:
    return
case value := <-dataCh:
}

random: the current implementation
priority: by the case appearance order
ordered: one by one. (The last selected case will be the last candidate in the next round)

 

[Egon]

type poller func() bool

var pollers []poller

pollers = append(pollers, func() bool {

select {

case <-priority:

// ...

default:

return false

}

return true

})

for {

for _, p := range pollers {

if p() {

break

}

}

}

[Axel Wagner]

I don't believe the actual use case described can be mapped. From what I understand, the intended behavior was

a) put the goroutine to sleep until some communication can proceed

b) if exactly one communication can proceed, do it

c) if multiple communications can proceed, choose the one with the highest priority

The suggested solutions (or any I can think of) violate at least one of these. They either wait busily, violating a, or they try to communicate in priority-order, then, as a last resort, block on any particular case, violating b, or they fall back to a regular select, violating c.

I don't know enough about how select is implemented to pass any judgement on whether this can be efficiently implemented, but I'm also not sure it's such a great idea. Choosing a case uniformly at random was a deliberate design decision to prevent starvation. There is a certain danger in people not realizing that they become susceptible to starvation if they do this. It's also a feature rabbit-hole. I'd predict, that next up, someone who experiences starvation wants to add weighted scheduling ("give this case an 80% chance of succeeding and this other case 20%, so that eventually either will proceed") or more complicated scheduling strategies.

I think such edge-cases for scheduling requirements should rather be implemented separately in a library. Yes, it's complicated code, but that's all the more reason why it shouldn't be in everyone's go runtime.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jan Mercl]

On Wed, Jan 25, 2017 at 5:00 PM 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:

> I don't believe the actual use case described can be mapped. From what I understand, the intended behavior was
> a) put the goroutine to sleep until some communication can proceed
> b) if exactly one communication can proceed, do it
> c) if multiple communications can proceed, choose the one with the highest priority
>
> The suggested solutions (or any I can think of) violate at least one of these. They either wait busily, violating a, or they try to communicate in priority-order, then, as a last resort, block on any particular case, violating b, or they fall back to a regular select, violating c.

v2: https://play.golang.org/p/lE4SpFjK_C

--

-j

[Axel Wagner]

Well, while this changes the random distribution, it still violates c. c specifically requires deterministic behavior in the case that multiple communications can proceed.

I may be reading OP wrong, but from what I understand, the idea is that this test suite (roughly) is supposed to deterministically pass: https://play.golang.org/p/gjl-1ny1Iw (and yes, I am aware that a) this doesn't work because we can't test for deadlocks and b) strictly speaking it's not deterministic that other goroutines get scheduled during time.Sleep, but you get the point).

I don't believe this to be possible currently, only using the primitives given by the language. An implementation would basically (IMHO) need to create their own scheduling and channel implementation. Which (IMHO) is also the correct way to solve this, as legitimate use cases for it are a rare edge-case that we shouldn't complicate the language for.

[John Souvestre]

> I don't believe the actual use case described can be mapped. From what I understand, the intended behavior was

> a) put the goroutine to sleep until some communication can proceed

> b) if exactly one communication can proceed, do it

> c) if multiple communications can proceed, choose the one with the highest priority

 

How about:

 

        select {

        case <-priorityHigh:

                ...

        default:

                select {

                case <-priorityLow:

                        ...

                default:

                        select {

                        case <- priorityHigh:

                                ...

                        case <- priorityLow:

                                ...

                        case <- priorityLowest:

                                ...

                        }

                }

        }

John

    John Souvestre - New Orleans LA

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

 

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[Axel Wagner]

Doesn't work. If no communication can proceed when entering the select, this degenerates to a simple select. For example, say there are no writers to any of those channels. At the same time, that the last select is entered, three different goroutines start blocking to write to one of the channels each. Even though priorityHigh could proceed, you will read from one of the other with ⅔ ​probability.

(a simpler case: Imagine that, while the goroutine is blocking in the innermost select, a second goroutines enters *the same* select, just with writes. Semantically, all three communications can proceed at the same time for both goroutines, so one is chosen uniformly)

This is the fundamental problem with all the nested select solutions; they assume that the code is evaluated atomically. But in reality, the state of a communication being possible can change at any point for an arbitrary number of channels. Thus, you can always construct a sequence where you revert to the innermost select, violating c.

[John Souvestre]

I understand what you are saying, but all of these situations are basically race conditions, aren’t they?  So there is no deterministic manner of resolving them.  Thus it doesn’t matter which is chosen.  However, in the more general, non-race, condition I believe that it meets the goals.

 

John

    John Souvestre - New Orleans LA

 

From: Axel Wagner [mailto:axel.wa...@googlemail.com]
Sent: 2017 January 25, Wed 13:19
To: John Souvestre
Cc: golang-nuts
Subject: Re: [go-nuts] Re: Priority cases in select?

 

Doesn't work. If no communication can proceed when entering the select, this degenerates to a simple select. For example, say there are no writers to any of those channels. At the same time, that the last select is entered, three different goroutines start blocking to write to one of the channels each. Even though priorityHigh could proceed, you will read from one of the other with ⅔ ​probability.

[Paul Borman]

I originally was thinking on the lines of what John said, but I proved it wrong, see https://play.golang.org/p/JwX_cxaR99 for the code.  You can't run it in the playground, but on my MacPro I get output like:

$ GOMAXPROCS=1 go run r.go

Failed after 1137702

Failed after 699376

Failed after 757658

^Csignal: interrupt

$ GOMAXPROCS=2 go run r.go

Failed after 12954

Failed after 63778

Failed after 11831

Failed after 277038

^Csignal: interrupt

So even though hi was clearly written before lo, it is possible to fail the first select, have hi and lo written (in that order), and then enter the second select which has a 50% chance on reading from lo, even with GOMAXPROCS set to 1.

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[Val]

Thank you John and Paul, I find this debate really interesting.

> hi was clearly written before lo

This is not my understanding of the memory model : because the channels are buffered, I can't really infer the "happens-before" relationship between the reading event of the channels.
And even if the relationship holds locally in the writing side, it has no strong implication on what other goroutines can see. I would say the hi and lo communications happen concurrently, hence the "wrong" results once in a while.

Val

[John Souvestre]

I believe that there is a typo in your example.  It seems that you have separate selects instead of nested selects.

 

Try:  https://play.golang.org/p/YWYhnLJsdS

 

John

    John Souvestre - New Orleans LA

 

From: Paul Borman [mailto:bor...@google.com]
Sent: 2017 January 25, Wed 16:01
To: John Souvestre
Cc: golang-nuts
Subject: Re: [go-nuts] Re: Priority cases in select?

 

I originally was thinking on the lines of what John said, but I proved it wrong, see https://play.golang.org/p/JwX_cxaR99 for the code.  You can't run it in the playground, but on my MacPro I get output like:

 

$ GOMAXPROCS=1 go run r.go

Failed after 1137702

Failed after 699376

Failed after 757658

^Csignal: interrupt

$ GOMAXPROCS=2 go run r.go

Failed after 12954

Failed after 63778

Failed after 11831

Failed after 277038

^Csignal: interrupt

 

So even though hi was clearly written before lo, it is possible to fail the first select, have hi and lo written (in that order), and then enter the second select which has a 50% chance on reading from lo, even with GOMAXPROCS set to 1.

On Wed, Jan 25, 2017 at 11:27 AM, John Souvestre <jo...@souvestre.com> wrote:

I understand what you are saying, but all of these situations are basically race conditions, aren’t they?  So there is no deterministic manner of resolving them.  Thus it doesn’t matter which is chosen.  However, in the more general, non-race, condition I believe that it meets the goals.

 

John

    John Souvestre - New Orleans LA

 

From: Axel Wagner [mailto:axel.wa...@googlemail.com]
Sent: 2017 January 25, Wed 13:19
To: John Souvestre
Cc: golang-nuts
Subject: Re: [go-nuts] Re: Priority cases in select?

 

Doesn't work. If no communication can proceed when entering the select, this degenerates to a simple select. For example, say there are no writers to any of those channels. At the same time, that the last select is entered, three different goroutines start blocking to write to one of the channels each. Even though priorityHigh could proceed, you will read from one of the other with ⅔ ​probability.

 

(a simpler case: Imagine that, while the goroutine is blocking in the innermost select, a second goroutines enters *the same* select, just with writes. Semantically, all three communications can proceed at the same time for both goroutines, so one is chosen uniformly)

 

This is the fundamental problem with all the nested select solutions; they assume that the code is evaluated atomically. But in reality, the state of a communication being possible can change at any point for an arbitrary number of channels. Thus, you can always construct a sequence where you revert to the innermost select, violating c.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[John Souvestre]

Hi Paul.

 

I looked at your code a bit more.  I believe that there might be another problem.  The call to “next” is concurrent with the setting of hi and low.  This means that “next” might get through the first select, get paused, hi and low be set, then “next” continues and executes the second select.  In this case, the result is nondeterministic – as expected.  To “next” it appears that hi and low were set at the same time.

 

If you ensure that next does have a chance to run between when hi gets set and when low gets set, then it works deterministically.  You could put a 1ms sleep between them, for example.  Even a “runtime.Gosched()” helps – but it isn’t a guarantee.

 

How close together can the hi and low settings be without there being a race?  There is no guaranteed safe interval, but on my machine 1ms was good enough that there were no “failures” within a one minute test run.  On Windows I can’t sleep for less than 1ms, but I suspect that the real answer is more like 1us for practical (not absolutely guaranteed) usage.  This is assuming the CPU isn’t loaded, too.  J

 

John

    John Souvestre - New Orleans LA

 

From: John Souvestre [mailto:Jo...@Souvestre.com]
Sent: 2017 January 25, Wed 17:02
To: 'golang-nuts'
Subject: RE: [go-nuts] Re: Priority cases in select?

 

I believe that there is a typo in your example.  It seems that you have separate selects instead of nested selects.

 

Try:  https://play.golang.org/p/YWYhnLJsdS

 

John

    John Souvestre - New Orleans LA

 

From: Paul Borman [mailto:bor...@google.com]
Sent: 2017 January 25, Wed 16:01
To: John Souvestre
Cc: golang-nuts
Subject: Re: [go-nuts] Re: Priority cases in select?

 

I originally was thinking on the lines of what John said, but I proved it wrong, see https://play.golang.org/p/JwX_cxaR99 for the code.  You can't run it in the playground, but on my MacPro I get output like:

 

$ GOMAXPROCS=1 go run r.go

Failed after 1137702

Failed after 699376

Failed after 757658

^Csignal: interrupt

$ GOMAXPROCS=2 go run r.go

Failed after 12954

Failed after 63778

Failed after 11831

Failed after 277038

^Csignal: interrupt

 

So even though hi was clearly written before lo, it is possible to fail the first select, have hi and lo written (in that order), and then enter the second select which has a 50% chance on reading from lo, even with GOMAXPROCS set to 1.

On Wed, Jan 25, 2017 at 11:27 AM, John Souvestre <jo...@souvestre.com> wrote:

I understand what you are saying, but all of these situations are basically race conditions, aren’t they?  So there is no deterministic manner of resolving them.  Thus it doesn’t matter which is chosen.  However, in the more general, non-race, condition I believe that it meets the goals.

 

John

    John Souvestre - New Orleans LA

 

From: Axel Wagner [mailto:axel.wa...@googlemail.com]
Sent: 2017 January 25, Wed 13:19
To: John Souvestre
Cc: golang-nuts
Subject: Re: [go-nuts] Re: Priority cases in select?

 

Doesn't work. If no communication can proceed when entering the select, this degenerates to a simple select. For example, say there are no writers to any of those channels. At the same time, that the last select is entered, three different goroutines start blocking to write to one of the channels each. Even though priorityHigh could proceed, you will read from one of the other with ⅔ ​probability.

 

(a simpler case: Imagine that, while the goroutine is blocking in the innermost select, a second goroutines enters *the same* select, just with writes. Semantically, all three communications can proceed at the same time for both goroutines, so one is chosen uniformly)

 

This is the fundamental problem with all the nested select solutions; they assume that the code is evaluated atomically. But in reality, the state of a communication being possible can change at any point for an arbitrary number of channels. Thus, you can always construct a sequence where you revert to the innermost select, violating c.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[John Souvestre]

Hi Val.

Yes! Not all software races are critical. I would say that this is an example of a non-critical one, depending on your needs (is 1us resolution good enough?). The only software method of synchronizing events absolutely would probably would require locking the CPU's interrupts. :)

Digital designers generally classify races as either critical (bad) or non-critical (not bad). Indeed, some non-critical races are necessary else things wouldn't work. :)

John

John Souvestre - New Orleans LA

-----Original Message-----
From: golan...@googlegroups.com [mailto:golan...@googlegroups.com] On Behalf Of Val
Sent: 2017 January 25, Wed 16:40
To: golang-nuts
Subject: Re: [go-nuts] Re: Priority cases in select?

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[Paul Borman]

Hi John, they are equivalent.  I chose to not indent the second select.  Your comment on the call to next being concurrent is the exact point of this program.  It reveals the race condition between the first and second select and demonstrates that even if hi and lo are both ready, or hi became ready first, the receive on lo can be satisfied first.

Val, the send on hi happens before the send on lo with the current compiler.  I am pretty sure the compiler will currently not reorder these, there is no reason.  Yes, a theoretical compiler could, but for this example, the demonstration that this is not deterministic, it is good that the compiler does not reorder the events.  This test case is to demonstrate the even if a send happens on the hi channel before a send happens on the lo channel, the next function may still decide to process the event from the lo channel as both sends happened between the first and second select.  Thus the fact that this is not deterministic is no longer theory, but empirical.  I believe from the OP's standpoint, they would have wanted the receive on hi to always be the selected one.

BTW, by the definition of determinism, it is not possible to have two events happen at once and that either of them may be considered first.  That is a nondeterministic program.  A deterministic program always produces the same results each time it is run.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

 

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[Wim Lewis]

On Jan 25, 2017, at 8:00 AM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
> It's also a feature rabbit-hole. I'd predict, that next up, someone who experiences starvation wants to add weighted scheduling ("give this case an 80% chance of succeeding and this other case 20%, so that eventually either will proceed") or more complicated scheduling strategies.
>
> I think such edge-cases for scheduling requirements should rather be implemented separately in a library. Yes, it's complicated code, but that's all the more reason why it shouldn't be in everyone's go runtime.

Since it is an edge case, but one which has legitimate (if idiosyncratic) uses, maybe the best approach would be to implement only enough in the go runtime to allow people to implement what they want. It seems to me that the minimal functionality needed would be a "non-receiving select". In other words, an addition to the reflect package which would allow people to efficiently wait for any of N channels to become receivable, without actually receiving anything.

Straw-man suggestion: a function reflect.TestSelect(cases []SelectCase) -> []int

which blocks until at least one case can proceed, and then returns a list of all cases which could proceed without blocking. Given that primitive, people can implement whatever behavior they want, and the primitive itself is fairly simple and well-defined.

Another option that occurs to me is to add a bool to the SelectCase struct which tells select, "block on this, but don't actually perform the action", but I think that would be less clean.

[Jakub Labath]

Glad someone mentioned reflect.Select. Implemented simple round robin solution with a timeout case (if no data is available at all) using just that .

To add to some priority would be just be a matter of setting the channel/cases to nil after several writes, rather than just after one like I do. Lower priority cases would get set to nil sooner.

The other reason I needed reflect.Select was because the number of channels being polled changes at runtime.

I agree with Wim that you can probably implement quite a few things using that - with priority just being one of them.

It does seem like use of reflect.Select would be really wasteful to use inside a loop but in my case at least I did not notice any problems (sorry don't have more scientific numbers than that).

Cheers

Jakub

[dja...@gmail.com]

Hi,
multiple priority with only 2 nested selects:
https://play.golang.org/p/ViI54yGyIm

Djadala

[T L]

The intention of priority cases is just to reduce the select block usages (from several to one) at some special situations,
instead of to control/adjust the selection possibilities of select-cases.
Fewer select-block usages means more efficient code.




 

[Volker Dobler]

[...] Fewer select-block usages means more efficient code.

What if the priority-enabled-select is much complexer and

massively less efficient than two all-equal-selects?

It might be less lines of code but not in itself more efficient

(for whatever definition of efficiency).

V.

[T L]

This shouldn't happen.

There is a case sorting stage in the select implementation.
For priority-enabled-select, the sorting stage can be omitted,
which makes the select flow a little more efficient (than the random sorting one) .