Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Chinese Whispers in Rust

thornydev.blogspot.com

Post reply on HN
Print view View original

31–40 of 47 posts

Re: Chinese Whispers in Rust

#31

Post by Aloisius »

I'm not sure I understand concurrency for concurrency's sake. It seems a non-concurrent version of this would run at least two orders of magnitude faster than either implementation.

Maybe I'm just set in my old ways, but I tend to equate adding concurrency with adding complexity (mostly to debugging and code legibility) and really only do it when I'm CPU-bound. Even then, it has to be a pretty darn good reason.

I understand there are some benefits of CSP programming, but simple message passing where every single thread wakes up during the call? Half the time you're looking at network or memory bandwidth issues which a single thread could easily saturate.

Now maybe if each of these threads were say, an intelligent agent doing hitting the CPU hard, but this? This two microbenchmarks run for an exceptionally short period of time merged together: one is the creation of threads and one is message passing between them.

Re: Chinese Whispers in Rust

#32

Post by pcwalton »

redbad wrote: post #30
strcat wrote: post #25

Earlier quoted context omitted.

Rust tasks have the same large fixed-size stack as OS threads. A fine-grained concurrency model like a task graph would be build on top of them.

> Rust tasks have the same large fixed-size stack as OS > threads. A fine-grained concurrency model like a task > graph would be build on top of them. In the absence of other context (I don't really know much about Rust) I would then argue that Rust tasks miss the point of CSP.

I think that's unfair. There's no absolute threshold that defines "the point of CSP"; you might equally say Go's goroutines miss the point of CSP because they're slower than the equivalent for loop.

Besides, the only substantive difference between Go's implementation and Rust's implementation is that Go uses segmented stacks, while Rust does not. That is because segmented or relocating stacks are in opposition to Rust's design goals of no GC, fast calling into C, and predictable performance.

Re: Chinese Whispers in Rust

#33

Post by derefr »

pcwalton wrote: post #9

Copying my message on Reddit here: I profiled this and found that the vast majority of the time was spent allocating stack segments. So the basic problem is that this benchmark is simply tuned for segmented stacks. An implementation that does not use segmented stacks will do worse on this benchmark. We've rejected segmented stacks because they don't perform well in the real world (and hurt many other benchmarks, incl…

> The fastest version of this program would be println((N + 1).to_str()).

Chinese Whispers basically represents a DSP system: each agent is "plugged into" the next one in the chain, and a signal has to propagate through the chain, being modified by each agent in an arbitrary fashion. The fact that they all just +1 the signal is irrelevant; each one could output whatever it likes. The only assumption is that the work each agent performs is O(1).

Re: Chinese Whispers in Rust

#34

Post by pcwalton »

samth wrote: post #29
pcwalton wrote: post #26

Earlier quoted context omitted.

> I don't think the second claim is true at all, though. Lightweight threads have been extremely successful in Haskell, Erlang, etc, and not just on microbenchmarks. They're mostly successful in languages that GC/heap-allocate all stack frames (paying the costs that come with it). Rust uses the machine stack so the benefits come with some very significant drawbacks, most notably unpredictability of performance that c…

I think Simon & Simon are making exactly the point I am: lightweight threads are significantly faster than any other threading system, and work in real system, not just microbenchmarks. Rust has made some other design choices that it seems make it harder to have some nice things that most modern functional language runtimes have -- I'm sure there are good reasons for all of those choices. But I don't think your claim…

I think I should have been more precise: I meant that in Rust small stacks mostly help microbenchmarks. Obviously if you're willing to pay the costs of heap allocating stack frames one by one (or have a relocating stack implementation and are willing to pay the costs associated with that) then small stacks can help a lot.

Re: Chinese Whispers in Rust

#35

Post by pcwalton »

derefr wrote: post #33
pcwalton wrote: post #9

Copying my message on Reddit here: I profiled this and found that the vast majority of the time was spent allocating stack segments. So the basic problem is that this benchmark is simply tuned for segmented stacks. An implementation that does not use segmented stacks will do worse on this benchmark. We've rejected segmented stacks because they don't perform well in the real world (and hurt many other benchmarks, incl…

> The fastest version of this program would be println((N + 1).to_str()). Chinese Whispers basically represents a DSP system: each agent is "plugged into" the next one in the chain, and a signal has to propagate through the chain, being modified by each agent in an arbitrary fashion. The fact that they all just +1 the signal is irrelevant; each one could output whatever it likes. The only assumption is that the work…

In that case the fastest way to do it in Rust would be to use an iterator.

Re: Chinese Whispers in Rust

#36

Post by derefr »

pcwalton wrote: post #35
derefr wrote: post #33

Earlier quoted context omitted.

> The fastest version of this program would be println((N + 1).to_str()). Chinese Whispers basically represents a DSP system: each agent is "plugged into" the next one in the chain, and a signal has to propagate through the chain, being modified by each agent in an arbitrary fashion. The fact that they all just +1 the signal is irrelevant; each one could output whatever it likes. The only assumption is that the work…

In that case the fastest way to do it in Rust would be to use an iterator.

Oh, sorry, forgot to include: 1. Only the agent that outputs a signal knows where it should be propagated[1]. (The decision of propagation is part of the each agent's internal state.) and 2. Each agent may be running on a different system than the next, and may propagate the signal using a network call instead of an internal message-pass-and-yield.

Chinese Whispers is inherently a test of message passing in a distributed system. An iterator-based design (e.g. a "controller" agent that pulls in the state after each call and sends it to the next agent, forcing a hub-and-spoke series of RPC calls) will

• tend to introduce highly-degraded performance, since you've doubled the number of messages being sent;

• force a synchronous wait in the controller (it can't do anything until it's talked to everyone, whereas with the asynchronous propagation, all it has to do is "kick it off");

• possibly just not work at all--if, for example, an agent propagates into a private network that only accepts messages from that agent, not from your controller.

---

[1] The Chinese Whispers problem includes a set-up phase, where the controller instantiates the agents and wires them to one-another. This is just for the sake of convenience, though; the controller should not be assumed to have knowledge of how the agents are interconnected once it has the ring established.

Re: Chinese Whispers in Rust

#37

Post by noodly »

pcwalton wrote: post #9

Copying my message on Reddit here: I profiled this and found that the vast majority of the time was spent allocating stack segments. So the basic problem is that this benchmark is simply tuned for segmented stacks. An implementation that does not use segmented stacks will do worse on this benchmark. We've rejected segmented stacks because they don't perform well in the real world (and hurt many other benchmarks, incl…

Do you know if ghc uses segmented stacks ?

I'm wondering, because I implemented chinese whispers in haskell and it seems to be on par with go.

Re: Chinese Whispers in Rust

#38

Post by pcwalton »

derefr wrote: post #36
pcwalton wrote: post #35

Earlier quoted context omitted.

In that case the fastest way to do it in Rust would be to use an iterator.

Oh, sorry, forgot to include: 1. Only the agent that outputs a signal knows where it should be propagated[1]. (The decision of propagation is part of the each agent's internal state.) and 2. Each agent may be running on a different system than the next, and may propagate the signal using a network call instead of an internal message-pass-and-yield. Chinese Whispers is inherently a test of message passing in a distrib…

This particular benchmark is especially poor if that's what it's trying to test then, because this benchmark is completely gated on task/goroutine spawning performance and message passing barely even shows up in the profile in both Rust and Go.

Re: Chinese Whispers in Rust

#39

Post by nickik »

pcwalton wrote: post #9

Copying my message on Reddit here: I profiled this and found that the vast majority of the time was spent allocating stack segments. So the basic problem is that this benchmark is simply tuned for segmented stacks. An implementation that does not use segmented stacks will do worse on this benchmark. We've rejected segmented stacks because they don't perform well in the real world (and hurt many other benchmarks, incl…

Since you might be reading this, why does rust do this channel/port thing instead of just channels? Is that written down somewhere? Does it have to do with the type system or the ownership sematics?

Re: Chinese Whispers in Rust

#40

Post by nickik »

kinofcain wrote: post #28
pcwalton wrote: post #10

Earlier quoted context omitted.

The solution is "don't spawn a huge number of tasks in a tight loop". Rust tasks are optimized for maximum performance once you spin them up, at the cost of some overhead once you spawn them. That was a deliberate choice, because not having segmented stacks makes many much more important things far faster, such as calling into C and performing tight sequential computations without thrashing on stack boundaries or usi…

Thanks for the reply. My comment apparently came off as trite, apologies. One of the enlightening things for me about CSP and Erlang, in particular, was using channels and messages and a bunch of lightweight tasks for flow control and state management. Reading the reddit comments, and even your reply here, seems to indicate that that type of programming isn't a good fit for rust, and that perfectly reasonable trade o…

It seams to me that Rust is still good at CSP, one can still start up many threads (logical) but they are not as cheap.

This might just mean that it is more senceable to span a smaller number and communicate with them via port.

Its still CSP, its still usful, but its not exactly like go. My guess is that if you start to do more computation in each thread the benchmarks are gone change.

The Go style is only cheap if the stack does not grow.

Post reply on HN