Say that I have two threads and two crossbeam channels between them. If I do
tx1.send(a_lot_of_data);
tx2.send(a_little_bit_of_data);
in one thread, and
let foo = rx2.recv();
let bar = rx1.try_recv();
in the other, might the try_recv() return Err(TryRecvError::Empty)?
I could use a blocking read or loop on the try_recv, but I'm curious about the guarantees.
If you're using try_recv, then there's especially no guarantee that you'll receive the item in this case. You can use the rust rate loom to prove that try_recv's output is non-deterministic.
On a second note: if sequentially consistent (SeqCst) ordering is used internally, then try_recv would return a value deterministically since the order is guaranteed at a global level. However, if Relaxed ordering is used, then try_recv would be non-deterministic. It depends on crossbeam's implementation
I'm just wondering which it is. I started looking at the source code, but it's beyond my abilities.
Yes, that behavior is guaranteed. It is considered pretty important, and one of the other channel implementations entirely removed their try_recv method because that channel did not guarantee it, as seen here.
That's good to know. I assume no message was sent on channel 1 if it is empty when I do the try_recv. I'd have to rethink my algorithm if this ordering wasn't guaranteed.
The issue you pointed to appears to me to something different, namely "that previously sent messages may not be available immediately". In other words, a semaphore set when the message was sent would not guarantee that a try_recv would succeed after checking the semaphore.
In my use case, I don't care if the message on a channel doesn't appear right away as long as the order between channels is preserved. Of course, the root cause for both is likely to be that it can take a long time for a lot of data to show up on a channel.
Whether you are synchronizing using a semaphore or a different channel doesn't really matter for this guarantee.
Thank you. That's just what I needed to know.
I'm feeling a bit dumb here.
It's not clear to me why one would expect any ordering guarantees between messages over two channels between two threads. I mean, if these were TCP/IP connections between servers running over the net one would not expect such a correlation.
It's not clear to me why, if one wants ordering between messages one would use two channels when it can be done with one.
Clearly I am missing a finer point here.
You are right, it is not obvious.
Basically, it's a question of whether the channel behaves like a Relaxed memory ordering, or like a Release/Acquire ordering, where these ordering names come from the Ordering enum used with atomic integers. With Relaxed, you can't rely on it, but with Release/Acquire, you can.
I can make an analogy to another form of "message passing" where you absolutely would expect analogous behavior. Consider this:
shared_mem = new_value;
mutex.unlock();
in one thread, and
mutex.lock();
let new_value = shared_mem;
in the other. Here, I call the lock/unlock methods in the style you would see in C or C++, to make the analogy more clear. In the above case, you would absolutely expect that, if the second thread starts to try to acquire the lock while the first thread has the lock, the second thread will see whatever value the first thread wrote to the shared memory.
Here the "message" is that the lock is unlocked, and the blocking .lock() call corresponds to the blocking .recv() call in the original post.
Of course, this requires knowing that crossbeam actually corresponds to Release/Acquire orderings. See e.g. this comment from conversations regarding the issue I linked earlier with some other channel.
Hmm.. thing is I have always thought of channels as a way to implement totally independent but communicating processes. Abstracting away the fact they might run on the same CPU/core or live in the same memory space or even be on the same machine.
Probably comes from my understanding of the Transputer chip and the Occam language over networks of hundreds of devices back in the day.
In that light all this talk of ordering introduces coupling between processes that should not be there.
Generally in-memory channels come with an assumption that a message is transmitted "instantly", so the argument is just that if A happens before B, and B happens before C, then it really should be the case that A happens before C.
If the crossbeam code is synchronous, a call to send will return only after the data has been put into the channel and the flag that data is ready was set . With the right memory model a subsequent try_read is guaranteed to succeed. On the other hand, the code could be asynchronous and return early or the memory model might be such that the flag is set, but the reading thread sees the old value. In that case, try_read will report the channel is empty.
Hans Bohm wrote a nice article (which I can't find right now) explaining why issues with memory ordering means you can't do synchronization purely in a C++ library. You need detailed information about when a store becomes visible to other threads or processes sharing that memory. Knowing about that work made me realize I didn't understand what would happen in the example I showed.
You can learn more about memory models in a tech report by the inventor(?) of release/acquire semantics, Kourosh Gharachorloo. I actually sat in on his thesis defense on this topic. It took me years to figure out what he was talking about.
I see what you mean.
It's just that from my past experience, going back to Occam, which is based on the ideas of "Communicating Sequential Processes" by Tony Hoare, there is no notion that "channels" are in memory or between the same machines even. The whole point of "channels" was to abstract over that. As such "channels" do not include notions like ordering.
The Transputer supported "channels" in hardware. The code one wrote that may consist of many processes communicating over channels on a single chip could be run as many processes communicating over "channels" between hundreds of chips. The idea being that those processes are totally isolated, apart from the channels between them, and can be moved around as required.
Correct. The transputer and Occam language presented an actor-like model with no shared memory at the language level.
I believe that Occam running on a conventional computer did its message passing through shared memory. That was easier in those days because machines did not have the complicated memory hierarchies they do today. You got a sequentially consistent memory model for free, which meant you could rely on every read seeing the result of the most resent write no matter who did the write.
I'm very sure it did.
The point is though that when one writes an Occam task one would not assume that it is in the same memory space, or even the same machine. To do so breaks the abstraction of communicating sequential processes.
Exactly right. Rust is not an actor-like system, though, so you (well, I anyway) have to deal with the messiness of the memory model.
In case of the std channels it's easy as they're defined as fifo queues:
Multi-producer, single-consumer FIFO queue communication primitives
and
All data sent on the
Senderwill become available on theReceiverin the same order as it was sent
Crossbeam-channel doesn't document any ordering (at least I couldn't see any) so not sure what is an implementation detail and what is guaranteed.
I would expect nothing less from such a channel.
However our OP is asking a different question. About the ordering of messages sent over two channels from one thread to another.
I would not, at first guess, assume there should be any such ordering guarantee between two channels.
It's still not clear why one would want to do that. Why not send all messages down a single channel and enjoy that FIFO ordering?
The kind of ordering we are talking about when it comes to several channels is a different and much weaker guarantee than the FIFO order of individual messages in a single channel. The guarantee is:
send on the channel may not be reordered to happen after the send.recv on the channel may not be reordered to happen before the recv.The above is enough to guarantee that @alanhkarp's program behaves as he wants it to.
I was using two channels to avoid exposing the internal state of the receiver to a particular component of the sender. In trying to explain that to @ZiCog, I realized that there was a way to do it with one channel. I might never have thought of that solution without @ZiCog's prodding. Looks like I'm going to have a negative code day.
I'm still glad I asked the question, since the answer isn't obvious. @alice's last explanation puts it in terms of what's visible when, i.e., the memory model, which gives me a deeper understanding of what's going on.