Still "missing" priority or ordered select in go?

[Øyvind Teig]

I know from some years ago that go did not have any priority or ordered select construct [1].

The idea is that select always is a nondeterministic choice operator, if this is still so. Implemented with a random, I assume.

Programming user defined "fair" algorithms or patterns is then not possible, I believe.

Is this still so in Go? No prioritised or ordered select in go?

But is there still a way to code this by f.ex. combining several selects? I saw a different take at this at [2], where the select is replaced a single chan containing a chan bundle, thus becoming "deterministic".

[1] Blog note Nondeterminism (disclaimer: no ads, no gifts, only fun and expenses)

[2] “A pattern for overcoming non-determinism of Golang select statement (3May2019) by Pedram Hajesmaeeli

[Jan Mercl]

On Thu, Apr 29, 2021 at 10:52 AM Øyvind Teig <oyvin...@teigfam.net> wrote:

> I know from some years ago that go did not have any priority or ordered select construct [1].

Not sure what does "ordered" wrt select mean, but the default clause
of the select statement provides exactly that - a priority mechanism:
first try something, otherwise do something else. The most elementary
one, sure, but all the more complex ones can be built with this basic
building block.

[Øyvind Teig]

Thanks! A construct like "pri select" or "alt select" or "ordered select", so it's not a "wrt", it's a tagging of select changing ets sematics from being nondeterminstic to deterministic. 

CSP has both: external choice (nondeterminsitic), internal choice (deterministic).

The occam programming language has both "ALT" (=select) and "PRI ALT".

The xC programming language has both "select" and "[[ordered]] select".

This is not solved with a default clause, which transforms the selective choice waiting for some event to happen into busy polling. It's nice yo have some times, but that is something orthogonal to pri/ordered.

[Jan Mercl]

On Thu, Apr 29, 2021 at 11:24 AM Øyvind Teig <oyvin...@teigfam.net> wrote:

> This is not solved with a default clause, which transforms the selective choice waiting for some event to happen into busy polling. It's nice yo have some times, but that is something orthogonal to pri/ordered.

Not sure if I would call it busy polling, but I meant schematically this:

select {
case x := <-highPriority:
handle(x)
default:
select {
case x := <-highPriority:
handle(x)
case x := <-lowPriority:
handle(x)
}
}

[Øyvind Teig]

Interesting! 

Your suggestion would in fact do pri select in the special case 1. below:

1. Poll highPri first (take it if it's ready), if highPri not ready then take lowPri (provided highPri has not become ready since the first poll)
2. However, if highPri has become ready between the first and the second, then it would be taken (provided lowPri is not also ready)
3. If both have become ready when the second select is entered they would be taken 50% of the time on the average
   

I fail to see that this is the general pri select that I am quering about whether it has "appeared" in go over the last years. I have a stomach feeling that it can not be implemented by polling. In the semantics of a select the whole select is evaluated before it is entered to se if there is/are any guard(s) ready. If not, pick randomly. If not, set alle guards up in some wait state.

The default case I have always used like "since no event ready (polling) then do something else than listening again on the same events". occam has deafult (although it's called TRUE & SKIP), xC does not.

[Øyvind Teig]

If not, pick randomly -> If so, pick randomly

[Axel Wagner]

On Thu, Apr 29, 2021 at 2:26 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

Interesting! 

Your suggestion would in fact do pri select in the special case 1. below:

1. Poll highPri first (take it if it's ready), if highPri not ready then take lowPri (provided highPri has not become ready since the first poll)
2. However, if highPri has become ready between the first and the second, then it would be taken (provided lowPri is not also ready)
3. If both have become ready when the second select is entered they would be taken 50% of the time on the average
   

One thing to point out is that since we are talking about concurrency, where you can really only talk about something happening "after" something else happened, if there is a causal edge between them, this really *is* equivalent to a simple priority select. You can't observe the difference, unless you add more synchronization - in which case we aren't really talking about the code under discussion anymore.

I fail to see that this is the general pri select that I am quering about whether it has "appeared" in go over the last years.

I tend to agree with you on this though. So to answer that question plainly: No, there is no prioritized select in Go and I find it personally unlikely that we'll get one. It might be possible to address some use cases when we get generics, though.

 

I have a stomach feeling that it can not be implemented by polling. In the semantics of a select the whole select is evaluated before it is entered to se if there is/are any guard(s) ready. If not, pick randomly. If not, set alle guards up in some wait state.

The default case I have always used like "since no event ready (polling) then do something else than listening again on the same events". occam has deafult (although it's called TRUE & SKIP), xC does not.

torsdag 29. april 2021 kl. 11:36:45 UTC+2 skrev Jan Mercl:

On Thu, Apr 29, 2021 at 11:24 AM Øyvind Teig <oyvin...@teigfam.net> wrote:

> This is not solved with a default clause, which transforms the selective choice waiting for some event to happen into busy polling. It's nice yo have some times, but that is something orthogonal to pri/ordered.

Not sure if I would call it busy polling, but I meant schematically this:

select {
case x := <-highPriority:
handle(x)
default:
select {
case x := <-highPriority:
handle(x)
case x := <-lowPriority:
handle(x)
}
}

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/47051a51-f040-4b51-a792-24a0f96c50f4n%40googlegroups.com.

[Jan Mercl]

On Thu, Apr 29, 2021 at 2:26 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

> Your suggestion would in fact do pri select in the special case 1. below:
>
> Poll highPri first (take it if it's ready), if highPri not ready then take lowPri (provided highPri has not become ready since the first poll)
> However, if highPri has become ready between the first and the second, then it would be taken (provided lowPri is not also ready)
> If both have become ready when the second select is entered they would be taken 50% of the time on the average

My analysis is different. There are four cases on entry of the outer
select statement:

1. high is ready and low is ready -> high handled, correct.
2. high is ready and low is not ready -> high handled, correct.
3. high is not ready and low is ready -> low handled, correct.

The "interesting" case is

4. high not ready and low not ready.

We enter the default clause of the outer select statement and enter
the inner select statement. Now there are three subcases when
eventually something gets ready:

4a. high gets ready before low gets ready -> high handled, correct.
4b. low gets ready before high gets ready -> low handled, correct.
4c. both high and low get ready at the same time -> one of them is
randomly chosen, correct.

[Øyvind Teig]

I agree with you.

However, with the first select in the example we have a "first" and with the second we have an "after" which might be considered race condition(s9 for the purpose of seeing the example of what I was after.

Also, scheduling arguments cannot be used here: like "we know that there is no scheduling (of go goroutines) between the first and the second select." If we know, it's not an argument.

[Robert Engels]

It is trivial to do a priority select. Check the high priority channel again after getting a low priority value. If the high priority is available enqueue the low value and handle the high. 

It is also trivial to “delay” the handling to allow more time for high events to arrive if dealing with synchronized events and you need to account for jitter. 

On Apr 29, 2021, at 8:10 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:

I agree with you.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/cf43611c-599f-46d9-98ac-60ede00daea9n%40googlegroups.com.

[Øyvind Teig]

Jan, I agree on your list, it's better set up than mine. 

But you can add a point after (4.) though, call it (second.pre), dealing with what might have happened after the first select decided that none were taken until it evaluates the precondition to the second select. 

4c is not "correct" as I want it. In the pri select case, if more than one is ready, then they shall not be randomly chosen. Never. They should be selected according to priority.

As I discussed (and several with me) in the blog note, the fact that Go doesn't seem to have it, then go needs another definition of "fair" than what is normal discussing these things. The basic idea for Google was, if we have a problem with fairness (none gets starved, all get served), just add another computer (said over a beer). Plus, the need for the fairness that one can build with a pri select (most often by reordering the list of guards according to one's pleasing of what one might think of as fair), is according to Goodle (on go, I think), so tiny that we make it simple: drop it. Of course it's also easy to try to implement one's own fairness and fail with it. In a realtime system it's not that easy to test, and these things most often are best evaluated on paper. So a formal proof might do.

[Axel Wagner]

My argument is that you can't distinguish the case "neither was ready and highPriority and lowPriority became ready simultaneously and lowPriority was selected" from "highPriority became ready after lowPriority" (as long as there is the same code in both highPriority cases). Because there is no "simultaneous" or "after" in concurrency, unless you use synchronization - the real phrasing is "highPriority and lowPriority became ready simultaneously" and if, *in real time* that means one or the other came first is indeterminate. There is no implementation or scheduling argument here - this argument is purely based on the Go memory model and the spec.

If there is no observable difference in behavior, the two are equivalent.

But either way, as I said, it's not really the same, just based on readability and clarity. It's semantically equivalent, but semantically, Go is equivalent to Assembly and yet we prefer Go :)

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/cf43611c-599f-46d9-98ac-60ede00daea9n%40googlegroups.com.

[Øyvind Teig]

I sent that to the wrong entry! Is it possible that you could make a code example?

[Øyvind Teig]

axel, it's difficult to try to explain in words how a select behaves. On that we can agree. For me, select cases can be channels, timeouts, external events etc. If a task is in a select (none triggered yet) and there is an interrupt that detects the select entry, it's ticked as triggered, the select is torn down, and in time the select will be taken with that event only. Not like Linux select which can deliver several causes. But if the timrout came just before the pin, then.. etc. Temporal logic in this case certainly makes sense.

[Jan Mercl]

On Thu, Apr 29, 2021 at 3:23 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

> 4c is not "correct" as I want it. In the pri select case, if more than one is ready, then they shall not be randomly chosen. Never. They should be selected according to priority.

That's not what 4c says. Instead of "more than one ready" it says
"both high and low _get ready at the same time_".

Note that in the first approximation the probability of 4c happening
is approaching zero. If we consider time "ticks" in discrete quanta,
the probability is proportional to the size of the quantum. And
depending on a particular implementation of the scheduler the
probability of 4c can still be exactly zero. For example, the OS
kernel may deliver only one signal at a time to the process etc.

So the "Never" case may quite well never happen at all.

[Øyvind Teig]

They could still both have become ready (not in the same "cycle") between the two selects. Even if that probability is low, it would need knowledge like yours to show that this may in fact be zero. There could be a descheduling in between, one of those in my opinion, not relevant arguments.

[robert engels]

I will give you the pseudo code:

{ // step #1 do select on both

   select high

   select low

}

if high read:

   return high

else:

   // we read a low so do a high poll

   {

       select high:

       default:

   }

 if high read:

      enqueue low and return high

 else:

      if queue empty:

         return low

      else:

           use queue and enqueue low from step #1 // FIFO order on low reads 

The above code will always return high values over low values (if high available), and return low values in order of events

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/ac6eecc4-ee82-4a21-9001-b2c704e74e8cn%40googlegroups.com.

[Jan Mercl]

On Thu, Apr 29, 2021 at 3:54 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

> Even if that probability is low, it would need knowledge like yours to show that this may in fact be zero. There could be a descheduling in between, one of those in my opinion, not relevant arguments.

The upper limit of 4c happening is 1/12 for random events. I guess in
practice it is at least an order of magnitude lower because the
"effective" time ticks are small.

[Ian Davis]

On Thu, 29 Apr 2021, at 3:09 PM, robert engels wrote:

I will give you the pseudo code:

{ // step #1 do select on both

   select high

   select low

}

if high read:

   return high

else:

   // we read a low so do a high poll

   {

       select high:

       default:

   }

 if high read:

      enqueue low and return high

 else:

      if queue empty:

         return low

      else:

           use queue and enqueue low from step #1 // FIFO order on low reads 

The above code will always return high values over low values (if high available), and return low values in order of events

This seems likely deadlock if the low channel is being filled continually by another goroutine. In addition I usually aim to give ownership of the channel to the writer so it can close cleanly, but mixing reads and writes in a single function greatly complicates that.

Ian

[robert engels]

It needs one other fix, and that is to have a check of the queue and poll high, in case the queue has elements when the method is entered.

But if you implement the queue using a buffered channel it is trivial to change the step #1 to handle this (the low and queue channels are mimic the high and low channel).

--
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.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/2460a16f-af1b-4613-ba4a-72b13e816a2bn%40googlegroups.com.

[robert engels]

It is not.

Because the low items will be read if there are no highs available. If the low isn’t read, the producer on the low will block.

Or you run out of memory if you cannot process the events fast enough - which is also easily handled by bounding the queue - but then you may need to drop items.

There are no free lunches.

But no deadlock.

-- 
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.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/f26ee7f2-a518-433f-89d4-d55aa0a9b07d%40www.fastmail.com.

[robert engels]

To clarify, you might never process a low item if a high is always available - but I believe that is what the OP is requesting.

It is also fairly trivial to add fairness to this ti always process a low if available every N cycles.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/00218548-6E27-4E16-A75F-88B6E30195E5%40ix.netcom.com.

[Axel Wagner]

On Thu, Apr 29, 2021 at 3:54 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

They could still both have become ready (not in the same "cycle") between the two selects. Even if that probability is low, it would need knowledge like yours to show that this may in fact be zero. There could be a descheduling in between, one of those in my opinion, not relevant arguments.

FTR, again: Yes, it's definitely possible, but it's irrelevant. It makes no observable difference. Even if we had a prioritized select, it would still be *de facto* implemented as a multi-step process and even then, you might run into exactly the same situation - you could have both channels becoming ready while the runtime does setup, or you could have a random scheduling event delaying one of the goroutines infinitesimally, or you could have…

This is why we *don't* talk about the behavior of concurrent programs in terms of cycles and time, but instead based on causal order. We don't know how long it takes to park or unpark a goroutine, so all we can say is that a read from a channel happens after the corresponding write. In terms of time, between entering the `select` statement and between parking the goroutine might lie a nanosecond, or a million years - we don't know, so we don't talk about it.

The memory model is exactly there to abstract away these differences and to not get caught up in scheduling and cycle discussions - so, FWIW, if these arguments are not relevant, you shouldn't bring them up. Logically, between the first `select` statement and the second `select` statement, there is zero time happening. Arguing that there is, is using exactly those irrelevant arguments about schedulers and processing time.

 

torsdag 29. april 2021 kl. 15:47:42 UTC+2 skrev Jan Mercl:

On Thu, Apr 29, 2021 at 3:23 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

> 4c is not "correct" as I want it. In the pri select case, if more than one is ready, then they shall not be randomly chosen. Never. They should be selected according to priority.

That's not what 4c says. Instead of "more than one ready" it says
"both high and low _get ready at the same time_".

Note that in the first approximation the probability of 4c happening
is approaching zero. If we consider time "ticks" in discrete quanta,
the probability is proportional to the size of the quantum. And
depending on a particular implementation of the scheduler the
probability of 4c can still be exactly zero. For example, the OS
kernel may deliver only one signal at a time to the process etc.

So the "Never" case may quite well never happen at all.

--

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/2460a16f-af1b-4613-ba4a-72b13e816a2bn%40googlegroups.com.

[Axel Wagner]

FWIW, maybe this helps:

Assume a read happened from lowPriority, even though highPriority was ready to read as well. That's, AIUI, the outcome you are concerned about.

In that situation, how would you know that highPriority was ready to read as well?

[roger peppe]

I agree with Axel's take here. It seems, Øyvind, that you are concerned more with principle than practice here. Can you give an example of a real world case where you think that this might actually matter?

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfFC1gtxbWZsy88gM4ymPncCjs6Q3YJpTcXym8bT1Ev6Kw%40mail.gmail.com.

[Øyvind Teig]

torsdag 29. april 2021 kl. 20:22:32 UTC+2 skrev rog:

I agree with Axel's take here. It seems, Øyvind, that you are concerned more with principle than practice here. Can you give an example of a real world case where you think that this might actually matter?

Thanks, yes. I have written some about that in the Nondeterminsim blog note, referred to at the top. I admit I indicated that seeing some code might be interesting, but it was the principle I was after. In the end a "yes" or "no".

Some from the chapter "-Nondeterministic selective choice in implementations is not good": (Preceeding the quote I have been telling about CSP's external nondeterministic choice in the specfications ("implement this any way you want") but in the implementation part we have to take decisions (deterministic, inner choice: "we do it this way"). I was thinking this is relevant because Why build concurrency on the ideas of CSP? Here's the quote:

"The statement was that with the non-deterministic guarded choice in Go, what happens is up to the run-time, which is “not good”. This is implementation, not specification. With occam there is ALT or PRI ALT, always coded as PRI ALT. For a server to be “fair” I have to code it myself, it’s up to me, at the application level to find the best algorithm. Which, during my years as occam programmer was “new starting channel index in the ALT-set is the channel index of the served channel + 1 modulo-divided by number of channels”. Channels are clients[0..4] (five) ALT‘ed in set [4,0,1,2,3] served index 4, then 4+1 rem 5 == 0 yields next ALT set [0,1,2,3,4]. Just served 4 and you’re at the back of the set."

The example here is a server with N clients where it is essential that none of clients will starve and none jam the server. I have needed to do this coding several times. Go has random select which in theory may mean starving and jamming. I worked with safety critical fire detection, and it was necessary to ensure this. Or at least we didn't dare to take the chance. We could not just add another machine.

To use select when that's fair enough (pun 1) - "fair enough" (pun 2). But If I want to be certain of no starving or jamming I need to code the fairness algorithm. I can then promise a client that may have been ready but wasn't served to come in before I take the previous clients that were allowed. This is at best very difficult if all we have is select. Having pri select as the starting point is, in this case, easier.

Øyvind

[Robert Engels]

I already gave you the solution to this. Trust me it works. I did HFT for 7+ years - the algo is well known. 

On Apr 29, 2021, at 2:05 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:



To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/20c0a14c-5e4e-47a3-a198-808f207980c4n%40googlegroups.com.

[Øyvind Teig]

1. I'm sorry I didn't follow up on your answer where you had got to the length of spelling out some code right before my eyes. I got lost in the other points (I actually started a response..)
2. I trust you
3. But to do more than trusting, understanding would be much better. I'm sorry: to understand I would need more than pseudo code
4. But I was really after whether the "pri" keyword (or whatever) in front of "select" had been introduced over the last years. The answer seems to be "no"
5. Although I appreciate that Turing proved that any language can code anything, I some times have had a hard time believing it. Maybe that's not exactly what he meant. But then, since I trust you, I do find that solution as surprising as as I would be happy to run it on The Go Playground

[Axel Wagner]

On Thu, Apr 29, 2021 at 10:47 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

1. I'm sorry I didn't follow up on your answer where you had got to the length of spelling out some code right before my eyes. I got lost in the other points (I actually started a response..)
2. I trust you
3. But to do more than trusting, understanding would be much better. I'm sorry: to understand I would need more than pseudo code
4. But I was really after whether the "pri" keyword (or whatever) in front of "select" had been introduced over the last years. The answer seems to be "no"

FWIW I did answer this explicitly above :) No, there is no way to manually specify priorities of `select` and no, I subjectively wouldn't predict it happening at any point in the near or far future. Unless someone comes up with an extremely convincing, so far unheard of argument in its favor :)

 

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/7ae6ae45-c341-4998-9229-74b133ac213fn%40googlegroups.com.

[roger peppe]

On Thu, 29 Apr 2021, 20:05 Øyvind Teig, <oyvin...@teigfam.net> wrote:

torsdag 29. april 2021 kl. 20:22:32 UTC+2 skrev rog:

I agree with Axel's take here. It seems, Øyvind, that you are concerned more with principle than practice here. Can you give an example of a real world case where you think that this might actually matter?

Thanks, yes. I have written some about that in the Nondeterminsim blog note, referred to at the top. I admit I indicated that seeing some code might be interesting, but it was the principle I was after. In the end a "yes" or "no".

Some from the chapter "-Nondeterministic selective choice in implementations is not good": (Preceeding the quote I have been telling about CSP's external nondeterministic choice in the specfications ("implement this any way you want") but in the implementation part we have to take decisions (deterministic, inner choice: "we do it this way"). I was thinking this is relevant because Why build concurrency on the ideas of CSP? Here's the quote:

"The statement was that with the non-deterministic guarded choice in Go, what happens is up to the run-time, which is “not good”. This is implementation, not specification. With occam there is ALT or PRI ALT, always coded as PRI ALT. For a server to be “fair” I have to code it myself, it’s up to me, at the application level to find the best algorithm. Which, during my years as occam programmer was “new starting channel index in the ALT-set is the channel index of the served channel + 1 modulo-divided by number of channels”. Channels are clients[0..4] (five) ALT‘ed in set [4,0,1,2,3] served index 4, then 4+1 rem 5 == 0 yields next ALT set [0,1,2,3,4]. Just served 4 and you’re at the back of the set."

The example here is a server with N clients where it is essential that none of clients will starve and none jam the server.

I have needed to do this coding several times. Go has random select which in theory may mean starving and jamming. I worked with safety critical fire detection, and it was necessary to ensure this. Or at least we didn't dare to take the chance. We could not just add another machine.

To use select when that's fair enough (pun 1) - "fair enough" (pun 2). But If I want to be certain of no starving or jamming I need to code the fairness algorithm. I can then promise a client that may have been ready but wasn't served to come in before I take the previous clients that were allowed. This is at best very difficult if all we have is select. Having pri select as the starting point is, in this case, easier.

To start with, if you've got N clients where N isn't known in advance, it's not possible to use Go's select statement directly because it doesn't provide support for reading from a slice.

You can do it with reflection though. It's not too hard to code something quite similar to your algorithm above.

For example: https://go2goplay.golang.org/p/S_5WFkpqMP_H

I think the above code should fit your definition of fairness, and it seems to me that it's a reasonably general approach.

 

  cheers,

    rog.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/20c0a14c-5e4e-47a3-a198-808f207980c4n%40googlegroups.com.

[Ian Lance Taylor]

On Thu, Apr 29, 2021 at 12:05 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
>
> The example here is a server with N clients where it is essential that none of clients will starve and none jam the server. I have needed to do this coding several times. Go has random select which in theory may mean starving and jamming. I worked with safety critical fire detection, and it was necessary to ensure this. Or at least we didn't dare to take the chance. We could not just add another machine.
>
> To use select when that's fair enough (pun 1) - "fair enough" (pun 2). But If I want to be certain of no starving or jamming I need to code the fairness algorithm. I can then promise a client that may have been ready but wasn't served to come in before I take the previous clients that were allowed. This is at best very difficult if all we have is select. Having pri select as the starting point is, in this case, easier.

When there are multiple ready results, the select statement in Go is
guaranteed to use a uniform pseudo-random selection
(https://golang.org/ref/spec#Select_statements). The fact that cases
are selected using a uniform distribution ensures that executing a
select statement in a loop can't lead to starving (I'm not sure what
jamming is).

As several people have said, it's meaningless to say "I want to ensure
that if both case A and case B are available then the select statement
will choose case A." It's meaningless because it relies on a notion
of simultaneity that literally doesn't exist. There will always be a
period of time after the select statement chooses B, but before it
actually executes the case, that case A may become ready. That will
be true for any possible implementation of select, because select is
not an atomic operation.

Therefore, this code using a hypothetical priority case

select {
case pri <-c1:
case <-c2:
}

can always be rewritten as

select {
case <-c1:
default:
select {
case <-c1:
case <-c2:
}
}

The rewritten select is exactly equivalent to the first. The only way
that they could not be equivalent would be if select were atomic.

Ian

[Øyvind Teig]

torsdag 29. april 2021 kl. 23:52:05 UTC+2 skrev rog:

On Thu, 29 Apr 2021, 20:05 Øyvind Teig, <oyvin...@teigfam.net> wrote:

torsdag 29. april 2021 kl. 20:22:32 UTC+2 skrev rog:

I agree with Axel's take here. It seems, Øyvind, that you are concerned more with principle than practice here. Can you give an example of a real world case where you think that this might actually matter?

Thanks, yes. I have written some about that in the Nondeterminsim blog note, referred to at the top. I admit I indicated that seeing some code might be interesting, but it was the principle I was after. In the end a "yes" or "no".

Some from the chapter "-Nondeterministic selective choice in implementations is not good": (Preceeding the quote I have been telling about CSP's external nondeterministic choice in the specfications ("implement this any way you want") but in the implementation part we have to take decisions (deterministic, inner choice: "we do it this way"). I was thinking this is relevant because Why build concurrency on the ideas of CSP? Here's the quote:

"The statement was that with the non-deterministic guarded choice in Go, what happens is up to the run-time, which is “not good”. This is implementation, not specification. With occam there is ALT or PRI ALT, always coded as PRI ALT. For a server to be “fair” I have to code it myself, it’s up to me, at the application level to find the best algorithm. Which, during my years as occam programmer was “new starting channel index in the ALT-set is the channel index of the served channel + 1 modulo-divided by number of channels”. Channels are clients[0..4] (five) ALT‘ed in set [4,0,1,2,3] served index 4, then 4+1 rem 5 == 0 yields next ALT set [0,1,2,3,4]. Just served 4 and you’re at the back of the set."

The example here is a server with N clients where it is essential that none of clients will starve and none jam the server.

I have needed to do this coding several times. Go has random select which in theory may mean starving and jamming. I worked with safety critical fire detection, and it was necessary to ensure this. Or at least we didn't dare to take the chance. We could not just add another machine.

To use select when that's fair enough (pun 1) - "fair enough" (pun 2). But If I want to be certain of no starving or jamming I need to code the fairness algorithm. I can then promise a client that may have been ready but wasn't served to come in before I take the previous clients that were allowed. This is at best very difficult if all we have is select. Having pri select as the starting point is, in this case, easier.

To start with, if you've got N clients where N isn't known in advance, it's not possible to use Go's select statement directly because it doesn't provide support for reading from a slice.

You can do it with reflection though. It's not too hard to code something quite similar to your algorithm above.

For example: https://go2goplay.golang.org/p/S_5WFkpqMP_H

Thanks! I like the fact that you can do it like this. However, there was "client 2" in the log(?)

Øyvind

[Øyvind Teig]

fredag 30. april 2021 kl. 02:45:02 UTC+2 skrev Ian Lance Taylor:

On Thu, Apr 29, 2021 at 12:05 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
>
> The example here is a server with N clients where it is essential that none of clients will starve and none jam the server. I have needed to do this coding several times. Go has random select which in theory may mean starving and jamming. I worked with safety critical fire detection, and it was necessary to ensure this. Or at least we didn't dare to take the chance. We could not just add another machine.
>
> To use select when that's fair enough (pun 1) - "fair enough" (pun 2). But If I want to be certain of no starving or jamming I need to code the fairness algorithm. I can then promise a client that may have been ready but wasn't served to come in before I take the previous clients that were allowed. This is at best very difficult if all we have is select. Having pri select as the starting point is, in this case, easier.

When there are multiple ready results, the select statement in Go is
guaranteed to use a uniform pseudo-random selection
(https://golang.org/ref/spec#Select_statements). The fact that cases
are selected using a uniform distribution ensures that executing a
select statement in a loop can't lead to starving (I'm not sure what
jamming is).

As several people have said, it's meaningless to say "I want to ensure
that if both case A and case B are available then the select statement
will choose case A." It's meaningless because it relies on a notion
of simultaneity that literally doesn't exist.

I have a stomach feeling that I agree with you. I will still argue against. I just wish someone could pinpoint where these standpoints clash, or don't. 

If there is no notion of simultaneity why all the effort to describe the random distribution? 

The select is first set up, at which time the code decides on which one to take if more than one guard is ready. If the clients were only sending, then nowhere in the system is this noted on "the other" side of the channel (in the server) before it enters the select. The channel would have noted the first contender, yes, but the servre have yet no idea. If none is ready, then the server was first on all the ends, and when a sender arrives it will match the guard set in the server and tear down the select. In due time the server is scheduled with that one event.

This is how I have seen it in several systems. I wonder what might be so different with go.

 

There will always be a
period of time after the select statement chooses B, but before it
actually executes the case, that case A may become ready. That will
be true for any possible implementation of select, because select is
not an atomic operation.

Therefore, this code using a hypothetical priority case

select {
case pri <-c1:
case <-c2:
}

can always be rewritten as

select {
case <-c1:
default:
select {
case <-c1:
case <-c2:
}
}

The rewritten select is exactly equivalent to the first. The only way
that they could not be equivalent would be if select were atomic.

Ok, so this is a pattern that Go people would use if they needed to do pri select. Then, why go to the lengths of the other code shown above? Is it because I have kind of "pressed" you to come up with code and then of course, one thing may be solved several ways? 

Will your Go code examples stand the test of formal verification? Of course, when it's not formally verified you probaby could not answer such a question. But the stomach feeling?

Another angle: Go does not have the expression before the select that evaluates to true or false. Nothing like

select { 

case (do_this) => val1 <-c1: 
case val2  <-c2: 
} 

Instead, the chan is set to nil to exclude it from the set. What might happen if we had a set of 100 clients and they were switched on and off internally in the server (that's their purpose) - when will the uniform distribution be reset? What's the life span of the distribution? With a psudorandom sequence any one value is only visited once on a round. We still want this to be fair. Could those having been served be served again (before the others) after a reset of the distribution, and this introduce a notion of unfairness?

 (I gues that jamming is that only one client alone gets to the server, whereas starving is that a client never gets to the server).

Øyvind

 

Ian

[Axel Wagner]

On Fri, Apr 30, 2021 at 9:53 AM Øyvind Teig <oyvin...@teigfam.net> wrote:

If there is no notion of simultaneity why all the effort to describe the random distribution?

While it's not possible for two cases to become ready at the same time, it's definitely possible for two cases to be ready when entering a select. That's where the random selection comes in.

There's also the notable difference between a select with a default and one without. A select with a default never blocks, so which branch is taken is *only* determined by what's ready when entering the select, whereas a select without can block and then gets woken up by the first communication that's ready - and there'll always be a "first".

In a sense, the nested select uses that: The outer select handles the "what's currently ready" case and the inner select handles the "what becomes ready in the future".

The priority select would use the same basic logic:

- Is the high priority case ready? If so, do that

- If not, block until one of the cases become ready - do the first that becomes ready

The crux here is exactly that we can't have two cases "becoming ready" at the same time, so we really *have* to "take the first one that becomes ready".

The select is first set up, at which time the code decides on which one to take if more than one guard is ready. If the clients were only sending, then nowhere in the system is this noted on "the other" side of the channel (in the server) before it enters the select. The channel would have noted the first contender, yes, but the servre have yet no idea. If none is ready, then the server was first on all the ends, and when a sender arrives it will match the guard set in the server and tear down the select. In due time the server is scheduled with that one event.

This is how I have seen it in several systems. I wonder what might be so different with go.

I don't think I understand this exposition. But on first glance, your description doesn't sound terribly different from what's happening in Go.

To be clear: No one is claiming it would be impossible to implement a priority select in Go. Obviously we could replace the pseudo-random choice by something else. We are just saying that it would be equivalent to the nested select code.

Ok, so this is a pattern that Go people would use if they needed to do pri select. Then, why go to the lengths of the other code shown above? Is it because I have kind of "pressed" you to come up with code and then of course, one thing may be solved several ways? 

I think the first code you where shown by Jan (which is the same as Ian's) is correct and I believe it's likely that your insistence that it isn't is what prompted people to come up with more and more complicated code.

Will your Go code examples stand the test of formal verification? Of course, when it's not formally verified you probaby could not answer such a question. But the stomach feeling?

I'm not very familiar with formal methods for this, or what the invariant is that would be verified.

I do feel quite confident about the statement that the shown snippet is equivalent to how I'd think a priority select would work.

Another angle: Go does not have the expression before the select that evaluates to true or false. Nothing like

select { 

case (do_this) => val1 <-c1: 
case val2  <-c2: 
} 

Instead, the chan is set to nil to exclude it from the set. What might happen if we had a set of 100 clients and they were switched on and off internally in the server (that's their purpose) - when will the uniform distribution be reset? What's the life span of the distribution? With a psudorandom sequence any one value is only visited once on a round.

I'm not sure what you mean here. Is what you call a "round" the cycle of the PRNG? In that case, this statement isn't true, the cycle is likely significantly longer than the number of cases. So we definitely chose at least one case multiple times per cycle.

AFAIK this is the PRNG used by the select, FWIW. I assume it simply calls into it (or likely `fastrandn` directly below) when entering a select with multiple available cases.

We still want this to be fair. Could those having been served be served again (before the others) after a reset of the distribution, and this introduce a notion of unfairness?

It can definitely happen, but I'm not sure that "unfairness" is a meaningful term here. AIUI the process is "if the runtime enters a select and multiple cases are ready, it chooses one uniformly at random" (within the limits of the PRNG). Yes, as an outcome this can mean that one case is hit more often than the others. But all cases are equally likely to be hit more often. And by the law of large numbers, you'd expect the distribution to flatten over time.

 (I gues that jamming is that only one client alone gets to the server, whereas starving is that a client never gets to the server).

Both are statistically unlikely, if we assume the PRNG is reasonably good - which I think we can, it has been subjected to reasonable statistical tests.

 

Øyvind

 

Ian

--
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.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/ec5e5c0f-c5bf-4efb-b1c4-dc056720ba5cn%40googlegroups.com.

[Øyvind Teig]

Axel, it is impolite not to try to comment and discuss each and every point above. I actually started to do exactly that when I discovered that it all boils down to this (FWIW?):

I have tried to expand on Jan's code (https://go2goplay.golang.org/p/7xDzP6Jvyl8), here: https://go2goplay.golang.org/p/vhmo_Vw6OQy. I have added a mediumPriority channel. (Hope it's right..)

Ian said that select is not an atomic operation. I assume (but everyone here seems to tell me the opposite), that at each default there are starts of new, unique selects? 

Here is one of the comments I wrote to one of Axel's points above, and it could be iterated over three priorities as well:

I think this is where I need to understand Go a little better, because it might be different from occam's default (TRUE & SKIP). Actually, this may be the reason why this thread is still not closed. To me it is very strange that between the first polling of the highPri and the default, why that outer select is not torn down. Then enter a new select, which would have two guards: high and low pri. In my head when setting up the new select there would be a decision of which one to select. It would select from the set of ready guards right there. They could both have become ready. Remember in my head these two may be hw pins. (If the first high pri poll was done at 0 ns and the second select's decision could be 10 ns later, then both hw pins could have become ready at 5 ns). If so the decision needs to be on one of them. With "only random" (yes, I think think this is so, on a general basis, but I accept that Go doesn't have the other option) to chose from, then it may chose the low pri, even if the high pri also was, hw wise, ready. 

If these two (or three) cannot be hardware pins (as in Go), then I reason (by induction(?)) that all of the code must be atomic with no descheduling in between, for me to understand that the scheme is 100% as intended: meaning that there is not any state where random select is ever used. 

rog wrote above (where I had indicated that occam (and also xC, said here) has a looping channel construct): "To start with, if you've got N clients where N isn't known in advance, it's not possible to use Go's select statement directly because it doesn't provide support for reading from a slice." Does this mean that aside from reflection (https://go2goplay.golang.org/p/S_5WFkpqMP_H - which still does not serve "client 2", shouldn't it?) then idiomatic Go for a small number of priorities is the one with default case(s), and it works 100% as intended, with no cognitive (?) reliance on Go's inner working under the hood? (I mean: "WYSIWYG semantics" kind of.)

I am at a point now that if the answer to the above is yes, I'll just say thank you for your help, and I will be a Go-wise wiser person. With my cognitive bias I will then have to accept that this is Go, nothing more to say. Just accept it. Anyhow, in case, thank you!

Øyvind

[Øyvind Teig]

One more thing, if (by presumably faulty reasoning above) random select is never done, would we need the two guards in the second select? 

https://go2goplay.golang.org/p/EJ2J1sQXVEk 

[Axel Wagner]

On Sun, May 2, 2021 at 9:23 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

Axel, it is impolite not to try to comment and discuss each and every point above.

I wasn't trying to be impolite. But I also won't go through your messages sentence by sentence, trying to say something even if I have nothing to say. Sorry. If that doesn't suit you, I'll step out of the conversation.

 

I have tried to expand on Jan's code (https://go2goplay.golang.org/p/7xDzP6Jvyl8), here: https://go2goplay.golang.org/p/vhmo_Vw6OQy. I have added a mediumPriority channel. (Hope it's right..)

That code is missing a case in the innermost select. This one seems correct:

https://go2goplay.golang.org/p/ZEy752iEOb9

 

Ian said that select is not an atomic operation. I assume (but everyone here seems to tell me the opposite), that at each default there are starts of new, unique selects? 

Here is one of the comments I wrote to one of Axel's points above, and it could be iterated over three priorities as well:

I think this is where I need to understand Go a little better, because it might be different from occam's default (TRUE & SKIP). Actually, this may be the reason why this thread is still not closed. To me it is very strange that between the first polling of the highPri and the default, why that outer select is not torn down. Then enter a new select, which would have two guards: high and low pri. In my head when setting up the new select there would be a decision of which one to select. It would select from the set of ready guards right there. They could both have become ready.

This description sounds correct. This is how Go behaves.

 

Remember in my head these two may be hw pins. (If the first high pri poll was done at 0 ns and the second select's decision could be 10 ns later, then both hw pins could have become ready at 5 ns). If so the decision needs to be on one of them. With "only random" (yes, I think think this is so, on a general basis, but I accept that Go doesn't have the other option) to chose from, then it may chose the low pri, even if the high pri also was, hw wise, ready.

This is fundamentally correct (though I'm not sure what you mean by "hw pin").

 

If these two (or three) cannot be hardware pins (as in Go), then I reason (by induction(?)) that all of the code must be atomic with no descheduling in between, for me to understand that the scheme is 100% as intended: meaning that there is not any state where random select is ever used.

It is.

Again: Your understanding is correct. But the resulting situation is still equivalent to a priority select. There is no observable behavior in difference between the two.

So let me repeat my question:

Assume a read happened from lowPriority, even though highPriority was ready to read as well. That's, AIUI, the outcome you are concerned about.

In that situation, how would you know that highPriority was ready to read as well?

I believe you'll find that the answer is "you can't".

 

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/9186c34b-1088-4ae0-8076-6c5cd0cdde38n%40googlegroups.com.

[Øyvind Teig]

Axel, I was saying (at least meaning) that it was impolite of me not to answer your exhaustive comments! The other way around. But I now see why you got upset. It may read that way too! I read things over many times, did spell checking, but I didn't see this coming! I will read the rest of the comments tomorrow! Please excuse me for my Bad English! I have always been impressed by the golang-nuts group, how well everything has been responded to, and how much people have taken the time to answer my questions, coming from the other side of the field. I don't take this for granted at all! Øyvind

[Axel Wagner]

No worries, I was not upset :) But I did misunderstand you, thanks for clearing that up.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/dc3898ea-032e-4b28-acd4-65e1b7cef21fn%40googlegroups.com.

[Øyvind Teig]

søndag 2. mai 2021 kl. 21:42:10 UTC+2 skrev axel.wa...@googlemail.com:

On Sun, May 2, 2021 at 9:23 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

(Removed clumsy sentence from me. Again: sorry!) Thanks for all this answering, Axel!

I have tried to expand on Jan's code (https://go2goplay.golang.org/p/7xDzP6Jvyl8), here: https://go2goplay.golang.org/p/vhmo_Vw6OQy. I have added a mediumPriority channel. (Hope it's right..)

That code is missing a case in the innermost select. This one seems correct:

https://go2goplay.golang.org/p/ZEy752iEOb9

Great! The rule is high in all selects, medium in two lowest, low only the last select.

Ian said that select is not an atomic operation. I assume (but everyone here seems to tell me the opposite), that at each default there are starts of new, unique selects? 

Here is one of the comments I wrote to one of Axel's points above, and it could be iterated over three priorities as well:

I think this is where I need to understand Go a little better, because it might be different from occam's default (TRUE & SKIP). Actually, this may be the reason why this thread is still not closed. To me it is very strange that between the first polling of the highPri and the default, why that outer select is not torn down. Then enter a new select, which would have two guards: high and low pri. In my head when setting up the new select there would be a decision of which one to select. It would select from the set of ready guards right there. They could both have become ready.

This description sounds correct. This is how Go behaves.

Great. I hoped so. Even if it migth get me into trouble below.

  

Remember in my head these two may be hw pins. (If the first high pri poll was done at 0 ns and the second select's decision could be 10 ns later, then both hw pins could have become ready at 5 ns). If so the decision needs to be on one of them. With "only random" (yes, I think think this is so, on a general basis, but I accept that Go doesn't have the other option) to chose from, then it may chose the low pri, even if the high pri also was, hw wise, ready.

This is fundamentally correct (though I'm not sure what you mean by "hw pin").

Great, I hoped so (2). Even if it migth get me into trouble below (2).

"hw pin": On xC (by XMOS) this is valid: https://go2goplay.golang.org/p/Min0kAI7Wao (it looked so much like Go that formatting was ok!)

Observe the clause between "case" and "=>" which is the expression, it has to be true to enable the guard. All guards false is an error.

If these two (or three) cannot be hardware pins (as in Go), then I reason (by induction(?)) that all of the code must be atomic with no descheduling in between, for me to understand that the scheme is 100% as intended: meaning that there is not any state where random select is ever used.

It is.

Trouble A: If random select is never used in the code example, then (as I queried after this text yesterday) why do we need to have more than one component in each select? Like this https://go2goplay.golang.org/p/ttr7sojJ-9T ??

Again: Your understanding is correct. But the resulting situation is still equivalent to a priority select. There is no observable behavior in difference between the two.

So let me repeat my question:

Assume a read happened from lowPriority, even though highPriority was ready to read as well. That's, AIUI, the outcome you are concerned about.

In that situation, how would you know that highPriority was ready to read as well?

I believe you'll find that the answer is "you can't".

Trouble B: Since I think you have affirmed my scenarios above, that on each select's default there is a tear-down of the previous select and a set-up of the next select, which initially checks the guards to see if there is any, and in case more than two, does random select and selects the wrong (0 ns, 5 ns, 10 ns, 15 ns..). So I would say, "yes, I can". 

Again, where do I go wrong in this argument (when I think you confirmed..)?

You are all allowed to give up on me at this point.. (But I don't seem to be able to trust your truth without this reflection.)

If so, maybe a constructive point is to try to write some runnable Go code that uses this pri select pattern. I have thought about it, but I don't know how to check whether it would ever enter one of the selects and in fact need to do a random select, and select a lower when a higher is present (or became present). Plus, if I try to synchronise clients and send over sequence counts, the scheduling pattern could become so repetitive that no such situation would occur. 

Is there a way to inspect the built code and do it from code inspection? (I guess so?)

But for all this, I would need even more help...

(Maybe I'll try to trigger a student since I have so much xC ahead of me..)

Øyvind