Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: Go 2: introduce a new broadcast channel generic type #28157

Closed
urandom opened this issue Oct 11, 2018 · 10 comments

Comments

@urandom
Copy link

@urandom urandom commented Oct 11, 2018

Introduction

The following proposal introduces the concept of broadcast channels (cast). Similar to chans, casts pass values around. Unlike a chan, a cast allows a copy of the same value to be received by multiple recepients.

Problem

Channels, being a one-to-one blocking relationship, are ill suited for tasks requiring the notification of multiple recipients. The prime example of this is eventing systems. Due to the blocking nature of channels, one has to manually orchestrate the multiplication of the payload to all interested parties, which is difficult and error prone. Sometimes it is virtually impossible to manage these lifecycles if the receivers' lifecycles isn't known.

Solution

A broadcast channel provides a mechanism for producers to emit values of a specific type without carying how many receivers there are, or indeed if there are any at all. It is defined as a regular generic type (cast) (using the generic draft proposal syntax), which prevents any naming collisions with existing code.

bcast := make(cast(int), 10)
var recv <-cast(string)

Like its counterpart, a broadcast channel supports the "<-" operator and can be defined with a direction. It can also have a capacity.

A broadcast is never bidirectional. When a direction is not specific, a send direction is assumed:

var b1 cast(func())
var b2 cast<-(func())

b1 == b2

Unlike a channel, a broadcast never blocks on a send, regardless of capacity.

Broadcasting is achieved by way of assigning/converting a sending broadcast to a receiving one. A broadcast channel can only be converted from a sending to a receiving channel, never the other way around. Each receiving copy of the sending channel will in turn receive any value sent through that broadcast channel, whenever they are requesting to receive items (in case the broadcast capacity is 0).

Consider a hypothetical UI library, with its hypothetical 'Button' element:

func (b *Button) clicked() <-cast(ClickEvent) {
   return b.clickCast
}

...

// Processing all clicks of the button somewhere in the app
for ev := range button.clicked() {
}

...

// same button, awaiting the next click event, at some point in the of the lifecycle of the app
ev := <-button.clicked()

A single instance of the button will be able to notify both listeners for its click event. There will be no need to manage the complex lifecycles of any listener, and in turn the receivers need not worry about notifying the button that they have stopped listening. This management will be handled by the Go runtime automatically.

Capacity

As stated earlier, a broadcast channel also supports a capacity, similarly to a channel. On the sender side, the capacity indicates the size of the value buffer queue. With 0 capacity, the buffer size will still be one, but the effects on the receivers will be different. Each time the sender receives a new value, it places it in the tail of the buffer and wakes all receives currently waiting for a value.

When a receiver first tries to read a value, it looks at the capacity of the sender. If it is zero, it sleeps until the sender wakes it up with a fresh value. When it wakes up, it reads the value from the buffer. Subsequent receive operations first check if there is a new value in the buffer, and will use it if one is available.

If the capacity is non-zero, it starts using the value buffer directly. When it reaches the head of the buffer, it blocks until it is woken up and can read a new value from it.

var b := make(cast(int), 4)

for i := 0; i < 5; i++ {
    b <- i
}

r1 := (<-cast(int))(b)

println(<-r1) // 1
println(<-r1) // 2
println(<-r1) // 3

r2 := (<-cast(int))(b)
println(<-r2) // 1

b <- 10
b <- 11

println(<-r1) // 4
println(<-r1) // 10
println(<-r1) // 11
// println(<-r1) blocks


println(<-r2) // 3
println(<-r2) // 4
println(<-r2) // 10
println(<-r2) // 11
// println(<-r2) blocks

Some naive implementation details

When a receiver is read from, the runtime will add it to a list of receivers that are waiting for an item from the sender. When the item is received, the receiver will be removed from the list.

If we consider the buffer queue as a linked list, the item will have a pointer to the next one in the queue. When a receiver requests a new item, it will attempt to get the next item using the pointer. If the next is nil, and the item it holds is the same as one in the front of the queue, that means that no other items are present and it will block until one appears. If the next pointer is nil but the item differs from the first, then that means that the item is already stale and has dropped from the queue. The receiver will therefore use the item from the front as its new current one.

@networkimprov

This comment has been minimized.

Copy link

@networkimprov networkimprov commented Oct 14, 2018

Related: new channel primitives, clone (i.e. tee) & splice #26282

@ianlancetaylor ianlancetaylor changed the title (draft) proposal: Go2: introduce a new broadcast channel generic type proposal: Go 2: introduce a new broadcast channel generic type Oct 14, 2018
@gopherbot gopherbot added this to the Proposal milestone Oct 14, 2018
@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Oct 14, 2018

How does the sender know whether there is room in the buffer? Does the sender have to track the number of receiver copies, and count the number of times each value has been received?

@urandom

This comment has been minimized.

Copy link
Author

@urandom urandom commented Oct 15, 2018

The wayi think about it is, the buffer is a pointer to some sort of a container, let's say for now that it's a list. So there really is only one buffer. So naturally the sender would know how many items are currently in it, and if the oldest item needs to be evicted when a new one is added.

As for the second question, right now i can't think of a reason why the sender would need to do such tracking.

@deanveloper

This comment has been minimized.

Copy link

@deanveloper deanveloper commented Oct 15, 2018

I do not like the "sorta-kinda similar syntax to channels but not really" thing going on here.

We use chan string, not chan(string). If we're going to make these similar to channels, we should have cast string and not cast(string)

var recv <-cast(string) I do not like the look of this one bit... it really does not look like a type definition, as cast(string) looks like a function call, and <- looks like "wait for the result" rather than "read-only cast". This is clearer with var recv <-chan string though, as chan string does not look like a function call. So I guess it's the same issue as the previous paragraph.

Also, this is actually a pretty bad implementation for an event handler. If sending never blocks, then what about the following code?

func main() {
    clickBroadcaster := make(cast(struct{}))
    clickReceiver := (<-cast(struct{}))(clickBroadcaster)

    go listenForClicks(clickReceiver)

    // send 100 values over the broadcaster
    for i := 0; i < 100; i++ {
        clickBroadcaster<-struct{}{}
    }

    time.Sleep(1 * time.Second)
}

func listenForClicks(recv <-cast(int)) {
    for {
        fmt.Println("Received:", <-recv)
        
        runtime.Gosched() // simulate context switch
    }
}

What you will probably see outputted is something like:

Received: 0
Received: 53
Received: 90

Process exited.

We just missed 97% of the events that were fired! This is what happens when broadcasts don't block, and it's why channels are not designed this way

@creker

This comment has been minimized.

Copy link

@creker creker commented Oct 15, 2018

This is extremely complex. I had a hard time understanding any of this and had to do multiple reads of your example. Now imagine real production code. All this complex logic around capacity is gonna be multiplied but complexities of real code. Not to mention that I don't really see a value here. It kinda still looks like registration for callbacks but this may not suffer from circular references. Don't think it's worth it.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Oct 16, 2018

@urandom I don't see how we can discard any element from the sender's buffer until all the receivers have seen that element. Otherwise these channels are very unpredictable. So it seems to me that the sender has to track the number of receiver's that have seen an element.

@urandom

This comment has been minimized.

Copy link
Author

@urandom urandom commented Oct 16, 2018

I do not like the "sorta-kinda similar syntax to channels but not really" thing going on here.

We use chan string, not chan(string). If we're going to make these similar to channels, we should have cast string and not cast(string)

That's bikeshedding at this point in time. The syntax is the least important part.

var recv <-cast(string) I do not like the look of this one bit... it really does not look like a type definition, as cast(string) looks like a function call, and <- looks like "wait for the result" rather than "read-only cast". This is clearer with var recv <-chan string though, as chan string does not look like a function call. So I guess it's the same issue as the previous paragraph.

  1. You are going to havea really bad time in the future if the genetics draft is implemented.
  2. I always thought that this is a good way of explaining parametric polymorphism to beginners. They can think of a generic type as a function that returns a specific one. So that's also good :)

Also, this is actually a pretty bad implementation for an event handler. If sending never blocks, then what about the following code?

I completely disagree.

func main() {
    clickBroadcaster := make(cast(struct{}))
    clickReceiver := (<-cast(struct{}))(clickBroadcaster)

    go listenForClicks(clickReceiver)

    // send 100 values over the broadcaster
    for i := 0; i < 100; i++ {
        clickBroadcaster<-struct{}{}
    }

    time.Sleep(1 * time.Second)
}

func listenForClicks(recv <-cast(int)) {
    for {
        fmt.Println("Received:", <-recv)
        
        runtime.Gosched() // simulate context switch
    }
}

What you will probably see outputted is something like:

Received: 0
Received: 53
Received: 90

Process exited.

Yep, this is exactly what you want. The last thing you need is the sender (in this case your UI) to freeze because you have a misbehaving receiver that's doing too much work. Imagine if you moved the cursor and then had to waita while before the system started responding again, because an event listener was receiving every single move point and was processing them.

We just missed 97% of the events that were fired! This is what happens when broadcasts don't block, and it's why channels are not designed this way

Yes, and channels are rightly not used for this

@deanveloper

This comment has been minimized.

Copy link

@deanveloper deanveloper commented Oct 16, 2018

Yep, this is exactly what you want. The last thing you need is the sender (in this case your UI) to freeze because you have a misbehaving receiver that's doing too much work.

So if I broadcast two messages over a cast, it's intended behavior for receivers to receive the second message about 1% of the time? That doesn't seem like good form of communication between goroutines.

This seems a lot more like sharing memory to communicate, as opposed to Go's design which is more along the lines of communicating to share memory.

I personally think that this is a lot better suited to just be a library with Broadcast() and Receive() functions.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Oct 16, 2018

Lossy broadcast channels seem to me to be a non-starter. That is much too different from ordinary channels.

@bcmills

This comment has been minimized.

Copy link
Member

@bcmills bcmills commented Nov 12, 2018

Due to the blocking nature of channels, one has to manually orchestrate the multiplication of the payload to all interested parties, which is difficult and error prone.

See my talk on Rethinking Classical Concurrency Patterns. Broadcast patterns are covered in the section starting at slide 67, with some extended examples on 102–105.

The approaches discussed there require about one slide of code each (a bit more if you want to handle cancellation really robustly), and in exchange the code is very explicit about what happens when the receivers aren't ready — whether and when the sender blocks, who receives the payload information, etc.

Because there are so many possible buffering behaviors for broadcast events, I think it's important that the API prompt the caller to decide which behavior they intend. This proposal seems to favor one (lossy buffering) at the expense of the others: that makes it a good fit for a very specific use-case, but probably too specific to be codified in the language or standard library.

@urandom urandom closed this Nov 13, 2018
@golang golang locked and limited conversation to collaborators Nov 13, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
8 participants
You can’t perform that action at this time.