Priority select in Go

[Øyvind Teig]

Dear group

I have tried to write a blog note called "Priority select in Go" [1].

 

I only discuss some aspects of the problem, and then mostly syntax. 

It is probably too long to paste in here, and then I don't fancy duplicates.

Feel free to comment there (moderated) or here.

[1] - http://www.teigfam.net/oyvind/home/047-priority-select-in-go/

/aclassifier

[Rob Pike]

A similar sort of thing can already be achieved with a channel-valued
closure that returns nil if some condition is not satisfied.

-rob

[Jan Mercl]

On Oct 7, 2012 10:56 PM, "Øyvind Teig" <oyvind.teig@teigfam.net> wrote:
>

"There is no way that I am aware of to write a prioritised select."

select  {
case <-higher:
        foo()
default:
        select {
        case <-lower:
                bar()
        default:
                ...
        }
}

-j

[Dan Kortschak]

For convenience:

http://groups.google.com/group/golang-nuts/browse_thread/thread/0a13f1aff87c9143

[Øyvind Teig]

Rob, 

closures always come as a surprise to me. 

So, what's the priority select code example for Go? 

Is that solution also relying on pseudo-random choice in "phase one", as I understand the other suggestion here is?

-Øyvind

[Rob Pike]

The link posted by Dan Kortschak has an example of this technique.

-rob

[Øyvind Teig]

Nice. But the scheduler has to do two (rather unnecessary) pseudo-random choices for this. I was thinking this could be avoided, so I didn't even search for a solution along that line. Which I of course should have had.

kl. 23:08:35 UTC+2 søndag 7. oktober 2012 skrev Jan Mercl følgende:

[Øyvind Teig]

I did do a search for this kind of discussion, but thanks for it! It discusses the matter, which I pointed out I really didn't much do.

There is a comment in the thread that the languages which do have this essentially are single threaded. This is correctly denied in that post.

But my blog raises another question: pseudo-random and priority based choice. I would do priority select provided at least one of the cases has a boolean expression (side effect free, evaluated one, at the top of the select - as also described in your url). My sugegstion may not be orthogonal to the problem domain, and thus perhaps not a good language solution, but discussing it may be worth while. 

I do notice that the Go design team has done very little pseudo-random choices themselves! Those choices seem to be priority based.

-Øyvind

[Jan Mercl]

On Mon, Oct 8, 2012 at 8:45 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> Nice. But the scheduler has to do two (rather unnecessary) pseudo-random
> choices for this. I was thinking this could be avoided, so I didn't even
> search for a solution along that line. Which I of course should have had.

"If multiple cases can proceed, a uniform pseudo-random choice is made
to decide which single communication will execute."
(http://golang.org/ref/spec#Select_statements)

In the specific example discussed, at most *one* case can proceed in
any of the selects, so the above is not applicable, according to the
specs.

-j

[Lucio]

If you take this example to any extreme, it totally matches the behaviour
of an ordered select{} (same criteria as switch{}), it just adds a lot of indentation.
One wonders...

Lucio.

On Sunday, 7 October 2012 23:08:35 UTC+2, Jan Mercl wrote:

[Øyvind Teig]

At most one, of course. But the example gives at most one two times. If not select higher then default, then new select. Isn't that two selects? I can't seen how the compiler would merge those into one select?

-Øyvind

[Øyvind Teig]

But of course you didn't mean to say that select and switch in any way are equal?

-Øyvind

[Øyvind Teig]

Ok. I assume this is Russ Cox's "maybe" function?

So there would at max be one individual "maybe" defined per choice.

And the evaluations in the maybes would not be side effect free.

Nice, but hmm..

- Øyvind

[Jan Mercl]

On Mon, Oct 8, 2012 at 10:44 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> At most one, of course. But the example gives at most one two times. If not
> select higher then default, then new select. Isn't that two selects? I can't
> seen how the compiler would merge those into one select?

Equivalent pseudo code:

if isReady(higher) then // isReady or canCommunicate or ... the name
doesn't matter
foo()
elif isReady(lower) then
bar()
fi

I can't see any further possible reduction if it has still to
implement the required priority. No randomness, fully deterministic.

-j

[Øyvind Teig]

Jan

I may be misunderstanding completely you are not pseudocoding Go.

There is no "else if" clause in select, only comm clause and default.

But you are pseudocoding what we want to achieve.

-Øyvind

[Lucio]

Definitely not, although the roots must lie in the same construct.  No, what I'm saying is that the difference is one of convenience, not a natural one, but that we're more or less stuck with it because I certainly can't propose a better idea that covers both possibilities.  It would occasionally be nice to have options here, but the language is better without them.  Even a switch{} with random selection between conflicting cases may have its uses (I seem to recall finding something like that in the literature), but having the compiler point out these conflicts is well worth the loss.

Lucio.

[Jan Mercl]

On Mon, Oct 8, 2012 at 12:33 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> I may be misunderstanding completely you are not pseudocoding Go.
> There is no "else if" clause in select, only comm clause and default.

Where the select statement default clause is the pseudocode if
statement otherwise[1]/else part:

1 select {
2 case <-higher: // 100
3 foo() // 101
4 default: // 102
5 select {
6 case <-lower: // 103
7 bar() // 104
8 default:
9 ...
10 } // 105
11 } // 106


100 if isReady(higher) then
101 foo()
102 else
103 if isReady(lower) then
104 bar()
105 fi
106 fi

> But you are pseudocoding what we want to achieve.

Hope so ;-)

-j

[1]: ".... If any of the resulting operations can proceed, one of
those is chosen and the corresponding communication and statements are
evaluated. Otherwise, if there is a default case, that executes; ... "
(http://golang.org/ref/spec#Select_statements)

[Øyvind Teig]

kl. 13:03:27 UTC+2 mandag 8. oktober 2012 skrev Lucio følgende:

Definitely not, although the roots must lie in the same construct. 

 

No, what I'm saying is that the difference is one of convenience, not a natural one,

But "select case" helps us with whom to communicate with and "switch case" with what to do. Personally I would consider that a "natural" difference? The first case and the other case only have letters in common.

-Øyvind

[minux]

On Mon, Oct 8, 2012 at 7:04 PM, Jan Mercl <0xj...@gmail.com> wrote:

On Mon, Oct 8, 2012 at 12:33 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> I may be misunderstanding completely you are not pseudocoding Go.
> There is no "else if" clause in select, only comm clause and default.

Where the select statement default clause is the pseudocode if
statement otherwise[1]/else part:

 1 select  {
 2 case <-higher: // 100
 3        foo() // 101
 4 default: // 102

I think there is a race here.

what if higher become ready just after runtime chooses the default branch?

[Jan Mercl]

On Mon, Oct 8, 2012 at 1:13 PM, minux <minu...@gmail.com> wrote:
>> Where the select statement default clause is the pseudocode if
>> statement otherwise[1]/else part:
>>
>> 1 select {
>> 2 case <-higher: // 100
>> 3 foo() // 101
>> 4 default: // 102
>
> I think there is a race here.
> what if higher become ready just after runtime chooses the default branch?

I would agree if the default clause would be specified otherwise than
it is. In summary:

a) evaluate all cases
b) if there is any which can proceed
c) if more than one -> perform one of them randomly
d) else perform that one
e) else
f) continue execution at the default clause (if present)


The specs don't say, that the execution of the default clause may
start iff no of the cases is ready, but it is specified as per above
schema. Full: http://localhost:6060/ref/spec#Select_statements

Conclusion: IMO there's no race as the assumption "default executed
implies no case is ready *now*" is false. The correct implication is
IMO: if the default clause is executed then no case *was* ready when
evaluated.

Note: The IMO incorrect interpretation would lead to a always present
race in a select with multiple cases. Per specs all of them are
evaluated *once* in source order. It may happen that after evaluation
A as not ready, while evaluating B, A becomes ready. But per specs A
cannot be re-tested (as that would require re-evaluation of the case
w/ all the unwelcome outcomes).

select {
case <-A:
case <-B:
}

I admit being possibly totaly wrong (didn't check runtime.c or where
the relevant code is). My/worth 1/2c ;-)

-j

[Øyvind Teig]

(I put in a too fast reply that I deleted (twice??)

If it does not take higher it has not committed to communicate. So it goes on and finds lower. Ok.

Any select will work like this: when any one is taken then atomically the other ready are still blocking.

When one was not ready when select was intered but then becomes ready during the evaluation, that's ok.

Ready does not mean committed.

But there is the problem here that both cases have default clauses. 

I only saw that now. It won't work if none are ready when select is entered.

We don't want busy-polling. The example falls?

-Øyvind

[roger peppe]

Here's the kind of thing I was alluding to in my initial comment
(which was typed on a phone, hence its brevity).

http://play.golang.org/p/1ZVdYlA52x

It's interesting to see what happens when this program
is run with different values of GOMAXPROCS:

% for(i in 0 1 2 3 4 5 6){GOMAXPROCS=$i go run tst.go}
[4000 2000 2000 2000]
[4000 2000 2000 2000]
[6196 2649 1044 111]
[6516 2427 919 138]
[5866 2856 1116 162]
[7178 1875 687 260]
[6995 2241 753 11]
%

The priority effect is clear except when GOMAXPROCS <= 1;
in that case the other generators contribute equally, because
the high priority generators don't have a chance to generate
another value before all the others have had a go.

With four levels of priority, the code is tedious, but I
haven't yet found a situation where I want more than two,
and certainly not enough to warrant a new language feature.

Out of interest, when have you needed to use a prioritised select with
more than two levels of priority in a real application?

> --
>
>

[Jan Mercl]

On Mon, Oct 8, 2012 at 1:40 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> But there is the problem here that both cases have default clauses.
> I only saw that now. It won't work if none are ready when select is entered.
> We don't want busy-polling. The example falls?

Falls what?

Well, actually I see what you mean, but the construct was a counter
example to: "There is no way that I am aware of to write a prioritised
select.". Nothing more.

Otherwise it fails to block while both higher and lower are not ready
and it would really lead to busy waiting, unless... What about adding
a OR channel (== any of the cases is ready). Umm, it's ugly, but I
have no better idea within current Go specs:

// No need to run this code, it does nothinf useful, it's a schema only.
// Also not tested to be sane at all.
package main

func produce(c, or chan int) {
for i := 0; ; i++ {
c <- i
or <- 1
}
}

func main() {
higher, lower, higherOrLower := make(chan int, 10), make(chan
int, 10), make(chan int, 10)

go produce(higher, higherOrLower)
go produce(lower, higherOrLower)

for {
<-higherOrLower
select {
case <-higher:
default:
select {
case <-lower:
}
}
}
}

-j

[Øyvind Teig]

If you have priority select and you are a server to N clients, then being able to have control of the "fairness algorithm" and at the same time have N-pri-select then it would be a good tool.

For occam, which did not have pseudo-random choice (but pretended to), talking with a set of N clients was typically done with two arrays of channels of N channels in each. These were statically made (no new). So, when one of the cases were taken (say index i), then that same index of the return channel set was used to communicate further, if a session was needed (no need to send the return channel across). Then, in the select (there could be only one, at least coneptually), during the session the other boolean values were false and only bool[i] would be true.

Then, after the session with i, typicallly the next index ((i+1)modulo N) would be set up first in the select (ALT). That proved to be a very good fair algorithm. And from then on, if this was not good enough, well - make your own. Or use Go's pseudo-random as a very easy and nice choice. But not because that's the only way.

So there definitively is a nice feature to be able to have N-pri-select.

- Øyvind

[Jan Mercl]

On Mon, Oct 8, 2012 at 2:05 PM, roger peppe <rogp...@gmail.com> wrote:
> Here's the kind of thing I was alluding to in my initial comment
> (which was typed on a phone, hence its brevity).
>
> http://play.golang.org/p/1ZVdYlA52x
>
> It's interesting to see what happens when this program
> is run with different values of GOMAXPROCS:
>
> % for(i in 0 1 2 3 4 5 6){GOMAXPROCS=$i go run tst.go}
> [4000 2000 2000 2000]
> [4000 2000 2000 2000]
> [6196 2649 1044 111]
> [6516 2427 919 138]
> [5866 2856 1116 162]
> [7178 1875 687 260]
> [6995 2241 753 11]
> %
>
> The priority effect is clear except when GOMAXPROCS <= 1;
> in that case the other generators contribute equally, because
> the high priority generators don't have a chance to generate
> another value before all the others have had a go.

Interesting! This variant: http://play.golang.org/p/y-DN-BMclS gives
(a 2x Intel X5450 machine):

(14:23) jnml@fsc-r550:~/src/tmp$ for i in 1 2 3 4 5 6 7 8 9 10; do
(echo -n "$i:"; GOMAXPROCS=$i go run main.go) ; done
1:[9901 99 0 0]
2:[8028 1972 0 0]
3:[4809 2298 1997 896]
4:[2614 2943 4160 283]
5:[1272 7589 1031 108]
6:[6243 1964 1655 138]
7:[3450 3356 3121 73]
8:[2697 5709 1515 79]
9:[1901 1782 6237 80]
10:[3625 3088 3149 138]
(14:23) jnml@fsc-r550:~/src/tmp$

-j

[Øyvind Teig]

I probably should have specified that 

• there should be no busy polling (but to me this is so default)
  
• so examples where the select hasn't been blocking "for a year" is prohibited
  
• and no main fork that does nothing but test an always busy select
  

If may be completely off track, but I would say that none of the examples given convince me that Go in fact has "real" priority select.

Could I really be so wrong?

- Øyvind

kl. 14:09:32 UTC+2 mandag 8. oktober 2012 skrev Jan Mercl følgende:

On Mon, Oct 8, 2012 at 1:40 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> But there is the problem here that both cases have default clauses.
> I only saw that now. It won't work if none are ready when select is entered.
> We don't want busy-polling. The example falls?

Falls what?  

Well, actually I see what you mean, but the construct was a counter

[Jan Mercl]

On Mon, Oct 8, 2012 at 2:33 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:
>
> I probably should have specified that
>
> there should be no busy polling (but to me this is so default)
> so examples where the select hasn't been blocking "for a year" is prohibited
> and no main fork that does nothing but test an always busy select
>
> If may be completely off track, but I would say that none of the examples
> given convince me that Go in fact has "real" priority select.
>
> Could I really be so wrong?

The examples with the "or" channel as so as the Roger's one
- do not busy wait/poll
- block only as long as nothing is ready (but I'm not sure what your
2nd bullet means)
- do not need to fork main to work

Except for the undefined "real" backdoor, the example solutions show
that "real" priority select in Go is possible.

-j

[roger peppe]

On 8 October 2012 13:24, Øyvind Teig <oyvin...@teigfam.net> wrote:
> If you have priority select and you are a server to N clients, then being
> able to have control of the "fairness algorithm" and at the same time have
> N-pri-select then it would be a good tool.
>
> For occam, which did not have pseudo-random choice (but pretended to),
> talking with a set of N clients was typically done with two arrays of
> channels of N channels in each. These were statically made (no new). So,
> when one of the cases were taken (say index i), then that same index of the
> return channel set was used to communicate further, if a session was needed
> (no need to send the return channel across). Then, in the select (there
> could be only one, at least coneptually), during the session the other
> boolean values were false and only bool[i] would be true.
>
> Then, after the session with i, typicallly the next index ((i+1)modulo N)
> would be set up first in the select (ALT). That proved to be a very good
> fair algorithm. And from then on, if this was not good enough, well - make
> your own. Or use Go's pseudo-random as a very easy and nice choice. But not
> because that's the only way.
>
> So there definitively is a nice feature to be able to have N-pri-select.

I'm not sure I see that. I see the Occam-specific idioms (largely to
get around Occam's lack of dynamic allocation AFAICS), but I don't
see anything that you're doing there that Go's pseudo-random
choice won't be sufficient for.

Doing a priority select when the number of channels is only
known at run time is a little harder, but still doable if efficiency isn't
paramount: http://play.golang.org/p/lYKah_7CVw

% for(i in 0 1 2 3 4 5 6 8 9 10){GOMAXPROCS=$i go run tst.go}
[2500 2500 2500 2500]
[2500 2500 2500 2500]
[2622 3735 1896 1747]
[3490 2434 2710 1366]
[3857 3100 2335 708]
[3924 3168 2486 422]
[3890 3301 2131 678]
[3894 3308 2039 759]
[3471 3172 2547 810]
[4052 3374 2140 434]

[Øyvind Teig]

Roger's example above does (as I understand it) some kind of set algebra with an increasing number of channels, assuming that if one is taken, then if that one is shared with one and then another yet, then one and two others, then it accounts to pri select. And what happens depends in internal magic like GOMAXPROCS and which machine it runs on. Isn't this closer to pseudo-random? Hmm..

I meant that both producers and consumer should have blocked "a year" so that we would not analyse speed or how fast events may be produced or consumed. It's ok to have a main fork, I just saw that the examples were running like the d.. I will try to rephrase later on.

- Øyvind

[Øyvind Teig]

kl. 15:12:55 UTC+2 mandag 8. oktober 2012 skrev rog følgende:

On 8 October 2012 13:24, Øyvind Teig <oyvin...@teigfam.net> wrote:
> If you have priority select and you are a server to N clients, then being
> able to have control of the "fairness algorithm" and at the same time have
> N-pri-select then it would be a good tool.
>
> For occam, which did not have pseudo-random choice (but pretended to),
> talking with a set of N clients was typically done with two arrays of
> channels of N channels in each. These were statically made (no new). So,
> when one of the cases were taken (say index i), then that same index of the
> return channel set was used to communicate further, if a session was needed
> (no need to send the return channel across). Then, in the select (there
> could be only one, at least coneptually), during the session the other
> boolean values were false and only bool[i] would be true.
>
> Then, after the session with i, typicallly the next index ((i+1)modulo N)
> would be set up first in the select (ALT). That proved to be a very good
> fair algorithm. And from then on, if this was not good enough, well - make
> your own. Or use Go's pseudo-random as a very easy and nice choice. But not
> because that's the only way.
>
> So there definitively is a nice feature to be able to have N-pri-select.

I'm not sure I see that. I see the Occam-specific idioms (largely to
get around Occam's lack of dynamic allocation AFAICS),

but I don't
see anything that you're doing there that Go's pseudo-random
choice won't be sufficient for.

That's not the point. Discussing when pri select and pseudo-random select should be used or not used (and I could agree, as een from my comment above) vs. how you do it when you have chosen to do it one way, are two different matters.

-Øyvind

[Jan Mercl]

On Mon, Oct 8, 2012 at 3:15 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> I meant that both producers and consumer should have blocked "a year" so
> that we would not analyse speed or how fast events may be produced or
> consumed.

I think that's not the case in the discussed examples. Worsened
throughput might be an issue, though.

> It's ok to have a main fork, I just saw that the examples were
> running like the d.. I will try to rephrase later on.

Please do, there were no daemons/forking involved AFAICS ;-)

-j

[roger peppe]

On 8 October 2012 14:15, Øyvind Teig <oyvin...@teigfam.net> wrote:
> Roger's example above does (as I understand it) some kind of set algebra
> with an increasing number of channels, assuming that if one is taken, then
> if that one is shared with one and then another yet, then one and two
> others, then it accounts to pri select. And what happens depends in internal
> magic like GOMAXPROCS and which machine it runs on. Isn't this closer to
> pseudo-random? Hmm..

A real prioritised select would vary depending on those things too.
The results depend on GOMAXPROCS because GOMAXPROCS
determines how the *producing* goroutines run.

Of course, my example isn't *exactly* equivalent to priority select.
If two goroutines send after an initial (default) select has happened,
and before the final select has started, then there is no
priority between those two. I maintain that if the events are that close
together, then any scheduling variation of a few nanoseconds
may have delivered the events in a different order, and it is
highly unlikely that processing them in pseudo-random order
will affect the correctness of anything.

If the consumer is a little slower, then the priority is clearer.
For example in this example, the consumer talks to some other
goroutines before using the pri select: http://play.golang.org/p/IkRIW9hwTj

[Øyvind Teig]

I have tried to rephrase in a chapter in my own blog, as it may have to be changed as this or other threads develop: http://www.teigfam.net/oyvind/home/047-priority-select-in-go/#golang-nuts_ref07_ref08

Should any of you point to something fiercely wrong there, I would fix and refer back to here. Or please comment in there (I would not trash opinions from here, but with all the spam coming in I do have to moderate. Sorry.)

- Øyvind

[Dan Kortschak]

This also works, thought the effect is less noticeable, but with the
advantage that you can adjust the priority by changing the target size
(i.e. number of matching cases for any particular priority level):

(Priority is apparent even when GOMAXPROCS=1 so this works in
playground)

http://play.golang.org/p/nhpeBVY6CG

[andrey mirtchovski]

> http://play.golang.org/p/nhpeBVY6CG

reduced to a readable minimum: http://play.golang.org/p/AJypEkkEcc

$ for i in {1..10}; do GOMAXPROCS=$i ./t; done
[2831 2562 2417 2190]
[3010 2871 2489 1630]
[3136 2856 2390 1618]
[3099 2827 2395 1679]
[3144 2825 2397 1634]
[3151 2852 2408 1589]
[3156 2857 2411 1576]
[3131 2898 2416 1555]
[3187 2834 2472 1507]
[3104 2827 2435 1634]

[Dan Kortschak]

Thank you, just woke up.

[Tamás Gulácsi]

Wow! How nobody thouggt this simple, efficient and tweakable solution!?

[andrey mirtchovski]

> But there is no priority here. Just probability.

what is the definition of 'priority' here?

[Øyvind Teig]

(I just deleted this comment because I had a formatting problem. Hope it won't appear twice. I hope this will have single lines)

What's the theory behind this solution?

The function "priselect", could it instead be called "mydice"?

Are you searching for a dice that suits your needs?

And a thrower that has learned how to tweak the dice so that it behaves like, like, like, ..this!

I am using pun here, not to make fun of anybody, but to try to get a point across.

Seriously, select does pseudo-random always, always. It's its DNA in Go.

Just to offset the select dice with more sides makes it skewed, but no general pri select.

But like 6 sides (1-6) or 12 sides (double of 1-6) or 24 sides (quad of 1-6) makes distribution the same flat curve.

Now take the 24th side and put a 7 on it, and it will be seen 1/24 times, and the rest 1-6 will be seen (23/24) of the incidents.

But there is no priority here. Just probability.

I see that there are some general solutions of small dice out there, 

but my head can't tweak the preselect example code shown.

- Øyvind

[Jan Mercl]

On Tue, Oct 9, 2012 at 8:32 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> Seriously, select does pseudo-random always, always. It's its DNA in Go.

Why you are repeating (in the blog update too) this? It's not true and
it has been previously shown to you where the specs disagree with you.

Another fallacy is (form the blog update): default clause implies busy
waiting. No. Simply not true. Actually one of the solutions presented
here earlier used default clauses (to prioritize) - but actually in a
select guaranteed to be never blocking.

I'm afraid this moves the discussion from the academic field to somewhere else.

-j

[Øyvind Teig]

I am sorry if this you see it like that. I don't want to move the discussion to somewhere else.

And I do know that repeating something that is wrong does not make it correct!

To the points: 

1. Does it say anywhere in the spec that select uses anything else than pseudo-random choice?
   
2. If there is a default clause then if none of the other cases are taken, it always "commits" to the default. The default is always ready, right?
3. If in the default in next level there is a single commclause and no default, it will take that secondly, and yes we have a priority scheme just there in time.
4. I meant that if the select _ends_up_ in a default (not like in 3), then we must do busy poll, ie. re-run the select?
5. The total effect of "indented" one case and one default (then one case and one default) makes a special case of the pseudo-random choice mechanism. It think it is this mechanism that the Go community uses to simulate a pri select in some cases?
6. But the problem is if like 7 of the cases above are not taken, and we come to the 8th (having low priority of 8th) and there is no default clause, so the 8th blocks, and then one of the 1-7 arrives (with higher priority) - how are those 1-7 then prioritised above the 8th? 
7. Don't you have to have default also after the 8th?
8. And then revert to busy poll?

This will end up in facts, and I want to agree with you on facts. Please help!

- Øyvind

-j

[Øyvind Teig]

kl. 08:35:45 UTC+2 tirsdag 9. oktober 2012 skrev aam følgende:

> But there is no priority here. Just probability.

what is the definition of 'priority' here?

I meant to say that pseudo-random has a flat probability, and that it cannot be considered priority if some numbers are repeated in the set. But I agree that throwing in the double amount of a number starts to look like priority, but even having 999 1's and 1 zero does not make 1's prioritised. It just makes it more probable that they appear, because if 1 is prioritized it should always overrule the single zero, and not let the zero come through 1/999 of the incidents. (Hope I shuffled that right!-)

/ Øyvind

[Øyvind Teig]

By the way, this shows the problem of fairness! Not much fair that just because they are many the single one will never get through! In this case pseudo-random is more fair than priority (always assuming all in the set are ready). But random may be unfair! And some hand coded scheme using priority may even be better. It depends on what is expectation of "fair" in that particular application.

/ Øyvind

 

[Rory McGuire]

Does anyone know why the numbers become purfectly equal if you add a default case with a time.sleep

 call to the select in the code that kortschak and aam posted?

http://play.golang.org/p/nb61C-YyyY [Note: no sleeping in the playground! lol] output on my PC is:

[2000 2000 2000 2000 2000]

[roger peppe]

On 9 October 2012 08:04, Øyvind Teig <oyvin...@teigfam.net> wrote:
> But the problem is if like 7 of the cases above are not taken, and we come
> to the 8th (having low priority of 8th) and there is no default clause, so
> the 8th blocks, and then one of the 1-7 arrives (with higher priority) - how
> are those 1-7 then prioritised above the 8th?

This is the case I was trying to describe in my previous message.
There is no priority in this case, but I don't believe it matters.

It only matters if two or more cases become ready at *exactly* the same
time (well, in the time between the last default case and the blocking
select, which amounts to a similar thing). I believe that a genuine
prioritised select would have the same issue, albeit with a smaller
time window.

Let's assume we *have* got an implementation of a prioritised select
statement. If two cases become ready at exactly the same time, how are
we going to know that and choose the one with higher priority? I don't
believe we are - one of the two will manage to take the lock on the
waiting select and its case will proceed, regardless of its priority. I
suppose it might be possible for the higher priority case to preempt
the lower priority case that's busy putting its value on the channel,
but putting a value onto a ready channel is such a low cost operation
(one memory assignment) that this would almost never happen.

AFAICS, to all intents and purposes (modulo a few hundred nanoseconds
of uncertainty) the default-select-then-blocking-select idiom implements
prioritised select correctly.

[roger peppe]

On 8 October 2012 22:25, Dan Kortschak <dan.ko...@adelaide.edu.au> wrote:
> This also works, thought the effect is less noticeable, but with the
> advantage that you can adjust the priority by changing the target size
> (i.e. number of matching cases for any particular priority level):
>
> (Priority is apparent even when GOMAXPROCS=1 so this works in
> playground)
>
> http://play.golang.org/p/nhpeBVY6CG

I suppose this might be useful sometimes, but it's really not
the same thing - in my original, a lower priority case will never
be chosen if a higher priority case is ready. There's no probability
involved.

The uncertainty you see in the numbers I published are due to
uncertainty in the goroutines that generate the values.
If the consumer is slower than the producers, you'll see that it will
choose the highest priority case with 100% probability.

[Øyvind Teig]

kl. 11:01:10 UTC+2 tirsdag 9. oktober 2012 skrev rog følgende:

On 9 October 2012 08:04, Øyvind Teig <oyvin...@teigfam.net> wrote:
> But the problem is if like 7 of the cases above are not taken, and we come
> to the 8th (having low priority of 8th) and there is no default clause, so
> the 8th blocks, and then one of the 1-7 arrives (with higher priority) - how
> are those 1-7 then prioritised above the 8th?

This is the case I was trying to describe in my previous message.
There is no priority in this case, but I don't believe it matters.

It only matters if two or more cases become ready at *exactly* the same
time (well, in the time between the last default case and the blocking
select, which amounts to a similar thing).  I believe that a genuine
prioritised select would have the same issue, albeit with a smaller
time window.

What if *none* of the cases are ready when the select is entered?

/ Øyvind

[roger peppe]

This an artifact of the scheduler - you're ensuring (by accident)
that all goroutines
get an equal turn at producing.

With GOMAXPROCS > 1, you'll see the different priorities as usual.

[roger peppe]

On 9 October 2012 10:12, Øyvind Teig <oyvin...@teigfam.net> wrote:
>
>
> kl. 11:01:10 UTC+2 tirsdag 9. oktober 2012 skrev rog følgende:
>>
>> On 9 October 2012 08:04, Øyvind Teig <oyvin...@teigfam.net> wrote:
>> > But the problem is if like 7 of the cases above are not taken, and we
>> > come
>> > to the 8th (having low priority of 8th) and there is no default clause,
>> > so
>> > the 8th blocks, and then one of the 1-7 arrives (with higher priority) -
>> > how
>> > are those 1-7 then prioritised above the 8th?
>>
>> This is the case I was trying to describe in my previous message.
>> There is no priority in this case, but I don't believe it matters.
>>
>> It only matters if two or more cases become ready at *exactly* the same
>> time (well, in the time between the last default case and the blocking
>> select, which amounts to a similar thing). I believe that a genuine
>> prioritised select would have the same issue, albeit with a smaller
>> time window.
>
>
> What if *none* of the cases are ready when the select is entered?

That's the case I'm trying to describe.

If no case is ready when the select is entered, the first case to
become ready will be the first case to run, regardless of its
priority. This is surely the case with Occam's PRI ALT too.

>
> / Øyvind
>
>>
>> Let's assume we *have* got an implementation of a prioritised select
>> statement. If two cases become ready at exactly the same time, how are
>> we going to know that and choose the one with higher priority? I don't
>> believe we are - one of the two will manage to take the lock on the
>> waiting select and its case will proceed, regardless of its priority. I
>> suppose it might be possible for the higher priority case to preempt
>> the lower priority case that's busy putting its value on the channel,
>> but putting a value onto a ready channel is such a low cost operation
>> (one memory assignment) that this would almost never happen.
>>
>> AFAICS, to all intents and purposes (modulo a few hundred nanoseconds
>> of uncertainty) the default-select-then-blocking-select idiom implements
>> prioritised select correctly.
>

> --
>
>

[Øyvind Teig]

I don't want to jam this thread, but isn't this tweaking the dice and the thrower to get what you want out of probability?

/Øyvind

[Øyvind Teig]

kl. 11:16:10 UTC+2 tirsdag 9. oktober 2012 skrev rog følgende:

On 9 October 2012 10:12, Øyvind Teig <oyvin...@teigfam.net> wrote:
>
>
> kl. 11:01:10 UTC+2 tirsdag 9. oktober 2012 skrev rog følgende:
>>
>> On 9 October 2012 08:04, Øyvind Teig <oyvin...@teigfam.net> wrote:
>> > But the problem is if like 7 of the cases above are not taken, and we
>> > come
>> > to the 8th (having low priority of 8th) and there is no default clause,
>> > so
>> > the 8th blocks, and then one of the 1-7 arrives (with higher priority) -
>> > how
>> > are those 1-7 then prioritised above the 8th?
>>
>> This is the case I was trying to describe in my previous message.
>> There is no priority in this case, but I don't believe it matters.
>>
>> It only matters if two or more cases become ready at *exactly* the same
>> time (well, in the time between the last default case and the blocking
>> select, which amounts to a similar thing).  I believe that a genuine
>> prioritised select would have the same issue, albeit with a smaller
>> time window.
>
>
> What if *none* of the cases are ready when the select is entered?

That's the case I'm trying to describe.

I still don't understand. None are neither ready when select is entered nor ready during the assumed pickup of commevent. One that was passed on the list got ready "after a year", and we're hanging on the lowest priority (assuming no ending default). Therefore I don't understand the nanosecond argument either.

If no case is ready when the select is entered, the first case to
become ready will be the first case to run, regardless of its
priority. This is surely the case with Occam's PRI ALT too.

I believe that occam processes the ALT atomically, and the boolean expressions are side effect free. I see in the "Transputer instruction set" that ALT evaluation starts with an "alt start" instruction. And besides, I haven't seen any preemptive scheduling of occam. But on the transputer, a physical pin could be a channel, so the "alt start" must have done the trick, I assume. 

/ Øyvind 

[roger peppe]

On 9 October 2012 10:17, Øyvind Teig <oyvin...@teigfam.net> wrote:
> I don't want to jam this thread, but isn't this tweaking the dice and the
> thrower to get what you want out of probability?
> /Øyvind

The difference in the numbers here is entirely to do with the behaviour
of the *scheduler*, not the select statement. We are not just measuring
the select cases here - we are also measuring the ability of the generating
goroutines to keep up with the consumer.

Given that we don't have goroutine priorities in Go (an entirely
different issue) I don't think this is surprising.

If we take the scheduler out of the equation (for example by using channels that
are always ready), then you'll see the select statement working independently
of the scheduler: http://play.golang.org/p/PqGENFmeCh

[roger peppe]

On 9 October 2012 10:25, Øyvind Teig <oyvin...@teigfam.net> wrote:
>> > What if *none* of the cases are ready when the select is entered?
>>
>> That's the case I'm trying to describe.
>
> I still don't understand. None are neither ready when select is entered nor
> ready during the assumed pickup of commevent. One that was passed on the
> list got ready "after a year", and we're hanging on the lowest priority
> (assuming no ending default). Therefore I don't understand the nanosecond
> argument either.

We're not hanging on the lowest priority - we're hanging on *all* priorities.
The first case to be ready, regardless of priority, will unblock the
select and proceed.

>> If no case is ready when the select is entered, the first case to
>> become ready will be the first case to run, regardless of its
>> priority. This is surely the case with Occam's PRI ALT too.
>
>
> I believe that occam processes the ALT atomically, and the boolean
> expressions are side effect free. I see in the "Transputer instruction set"
> that ALT evaluation starts with an "alt start" instruction. And besides, I
> haven't seen any preemptive scheduling of occam. But on the transputer, a
> physical pin could be a channel, so the "alt start" must have done the
> trick, I assume.

The question isn't whether the ALT is processed atomically, but what the
ALT does when it finds that a lower priority case has become ready. Does
it wait for a while in case a higher priority case might become ready
in the next few microseconds? Or does it just proceed with the lower
priority case anyway?

I believe that the latter is the only reasonable way to make an
efficient implementation. If that's true, the Go implementation will
behave identically to the Occam implementation when no cases are ready
on entry to the select - that is, the first case to become ready will
proceed, regardless of priority. The Go random choice semantics do not
apply in this case.

[Dan Kortschak]

I'm not sure the situation is as clear as you're suggesting. In your original, if a is not ready at the first select, the default is chosen. Let's say b is ready in this case. We get to the second select, but in the mean time a becomes ready. We now have a pseudo-random choice between a and b, where approximately 0.5 of the time the lower priority case is chosen. This depends on a race, but it's still a probability game.

[Jan Mercl]

On Tue, Oct 9, 2012 at 11:53 AM, Dan Kortschak
<dan.ko...@adelaide.edu.au> wrote:
> I'm not sure the situation is as clear as you're suggesting. In your original, if a is not ready at the first select, the default is chosen. Let's say b is ready in this case. We get to the second select, but in the mean time a becomes ready. We now have a pseudo-random choice between a and b, where approximately 0.5 of the time the lower priority case is chosen. This depends on a race, but it's still a probability game.

This perhaps nailed one source of mutual confusion in this thread. Let
me rephrase:

Q: "What if, after making a decision based on some input, the input is changed".
A: Nothing. It's irrelevant to the decision already made. Unless one
can bear the risk to never reach the decision.

-j

[Dan Kortschak]

Absolutely.

[Øyvind Teig]

kl. 11:41:02 UTC+2 tirsdag 9. oktober 2012 skrev rog følgende:

On 9 October 2012 10:25, Øyvind Teig <oyvin...@teigfam.net> wrote:
>> > What if *none* of the cases are ready when the select is entered?
>>
>> That's the case I'm trying to describe.
>
> I still don't understand. None are neither ready when select is entered nor
> ready during the assumed pickup of commevent. One that was passed on the
> list got ready "after a year", and we're hanging on the lowest priority
> (assuming no ending default). Therefore I don't understand the nanosecond
> argument either.

We're not hanging on the lowest priority - we're hanging on *all* priorities.
The first case to be ready, regardless of priority, will unblock the
select and proceed.

Which code is this (playground, there are so many, I am confused!-] 

>> If no case is ready when the select is entered, the first case to
>> become ready will be the first case to run, regardless of its
>> priority. This is surely the case with Occam's PRI ALT too.
>
>
> I believe that occam processes the ALT atomically, and the boolean
> expressions are side effect free. I see in the "Transputer instruction set"
> that ALT evaluation starts with an "alt start" instruction. And besides, I
> haven't seen any preemptive scheduling of occam. But on the transputer, a
> physical pin could be a channel, so the "alt start" must have done the
> trick, I assume.

The question isn't whether the ALT is processed atomically, but what the
ALT does when it finds that a lower priority case has become ready. Does
it wait for a while in case a higher priority case might become ready
in the next few microseconds? Or does it just proceed with the lower
priority case anyway?

As you assume, the latter, I also assume: The Compiler Writer's book says that

"The sequence in which the alternatives are enabled is unimportant, but the 

sequence in which they are disabled determines the prioroties of the alternatives.

The first ready alternative to be disabled is selected"

I believe that the latter is the only reasonable way to make an
efficient implementation. If that's true, the Go implementation will
behave identically to the Occam implementation when no cases are ready
on entry to the select - that is, the first case to become ready will
proceed, regardless of priority.

Absolutely.

 

The Go random choice semantics do not
apply in this case.

Agree! 

/ Øyvind

[Øyvind Teig]

"Mutual confusion" !-) (Of course not meaning that I/we don't want to agree on facts! The problem is to smoke out the facts. I have heard that a frog only snaps and eats what's flying before his eyes, and will hunger to death if the food is placed on the table before it)

My view: Your answer to A is right. Kortschak is right. I am still a frog.

/ Øyvind

[roger peppe]

On 9 October 2012 11:20, Øyvind Teig <oyvin...@teigfam.net> wrote:
> kl. 11:41:02 UTC+2 tirsdag 9. oktober 2012 skrev rog følgende:
>>
>> On 9 October 2012 10:25, Øyvind Teig <oyvin...@teigfam.net> wrote:
>> >> > What if *none* of the cases are ready when the select is entered?
>> >>
>> >> That's the case I'm trying to describe.
>> >
>> > I still don't understand. None are neither ready when select is entered
>> > nor
>> > ready during the assumed pickup of commevent. One that was passed on the
>> > list got ready "after a year", and we're hanging on the lowest priority
>> > (assuming no ending default). Therefore I don't understand the
>> > nanosecond
>> > argument either.
>>
>> We're not hanging on the lowest priority - we're hanging on *all*
>> priorities.
>> The first case to be ready, regardless of priority, will unblock the
>> select and proceed.
>
>
> Which code is this (playground, there are so many, I am confused!-]

The first code I posted: http://play.golang.org/p/1ZVdYlA52x

[roger peppe]

On 9 October 2012 10:53, Dan Kortschak <dan.ko...@adelaide.edu.au> wrote:
> I'm not sure the situation is as clear as you're suggesting. In
> your original, if a is not ready at the first select, the default is
> chosen. Let's say b is ready in this case. We get to the second select,
> but in the mean time a becomes ready. We now have a pseudo-random
> choice between a and b, where approximately 0.5 of the time the lower
> priority case is chosen. This depends on a race, but it's still a
> probability game.

I should probably have said "a lower priority case will never be chosen
if a higher priority case is ready on entry to the first select".

The point that I've tried to make above is that the time between the first
select and the second select is only a few hundred nanoseconds. If the
two events are that close together, then scheduler jitter could easily
reorder them anyway; I find it difficult to think of an application
where this could cause a problem.

[Dan Kortschak]

I think the only time it would be an issue (if this whole thing is actually an issue - which I not really convinced of) is in the case of infrequent producers the may fire together at resonably high probability. This would leave the consumer waiting in the final catch all select with the possibility of random choice of case.

[Øyvind Teig]

Great!

Now I discovered that the last select in priselect does not have a default! (Advice: comment it explicitly in the code!)

So my most important criterion is granted!

Jogging along I do agree that this code has a primary dimension of priority.

And a secondary dimension of pseudo-random choice.

Now I understand the nanoseconds.

It's elegant in the sense of dreaming it up! Well done!

It's not elegant in the sense of how to do a missing feature in a language, but this is none of your fault!

Now the next question is if the jitter is important for formal verification. 

I have this feeling: if communication is synchronous (zero buffer in the channel) it won't introduce a formal problem.

If communication is buffered then the sender side of the "high priority channel" may proceed even if the high priority event was not taken.

If this is part of a communication cyclus, a CSP, LTSA or Promela model will show that this pri select is not adequate.

So, Go needs a proper pri select. I did suggest a syntax for that. 

So, your solution is ambigious. This is probably what you also stated.

All in the above paragraph may be falsified!

Now with that in place, what else needs to be shot before my eyes?

Thanks! I will update in my blog note, probably tonight.

/ Øyvind

 

[Rory McGuire]

strange. Thanks.

I presume this is implementation issue, and not part of the language?

Surely during the sleep the other options should have been running randomly still.

[roger peppe]

On 9 October 2012 13:43, Rory McGuire <rjmc...@gmail.com> wrote:
> strange. Thanks.
> I presume this is implementation issue, and not part of the language?

Yes. Otherwise setting GOMAXPROCS wouldn't change it.

> Surely during the sleep the other options should have been running randomly
> still.

There's no "running randomly" when GOMAXPROCS<=1 and there
are no syscalls running. It's a simple round-robin scheduler AFAIK.

[roger peppe]

I don't see how this is a problem. With a buffered channel,
the sender can proceed independent of the receiver, yes, but
a blocked receiver will still be woken immediately by the
first value to arrive on any channel.

It seems irrelevant to me whether a select case becomes ready because the
value was sent on a buffered or an unbuffered channel - the
effect will be the same in either case, no?

> If this is part of a communication cyclus, a CSP, LTSA or Promela model will
> show that this pri select is not adequate.

I'd like to see a Promela model that shows this.

[Ian Lance Taylor]

On Tue, Oct 9, 2012 at 4:53 AM, Dan Kortschak
<dan.ko...@adelaide.edu.au> wrote:
> I think the only time it would be an issue (if this whole thing is actually an issue - which I not really convinced of) is in the case of infrequent producers the may fire together at resonably high probability. This would leave the consumer waiting in the final catch all select with the possibility of random choice of case.

You are describing a race condition. In an implementation in which
one choice must be selected and processed, race conditions are always
possible. This has nothing to do with Go.

The only way to handle the scenario you describe would be to have
preemptive channel selection: provide some way of saying that data
arriving on channel A is always handled immediately, even if we are in
the middle of handling data arriving on channel B. Go does not
support preemption of that sort.

Ian

[Øyvind Teig]

I agree with you. It's probably not part of a cycle, so it should be safe. I also now don't think that buffering will make any difference. I have only 1% doubt. 

/ Øyvind 

[Dan Kortschak]

Yes, that's my point.

[Øyvind Teig]

I have updated in my blog, and also referred to some of your code (url in above). Should be facts! Thanks for your patience! 

So, provided priority select is wanted as a language primitive, I also suggested in my blog how to, other than the obvious pri select, spell it out. I coupled having or not having a boolean expressions in the case with priority or pseudo-random choice. It embeds a discussion (which did not catch on here) about how orthogonal boolean expression in select case (guard) is with the choice algorithm. (More about GUARDED selective waiting in golang-nuts.)

/ Øyvind (aclassifier)

Trondheim, Norway

[Øyvind Teig]

kl. 15:33:13 UTC+2 tirsdag 9. oktober 2012 skrev Ian Lance Taylor følgende:

On Tue, Oct 9, 2012 at 4:53 AM, Dan Kortschak
<dan.ko...@adelaide.edu.au> wrote:
> I think the only time it would be an issue (if this whole thing is actually an issue - which I not really convinced of) is in the case of infrequent producers the may fire together at resonably high probability. This would leave the consumer waiting in the final catch all select with the possibility of random choice of case.

You are describing a race condition.  In an implementation in which
one choice must be selected and processed, race conditions are always
possible.  This has nothing to do with Go.

In unix select, there may be several causes for the select. In CSP-type selects there is only one cause. In any case, at some stage the runtime system must stop picking up more causes. I assume that unix is picks up causes longer? CSP-type choice closes all other causes when one has been picked. Since it's basically synchronous, tearing down the select will keep the other sources that were also ready blocked.

Is this what you mean by "race conditions are always possible"? If affirmative I personally don't think I would call this a race. It's normal event handling. In occam the ALT isn't even queued.

The only way to handle the scenario you describe would be to have
preemptive channel selection: provide some way of saying that data
arriving on channel A is always handled immediately, even if we are in
the middle of handling data arriving on channel B.  Go does not
support preemption of that sort.

Are you aware of any language or scheduler that would do this? I am not.

/ Øyvind 

Ian

[Ian Lance Taylor]

On Tue, Oct 9, 2012 at 1:29 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:
>
>
> kl. 15:33:13 UTC+2 tirsdag 9. oktober 2012 skrev Ian Lance Taylor følgende:
>>
>> On Tue, Oct 9, 2012 at 4:53 AM, Dan Kortschak
>> <dan.ko...@adelaide.edu.au> wrote:
>> > I think the only time it would be an issue (if this whole thing is
>> > actually an issue - which I not really convinced of) is in the case of
>> > infrequent producers the may fire together at resonably high probability.
>> > This would leave the consumer waiting in the final catch all select with the
>> > possibility of random choice of case.
>>
>> You are describing a race condition. In an implementation in which
>> one choice must be selected and processed, race conditions are always
>> possible. This has nothing to do with Go.
>
>
> In unix select, there may be several causes for the select. In CSP-type
> selects there is only one cause. In any case, at some stage the runtime
> system must stop picking up more causes. I assume that unix is picks up
> causes longer? CSP-type choice closes all other causes when one has been
> picked. Since it's basically synchronous, tearing down the select will keep
> the other sources that were also ready blocked.
>
> Is this what you mean by "race conditions are always possible"? If
> affirmative I personally don't think I would call this a race. It's normal
> event handling. In occam the ALT isn't even queued.

What I mean (and what I think Dan said earlier) is that it's
meaningless to speak about the problem of one channel being picked
when another channel is just about to become ready. If select blocks
waiting for a communication, then the first one that arrives is the
one that is chosen. There is no reason to consider channel priority
when select is blocked. To speak about a blocked select returning the
wrong channel is to speak about a race condition, because the higher
priority response might always be just slightly slower than the amount
of time you want the select to wait. A correct program can not care
which channel is returned by a blocking select; if it does care, it
will have a race.

>> The only way to handle the scenario you describe would be to have
>> preemptive channel selection: provide some way of saying that data
>> arriving on channel A is always handled immediately, even if we are in
>> the middle of handling data arriving on channel B. Go does not
>> support preemption of that sort.
>
>
> Are you aware of any language or scheduler that would do this? I am not.

Language, no, but that's how interrupts work on a processor, and it's
what OS interrupt handlers expect to see. It's also how embedded OS's
handle events.

Ian

[Dan Kortschak]

Yes, and I think this is Jan's point too.

[Joubin Houshyar]

If we take the scheduler out of the equation (for example by using channels that 

are always ready), then you'll see the select statement working independently
of the scheduler: http://play.golang.org/p/PqGENFmeCh

In a way, actually user level scheduling if you take it to its conclusion: http://play.golang.org/p/kboO9t6RQw

/R

[Øyvind Teig]

Fully agree. 

But (not really to nitpick) from the above follows that there is no "wrong" channel:

 

To speak about a blocked select returning the
wrong channel is to speak about a race condition, because the higher
priority response might always be just slightly slower than the amount
of time you want the select to wait.  

..and therefore no race, there is noone to race with. And there is really no such 

thing as the amount of time we want the select to wait. An event comes from 

the outside of a goroutine/process, and we have no control of it. In some of the 

very nice playground cases, the producers and the consumers are "livelocked" 

for the sake of testing, and such thinking as time in select easily creeps in.

 

A correct program can not care
which channel is returned by a blocking select; if it does care, it
will have a race.

What comes from a blocking select is element in the set of possible commmevents 

(which may be reduced dynamically if we had boolean expressions in cases),

pri-select pr pseudo-random-select doesn't matter.

If the application as you say cares, it's plain wrong application coding.

An the race you mention here I agree on, but it's got nothing to do with 

the select and how it works. There is no race inside the select.

It could be a race if wrong coding of the select!

When the people at Kent wrote JCSP in the late ninetees there was a hidden race inside

their coding of the ALT, which was based on the Java monitor, notify and notifyall.

So simple and so difficult (I think because Brinch Hansen's recipe hadn't been adherred

to by Sun). When a student after two years all of a sudden discovered this error, their ALT

coding was modeled in FDR2 at Oxford, and after a day or two the error was found.

I think they swapped two lines of code. But I assume this is not the kind of

race you were thinking of.

To the purists the select should not have any algorithm to select, and the application 

shall not assume any algorithm. A formal analysis tool will traverse 

all possible event. It only asks whether something is possible sooner or later.

>> The only way to handle the scenario you describe would be to have
>> preemptive channel selection: provide some way of saying that data
>> arriving on channel A is always handled immediately, even if we are in
>> the middle of handling data arriving on channel B.  Go does not
>> support preemption of that sort.
>
>
> Are you aware of any language or scheduler that would do this? I am not.

Language, no, but that's how interrupts work on a processor, and it's
what OS interrupt handlers expect to see.  It's also how embedded OS's
handle events.

Of course, but the semantics of events, queueing (even into channels) and 

scheduling policy, I don't see what this has to do with the semantics of select.

Correct me if some of the above should be wrong. I like this conversation!

/ Øyvind 

Ian

[roger peppe]

Nice idea, but it doesn't really work I'm afraid. Consider what
happens if only one
of the generators is ready: http://play.golang.org/p/9CZtrI98cb

(BTW the code to fill out the channels to select on could also use
improvement - it only ever puts a single channel in the select array,
and it crashes if the numbers don't add up, e.g.
http://play.golang.org/p/f-j1ebpqJY)

[Joubin Houshyar]

On Wed, Oct 10, 2012 at 3:56 AM, roger peppe <rogp...@gmail.com> wrote:

On 9 October 2012 22:34, Joubin Houshyar <jhou...@gmail.com> wrote:
>
> If we take the scheduler out of the equation (for example by using channels
> that
>>
>> are always ready), then you'll see the select statement working
>> independently
>> of the scheduler: http://play.golang.org/p/PqGENFmeCh
>
>
> In a way, actually user level scheduling if you take it to its conclusion:
> http://play.golang.org/p/kboO9t6RQw

Nice idea, but it doesn't really work I'm afraid. Consider what
happens if only one
of the generators is ready: http://play.golang.org/p/9CZtrI98cb

Good catch; missed that. You can work around that by added case of timer in a tight loop and pushing the select down from call site.  Playing with various forms, there is a certain performance hit that caps throughput.

Given OP's original post, it would appear trivial to have explicit selection mechanisms in Go:

select {

case r0 := <-c0:

    // op0

..

case rn := <- cn:

   // opn

default:

   // op_def

selector:  // optional - defaults to default_selector (built-in func)

   [defer?] select_function

}

// given selector function type

// cell element true if corresponding (decl. ord.) case is available.  Return selection index.

type sel_fn func(available []bool) (selection int)

// with a builtin default_selector mapping to current spec semantics e.g. in declaration order 

func default_selector([]bool) int

This should look pretty familiar to various polling apis for things like IO such as Java NIO, externalizing the selection process to the caller.  Interesting possibilities.

(BTW the code to fill out the channels to select on could also use
improvement - it only ever puts a single channel in the select array,
and it crashes if the numbers don't add up, e.g.
http://play.golang.org/p/f-j1ebpqJY)

'not production ready!': check!!

[Joubin Houshyar]

On Fri, Oct 12, 2012 at 5:02 PM, Joubin Houshyar <jhou...@gmail.com> wrote:

On Wed, Oct 10, 2012 at 3:56 AM, roger peppe <rogp...@gmail.com> wrote:

On 9 October 2012 22:34, Joubin Houshyar <jhou...@gmail.com> wrote:
>
> If we take the scheduler out of the equation (for example by using channels
> that
>>
>> are always ready), then you'll see the select statement working
>> independently
>> of the scheduler: http://play.golang.org/p/PqGENFmeCh
>
>
> In a way, actually user level scheduling if you take it to its conclusion:
> http://play.golang.org/p/kboO9t6RQw

Nice idea, but it doesn't really work I'm afraid. Consider what
happens if only one
of the generators is ready: http://play.golang.org/p/9CZtrI98cb

Good catch; missed that. You can work around that by added case of timer in a tight loop and pushing the select down from call site.  Playing with various forms, there is a certain performance hit that caps throughput.

Given OP's original post, it would appear trivial to have explicit selection mechanisms in Go:

select {

On second thought, I like this much better:

 select [selector] {

 ...

 }

 

select rndrbn_selector {

...

}

[Joubin Houshyar]

On Fri, Oct 12, 2012 at 5:02 PM, Joubin Houshyar <jhou...@gmail.com> wrote:

On Wed, Oct 10, 2012 at 3:56 AM, roger peppe <rogp...@gmail.com> wrote:

On 9 October 2012 22:34, Joubin Houshyar <jhou...@gmail.com> wrote:
>
> If we take the scheduler out of the equation (for example by using channels
> that
>>
>> are always ready), then you'll see the select statement working
>> independently
>> of the scheduler: http://play.golang.org/p/PqGENFmeCh
>
>
> In a way, actually user level scheduling if you take it to its conclusion:
> http://play.golang.org/p/kboO9t6RQw

Nice idea, but it doesn't really work I'm afraid. Consider what
happens if only one
of the generators is ready: http://play.golang.org/p/9CZtrI98cb

Good catch; missed that. You can work around that by added case of timer in a tight loop and pushing the select down from call site.  Playing with various forms, there is a certain performance hit that caps throughput.

one variant for example: 

https://gist.github.com/3881643

http://play.golang.org/p/RiEr4aRg7j (doesn't work in playground ..)

A good counter point to "you can do that at user leve" (such as above) is that now the runtime is out of the loop of communications between go routines.  The call to p_select(carr) may never return and spin around forever.  Per normal Go semantics, would actually would expect a "all goroutines are .." instead of cpu churn.