What is the memory order when select on multiple channels that one is closing and the other is receiving?

[changkun]

Hi, golang nuts,

Let's think about this snippet: https://play.golang.org/p/3cNGho3gWTG

In the code snippet, a ticker is activating and another that that is closing, it seems that they can happen concurrently and result 

in two different outcomes: either ticker case being executed first or the other way around.

It is because of the pseudo-randomization of the select statement.

Intuitively, the close statement should happens-before select statement that starts choosing which case 

should be executing, and select a closed channel with the highest priority to prevent another receive case being executed once more.

My questions are:

Does the Go team or anybody else think of this memory order before? What was the decision that didn't make it?

If not, is it worth to be defined within the language? There are no language changes and only affects the runtime implementation.

[robert engels]

You need to code it knowing that either can occur in any order.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/6992b605-ff10-4659-8016-dd96066d4588%40googlegroups.com.

[changkun]

Hi Robert,

The provided code snipped on my machine can result in different outputs, which basically shows that it could occur in any order.

The randomization mechanism in select statement made the verification hard. Logically, my argument is rigorous

On Sunday, September 8, 2019 at 5:31:49 PM UTC+2, robert engels wrote:

You need to code it knowing that either can occur in any order.

On Sep 8, 2019, at 10:14 AM, changkun <euryu...@gmail.com> wrote:

Hi, golang nuts,

Let's think about this snippet: https://play.golang.org/p/3cNGho3gWTG

In the code snippet, a ticker is activating and another that that is closing, it seems that they can happen concurrently and result 

in two different outcomes: either ticker case being executed first or the other way around.

It is because of the pseudo-randomization of the select statement.

Intuitively, the close statement should happens-before select statement that starts choosing which case 

should be executing, and select a closed channel with the highest priority to prevent another receive case being executed once more.

My questions are:

Does the Go team or anybody else think of this memory order before? What was the decision that didn't make it?

If not, is it worth to be defined within the language? There are no language changes and only affects the runtime implementation.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golan...@googlegroups.com.

[Kurtis Rader]

On Sun, Sep 8, 2019 at 8:40 AM changkun <euryu...@gmail.com> wrote:

The provided code snipped on my machine can result in different outputs, which basically shows that it could occur in any order.

Yes

 

The randomization mechanism in select statement made the verification hard. Logically, my argument is rigorous

No, it isn't. You need to learn a lot more about concurrency and race conditions.

--

Kurtis Rader

Caretaker of the exceptional canines Junior and Hank

[changkun]

Hi Kurtis,

I am aware that you are talking about the happen-before algorithm which is basically the vector clock.

However, this discussion aims for the discussion regarding this proposal:

"the close statement should happens-before select statement that starts choosing which case 

should be executing, and select a closed channel with the highest priority to prevent another receive case being executed once more."

We are not entering write any code before we confirm that it is worthy.

[Robert Engels]

It’s hard to respond. I have done a lot of concurrent programming and haven’t heard the term “vector clock” so I am not sure what you are referring to.  You can write a logical “clock cycle” by sampling both and choosing the higher priority event - but overall performance is going to suffer greatly. 

There is not such thing as “priority” across multiple resources that are independent - by definition the order is undefined as nothing is instantaneous in practice. Happens before is going to be per channel - but in practice the memory flush is going to occur in either case (because of the backing locks) but it’s not guaranteed. 

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/d1c412e6-c775-49a6-8d1d-c417497dc9be%40googlegroups.com.

[burak serdar]

On Sun, Sep 8, 2019 at 3:16 PM Robert Engels <ren...@ix.netcom.com> wrote:
>
> It’s hard to respond. I have done a lot of concurrent programming and haven’t heard the term “vector clock” so I am not sure what you

Lamport's timestamps, vector clocks,etc:
https://en.wikipedia.org/wiki/Vector_clock

> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/297D58C7-04D4-4F6C-A6F2-62131724B071%40ix.netcom.com.

[Robert Engels]

Heh, didn’t know that and independently came up with it in 30 secs - that has to be worth something ? (Although mine uses sampling of all event sources)

[Axel Wagner]

On Sun, Sep 8, 2019, 17:14 changkun <euryu...@gmail.com> wrote:

Intuitively, the close statement should happens-before select statement that starts choosing which case 

should be executing, and select a closed channel with the highest priority to prevent another receive case being executed once more.

I don't really understand.ehat you mean by "intuitively" here. First: The close *does* happen-before the case clause of the select for the closed channel, as per the memory model. Second: If you actually establish an ordering "close happens-before the select statement, which happens-before the ticker firing", you should actually get the result you want, in that only the close-case is deterministically chosen, AIUI. So we are only talking about the case you tried to enforce, where you *don't* have that ordering - that is, where the close happens concurrently with the ticker firing and both happen concurrently to the select starting to execute.

Now, ISTM that the simplest intuitive interpretation of what "event A and B happen concurrently" (defined abstractly as "are not ordered in the happens-before partial order) is that the order that A and B happen in real time in is unclear and could happen either way olin practice. And under that intuitive understanding, I don't know how you conclude that the select should prioritize either or not execute the ticker case at all. After all - you can never know whether the ticker *has actually fired* at the concrete real point in time the select executed.

Note, by the way, that the fact that you observe either result doesn't actually say anything about the pseudo-randomness or lack thereof of the select statement: You can't, from the output of the program, distinguish between "both cases where ready to proceed and select flipped a coin coming up close" from "only close was ready to proceed, because select executed in between the closing/firing" (and the same for the timer firing). The pseudo-randomness of select is irrelevant for your case, it's the fact that these events are concurrent, both as specified and IMO as intuitively obvious.

My questions are:

Does the Go team or anybody else think of this memory order before? What was the decision that didn't make it?

If not, is it worth to be defined within the language? There are no language changes and only affects the runtime implementation.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/6992b605-ff10-4659-8016-dd96066d4588%40googlegroups.com.

[changkun]

Hi Alex,

Thank you for giving such great clarification. You thought is more sophisticated than me. 

First: The close *does* happen-before the case clause of the select for the closed channel, as per the memory model.

Indeed, no question here.

 

Second: If you actually establish an ordering "close happens-before the select statement, which happens-before the ticker firing", you should actually get the result you want, in that only the close-case is deterministically chosen, AIUI. So we are only talking about the case you tried to enforce, where you *don't* have that ordering - that is, where the close happens concurrently with the ticker firing and both happen concurrently to the select starting to execute.

Here comes with more interesting points. My "intuitive" comes from this scenario: 

I have an unbuffered channel "closedCh" that indicates if a network connection is closed, 

a timer handles for heartbeat detection and polls some data, if a connection is closed, then returns an error.

At some point, I close the "closedCh" for the termination of previous for-select loop.

I initially thought that the heartbeat detection case will not be executed and 

closedCh will safely return and terminates the loop.

However, there are some "false negative" results returned by the loop, 

because select still can select the heartbeat case if the heartbeat and closedCh arrive concurrently.

See the following code for TLDR:

// goroutine1
closedCh := make(chan struct{})

// do some preparation
...

for {
    select {
    case <- ticker.C:
        // it is possible that this case can still being executed
        // one more time if closedCh arrives.

        // heartbeat detection, data processing..
        ...

    case <- closedCh
        return
}



// goroutine2
close(closedCh)

To fix the issue I have encountered, I have to use an atomic value for double check

if the channel is closed inside the ticker case:

// "global" data
closedCh := make(chan struct{})
closed := uint32(0)

// goroutine1

// do some preparation
...

for {
    select {
    case <- ticker.C:
        // now it is ok
        if atomic.LoadUint32(&closed) == 1 {
            return
        }

        // heartbeat detection, data processing..
        ...

    case <- closedCh
        return
}



// goroutine2
if !atomic.CompareAndSwapUint32(&closed, 0, 1) {
    return ErrClosed
}
close(closedCh)

which does not like an ideal solution (not sure if there is a better way?), because for close a ticker, 

I need an atomic value and an unbuffered channel that appear in three different places.

 

Now, ISTM that the simplest intuitive interpretation of what "event A and B happen concurrently" (defined abstractly as "are not ordered in the happens-before partial order) is that the order that A and B happen in real time in is unclear and could happen either way olin practice. And under that intuitive understanding, I don't know how you conclude that the select should prioritize either or not execute the ticker case at all. After all - you can never know whether the ticker *has actually fired* at the concrete real point in time the select executed.

Sorry for lack of problem statement, see above

 

Note, by the way, that the fact that you observe either result doesn't actually say anything about the pseudo-randomness or lack thereof of the select statement: You can't, from the output of the program, distinguish between "both cases where ready to proceed and select flipped a coin coming up close" from "only close was ready to proceed, because select executed in between the closing/firing" (and the same for the timer firing). The pseudo-randomness of select is irrelevant for your case, it's the fact that these events are concurrent, both as specified and IMO as intuitively obvious.

You are right, it is not a suitable example for the question I have. I feel sorry about it. I hope you didn't get trouble for reading it. 

In fact, I am curious: if select work with a random selection, is it possible that a case will never be executed?

How can select statement provide fairness similar to the FIFO-semantic channel (https://github.com/golang/go/issues/11506)?

 

[changkun]

Sincerely sorry for the typo of your name :( Axel

[Axel Wagner]

Hey,

On Mon, Sep 9, 2019 at 9:55 AM changkun <euryu...@gmail.com> wrote:

Here comes with more interesting points. My "intuitive" comes from this scenario: 

I have an unbuffered channel "closedCh" that indicates if a network connection is closed, a timer handles for heartbeat detection and polls some data, if a connection is closed, then returns an error.

At some point, I close the "closedCh" for the termination of previous for-select loop.

I initially thought that the heartbeat detection case will not be executed and 

closedCh will safely return and terminates the loop.

However, there are some "false negative" results returned by the loop, 

because select still can select the heartbeat case if the heartbeat and closedCh arrive concurrently.

That's fair and I have to admit that I ran into similar situations once or twice in the past without having a super good solution. FWIW, I think one hindrance is that network interactions are usually inherently racey. You can't really know or guarantee when and in what order packages arrive. So it might be a good idea to think about a way to prevent this from causing issues anyway. For example, I would probably just try writing/reading the heartbeat and if an error occurs while doing that, follow that with a check if the connection was already closed. e.g. something like

case <- ticker.C:

    err := heartbeat()

    if err == nil {

        continue

    }

    select {

    case <-closedCh:

        // connection was closed properly, error is expected

        return nil

    default:

        return err

    }

}

 

this means that you *might* sometimes send an extra heartbeat message, but that's why I'm mentioning that you can't fully prevent that in practice anyway, so the receiver needs to be able to cope.

Note in particular, that your code remains racey. No matter *how* you implement the check for closed-nes (including your atomic variable), the close could always happen right after your check and before you do the heartbeat processing. It's an inherently asynchronous problem :)

Best,

Axel

PS: Don't worry about the name, it happens *all* the time and I'm no longer bothered :)

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/7736fea9-b4c0-4b1b-8b0e-9bc3b0e3bd7b%40googlegroups.com.