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
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: > >> *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...@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/dc3898ea-032e-4b28-acd4-65e1b7cef21fn%40googlegroups.com.
