Are waiting sends to an unbuffer channel ordered?

[Peter Kleiweg]

I got some goroutines, all waiting to write something to the same unbuffered channel.

When some other goroutine starts reading from that channel, al values come in in the same order the goroutines tried to write to the channel. Is this by design? Is this something I can rely on?

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

[andrewc...@gmail.com]

I doubt that relying on that is a good idea, I think channels themselves are a form of synchronization which means the actual ordering of reads is conceptually undefined until after the read occurs.

(Though I'm not 100 percent sure.)

[Dave Cheney]

On Sunday, 15 June 2014 18:51:21 UTC+10, Peter Kleiweg wrote:

I got some goroutines, all waiting to write something to the same unbuffered channel.

When some other goroutine starts reading from that channel, al values come in in the same order the goroutines tried to write to the channel.

No, there is no order defined.

 

Is this by design? Is this something I can rely on?

No, you should not rely on this observation.

 

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

[egon]

Usually you can test these by doing a randomized sleep before each send and receive... e.g. http://play.golang.org/p/fTsXCEWG1I

This simulates the behavior of different routines arriving at the send different times.

+ egon

[Peter Kleiweg]

Op zondag 15 juni 2014 13:10:42 UTC+2 schreef egon:

In this example the sends are out of order.

My point was, if the sends are ordered, than the receives are also ordered.

[Dave Cheney]

For an unbuffered channel, the send and receive are synchronous -- both operations only happen when the sender and receiver arrive at their respective side of the channel. 

That doesn't imply any ordering about *which* sender or receive is chosen.  

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/PWt4r9b40bc/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[egon]

Yup, then it is in order... http://tip.golang.org/ref/spec#Channel_types

 

A single channel may be used in send statements, receive operations, and calls to the built-in functions cap and len by any number of goroutines without further synchronization. Channels act as first-in-first-out queues. For example, if one goroutine sends values on a channel and a second goroutine receives them, the values are received in the order sent.

+ egon

[Peter Kleiweg]

Op zondag 15 juni 2014 13:27:51 UTC+2 schreef egon:

I don't find the last sentence very clear. Does it behave like a FIFO too on unbuffered channels when more than one goroutine tries to send and there is no goroutine that receives yet? 

[egon]

In practice mostly yes, but there is no guarantee...

Let's say you have:

ch := make(chan int, 2)

go func(){

ch <- 1

}()

time.Sleep(1*time.Millisecond)

go func(){

ch <- 2

}()

fmt.Println(<-ch)

fmt.Println(<-ch)

You can expect that it will print out in order 1, 2... but it still isn't guaranteed... 

One could imagine a VM going to sleep just during the sleep... and the first function hasn't been scheduled yet... and when the VM resumes the second function gets scheduled before the first one... printing out in the order 2, 1... or more likely that for some reason the first goroutine gets scheduled after the second one.

The scheduling of goroutines is indeterministic, which means there also cannot be a guarantee for the order of sending happening inside the goroutine.

So "Channels act as first-in-first-out queues."... but the sending from different goroutines without proper synchronization is indeterministic.

Here http://tip.golang.org/ref/mem#tmp_6 it also says:

The kth receive on a channel with capacity C happens before the k+Cth send from that channel completes.

If the sends are ordered on an unbuffered channel then will be the receives... but using time to guarantee that ordering is flaky, but it might work well enough in practice.

+ egon

[Kevin Gillette]

On Sunday, June 15, 2014 5:27:51 AM UTC-6, egon wrote:

Yup, then it is in order... http://tip.golang.org/ref/spec#Channel_types

 

For example, if one goroutine sends values on a channel and a second goroutine receives them, the values are received in the order sent.

You may be interpreting that  sentence a bit too broadly. It states that one goroutine sends, and one goroutine receives. There would be no way for an channel to pass values out of order in the single-producer-single-consumer case; however, when there is more than one sender or more than one receiver, there's no attempt to specify/guarantee inter-goroutine ordering at all. Consider this scenario: goroutine's A and B has a send-only reference to a channel, and goroutine C has a receive-only reference to that same channel; if C is not receiving at the time, and A begins a blocking send, followed by B beginning a blocking send, it is undefined which value C will receive once it begins a receive operation. Temporal ordering is fairly dependable for buffered channels, but only when the channel is not full. That means that a concurrent algorithm using a buffered channel is only temporally ordered as a whole when all senders are using non-blocking sends (e.g. in a select statement with a default clause).

[Peter Kleiweg]

Op zondag 15 juni 2014 15:57:51 UTC+2 schreef Kevin Gillette:

But the sentence starts with "For example".  And the sentence before it says "Channels act as first-in-first-out queues."

What are other examples?

I can imagine go keeps track of goroutines blocked for the same reason, in a list, and whenever the channel has a read possible, it picks the first blocked goroutine from the list associated with this channel. 

I think this should be clarified in the specification. So I submitted an issue: https://code.google.com/p/go/issues/detail?id=8212

[Brendan Tracey]

Take this code http://play.golang.org/p/BOuFvNePwv, for example.

It is guaranteed that 1 is received before 2.

[Brendan Tracey]

Sorry, that was a bad example. This is a better example (channel now buffered). http://play.golang.org/p/JTbb5GmcUt

Here, the send of the constant 1 happens before the send of the constant 2. Since channels are FIFO, the receive is guaranteed in that order as well (as far as I understand).

Take the second example that egon gave

ch := make(chan int, 2)

go func(){

ch <- 1

}()

time.Sleep(1*time.Millisecond)

go func(){

ch <- 2

}()

fmt.Println(<-ch)

fmt.Println(<-ch)

Here, neither channel send happens before the other. The only way to specify 'order of operations' between two goroutines is by using synchronization (usually with channels). In the above example, there is no such synchronization, and so there is no guarantee. This would be true for a buffered or unbuffered channel.

You can, however, make the order explicit by communicating. In this code http://play.golang.org/p/cePvrOakqS   we use channels to synchonize the actions of the two goroutines. Here, the send of "2" on ch happens before the send of struct{}{} on ch2 in the second goroutine. In the first goroutine, the receive from ch2 happens before the send of "1" on ch. Thus, the send of "2" on ch happens before the send of "1" on ch, and the code is guaranteed to print 2 before 1.

Note that in the above case, the FIFO guarantee is actually important. Both sends to the buffered channel could occur before the first read. We can, in fact, force this to happen. http://play.golang.org/p/-eeBzVAZpP . Now, the send on ch3 from goroutine 1 happens before the first receive from ch in the main goroutine. We are guaranteed to have both items in the buffered channel at the same time. Without the FIFO guarantee, the items could be printed in either order. However, we have explicitly synchronized the order in which items get sent to the buffered channel, and so we have guaranteed their print order.

Hope this helps

[Peter Kleiweg]

Op zondag 15 juni 2014 20:27:06 UTC+2 schreef Brendan Tracey:

ch := make(chan int, 2)

go func(){

ch <- 1

}()

time.Sleep(1*time.Millisecond)

go func(){

ch <- 2

}()

fmt.Println(<-ch)

fmt.Println(<-ch)

Here, neither channel send happens before the other.

Yes, it does, because the channel is buffered, and there is time between the start of the goroutines.

 

The only way to specify 'order of operations' between two goroutines is by using synchronization (usually with channels). In the above example, there is no such synchronization, and so there is no guarantee. This would be true for a buffered or unbuffered channel. 

People keep saying that about unbuffered channels, order is undefined, no guarantees. And still, the result is ordered. Every time. I haven't seen an example yet where the order is not preserved. 

So, the question remains: why is the order preserved? Is it by design or a result of how channels are implemented? The specs are not sufficiently specific about this.

I looks like communicating over an unbuffered channel isn't one synchronisation between two goroutines, but two synchronisations, one of a sending goroutine with the channel action, and the other of a receiving goroutine with the same channel action. 

[andrewc...@gmail.com]

Just because it looks like its working every time doesn't mean it will work when there is high cpu load, or a different number for GOMAXPROCS. Despite the sleep in the following example, I would argue that the read order is undefined.

The read/send order is undefined in the absence of other synchronization because the send read order IS the synchronization..

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

Regardless of what the implementation does today in the event the CPU physically reaches one send before the other, In the future the runtime may just decide to randomly select any one of the sending/recieving goroutines to be first.

[andrewc...@gmail.com]

On Sunday, June 15, 2014 8:51:21 PM UTC+12, Peter Kleiweg wrote:

The sleep in your original example is not a form of synchronization that is reliable. The order of output in that code is still entirely dependant on cpu load, number of goroutines in the system , GOMAXPROCS and the operating systems thread scheduler. Its possible a sudden system lag causes the first send to be delayed longer than the sleep, which means the second send could arrive throwing off your order.

This would manifest itself as random hard to detect failures in your code years down the line when the number of cores in your processor is higher, or when you code is put through high load.

[Peter Kleiweg]

Op zondag 15 juni 2014 22:55:33 UTC+2 schreef andrewc...@gmail.com:

On Sunday, June 15, 2014 8:51:21 PM UTC+12, Peter Kleiweg wrote:

I got some goroutines, all waiting to write something to the same unbuffered channel.

When some other goroutine starts reading from that channel, al values come in in the same order the goroutines tried to write to the channel. Is this by design? Is this something I can rely on?

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

The sleep in your original example is not a form of synchronization that is reliable. The order of output in that code is still entirely dependant on cpu load, number of goroutines in the system , GOMAXPROCS and the operating systems thread scheduler. Its possible a sudden system lag causes the first send to be delayed longer than the sleep, which means the second send could arrive throwing off your order.

Then the attempts to send would be out of order. That is a different thing. Could an attempt to send on a channel succeed, before another attempt to send on the same channel, that is waiting longer?

The documentation for the select statements states clearly what will happen if multiple case-clauses can run at the same time: One is picked at random; not the first, like in a switch statement. I would like the same clarity on the issue I am talking about.

The documentation says nothing about what happens on an unbuffered receive with multiple senders waiting. There is only the statement that channels act like FIFO, without stating the conditions. Just one example. No counter-example. Is the attempt to send part of the FIFO event context?

I would like the specifications to be clear about what will happen, either of these:

    (1) the longest waiting sender is picked first

    (2) one of the senders is picked at random (this is not the case)

    (3) which sender is picked is unspecified (depends on the implementation, depends on situation)

[andrewc...@gmail.com]

Perhaps a sentence saying the order is undefined should be added.

Could you give me an example of code where two sends can be guaranteed to have been started in a specified order? Also with the guarantee that the read has started only after both sends have started. Also you can't use sleep because that is not a reliable guarantee.

I'd like to see a real example of this, I'm not even sure it's possible given the semantics of channels and locks.

[Peter Kleiweg]

Op maandag 16 juni 2014 01:02:08 UTC+2 schreef andrewc...@gmail.com:

Perhaps a sentence saying the order is undefined should be added.

Could you give me an example of code where two sends can be guaranteed to have been started in a specified order? Also with the guarantee that the read has started only after both sends have started. Also you can't use sleep because that is not a reliable guarantee.

I'd like to see a real example of this, I'm not even sure it's possible given the semantics of channels and locks.

What if I increase the value for time.Sleep in the example to one hour? 

I have an application where times between the possibilities to receive can vary from minutes to weeks. Attempts to send are rare, but can happen any time. I don't want an attempt that is waiting for days to be bumped by an attempt that is waiting only minutes, adding another week to the waiting time of the older attempt. When there are only seconds in between, I don't care about the order.

Yes, I know I can fix this by using a large enough buffered channel. And so I did. (Though, what is large enough?) So it is more a theoretical issue, but I think the specification should be clear.

[Dan Kortschak]

If you want queue behaviour use a buffered chan (with a return send to
indicate receipt of the send if that is important). There is no way you
can expect ordered send when the ordering is only specified by the
channel itself. At the moment you are relying on the scheduler to queue
your sends. Since the scheduler is not even mentioned in the spec,
that's pretty optimistic.

[andrewc...@gmail.com]

"What if I increase the value for time.Sleep in the example to one hour?"

What if you run your code on an incredibly slow computer which takes 1 hour to execute the statements in between? Then the behaviour is undefined again.

What if time.Sleep uses the system time which gets adjusted while the code is running.

Conceptually it is not a guarantee.. when dealing with synchronization physical time is not used to verify correctness. Its more to do with execution ticks which can be arbitrarily long or short, each tick results in the code moving to the next synchronization point.

I know this is beyond your use case which can be solved by wrapping the channel in a data structure, but I'm trying to explain why the documentation is like that.

[Jesse McNelis]

On Mon, Jun 16, 2014 at 8:15 AM, Peter Kleiweg <pkle...@xs4all.nl> wrote:
> Then the attempts to send would be out of order. That is a different thing.
> Could an attempt to send on a channel succeed, before another attempt to
> send on the same channel, that is waiting longer?

There is not such thing as "waiting longer". There is only 'happens before'.
If you create a goroutine that blocks waiting to send on a buffered
channel happens before(using additional syncronisation) another
goroutine blocks waiting to send on that channel. The order with which
the sends proceed still isn't defined.

> The documentation says nothing about what happens on an unbuffered receive
> with multiple senders waiting. There is only the statement that channels act
> like FIFO, without stating the conditions. Just one example. No
> counter-example. Is the attempt to send part of the FIFO event context?

It's a FIFO, but the 'first in' isn't defined without synchronisation
and no order is defined for multiple senders blocking.

> I would like the specifications to be clear about what will happen, either
> of these:
>
> (1) the longest waiting sender is picked first
> (2) one of the senders is picked at random (this is not the case)
> (3) which sender is picked is unspecified (depends on the
> implementation, depends on situation)

It's 'unspecified' because it's not specified anywhere. It's also not
actually useful.
The synchronisation you'd have to do to get the goroutines to reach
the send operation in a specific order would require you to wait for
each send operation to complete in that order too.

[Jesse McNelis]

On Mon, Jun 16, 2014 at 9:30 AM, Peter Kleiweg <pkle...@xs4all.nl> wrote:
> What if I increase the value for time.Sleep in the example to one hour?

time.Sleep() is a minimum amount of time to wait. The wake up order is
unspecified.

[Brendan Tracey]

On Sunday, June 15, 2014 12:24:43 PM UTC-7, Peter Kleiweg wrote:

Op zondag 15 juni 2014 20:27:06 UTC+2 schreef Brendan Tracey:

ch := make(chan int, 2)

go func(){

ch <- 1

}()

time.Sleep(1*time.Millisecond)

go func(){

ch <- 2

}()

fmt.Println(<-ch)

fmt.Println(<-ch)

Here, neither channel send happens before the other.

Yes, it does, because the channel is buffered, and there is time between the start of the goroutines.

Peter, have you read the Go memory model? http://golang.org/ref/mem . The term "happens before" has a particular meaning.

The key points are

0) "To specify the requirements of reads and writes, we define happens before, a partial order on the execution of memory operations in a Go program. If event e₁ happens before event e₂, then we say that e₂ happens after e₁. Also, if e₁ does not happen before e₂ and does not happen after e₂, then we say that e₁ and e₂ happen concurrently. "
1) "Within a single goroutine, the happens-before order is the order expressed by the program."
      a) Though the compiler is allowed to reorder statements
2)" A send on a channel happens before the corresponding receive from that channel completes."

What does this mean? In the above code, we get the following guarantee for the main goroutine:
A) The first goroutine launch happens before the sleep, the sleep happens  before the second launch, and the second launch happens before the first channel read
B) We know that in the launched goroutines, the send on the channel happens before the read from the channel. In particular, this guarantees that the main goroutine cannot complete until  both sends have happened (using the channel send relationships

However, what don't we have? Let's think about the two channel sends in the goroutines

go func(){

ch <- 1

}()

time.Sleep(1*time.Millisecond)

go func(){

ch <- 2

}()

Well, we know the goroutines themselves are launched in order. But look at the two sends themselves. Bullet point 1) only counts for code in the same goroutine. The two channel sends are in different goroutines so 1) does not apply. Bullet point 2) shows that the send on the channel happens before the read form the channel in the main goroutine, but there is no synchronization happening between the two sending goroutines. The line "ch <- 1" does not happen before or after "ch <- 2", and thus the two happen concurrently. Because they happen concurrently, there are no guarantees about execution order.

In this particular case, the go runtime is smart enough to do something interesting during the call to sleep. However, an implementation that obeys the memory model could
1) Launch the first goroutine
2) Sleep for 1 milisecond
3) Launch the second goroutine
4) Encounter the channel read. The main goroutine cannot proceed until it can read from the channel.
5) There now exist two other goroutines that can be run (the one than sends 1 and the one that sends 2). Choose the second
6) Reach the channel send from the second, and send it on the buffered channel
7) Run the first goroutine and send that value on the buffered channel
8) In the main goroutine, receive and print the first value
9) Receive and print the second value

This would be perfectly valid. There was no synchronization to guarantee "1" gets sent before 2

 

The only way to specify 'order of operations' between two goroutines is by using synchronization (usually with channels). In the above example, there is no such synchronization, and so there is no guarantee. This would be true for a buffered or unbuffered channel. 

People keep saying that about unbuffered channels, order is undefined, no guarantees. And still, the result is ordered. Every time. I haven't seen an example yet where the order is not preserved. 

Have you tried running with multiple processors? On my computer this code does not print 1 through n in order
http://play.golang.org/p/0mUQFm7nWl

 

So, the question remains: why is the order preserved? Is it by design or a result of how channels are implemented? The specs are not sufficiently specific about this.

The spec is specific about this. The sends happen concurrently and no order is guaranteed. The observed behavior has something to do with the gc runtime implementation.
 

I looks like communicating over an unbuffered channel isn't one synchronisation between two goroutines, but two synchronisations, one of a sending goroutine with the channel action, and the other of a receiving goroutine with the same channel action. 

Well, it's synchronizing between two goroutines in the the send happens before the read. 

[Peter Kleiweg]

My point isn't at all about ensuring one goroutine attempts a send before another goroutine does.

I am only talking about the succeeding of one send before the other in the same order the attempts were started.

These are two completely different things. The example I gave was just to demonstrate the receiving end.

Op maandag 16 juni 2014 06:52:20 UTC+2 schreef Brendan Tracey:

[Jan Mercl]

On Mon, Jun 16, 2014 at 1:30 AM, Peter Kleiweg <pkle...@xs4all.nl> wrote:

Let's simplify thigs to two sends from two (only) goroutines - to the
same channel. If the two send statements execute concurrently then
they have no order (no HB relation). If the two sends have
deterministic order (there is a HB relation) then they are not
executing concurrently. The two modes are mutually exclusive.

It follows that any apparent order of the values received from
concurrently executing (sending) goroutines is at most an artifact of
the implementation and nothing that can be relied upon.

-j

[egon]

On Monday, 16 June 2014 11:33:15 UTC+3, Peter Kleiweg wrote:

My point isn't at all about ensuring one goroutine attempts a send before another goroutine does.

I think the question you want to ask is this: http://play.golang.org/p/IgwB5VkMq4

Would it be guaranteed that one of the senders doesn't wait infinitely?

The answer would be yes, as long as the scheduler does fair scheduling... which is based on best effort. Currently there must be a place where the scheduler can do a goroutine switch.

As an example... after you remove the sleeps... http://play.golang.org/p/Pxjs2Y6w6C the first sender does twice the work... but only because of the scheduling... the channel still works as a FIFO.

+ egon

[Peter Kleiweg]

Op maandag 16 juni 2014 10:40:31 UTC+2 schreef Jan Mercl:

Go isn't a quantum computer. Things happen at a certain time, even if you don't know at what time. There is an order of things. Even if two goroutines try to send on a channel at exactly the same time, those attempts are not handled at the same time. 

Change the channel to a buffered channel. Once an item is buffered and no items are received from the channel, the item stays put on its position in te buffer. Any new items arriving are appended at the end, not inserted before older items. See: http://play.golang.org/p/0sc6oB5azz

Non-buffered channels act in the same way. My simple question from the start was: Is this a result of the implementation, or is it part of the design?

[Jan Mercl]

On Mon, Jun 16, 2014 at 11:04 AM, Peter Kleiweg <pkle...@xs4all.nl> wrote:
> Go isn't a quantum computer. Things happen at a certain time, even if you
> don't know at what time. There is an order of things. Even if two goroutines
> try to send on a channel at exactly the same time, those attempts are not
> handled at the same time.

Technically, it can (losely said) happen in the same time on a multi
core CPU - if the channel would be implemented without locks (which is
possible to certain extent).
The gc implementation does uses locks so right, one of the sends
happens before the other. That's not in conflict with the previously
stated fact that the order is not deterministic and not guaranteed to
be repeatable. And if there's no guarantee of the order at the input
(sends) it makes no sense to talk about the order of the output
(receives).

> Change the channel to a buffered channel. Once an item is buffered and no
> items are received from the channel, the item stays put on its position in
> te buffer. Any new items arriving are appended at the end, not inserted
> before older items. See: http://play.golang.org/p/0sc6oB5azz
>
> Non-buffered channels act in the same way. My simple question from the start
> was: Is this a result of the implementation, or is it part of the design?

I believe "It follows that any apparent order of the values received from

concurrently executing (sending) goroutines is at most an artifact of

the implementation and nothing that can be relied upon." answered that question.

Let's try another perspective. It might be the case that you're
thinking in the terms of _when_ goroutines get blocked. But that
information may or may not play a role in a (fair or nor completely
fair) goroutine scheduler. And the specs prescribe no particular
scheduling policy. So once again the conclusion is - there's no
reliably predictable order in concurrently executing send statements
to the same channel, even when you may observe it for a particular
implementation. It's a bit comparable to the earlier implementation of
maps. For a small number of elements there was an apparent order while
ranging the map. However, it was always specified to be random and
later the implementation improve on this - and possibly broke some
programs (which were actually already broken by relying on the
unspecified order).

-j

[Jesse McNelis]

On Mon, Jun 16, 2014 at 7:04 PM, Peter Kleiweg <pkle...@xs4all.nl> wrote:
> Non-buffered channels act in the same way. My simple question from the start
> was: Is this a result of the implementation, or is it part of the design?

I don't understand why this matters to you, it's unobservable.
You can't use it for anything.
It's not part of the design, it's an implementation detail that you
can't actually observe from the perspective of the programmer.

[andrewc...@gmail.com]

The simple answer has already been explained, you cant rely on this even if it seems to be ordered by a buffer.

You seem to fail to understand the technical reasons behind the answer. 

[Peter Kleiweg]

Op maandag 16 juni 2014 11:55:47 UTC+2 schreef andrewc...@gmail.com:

The simple answer has already been explained, you cant rely on this even if it seems to be ordered by a buffer.

You seem to fail to understand the technical reasons behind the answer. 

Whether the observed behaviour is by design or not is not a technical matter. If it is a matter of design, it should be in the specification.

The specification on the release node is clear: http://golang.org/ref/spec#Channel_types

It is the specification on tip that is confusing: http://tip.golang.org/ref/spec#Channel_types

[Peter Kleiweg]

Op maandag 16 juni 2014 12:15:02 UTC+2 schreef Peter Kleiweg:

The specification on the release node is clear: http://golang.org/ref/spec#Channel_types

It is the specification on tip that is confusing: http://tip.golang.org/ref/spec#Channel_types

I see there is confusion in the  specification on the release node too, but there it is under "Send statements". On tip, the confusion is moved to "Channel types".

[Jesse McNelis]

There is no confusion in the spec.
If the spec did specify some order to the resolution of send
operations on a buffered channel this wouldn't make any difference to
any Go program. You can't write a Go program that would have different
behaviour given this addition to the spec.

[Peter Kleiweg]

Op maandag 16 juni 2014 13:19:51 UTC+2 schreef Jesse McNelis:

I was talking about unbuffered channels!

The spec IS confusing because it says that channels act like first-in-first-out, without further explanation, except a single example. Is it so hard to grasp that that is NOT an unambigous specification! What are the preconditions for a channel to act as a FIFO. Spell them out. 

All further speculation and theorizing around the issue is completely irrelevant. The specification needs to be fixed!

And that is all I have to say about it.

Have a nice day.

[Brendan Tracey]

I’m not sure what more to tell you. Saying that “it’s confusing” is not enough information at this time.

The spec guarantees that channels works as queues. The first item that is actually sent on the channel is the first item out of the channel. However, if two sends have no HB relationship, the order in which the sends occur is undeterminable, and thus order in which items are received from the channel is indeterminable.

Go isn't a quantum computer. Things happen at a certain time, even if you don't know at what time. There is an order of things. Even if two goroutines try to send on a channel at exactly the same time, those attempts are not handled at the same time.

You seem to be confusing two conflicting notions. One is the physical order in which the program got executed, and the other is the Happens Before relationships that establish what order the program must be executed. 

Go isn't a quantum computer. Things happen at a certain time, even if you don't know at what time. There is an order of things. Even if two goroutines try to send on a channel at exactly the same time, those attempts are not handled at the same time.

This is true.

See:  http://play.golang.org/p/0sc6oB5azz 

This code does not demonstrate that property. There is no HB relationships between any of the sends. The sends happen concurrently. It is luck that they come out in order. More specifically, it is a property of how the current runtime implementation works, but this behavior is neither guaranteed by the spec and memory model, nor is it guaranteed by the gc runtime implementation. 

Have you tried running my earlier program which demonstrated the sends coming in out of order?

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/PWt4r9b40bc/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Peter Kleiweg]

OK, one more then...

Op maandag 16 juni 2014 17:19:30 UTC+2 schreef Brendan Tracey:

See:  http://play.golang.org/p/0sc6oB5azz 

This code does not demonstrate that property. There is no HB relationships between any of the sends. The sends happen concurrently.

They don't. Look closely at the code.

[Henrik Johansson]

Why do they not happen concurrently?

Slight change:

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

--
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.

[chris dollin]

 Each send is in its own goroutine. I don't see as you can get them more

concurrent than that.

Chris

--
Chris "allusive" Dollin

[Brendan Tracey]

You really should read the memory model again. The sleep does nothing to change the guaranteed HB order of the channel.

The answer to your question is that 

a) Yes, channels are always FIFO. 

b)  You must establish a HB relationship (as per the memory model) in order to guarantee that one send happens before another send

as a corollary, if there is no happens before relationship, you cannot know the order of the sends. The channel is still FIFO, but you cannot guarantee which is first in. 

A reasonable implementation of the runtime will probably have the behavior you’ve been showing. A good implementation would rather do work than sit and wait. However, an implementation could do something else and still be a valid Go implementation.

[Ian Lance Taylor]

On Mon, Jun 16, 2014 at 8:18 AM, Peter Kleiweg <pkle...@xs4all.nl> wrote:
>
> The spec IS confusing because it says that channels act like
> first-in-first-out, without further explanation, except a single example. Is
> it so hard to grasp that that is NOT an unambigous specification! What are
> the preconditions for a channel to act as a FIFO. Spell them out.

You are phrasing your question about channels. But as far as I can
tell your question is not about channels.

Channels are FIFO. That is a simple, unambiguous statement. It is
guaranteed to be implemented by every implementation.

I think that what you are really asking about is the goroutine
scheduler. You are asking whether, when there are two different
goroutines writing to the same channel, and there is no happens-before
relationship between the two goroutines, there are any guarantees
about the order in which they write to the channel. That is not a
question about channels. It's a question about the goroutine
scheduler.

The answer to that question is that there are no guarantees. The
goroutine scheduler is not described in the language spec. Different
implementations may act differently.

At this point I don't think it would be appropriate to say anything
about the goroutine scheduler in the language spec. Anything that we
could say would be so anodyne as to mean nothing. It would not help
anybody when writing any actual Go program, nor would it help anybody
when writing any actual Go implementation. So there seems little
point to saying anything.

Ian

[Ian Lance Taylor]

On Mon, Jun 16, 2014 at 10:16 AM, Peter Kleiweg <pkle...@xs4all.nl> wrote:
> Ian Lance Taylor schreef op de 16e dag van de zomermaand van het jaar 2014:

>
>> You are phrasing your question about channels. But as far as I can
>> tell your question is not about channels.
>

> Actually, it is. How is the "first-in" part of first-in-first-out
> defined? Is a blocked send already "in"?

No, it's not.

That is a scheduling question. When there are multiple goroutines
waiting to send on an unbuffered channel, and a different goroutine
executes a receive operation on that channel, which of the sending
goroutines gets to execute? The language does not specify.

It's quite difficult to specify scheduler behaviour in the absence of
a happens-before relationship. I think the best we could do would be
to say something like "the scheduler does its best to not starve any
goroutine." I don't see how that would be a helpful statement.

Ian

[Kevin Gillette]

On Monday, June 16, 2014 2:33:15 AM UTC-6, Peter Kleiweg wrote:

I am only talking about the succeeding of one send before the other in the same order the attempts were started.

Absolutely no guarantee whatsoever in the spec. Even individual implementations are unlikely to be able to guarantee this -- if you've found the behavior wholly consistent, your testing may just be too limited. Increase GOMAXPROCS to a high value, tweak kernel scheduling parameters, preferrably with different priorities per thread to simulate heavily loaded conditions, and then maybe you'll revise your conclusions about expectable behavior. If you need send-order to be synchronized, and you want it to be non-racy, you need to synchronize it yourself.

[Peter Kleiweg]

Op zondag 15 juni 2014 10:51:21 UTC+2 schreef Peter Kleiweg:

I got some goroutines, all waiting to write something to the same unbuffered channel.

When some other goroutine starts reading from that channel, al values come in in the same order the goroutines tried to write to the channel. Is this by design? Is this something I can rely on?

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

I found a counter-example with a buffered channel:

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

All positive sends are waiting before the first receive, but they don't appear in order.

Still searching for a counter-example with an unbufered channel.

[Dan Kortschak]

The channels do, the scheduling for entry into the channels do not.

On 17/06/2014, at 12:48 AM, "Peter Kleiweg" <pkle...@xs4all.nl> wrote:

> channels act like first-in-first-out

[Jesse McNelis]

On Tue, Jun 17, 2014 at 4:24 AM, Peter Kleiweg <pkle...@xs4all.nl> wrote:
> http://play.golang.org/p/AJJ8LM0a_k
>
> All positive sends are waiting before the first receive, but they don't
> appear in order.

That program doesn't define an order for the send operations.
They all happen 'concurrently'

You would need to define a 'happens before relationship' for the
operations to proceed if you want them to proceed in that order.

[Peter Kleiweg]

Ian Lance Taylor schreef op de 16e dag van de zomermaand van het jaar 2014:

> You are phrasing your question about channels. But as far as I can
> tell your question is not about channels.

Actually, it is. How is the "first-in" part of first-in-first-out
defined? Is a blocked send already "in"?

--
Peter Kleiweg

[Dan Kortschak]

On Mon, 2014-06-16 at 19:16 +0200, Peter Kleiweg wrote:
> Actually, it is. How is the "first-in" part of first-in-first-out
> defined?

Once something has been sent, it is in the queue.

> Is a blocked send already "in"?

No.

[Dmitry Vyukov]

On Sun, Jun 15, 2014 at 3:19 PM, Peter Kleiweg <pkle...@xs4all.nl> wrote:
> Op zondag 15 juni 2014 13:10:42 UTC+2 schreef egon:

>
>>
>>
>> On Sunday, 15 June 2014 11:51:21 UTC+3, Peter Kleiweg wrote:
>>>
>>> I got some goroutines, all waiting to write something to the same
>>> unbuffered channel.
>>> When some other goroutine starts reading from that channel, al values
>>> come in in the same order the goroutines tried to write to the channel. Is
>>> this by design? Is this something I can rely on?
>>>
>>> http://play.golang.org/p/f2yvnNUspz
>>
>>

>> Usually you can test these by doing a randomized sleep before each send
>> and receive... e.g. http://play.golang.org/p/fTsXCEWG1I
>> This simulates the behavior of different routines arriving at the send
>> different times.
>
>
> In this example the sends are out of order.
> My point was, if the sends are ordered, than the receives are also ordered.


IN your original post, you've said that there are several goroutines
blocked on send.
These are conflicting statements. If there are several gorotuines are
blocked on send, then sends are unordered. So what is your case?

[roger peppe]

I've sometimes thought that there's a similarity
relation between:

c := make(chan int)
go func() { c <- 1 }()
time.Sleep(someTime)
go func() { c <- 2 }()
time.Sleep(someTime)
<-c
<-c

and

c1 := make(chan int)
c2 := make(chan int)
go func() { c1 <- 1 }()
time.Sleep(someTime)
go func() { c2 <- 2 }()
time.Sleep(someTime)
select {
case <-c1:
case <-c2:
}
select {
case <-c1:
case <-c2:
}

In the first case, assuming someTime is large enough,
the current implementation will always deliver 1 and 2
in that order.

In the second case, the implementation takes care to randomise
the order.

As multiplexing onto a single channel is a common idiom
for working around variable-number-of-cases select, I
wonder if it wouldn't be better if the first case was
explicitly random too.


On 17 June 2014 02:41, 'Dmitry Vyukov' via golang-nuts

> --
> 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.

[Dmitry Vyukov]

It's probably possible for sync channels, but not for async channels.
This will make it an inconsistent feature.

Also fairness is a good thing.

[Dan Kortschak]

Just to clarify. Do you mean "is alway observed to" by "will always"?

[Bakul Shah]

On Tue, 17 Jun 2014 18:29:00 BST roger peppe <rogp...@gmail.com> wrote:
> I've sometimes thought that there's a similarity
> relation between:
>
> c := make(chan int)
> go func() { c <- 1 }()
> time.Sleep(someTime)
> go func() { c <- 2 }()
> time.Sleep(someTime)
> <-c
> <-c

c yielding 1 and then 2 makes sense as a channel is a FIFO.
Unless there are zillions of other threads it is very likely
the first thread will get to c<-1 before the second one for a
large someTime.

>
> and
>
> c1 := make(chan int)
> c2 := make(chan int)
> go func() { c1 <- 1 }()
> time.Sleep(someTime)
> go func() { c2 <- 2 }()
> time.Sleep(someTime)
> select {
> case <-c1:
> case <-c2:
> }
> select {
> case <-c1:
> case <-c2:
> }

If both channels are ready, randomization makes sense
in select.

>
> In the first case, assuming someTime is large enough,
> the current implementation will always deliver 1 and 2
> in that order.
>
> In the second case, the implementation takes care to randomise
> the order.
>
> As multiplexing onto a single channel is a common idiom
> for working around variable-number-of-cases select, I
> wonder if it wouldn't be better if the first case was
> explicitly random too.

I don't see how you can do this without breaking FIFO
semantics.

It would make more sense to provide something like poll() that
takes a vector of <channel, func> pairs and not multiplex on a
single channel for such a variable number of cases select.

Of course, I may be completely missing your point!

[Jan Mercl]

On Tue, Jun 17, 2014 at 8:54 PM, Bakul Shah <ba...@bitblocks.com> wrote:
> I don't see how you can do this without breaking FIFO
> semantics.

FIFO == first sent value is the first value received, only. Order, or
random order of scheduling of the concurrent send statements doesn't
break that FIFO invariant. Dmitry's note is about randomness of
scheduling the two blocked sends, not about the FIFO property. IOW,
the times when the sending goroutines get blocked do not necessarily
prescribe any scheduling order/priority when an unblocking event (read
from c) occurs and it's completely legal if the "later" one gets
(randomly) scheduled first.

-j