Chinese Whispers in Rust

http://thornydev.blogspot.com/2014/01/chinese-whispers-in-rust.html

by arizabu • 13 years ago

41 43 13 years ago

thornydev.blogspot.com

kinofcain3• 13 years ago

There was talk recently that rust had made the choice of m:n tasks and real threads configurable. Is it still using m:n tasks by default? Would be interesting to see a comparison between the two for something like this (which should of course heavily favor lightweight task model)

pcwalton8• 13 years ago

I don't expect much if any of a performance difference. Both M:N and 1:1 threading use non-segmented stacks in Rust, and that is the source of the performance issues.

levosmetalo• 13 years ago

After compiling this with the latest rust built from git, I get only the "Illegal instruction" as an error message when I try to run this example.

strcat2• 13 years ago

You're running out-of-memory, and hitting the `llvm.trap` intrinsic call. It causes an illegal instruction to invoke a core dump. It doesn't currently print an error message.

kibwen2• 13 years ago

See the discussion on the Rust subreddit for a more thorough discussion of the caveats in the Rust implementation:

http://www.reddit.com/r/rust/comments/1vnrp8/chinese_whisper...

The most salient quote from Daniel Micay (strncat):

"It doesn't demonstate a pattern you would use in Rust. Rust tasks aren't a substitute for generators/iterators and they're not around as a control flow feature."

kinofcain3• 13 years ago

Sadly it seems the "solution" there is "don't do CSP in Rust".

masklinn3• 13 years ago

Not quite. It's "don't do retarded things using CSP in Rust".

pcwalton8• 13 years ago

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 using a garbage collector to move stacks around and rewrite all the pointers. Rust is about making costs explicit: when every function call could turn into a huge malloc(), you lose a lot of predictability over performance (and Go found this out too from what I gather).

Calling into C is a big one: we concluded it was basically impossible to make Rust calling into C as cheap as C calling into C in a segmented stack implementation. In practical usage, we found that the ability to call into C cheaply was much more important than the benefits of small stacks, which mostly help microbenchmarks like this at the expense of real-world code.

pcwalton8• 13 years ago

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, including most of the shootout), but they do make this one particular program fast.

The debate on M:N versus 1:1 threading seems irrelevant to this benchmark. In 1:1 mode we will also allocate a lot of stack space.

Channel performance is mostly irrelevant to this benchmark.

It's hard to say what the more "idiomatic" Rust version of this program would be, because this program doesn't do anything. The fastest version of this program would be println((N + 1).to_str()). :) An implementation based on libdispatch/TBB-style blocks might be faster, but it would look quite a bit different from this benchmark.

kibwen2• 13 years ago

  > including most of the shootout

I feel like this comment makes it sound like we care more about the shootout benchmarks than we actually do.

jzelinskie• 13 years ago

IIRC I've read something that said Go was going to move away from segmented stacks in future versions. I have no idea about the progress.

derefr2• 13 years ago

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

pcwalton8• 13 years ago

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

noodly• 13 years ago

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.

coolsunglasses• 13 years ago

Yeah, but they're recent (segmented stacks).

How stacks work in something like STG are very different from a language like Rust or C.

nickik5• 13 years ago

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?

tinco• 13 years ago

Why do people always insist on posting sub-second performance benchmarks in blogs? Is it really so hard to put a for(var i = 0;i < 1000;i++) {} around the code?

I'm not talking about making the benchmarks actually being reliable, but make them at least pass the most basic of inspections.

Your computer could be doing anything in the few seconds that your application ran. Is your blog really that worthless to you that you couldn't wait 5 minutes to establish that what you're saying holds water?

edit: okey, I need to sleep a bit better, I'm coming off bitter again :P

msie2• 13 years ago

I must really be sheltered because that is only the third time I've ever heard the term "Chinese Whispers" used for a game that I remembered as "Broken telephone".

mistercow• 13 years ago

I'm guessing that you're American, and that the author is not. My understanding is that in most of the English-speaking world, the game is called "Chinese whispers" (although that name is falling out of favor because racism), while in America, it is usually called "telephone" or some variation on that.

msie2• 13 years ago

I'm Canadian so same thing, basically. The term is used by Rob Pike in the referred presentation and he's Canadian, but he's somewhat older than I am. I first noticed the term used by an Australian coworker about a year ago and I also heard it on a Stephen Fry talk show - so yes to your theory.

hacknat• 13 years ago

Rename your post, it's going to distract attention from whatever it is you are trying to communicate. I'd just as soon not read it until you call it "telephone" or something more PC.

edit

Also, you'll get flame detected soon enough once this turns into a debate about racism.

Aloisius• 13 years ago

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.

Chinese Whispers in Rust

Related Stories