mandag 3. mai 2021 kl. 21:11:48 UTC+2 skrev ren...@ix.netcom.com: > In most “select” implementations a set of “ready” endpoints is returned. > So it is trivial for the reader to prioritize some endpoints over others. >
Do you mean in user code in other languages than Go? If so, which ones were you thinking of? 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 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". Øyvind > > On May 3, 2021, at 1:23 PM, 'Axel Wagner' via golang-nuts < > golan...@googlegroups.com> wrote: > > > > 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 selects >> > > This is precisely what my question was getting at. FWIW, it's ultimately > pretty straight forward to demonstrate this behavior: > https://play.golang.org/p/UUA7nRFdyJE > 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. > <https://golang.org/ref/mem#tmp_2>"), `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. > > 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 >> >> >>> *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...@googlegroups.com. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/golang-nuts/cda2055a-8024-4ab1-87ca-18a177aa1cb2n%40googlegroups.com >> >> <https://groups.google.com/d/msgid/golang-nuts/cda2055a-8024-4ab1-87ca-18a177aa1cb2n%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/CAEkBMfFOUfDQJSpFQCOUAs%2BtKEATNO8K3pj0ZA%3DvRmNXDMokDg%40mail.gmail.com > > <https://groups.google.com/d/msgid/golang-nuts/CAEkBMfFOUfDQJSpFQCOUAs%2BtKEATNO8K3pj0ZA%3DvRmNXDMokDg%40mail.gmail.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/c5566e71-befb-4912-8004-91538f940b25n%40googlegroups.com.
