Interesting!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
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.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.
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/cf43611c-599f-46d9-98ac-60ede00daea9n%40googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/ac6eecc4-ee82-4a21-9001-b2c704e74e8cn%40googlegroups.com.
I will give you the pseudo code:{ // step #1 do select on bothselect highselect low}if high read:return highelse:// we read a low so do a high poll{select high:default:}if high read:enqueue low and return highelse:if queue empty:return lowelse:use queue and enqueue low from step #1 // FIFO order on low readsThe above code will always return high values over low values (if high available), and return low values in order of events
--
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.
--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/00218548-6E27-4E16-A75F-88B6E30195E5%40ix.netcom.com.
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.
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfFC1gtxbWZsy88gM4ymPncCjs6Q3YJpTcXym8bT1Ev6Kw%40mail.gmail.com.
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?
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.
- 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..)
- I trust you
- But to do more than trusting, understanding would be much better. I'm sorry: to understand I would need more than pseudo code
- 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"
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/7ae6ae45-c341-4998-9229-74b133ac213fn%40googlegroups.com.
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 view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/20c0a14c-5e4e-47a3-a198-808f207980c4n%40googlegroups.com.
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
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
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.
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 likeselect {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
--
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.
Axel, it is impolite not to try to comment and discuss each and every point above.
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/9186c34b-1088-4ae0-8076-6c5cd0cdde38n%40googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/dc3898ea-032e-4b28-acd4-65e1b7cef21fn%40googlegroups.com.
On Sun, May 2, 2021 at 9:23 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
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:
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".
meaning that there is not any state where random select is ever used.It is.
Trouble A: If random select is never used […]
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
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/cda2055a-8024-4ab1-87ca-18a177aa1cb2n%40googlegroups.com.
On May 3, 2021, at 1:23 PM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfFOUfDQJSpFQCOUAs%2BtKEATNO8K3pj0ZA%3DvRmNXDMokDg%40mail.gmail.com.
On Mon, May 3, 2021 at 6:34 PM Øyvind Teig <oyvin...@teigfam.net> wrote:meaning that there is not any state where random select is ever used.It is.Trouble A: If random select is never used […]I was unclear: When I said "It is", I meant "it is used". Your understanding of what select does is correct. There will be cases, where both channels are ready when the inner `select` is entered and thus, there will be a pseudorandom choice over which will proceed.
The argument put forward is that that's exactly how a priority select would have to behave as well. As least as I imagine it and as well as I understand the implementation of `select` (which is, admittedly, not *super* well).
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 selectsThis is precisely what my question was getting at. FWIW, it's ultimately pretty straight forward to demonstrate this behavior:
This program exits if and only if the inner select choses `lo`. Given that we know that `hi` is being closed before `lo` ("Within a single goroutine, the happens-before order is the order expressed by the program."), `lo` being ready implies `hi` being ready as well. Thus, by seeing that the program exits, we can show that the inner select sometimes chooses the `lo` case, even though the `hi` is ready as well.
Crucially, however, we needed to know that `close(hi)` happens before `close(lo)` to prove this case was taken - thus, the communications are not concurrent. That's what I meant by "external synchronization primitives".
I think my question was flawed, because really, the issue isn't about how the `select` with `default` construct we showed works - the question is how a priority `select` could work. That is, could we implement a priority `select` such that this code terminates: https://play.golang.org/p/4G8CY36L0Qy
I don't think we can - and based on that assumption I extrapolated how a priority select would actually behave - but I have to admit that I really don't understand `select` or the underlying hardware primitives enough to make a solid case either way here. Maybe you can provide an equivalent program in a language of your choice that terminates - that would certainly prove that it's at least possible (though to be clear: I don't understand your xC code, so I can't promise that I'd understand whatever you send here, personally :) ).All of that being said: I really think that in the cases where a priority select is needed, this construct is good enough to hold up.
In most “select” implementations a set of “ready” endpoints is returned. So it is trivial for the reader to prioritize some endpoints over others.
Because of the way Go select works it is more difficult - requiring nested selects - and it is more easily implemented using multiple readers and queues once it moves beyond a few producers.
I don't see where hi and lo are being sent to?
But then, "happens before" is "within a single gorotine". When it comes to several and concurrent goroutines there is no other order than those forced on them by synchronisation over nonbuffered channels (or the join you had in the code example).
I think my question was flawed, because really, the issue isn't about how the `select` with `default` construct we showed works - the question is how a priority `select` could work. That is, could we implement a priority `select` such that this code terminates: https://play.golang.org/p/4G8CY36L0Qy
But wouldn't this be 50% on each, like in https://play.golang.org/INacl7a-BU? (Taken from my note https://www.teigfam.net/oyvind/home/technology/049-nondeterminism/#go_or_go_or_golang)
I don't think we can - and based on that assumption I extrapolated how a priority select would actually behave - but I have to admit that I really don't understand `select` or the underlying hardware primitives enough to make a solid case either way here. Maybe you can provide an equivalent program in a language of your choice that terminates - that would certainly prove that it's at least possible (though to be clear: I don't understand your xC code, so I can't promise that I'd understand whatever you send here, personally :) ).All of that being said: I really think that in the cases where a priority select is needed, this construct is good enough to hold up.Hmm.. I must admit I smile here. I kind of like that we come to different conclusions. Would you you send your daughter with a fly by wire airplane that has some "good enough" sw?
There is a rather good explanation of PRI ALT (=pri select) of occam, where the TRUE & SKIP (=default) is also seen at page 72 of http://www.transputer.net/obooks/isbn-013629312-3/oc20refman.pdf.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/944ccecd-6a70-46de-a09f-7742eab9e2a1n%40googlegroups.com.
On May 3, 2021, at 2:24 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/c5566e71-befb-4912-8004-91538f940b25n%40googlegroups.com.
On Mon, May 3, 2021 at 9:16 PM Øyvind Teig <oyvin...@teigfam.net> wrote:I don't see where hi and lo are being sent to?They are being `close`d. Reading from a closed channel immediately succeeds, yielding the zero value.I chose to use `close` because it's a non-blocking way to make a channel readable. You could get the same demonstration by making the channels buffered and writing to them.But then, "happens before" is "within a single gorotine". When it comes to several and concurrent goroutines there is no other order than those forced on them by synchronisation over nonbuffered channels (or the join you had in the code example).Exactly. It is only *because* we use a single goroutine and we thus know that there is a happens-before edge.For example, this program *also* exits (i.e. line 16 is executed), but you can no longer conclude that `hi` was ready when it does.This is how most practical cases would likely happen.I think my question was flawed, because really, the issue isn't about how the `select` with `default` construct we showed works - the question is how a priority `select` could work. That is, could we implement a priority `select` such that this code terminates: https://play.golang.org/p/4G8CY36L0QyBut wouldn't this be 50% on each, like in https://play.golang.org/INacl7a-BU? (Taken from my note https://www.teigfam.net/oyvind/home/technology/049-nondeterminism/#go_or_go_or_golang)I don't understand this question. Though I also see that my question is wrong - it should be "could we implement a priority `select` such that this code *never* terminates.If we suppose a perfect priority select, which never chooses the `lo` case if the `hi` case is ready, the program I linked would never terminate. Because `lo` is never ready unless `hi` is ready too. This, AIUI, is the priority `select` you'd want. Note, in particular, the made up `pri` keyword in the example.So, no, in that scenario we wouldn't have a pseudo-random choice. The question I was begging is if we could actually implement a select like you want. If you can write this program in another language, and that program ends up not terminating, that would demonstrate that it's indeed possible to write a `select` as you are requesting.I don't think we can - and based on that assumption I extrapolated how a priority select would actually behave - but I have to admit that I really don't understand `select` or the underlying hardware primitives enough to make a solid case either way here. Maybe you can provide an equivalent program in a language of your choice that terminates - that would certainly prove that it's at least possible (though to be clear: I don't understand your xC code, so I can't promise that I'd understand whatever you send here, personally :) ).All of that being said: I really think that in the cases where a priority select is needed, this construct is good enough to hold up.Hmm.. I must admit I smile here. I kind of like that we come to different conclusions. Would you you send your daughter with a fly by wire airplane that has some "good enough" sw?This is… a strange question. I'm not saying "the software might be buggy, but it will be buggy software that is good enough". I'm saying "the construct is good enough to implement non-buggy software with it". Of course you need to know what the construct does and take it into account when writing your code - if you assume it works differently than it does, you'll introduce bugs, yes. That is true in any language.There is a rather good explanation of PRI ALT (=pri select) of occam, where the TRUE & SKIP (=default) is also seen at page 72 of http://www.transputer.net/obooks/isbn-013629312-3/oc20refman.pdf.Can you translate the example into that language? And demonstrate that it doesn't terminate?It's not practical for me to learn a different language and scour its reference manual, to try and figure out how their select works, if that is compatible with how Go's select works and thus if and how lessons learned from that language are transferable to Go.You seem to be convinced that their priority select is superior to Go's select construct and can map semantics that Go can't.
I see that, which is great. But I still don't understand why https://go2goplay.golang.org/p/S_5WFkpqMP_H (By rog, 29Apr2021 23:52:05) seems not to print "Client 2".
mandag 3. mai 2021 kl. 21:44:49 UTC+2 skrev axel.wa...@googlemail.com:On Mon, May 3, 2021 at 9:16 PM Øyvind Teig <oyvin...@teigfam.net> wrote:I don't see where hi and lo are being sent to?They are being `close`d. Reading from a closed channel immediately succeeds, yielding the zero value.I chose to use `close` because it's a non-blocking way to make a channel readable. You could get the same demonstration by making the channels buffered and writing to them.
But then, "happens before" is "within a single gorotine". When it comes to several and concurrent goroutines there is no other order than those forced on them by synchronisation over nonbuffered channels (or the join you had in the code example).Exactly. It is only *because* we use a single goroutine and we thus know that there is a happens-before edge.For example, this program *also* exits (i.e. line 16 is executed), but you can no longer conclude that `hi` was ready when it does.This is how most practical cases would likely happen.I think my question was flawed, because really, the issue isn't about how the `select` with `default` construct we showed works - the question is how a priority `select` could work. That is, could we implement a priority `select` such that this code terminates: https://play.golang.org/p/4G8CY36L0QyBut wouldn't this be 50% on each, like in https://play.golang.org/INacl7a-BU? (Taken from my note https://www.teigfam.net/oyvind/home/technology/049-nondeterminism/#go_or_go_or_golang)I don't understand this question. Though I also see that my question is wrong - it should be "could we implement a priority `select` such that this code *never* terminates.
If we suppose a perfect priority select, which never chooses the `lo` case if the `hi` case is ready, the program I linked would never terminate.
Because `lo` is never ready unless `hi` is ready too. This, AIUI, is the priority `select` you'd want. Note, in particular, the made up `pri` keyword in the example.
So, no, in that scenario we wouldn't have a pseudo-random choice. The question I was begging is if we could actually implement a select like you want. If you can write this program in another language, and that program ends up not terminating, that would demonstrate that it's indeed possible to write a `select` as you are requesting.
I don't think we can - and based on that assumption I extrapolated how a priority select would actually behave - but I have to admit that I really don't understand `select` or the underlying hardware primitives enough to make a solid case either way here. Maybe you can provide an equivalent program in a language of your choice that terminates - that would certainly prove that it's at least possible (though to be clear: I don't understand your xC code, so I can't promise that I'd understand whatever you send here, personally :) ).All of that being said: I really think that in the cases where a priority select is needed, this construct is good enough to hold up.Hmm.. I must admit I smile here. I kind of like that we come to different conclusions. Would you you send your daughter with a fly by wire airplane that has some "good enough" sw?This is… a strange question. I'm not saying "the software might be buggy, but it will be buggy software that is good enough". I'm saying "the construct is good enough to implement non-buggy software with it". Of course you need to know what the construct does and take it into account when writing your code - if you assume it works differently than it does, you'll introduce bugs, yes. That is true in any language.
There is a rather good explanation of PRI ALT (=pri select) of occam, where the TRUE & SKIP (=default) is also seen at page 72 of http://www.transputer.net/obooks/isbn-013629312-3/oc20refman.pdf.Can you translate the example into that language? And demonstrate that it doesn't terminate?
On May 5, 2021, at 11:59 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
Thanks, rog! (Blush.. I should have seen it and not nagged about it..) Sorry. Øyvind
--
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/47600a6c-6783-4cfc-beca-06be2ae48a3dn%40googlegroups.com.
You are over complicating things. Start with simple code based on Ian’s.
Still, I think you might be misunderstanding the tug between priority and starvation.
It depends on the frequency and latency of events processing.
There is no structure/language that can address this.
You either drop or you stall - and often only drop is appropriate for safety critical systems.
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
Imagine that the latency between the device detecting a disconnect
signal and a user hitting a disconnect button is D ns while the fire
detection latency is F ns. So if D > F the device would raise the
alarm even if you implement it all in hardware! The only difference
between a Go implementation vs a hardware one is the window size.
If you want to make it minimize it, Go is not the right solution.
For that, in H/W you'd probably *gate* the alarm line to the fire
department with the disconnect signal! But even so there is a small
window.
[0]: https://en.wikipedia.org/wiki/Hazard_(logic)
If that confirmation really is a confirmation, then the "Mercl code" is still not a pri select that matches the pri select I was querying about.
Øyvindtorsdag 6. mai 2021 kl. 14:29:31 UTC+2 skrev jesper.lou...@gmail.com:On Wed, May 5, 2021 at 11:34 PM Bakul Shah <ba...@iitbombay.org> wrote:
Imagine that the latency between the device detecting a disconnect
signal and a user hitting a disconnect button is D ns while the fire
detection latency is F ns. So if D > F the device would raise the
alarm even if you implement it all in hardware! The only difference
between a Go implementation vs a hardware one is the window size.
If you want to make it minimize it, Go is not the right solution.
For that, in H/W you'd probably *gate* the alarm line to the fire
department with the disconnect signal! But even so there is a small
window.
There's a more contrived example which takes this argument to the extreme. It illustrates some of the problems.Imagine you had D on Venus, and F on Mars. You receive radio signals on Earth from F and D. Due to planet orbits, this system is in constant motion, so the window constantly changes. It makes it really hard to nail down a good window, though it can be argued we can precompute the position of planets and thus compensate. However, you might have other systems where even the prediction of the window size is impossible.Most computer systems, as Ian writes, exhibit the same window fluctuations at a far smaller scale, seemingly at random. In particular, time is not absolute in computer systems. See e.g., "There is no Now" (https://queue.acm.org/detail.cfm?id=2745385) by Justin Sheehy for an example. The writing by Sheehy also injects an important point into these discussions: impossibility results. As you add more and more distribution to a system---of which one can argue that a modern multicore system is, in fact, a distributed system---you may end up with FLP or CAP in disguise. Both these results put a wooden stake through the determinism vampire.I don't think it is too far fetched to argue that prioritization, ordering and (non-)determinism are intertwined.--J.
--
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/69b83b54-1094-4321-9c27-cf4131bf6393n%40googlegroups.com.
PS: And I'm not saying there is no argument. Maybe "select is not atomic" is such an argument. But if there is an argument and/or if this is that argument, I don't fully understand it myself.
On Thu, May 6, 2021 at 3:40 PM Axel Wagner <axel.wa...@googlemail.com> wrote:FWIW after all this discussion I *am* curious about a more detailed argument for why we can't have a priority select that guarantees that if the high-priority case becomes ready before the low-priority one (in the sense of "there exists a happens-before edge according to the memory model"), the high-priority will always be chosen.That is, in the example I posted above, we do know that `hi` becoming readable happens-before `lo` becoming readable, so a true prioritized select would always choose `hi` and never return. The construct we presented does return.Now, I do 100% agree that it's not possible to have a select that guarantees that `hi` will be read if both become readable concurrently. But I don't see a fundamental issue with having a select that always chooses `hi` if `hi` becoming readable happens-before `lo` becoming readable.And to be clear, I also kinda like that we don't have that - I think the value provided by the pseudo-random choice in preventing starvation is worth not having an "ideal" priority select construct in the language. But I couldn't really make a good case why we can't have it.
--
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/CAEkBMfEJNtu1i1RyZxW5FNYkD0TB73nq0WyVCCW_E9_JOAVJmw%40mail.gmail.com.
On Thu, 6 May 2021 at 14:41, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:PS: And I'm not saying there is no argument. Maybe "select is not atomic" is such an argument. But if there is an argument and/or if this is that argument, I don't fully understand it myself.One reason is that the semantics can conflict. Consider this code, for example (assuming a hypothetical "pri select" statement that chooses the first ready arm of the select) - the priorities conflict. I suspect Occam doesn't encounter that issue because it only allows (or at least, it did back when I used Occam) select on input, not output. I believe that restriction was due to the difficulty of implementing bidirectional select between actual distributed hardware processors, but I'm sure Øyvind knows better.func main() {
c1, c2, c3 := make(chan int), make(chan int), make(chan int)
go func() {
pri select {
case c1 <- 1:
case v := <-c2:
c3 <- v
}
}()
go func() {
pri select {
case c2 <- 2:
case v := <-c1:
c3 <- v
}
}()
fmt.Println(<-c3)
}
That said, I suspect that the semantics could be ironed out, and the real reason for Go's lack is that it's not actually that useful; that it would be one more feature; and that in practice a random choice makes sense almost all the time.
On May 6, 2021, at 10:28 AM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfHEEDdL8adBDFoqwVHswK3kr_KawePGi%3DNtbaBVTP5KWw%40mail.gmail.com.
On May 6, 2021, at 12:37 PM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfHv2cKR1OLS97YN7JYKZXHu_s0a-6c0-2tW%3DS0gUU8jUA%40mail.gmail.com.
“If lo” means that if the lo channel was read.
This code will prevent a lo from being processed if a hi is available at the happens before moment of a value being ready.
Btw using indents rather than brackets in the above - maybe that is causing the confusion.
On May 6, 2021, at 1:30 PM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfHQq2p60OenLMYUFz%3DK9HigpbAqj7m%3D%2BRp7BnCX%2Bp1QLA%40mail.gmail.com.
But that is not really true because there are no constraints on if the source channels are buffered - if they are then my code operates similarly.
Even if using unbuffered channels there is buffering being done at a lower level (hardware buffers, network stack buffers, etc) - so not “unblocking a sender” is a dubious endeavor.
On May 6, 2021, at 3:15 PM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfHL_G5bGs6tGXO6U8H%3DYMNf6f3%2B4V1JDxALEfOpGhQjvA%40mail.gmail.com.
Yes, but barring the nanosecs of a window this is simply implemented as Ian wrote withSelect hiDefault:Select hi,lo
If both channels are ready when the code is entered the high will always be taken.
There is no such thing as simultaneous source events
On Thu, May 6, 2021 at 11:38 PM Robert Engels <ren...@ix.netcom.com> wrote:Yes, but barring the nanosecs of a window this is simply implemented as Ian wrote withSelect hiDefault:Select hi,loNo, it is not. "Barring a nanosecond" is not a guarantee. And that this is not actually doing what I'm asking is the entire start of my inquiry.Again: "It can't be implemented" is a valid answer to the question, though I'm specifically asking for details why. Posting code which doesn't do it, is not an answer.If both channels are ready when the code is entered the high will always be taken.But not if they are not both ready when the code is entered. Again, I was very specific about the guarantee I'm asking about: "If `hi` becomes ready before `lo` (in the sense of the memory model happens-before relationship), then the `hi` case should always be taken".
Happens before is only valid under the context of synchronization.
There is no such thing as simultaneous source eventsI am specifically talking about *non* simultaneous events. I am specifically talking about causally ordered events with a well-defined order, according to the memory model. And I
specifically acknowledged (and originally pointed out) the impossibility to even assign meaning to the question in the context of concurrent events.I am specifically *not* asking about any guarantees in the case where the two events are concurrent. *Neither* about the low-priority communication becoming ready before the high priority one. I am exclusively talking about the situation where it can be proven that the high-priority event happens before the low priority one - as is the case in the example I posted.
Again: If you don't have an answer, it is fine to not respond. If you don't know if it's possible to implement a `select` statement with these semantics - or why it isn't - you don't have an answer. The point of my question is pure curiosity. I'm not suggesting that we add a construct like this or arguing it is needed or saying that I want it. I'm only curious if it could be done. So there is absolutely nothing lost by not getting an answer and there is absolutely nothing gained by trying to convince me a non-answer actually is one.Sorry to be so blunt, but this interaction is very frustrating.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfFwhUCbRMO1pAwJWkky2WtJh2hieV4D6_66aUpyhtMc4A%40mail.gmail.com.
On May 6, 2021, at 6:11 PM, Robert Engels <ren...@ix.netcom.com> wrote:
On Thu, May 6, 2021 at 4:06 PM Øyvind Teig <oyvin...@teigfam.net> wrote:If that confirmation really is a confirmation, then the "Mercl code" is still not a pri select that matches the pri select I was querying about.I don't believe it is. It took a while to wrap my head around it - apologies for that.
But yes, at this point I believe the specific property that is violated that you'd be interested in is as I said in my last message, the guarantee that "if the high-priority case becomes ready before (in the sense of the memory model) the low-priority case, then the high-priority case will be chosen".That's certainly a reasonable expectation to have from a priority select and it is not a guarantee that the code we gave you, using nested selects with defaults, provides.I believe we became hung up on the idea of what happens if the cases become ready *concurrently*. In that case, there is no real sensible answer to what any select implementation could guarantee.
On Thu, 6 May 2021 at 14:41, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:PS: And I'm not saying there is no argument. Maybe "select is not atomic" is such an argument. But if there is an argument and/or if this is that argument, I don't fully understand it myself.One reason is that the semantics can conflict. Consider this code, for example (assuming a hypothetical "pri select" statement that chooses the first ready arm of the select) - the priorities conflict. I suspect Occam doesn't encounter that issue because it only allows (or at least, it did back when I used Occam) select on input, not output. I believe that restriction was due to the difficulty of implementing bidirectional select between actual distributed hardware processors, but I'm sure Øyvind knows better.
func main() {
c1, c2, c3 := make(chan int), make(chan int), make(chan int)
go func() {
pri select {
case c1 <- 1:
case v := <-c2:
c3 <- v
}
}()
go func() {
pri select {
case c2 <- 2:
case v := <-c1:
c3 <- v
}
}()
fmt.Println(<-c3)
}That said, I suspect that the semantics could be ironed out, and the real reason for Go's lack is that it's not actually that useful; that it would be one more feature; and that in practice a random choice makes sense almost all the time.
On Thu, 6 May 2021 at 14:41, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:PS: And I'm not saying there is no argument. Maybe "select is not atomic" is such an argument. But if there is an argument and/or if this is that argument, I don't fully understand it myself.One reason is that the semantics can conflict. Consider this code, for example (assuming a hypothetical "pri select" statement that chooses the first ready arm of the select) - the priorities conflict. I suspect Occam doesn't encounter that issue because it only allows (or at least, it did back when I used Occam) select on input, not output. I believe that restriction was due to the difficulty of implementing bidirectional select between actual distributed hardware processors, but I'm sure Øyvind knows better.func main() {
c1, c2, c3 := make(chan int), make(chan int), make(chan int)
go func() {
pri select {
case c1 <- 1:
case v := <-c2:
c3 <- v
}
}()
go func() {
pri select {
case c2 <- 2:
case v := <-c1:
c3 <- v
}
}()
fmt.Println(<-c3)
}
On Thu, May 6, 2021 at 8:22 PM Robert Engels <ren...@ix.netcom.com> wrote:“If lo” means that if the lo channel was read.Exactly. To fulfill the requirements and answering the question, it must not be read.This code will prevent a lo from being processed if a hi is available at the happens before moment of a value being ready.What the receiver does with the value is immaterial. Point is, that the receiver has already read the value, thus the communication has happened, thus the sender was unblocked. The question is about a select that wouldn't do that.Btw using indents rather than brackets in the above - maybe that is causing the confusion.I'm not confused. Your code is simply not answering the question posed. Which is about a select which always lets the high priority communication happen, if it is ready before the low priority communication - and consequently *doesn't* let the low priority communication happen.
But that is not really true because there are no constraints on if the source channels are buffered - if they are then my code operates similarly.Even if using unbuffered channels there is buffering being done at a lower level (hardware buffers, network stack buffers, etc) - so not “unblocking a sender” is a dubious endeavor.
Back in the days of transputers and occam, there was a desire to be able to manage all interesting events in a system in a within-language (language being occam) manner.Interrupts were a problem, because you can't describe interrupts as implemented by microprocessors (steal the PC and jump somewhere, saving minimal state) in a language which doesn't discuss stealing the PC nor what minimal state might be.So there were two scenarios handled.In one scenario, you created a high-priority process (occam had priorities) and had it wait on a hardware channel. If a signal arrived from hardware which would normally interrupt (in a classic microprocessor), it delivered a message to the hardware channel, and the waiting process work up pre-empting the execution of any currently-executing lower-priority process. This is a close approximation to the behaviour of classic device interrupts with the limitation of a single level of interrupt priority, the latter being imposed by the implementation of the transputers, not the language. This works fine if the high priority process is completely 'individualistic', and doesn't need to tell other processes anything (because then you fall direct into the second scenario, albeit in another process).In the other scenario, you had what we might look upon as sorta an object which got asked to do different sorts of things. All the requests arrived by messages on separate (unbuffered at the time) channels. The PRI ALT simply said that for one reason or another, if requests arrived on several channels while the process was busy doing other stuff, then it must choose to service the highest priority channel. It was still up to the software designer to be sure that the time the process was busy was not so long that the priority was useless.So to model classic prioritised interrupts, you would consider than handling an interrupt - classically, someone mashes the Big Red Button on a software controlled black box implemented by a number of communicating processes, requiring it to stop as close to Right Now as possible - as a message to a high-priority process, which would perform any immediate, time-critical operation (turning off the electricity to the black box?) and then send a message to a lower priority process in charge of the general state of the black box to tidy up internal state. Then you really want there to be a PRI ALT, because the black box isn't running any more and handling useless messages from prior 'clients' is just silly - you want the 'big red button mashed' message to be taken in preference to anything else.And the dual notions of process priority and select priority work together well to make it clear what the designer's intents were. Such transparency is valuable.It can be argued that go isn't and wasn't ever intended to deal with such scenarios, and so the provision of priorities in goroutines and selects is not an interesting capability.
To clarify again: As a litmus test, a `select` construct like the one I'm talking about would mean that this code blocks forever:With the current `select`, it doesn't. With a different `select`, which uses source order to express priority and under the semantics I'm asking about, this would always block, because `lo` would never be read.
On Thu, May 6, 2021 at 6:40 AM 'Axel Wagner' via golang-nuts
<golan...@googlegroups.com> wrote:
>
> FWIW after all this discussion I *am* curious about a more detailed argument for why we can't have a priority select that guarantees that if the high-priority case becomes ready before the low-priority one (in the sense of "there exists a happens-before edge according to the memory model"), the high-priority will always be chosen.
>
> That is, in the example I posted above, we do know that `hi` becoming readable happens-before `lo` becoming readable, so a true prioritized select would always choose `hi` and never return. The construct we presented does return.
>
> Now, I do 100% agree that it's not possible to have a select that guarantees that `hi` will be read if both become readable concurrently. But I don't see a fundamental issue with having a select that always chooses `hi` if `hi` becoming readable happens-before `lo` becoming readable.
>
> And to be clear, I also kinda like that we don't have that - I think the value provided by the pseudo-random choice in preventing starvation is worth not having an "ideal" priority select construct in the language. But I couldn't really make a good case why we can't have it.
I believe that we could implement a select statement that supports
priority cases, such that when multiple cases are ready, and at least
one is a priority case, then we would always choose one of the
priority cases.
The reason we don't have such a feature is not because of
implementation difficulty. It's because the feature isn't needed,
and
because, as this thread indicates, it tends to confuse people.
In
particular it's easy for people to be misled into thinking that if a
low priority case is chosen then at that point none of the high
priority cases can be ready, but of course that is false (as the high
priority case may have become ready in the span of time between
choosing the low priority case and starting to execute the associated
statements).
Ian
I don't know if one would use a pri select to pick up channels from the same task. Here's a mod that seems to behave wildly differently when the channels are signalled from one task each and those two tasks are swapped in order. How may that be explained? I would have suggested the same log trail for both: https://play.golang.org/p/lJA0XPWtj-w
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/b5dcb025-7cea-4f11-a7fc-8217b06ade59n%40googlegroups.com.
On Fri, May 7, 2021 at 8:49 PM Øyvind Teig <oyvin...@teigfam.net> wrote:I don't know if one would use a pri select to pick up channels from the same task. Here's a mod that seems to behave wildly differently when the channels are signalled from one task each and those two tasks are swapped in order. How may that be explained? I would have suggested the same log trail for both: https://play.golang.org/p/lJA0XPWtj-wIt does seem to make a difference, but that's mainly due to coincidences of the implementation. I assume it has something to do with how the newly created goroutines are scheduled - you do start one after the other and maybe, for some implementation specific detail, it tends to schedule the last one first.Either way, you can't rely on that behavior. From a pure spec and memory model POV, both programs provide you the same behavioral guarantees.
fredag 7. mai 2021 kl. 04:10:42 UTC+2 skrev Ian Lance Taylor:
The reason we don't have such a feature is not because of
implementation difficulty. It's because the feature isn't needed,..I hope you mean "isn't needed in Go"?
and
because, as this thread indicates, it tends to confuse people.I think the main reason for the confusion was that many tried to understand the select-pri-default-select-hi-lo code example? Or is this some "idiomatic Go confusion"?
On Fri, May 7, 2021, 3:10 PM Øyvind Teig <oyvin...@teigfam.net> wrote:fredag 7. mai 2021 kl. 04:10:42 UTC+2 skrev Ian Lance Taylor:
The reason we don't have such a feature is not because of
implementation difficulty. It's because the feature isn't needed,..I hope you mean "isn't needed in Go"?I am only talking about Go.
and
because, as this thread indicates, it tends to confuse people.I think the main reason for the confusion was that many tried to understand the select-pri-default-select-hi-lo code example? Or is this some "idiomatic Go confusion"?I think this thread has had many different confusions.
Ian
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
I once implemented something to solve the same problem in Java. So I have a high priority queue (hq) and a low priority queue (lq). Whenever an item is atted to the hq a token is also added to some associated high priority token queue (htq). Same for the lq and ltq.Some thread or goroutine takes tokens from the htq as long as in contains tokens. You can add a count so that after any n tokens taken from the htq the ltq is checked whether it contains a token.Works fine until both, htp and ltp, are empty. You don't want to iterate over htp and ltp all the time till one contains a token again. So I introduced a semaphore on which the thread serving all these queues would be blocked till htq ot ltq recevie a new token.I thought that the sempahore would slow things down. So I did measurements with a bare bone concurrent queue and the priority queue. The difference in time to serve n tokens in htq and m tokens in ltq was very small also for high values of n and m.
In addition to htq and ltq you have a third queue into which you also insert a token once one has been added to htq or ltp. The thread/goroutine that serves htq, ltp, hq, lq is blocked by this additional queue. When it is empty, htq and ltq are also empty. So when the goroutine is blocked it is fine in this case. This sound like this could be it :-)
By invoking one of the following methods, a process may passively wait for one or more of the guards associated with an Alternative object to become ready. The methods differ in the way they choose which guard to select in the case when two or more guards are ready:
--
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/ceeff584-7108-455d-b825-1f3845971134n%40googlegroups.com.
On May 15, 2021, at 3:48 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
Thanks, rog. I appreciate this! Even if I cant' stop thinking that a "pri" would have been sligtly more elegant. But you shall be praised for the try! I wont' take the time to fine read the code, though...
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/091bd9e7-a33e-4833-a33c-6ed3f5976861n%40googlegroups.com.