On Sun, May 2, 2021 at 9:23 PM Øyvind Teig <oyvind.t...@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". > > *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 > > fredag 30. april 2021 kl. 10:42:47 UTC+2 skrev axel.wa...@googlemail.com: > >> 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 >> <https://github.com/golang/go/blob/9c7207891c16951121d8b3f19f49ec72f87da9fe/src/runtime/stubs.go#L124>, >> 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 >>> <https://groups.google.com/d/msgid/golang-nuts/ec5e5c0f-c5bf-4efb-b1c4-dc056720ba5cn%40googlegroups.com?utm_medium=email&utm_source=footer> >>> . >>> >> -- > 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+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/9186c34b-1088-4ae0-8076-6c5cd0cdde38n%40googlegroups.com > <https://groups.google.com/d/msgid/golang-nuts/9186c34b-1088-4ae0-8076-6c5cd0cdde38n%40googlegroups.com?utm_medium=email&utm_source=footer> > . > > -- 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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfF50d82cCwwNdRo9JJ7%3DLn%3Dm3swAbe-z8nN8uD_hsuTvA%40mail.gmail.com.
