Re: [go-nuts] Using select with input and output statements in driver between fast producer and slow consumer

[roger peppe]

On 13 June 2012 09:06, Øyvind Teig <oyvin...@teigfam.net> wrote:
> In Go we see that the problem in mind (with a faster Producer than Consumer)
> may be solved without any XCHAN or extra overflow buffer (as occam would).
> However, we assume that this is not what the Go designers would think as
> idiomatic Go.
>
> What would idiiomatic Go be for this?

I'm not sure what context your XCHAN is proposed for, or exactly what
problem you're trying to solve with the above code, but here's some
more-or-less idiomatic Go code that does something similar.
Note that we don't need the two communication clauses because Go
any communication on a nil channel will block forever;
we can use this to simulate guards.

http://play.golang.org/p/75hUpqiHYN

package main

import (
"fmt"
)

func main() {
in := make(chan int)
out := make(chan int)
go lossyTransmitter(in, out)
in <- 4
in <- 7
in <- 9
fmt.Println(<-out)
}

// lossyTransmitter copies values from the in channel to the out channel.
// If the reader does not read as fast as the writer, values will be lost.
func lossyTransmitter(in <-chan int, out chan<- int) {
value := 0
valid := false
for {
outc := out
// If we have no value, then don't attempt
// to send it on the out channel.
if !valid {
outc = nil
}
select {
case value = <-in:
// "overflow" if valid is already true.
valid = true
case outc <- value:
valid = false
}
}
}

[Jim Whitehead II]

On Wed, Jun 13, 2012 at 9:06 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> I am writing a paper for a conference trying to argue for a new channel type
> "XCHAN" (based on these
> ideas: http://oyvteig.blogspot.com/2011/12/034-output-guard-vs-channel-ready.html).
> But here is some paper Go that I would appreciate comments on.
>
> This Go example uses blocking select (with no default case) with one output
> and one input. Line 10 attempts a blocking send (!) and line 14 attempts
> blocking receive (?). The select will block until the first component can
> execute. The top communication case is evaluated first, so sending takes
> priority if both are ready. In the receive statements of lines 14 and 21 we

This isn't actually the case, as I understand it. To quote the
specification [1]:

"RecvExpr must be a receive operation. For all the cases in the
"select" statement, the channel expressions are evaluated in
top-to-bottom order, along with any expressions that appear on the
right hand side of send statements. A channel may be nil, which is
equivalent to that case not being present in the select statement
except, if a send, its expression is still evaluated. 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; if there is no default
case, the statement blocks until one of the communications can
complete. If there are no cases with non-nil channels, the statement
blocks forever. Even if the statement blocks, the channel and send
expressions are evaluated only once, upon entering the select
statement.

Since all the channels and send expressions are evaluated, any side
effects in that evaluation will occur for all the communications in
the "select" statement.

If multiple cases can proceed, a uniform pseudo-random choice is made
to decide which single communication will execute."

The top-to-bottom here is a statement of the semantics of the
evaluation of the expressions, which may possibly have side-effects.
Say you have a stack of channels, and you pop one and attempt to
receive on it, something like <- stack.Pop(). It's important to know
that the branches are executed in order to understand what is
happening.

If multiple branches can occur, then the choice is uniformly
pseudo-random. Go really doesn't have a PRI ALT that is built-in with
syntactic support.

> have dropped an optional second parameter, so we assume the channel does not
> become closed.

Correct, the communication you receive may in fact be the zero value
receive on a closed channel.

> 01 var chan_in, chan_out chan int // in from left, out to right
> 02 var value             int
> 03 var do_chan_out       bool = false
> 04 var value_overflow    bool = false
> 05
> 06 for {
> 07     if (do_chan_out == true)
> 08         // BLOCK UNTIL SENT OR NEW value RECEIVED:
> 09         select {
> 10!            case chan_out <- value: // SEND?
> 11                 // SENT:
> 12                 value_overflow = false
> 13                 do_chan_out = false // Since no more to send
> 14?            case value := (<-chan_in): // RECEIVE?
> 15                 // RECEIVED:
> 16                 value_overflow = (do_chan_out == true) // Overflow?
> 17                 do_chan_out = true // ..or false?
> 18         }
> 19     else {
> 20         // BLOCK UNTIL NEW value RECEIVED:
> 21?        value := (<-chan_in) // RECEIVE?
> 22         // RECEIVED:
> 23         do_chan_out = true // ..or false?
> 24     }
> 25 }
>
> Initially it will listen for some input in line 21. When something arrives
> this is written to value and then attempted to be sent with any new input in
> lines 10 or 14 again. We have shown how overflow may be detected.
>
> Since select in Go does not support guarded statemenents, we have to program
> with setting up two selects. The first has two components, the second only
> one (so the select statement in itself is not needed).

>
> In Go we see that the problem in mind (with a faster Producer than Consumer)
> may be solved without any XCHAN or extra overflow buffer (as occam would).
> However, we assume that this is not what the Go designers would think as
> idiomatic Go.
>
> What would idiiomatic Go be for this?

It depends on your specification, and only the last paragraph seems to
be able to provide one for me. I may be misunderstanding, but I'll
sketch the CSP for what I believe you're trying to say.

channel in, out, full

LIMIT = 5

Buffer = let
Empty = in -> Occupied(1)
Occupied(n) = n < LIMIT & in -> Occupied(n+1)
[] n == LIMIT & full -> Occupied(n)
[] out -> Occupied(n-1)
within Empty

Notions of priority are difficult to express in CSP, but you don't
seem to specify output priority in your specification.
A straightforward translation of this to Go looks something like this:

If that's what you're looking to do, there are several ways to express
that same thing in Go that would be idiomatic.

[1]: http://golang.org/ref/spec#Select_statements

[Øyvind Teig]

Thank you Rog! I am learning all the time!

Now I am confused as to how much of your code I could adopt in my paper? It will appear in the Appendix, as it really explains how Go may solve that problem by select in/out and no extra buffer process or alternatively "my XCHAN". And how should I credit this (pointing to this thread?)? (The paper will be submitted for CPA-2012, but I would not know if it will be accepted, of course.)

kl. 11:39:46 UTC+2 onsdag 13. juni 2012 skrev rog følgende:

[Øyvind Teig]

Thank you, Jim, for your clarifications. Evaluation order and selection algorithm are two things, of course. Then same comment as with Rog (above) about using this stuff in my paper? In my next life I may learn real CSP! 

kl. 11:42:18 UTC+2 onsdag 13. juni 2012 skrev Jim Whitehead følgende:

Did you forget to paste the code, or did you mean to go to the url below?

[Jim Whitehead II]

On Wed, Jun 13, 2012 at 11:39 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> Thank you, Jim, for your clarifications. Evaluation order and selection
> algorithm are two things, of course. Then same comment as with Rog (above)
> about using this stuff in my paper? In my next life I may learn real CSP!

I think the points I'm making are general enough that you can just
refer to the language specification if you need to clarify any of
those points, so I have no concerns with you using any of this in your
paper.

I think I slightly misunderstood the point of your specification
(which is why I wondered if there was more), but if you're looking for
a leaky buffer that drops items that appear when the buffer is already
full, then the CSP specification I gave wouldn't actually reflect
that, although it could be altered to do so.

Actually Rog's code came up while I was still writing my response, so
I terminated that thought process and went back to my paper revision,
which is requiring most of my focus at the moment. His is a good
example of how you could do this sort of thing, if that was the
behaviour you were looking for.

>> If that's what you're looking to do, there are several ways to express
>> that same thing in Go that would be idiomatic.
>>
>> [1]: http://golang.org/ref/spec#Select_statements

The reference is just a link to the specification for select, to
clarify the priority points I made above.

- Jim

[Øyvind Teig]

Rog, just removing my email address!

kl. 11:39:46 UTC+2 onsdag 13. juni 2012 skrev rog følgende:

[Øyvind Teig]

Thank you!

kl. 12:43:03 UTC+2 onsdag 13. juni 2012 skrev Jim Whitehead følgende:

Ok, thank you! 

[roger peppe]

On 13 June 2012 11:34, Øyvind Teig <oyvin...@teigfam.net> wrote:
> Thank you Rog! I am learning all the time!
> Now I am confused as to how much of your code I could adopt in my paper?

Feel free to use my code. It took 5 minutes to write - use it as you like.

> It will appear in the Appendix, as it really explains how Go may solve that
> problem by select in/out and no extra buffer process

I'm not sure what you mean here. There *is* an extra buffer process.

[Øyvind Teig]

kl. 13:04:20 UTC+2 onsdag 13. juni 2012 skrev rog følgende:

On 13 June 2012 11:34, Øyvind Teig wrote:
> Thank you Rog! I am learning all the time!
> Now I am confused as to how much of your code I could adopt in my paper?

Feel free to use my code. It took 5 minutes to write - use it as you like.

Thanks! 

> It will appear in the Appendix, as it really explains how Go may solve that
> problem by select in/out and no extra buffer process

I'm not sure what you mean here. There *is* an extra buffer process.

This process is extra in one way as you say, but as a server to the nasty sender it protects the lazy consumer. In classical occam this would have been implemented as yet another process (composite or not) to ensure that sending any value to the lazy would not block incoming to the server from the nasty sender. There would either be a chain of occam buffer process elements (if one knew the max) or a composite "overflow buffer" (with two processes, see Figure 3 in paper at http://www.teigfam.net/oyvind/pub/pub_details.html#NoBlocking). This server must always listen on the input from the nasty.  

[Øyvind Teig]

Trying to remove my address

kl. 11:39:46 UTC+2 onsdag 13. juni 2012 skrev rog følgende:

[Steven Blenkinsop]

Removed, as long as nobody replies to you...

[Kyle Lemons]

If you are trying to implement a leaky buffer, I wouldn't do it with a goroutine, I'd do it with a type.

type Leaky chan int

func (ch Leaky) Send(x int) {

  select {

  case ch <- x:

  default:

  }

}

func (ch Leaky) Recv() int {

  return <-ch

}

On Wed, Jun 13, 2012 at 1:06 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:

I am writing a paper for a conference trying to argue for a new channel type "XCHAN" (based on these ideas: http://oyvteig.blogspot.com/2011/12/034-output-guard-vs-channel-ready.html). But here is some paper Go that I would appreciate comments on. 

This Go example uses blocking select (with no default case) with one output and one input. Line 10 attempts a blocking send (!) and line 14 attempts blocking receive (?). The select will block until the first component can execute. The top communication case is evaluated first, so sending takes priority if both are ready. In the receive statements of lines 14 and 21 we have dropped an optional second parameter, so we assume the channel does not become closed.

In Go we see that the problem in mind (with a faster Producer than Consumer) may be solved without any XCHAN or extra overflow buffer (as occam would). However, we assume that this is not what the Go designers would think as idiomatic Go. 

[roger peppe]

On 13 June 2012 23:45, Kyle Lemons <kev...@google.com> wrote:
> If you are trying to implement a leaky buffer, I wouldn't do it with a
> goroutine, I'd do it with a type.
>
> type Leaky chan int
> func (ch Leaky) Send(x int) {
>   select {
>   case ch <- x:
>   default:
>   }
> }
>
> func (ch Leaky) Recv() int {
>   return <-ch
> }

I thought of that (I wouldn't use a type at all in fact
if we were doing that), but the semantics are different.
The original code leaks intermediate values only - the receiver
will always receive the most recent value.

The code above leaks any value when the
sender blocks.

Both may be appropriate in different situations,
but I didn't want to make that decision.

[Øyvind Teig]

This is interesting. The paper I am writing does introduce a new channel type called XCHAN which at least seems very useful for systems than don't allow outputs in selects (occam (dead), XMOS XC (but I don't know how it applies there), our ChanSched etc.). The idea is to have this fast producer that is out in the world somewhere that we don't have any control of. Data may arrive on a socket, which I learn cannot be part of a Go select, but we either need to have it go on or to hold it (if TCP/IP). Anyway, I do want a server at the input terminals that relates to overrun, and detects it. Then, on the inside of that server, if there is a buffered channel or not buffered is not so important, but the server cannot block on that channel. It that channel has no capacity is also ok (as in your examples), as long as we can pick up the fact that there is no listener. The difference comes when (if no buffer) the inside receiver has not yet arrived "on the channel" (being first) and the sender is first. In the non-buffered case this is not different from "no buffer but still full" if you understand what I mean. So that needs to be related to as well.

And aging property of data is also important, as both of you point out. And the fact that it must not be the fast producer out there that "drives" the situation, if after a burst it stops after an overflow situation, the server still must go on and f.ex. send what it has, if that is what it wants. And no busy poll.

Another thing, Kyle - can I use your code in my paper, and how should I refer to it?

kl. 08:22:32 UTC+2 torsdag 14. juni 2012 skrev rog følgende:

[Kyle Lemons]

Ah, indeed.  Good catch :).  You can relatively simply modify it for the other end:

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

type Leaky chan int

func (ch Leaky) Send(x int) {

for {

select {

case ch <- x:

return

default:

<-ch

}

}

}

func (ch Leaky) Recv() int {

return <-ch

}

[Øyvind Teig]

Ok, if the receiver is there it successfully sends and returns.

If the receiver is not there, it tries to input (?) on the output channel but will block until the other side also inputs? Only then will it spool back again an then the send should succeed?

Is it possible to (fake) input on the sender end?
Or did I read Go syntax wrongly?

Being used to occam in the nineties this is new to me!

[Øyvind Teig]

[roger peppe]

On 14 June 2012 18:42, Kyle Lemons <kev...@google.com> wrote:
> Ah, indeed.  Good catch :).  You can relatively simply modify it for the
> other end:
> http://play.golang.org/p/Qq3sQqjq2S
>
> type Leaky chan int
>
> func (ch Leaky) Send(x int) {
> for {
> select {
> case ch <- x:
> return
> default:
> <-ch
> }
> }
> }
>
> func (ch Leaky) Recv() int {
> return <-ch
> }

that's wrong - it can deadlock if the receiver reads
between the default case being selected and the
channel receive running.

you could do this:

func (ch Leaky) Send(x int) {
for {
select {
case ch <- x:
return

case <-ch:
}
}
}

but that won't work if you've got multiple senders.

[Øyvind Teig]

Not multiple senders because of the for loop which may cause a different channel to be treated on the next round?

[roger peppe]

On 15 June 2012 12:33, Øyvind Teig <oyvin...@teigfam.net> wrote:
> Not multiple senders because of the for loop which may cause a different channel to be treated on the next round?

actually, i think it will probably work ok with multiple senders.

[Øyvind Teig]

Will calls to the Send and Recv methods be queued because Chan is a (concurrent) object?

If so, it is interesting since I think this was the reason why the Ada rendezvous, also based on CSP, was banned for the Ada Ravenscar high integrity profile, where analyzability with respect to timing is important. A standard occam ALT or XC select (I believe) do not queue.

Also, will a zero-buffered Go chan also queue? Where do I find this information?

[roger peppe]

On 15 June 2012 17:30, Øyvind Teig <oyvin...@teigfam.net> wrote:
> Will calls to the Send and Recv methods be queued because Chan is a (concurrent) object?

each channel has a queue of receivers and senders, yes,
one queue item for each goroutine blocked on the queue.
removing an item from the head of the queue is O(1) though.

the implementation is where the information is. it's quite
readable C.

BTW i was always under the impression that the Occam ALT
statement didn't allow select on output because it was
difficult to implement over a wire. i may well be wrong though.

[Øyvind Teig]

Thanks! When I get my paper done I will study that code!

You are right about occam, I have also heard that story. The transputer links and channels routed via other processors seemingly made a complex protocol for output guards. I have heard that the ALT alone was 2 KB of microcode, eveb without the output.

But as far as I see, the new XC language by XMOS (David May is still around, slightly younger then me), XC too has no output guards. Please prove me wrong!

A Go "Ravenscar profile" would prohibit those Go queues! That's a nuisance, I would think..

[Øyvind Teig]

Please, what happens at

case <- ch:
// no code

??

[Steven Blenkinsop]

A value is received from the channel and thrown out. 

[Øyvind Teig]

Ok. Thanks.
But taking a receiver role in a Send confuses me.
What about the Recv side?
Two receivers on the same channel?
Guess if I am confused.

[Steven Blenkinsop]

Yeah, you can have two receivers on the same channel. The idea is that, if the channel is full, you want to discard some of the older elements at the head. You have to do that during send to free space for the value you want to send. Don't confuse receiving on the channel with a Recv call. Consider the `<-ch` to be a `leak(ch)`

[Øyvind Teig]

Thank you! I am really learning now. Rather interesting.

The channel seems to have a role between a "pure" CSP channel (blocking), an object (with operations), and a buffer (different usage, like the reading in the Send to take one out while trying to send)? Is such a description of any value?

[Ian Lance Taylor]

Øyvind Teig <oyvin...@teigfam.net> writes:

> The channel seems to have a role between a "pure" CSP channel
> (blocking), an object (with operations), and a buffer (different
> usage, like the reading in the Send to take one out while trying to
> send)? Is such a description of any value?

I'm not sure just what you mean by a channel being an object with
operations. A channel has exactly two operations: send and receive.

Go supports two different kinds of channels. An unbuffered channel
synchronizes two goroutines, and transfers a piece of data between them.
A buffered channel holds zero or more items of data, and can be thought
of as a threadsafe FIFO queue.

Ian

[Øyvind Teig]

Good to have that verified. So they would be like the occam channels from the eightied plus buffering.

I goofed it since I did the wrong conclusion that binding the method Send  with receiver type chan, to the base type chan makes an operation Send to chan - should in any way extend the functionality of the basic chan type. But still the basic chan type of course still only has send and receive. (Now, did I get that right?..)

I must soon do some Go myself. But some times it's ok to learn by asking questions too, as long as the helpful Go community is out there!

[Øyvind Teig]

Just pointing to an new thread "Go vs Ada" at https://groups.google.com/forum/?fromgroups#!topic/golang-nuts/h0Pi010ly-U.