7 ms·

Chinese Whispers in Rust

41 points by arizabu 13y ago

deleted 13y ago
[deleted]
kinofcain 13y 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)
- pcwalton 13y 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 13y 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.
- strcat 13y 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.
kibwen 13y 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_whispers_in_rust_and_go/ 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."
- kinofcain 13y ago
  Sadly it seems the "solution" there is "don't do CSP in Rust".
  - masklinn 13y ago
    Not quite. It's "don't do retarded things using CSP in Rust".
    - ZoFreX 13y ago
      Oh, come on. Not only is your comment needlessly insulting but it's completely unconstructive. What types of CSP things should you do in Rust, then? Which should you not? Why is this code not a demonstration of a slowness in Rust but a 'bad idea'? How would you implement it in a more idiomatic manner in Rust?
      - coldtea 13y ago
        >Oh, come on. Not only is your comment needlessly insulting but it's completely unconstructive. I find his comment pretty spot on. If anything it was the "don't do CSP in Rust" comment that was unconstructive and passive aggresively insulting. Instead of understanding what he read and the constrains it shows, the commenter preffered to just piss on the language. As for the example, it was obviously "retarted" or rather, contrived. I mean, heck, it's "chinese whispers" with 10000 channels, what more do you need to see that this is not a serious way of solving actual problems with CSP? It's a bloody microbenchmark, and those are rarely representative of anything. >What types of CSP things should you do in Rust, then? The types of CSP things that people use threads and processes for. E.g getting lots of computations going on in parallel, not incrementing tens a single int in each of thousands of "computations". CSP and channels are meant for getting real (cpu intensive) work done. You don't just use threads (or greenthreads) "because concurrency". That some Go programmers like to use channels as a control mechanism, doesn't mean CSP was meant for that kind of abuse. That's like using Exceptions for control flow to me. Isn't it obvious that even in Go the times to complete this are horrible (just an order of magnitude less horrible because of different design trade-offs), and that doing the same job of 10,000 incrementings properly would complete in 1/1000 the time?
pcwalton 13y 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.
- kibwen 13y 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 13y 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.
- derefr 13y 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).
  - pcwalton 13y ago
    In that case the fastest way to do it in Rust would be to use an iterator.
tinco 13y 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
msie 13y 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 13y 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.
  - msie 13y 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 13y 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 13y 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.

41 points by arizabu 13y ago

deleted 13y ago

[deleted]

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)

pcwalton 13y 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 13y 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.

strcat 13y 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.

kibwen 13y 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_whispers_in_rust_and_go/ 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."

kinofcain 13y ago
Sadly it seems the "solution" there is "don't do CSP in Rust".
- masklinn 13y ago
  Not quite. It's "don't do retarded things using CSP in Rust".
  - ZoFreX 13y ago
    Oh, come on. Not only is your comment needlessly insulting but it's completely unconstructive. What types of CSP things should you do in Rust, then? Which should you not? Why is this code not a demonstration of a slowness in Rust but a 'bad idea'? How would you implement it in a more idiomatic manner in Rust?
    - coldtea 13y ago
      >Oh, come on. Not only is your comment needlessly insulting but it's completely unconstructive. I find his comment pretty spot on. If anything it was the "don't do CSP in Rust" comment that was unconstructive and passive aggresively insulting. Instead of understanding what he read and the constrains it shows, the commenter preffered to just piss on the language. As for the example, it was obviously "retarted" or rather, contrived. I mean, heck, it's "chinese whispers" with 10000 channels, what more do you need to see that this is not a serious way of solving actual problems with CSP? It's a bloody microbenchmark, and those are rarely representative of anything. >What types of CSP things should you do in Rust, then? The types of CSP things that people use threads and processes for. E.g getting lots of computations going on in parallel, not incrementing tens a single int in each of thousands of "computations". CSP and channels are meant for getting real (cpu intensive) work done. You don't just use threads (or greenthreads) "because concurrency". That some Go programmers like to use channels as a control mechanism, doesn't mean CSP was meant for that kind of abuse. That's like using Exceptions for control flow to me. Isn't it obvious that even in Go the times to complete this are horrible (just an order of magnitude less horrible because of different design trade-offs), and that doing the same job of 10,000 incrementings properly would complete in 1/1000 the time?

pcwalton 13y 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.

kibwen 13y 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 13y 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.
derefr 13y 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).
- pcwalton 13y ago
  In that case the fastest way to do it in Rust would be to use an iterator.

tinco 13y 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

msie 13y 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 13y 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.
- msie 13y 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 13y 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 13y 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.