5 ms·

Coincidentally, I used Rust for a little board game solver this week and have been delighted by its performance and typechecker feedback! My Scala v1 was was v

Coincidentally, I used Rust for a little board game solver this week and have been delighted by its performance and typechecker feedback! My Scala v1 was was very concise but took ~3 seconds to simulate a whole game. The naive Rust rewrite did it in 0.7 seconds and my current version churns them out at 0.015s each!! http://github.com/iamdanfox/qwirkler http://github.com/iamdanfox/qwirkler if you're curious.. This language is really fun!

kibwen 12y ago
Performance is an area where Rust still has a lot of low-hanging fruit to pick, so I'm happy to hear that you managed to make your version fast. Did you have to make any design compromises to that end? We're very interested in optimizing the typical use cases.
- iamdanfox 12y ago
  I have currently got some bit-swizzling [1] going on to fit the concept of a Piece into u8. (one of 6 colours and one of 6 shapes). I'd like to turn this back into a nice enum if I can! Introducing laziness by writing an iterator was actually one of the biggest single improvements (I couldn't figure out the syntax for a while, but lifetimes worked much better than I was expecting)! [1]: https://github.com/iamdanfox/qwirkler/blob/master/src/piece.rs https://github.com/iamdanfox/qwirkler/blob/master/src/piece....
  - kibwen 12y ago
    Hm, an enum like `enum Color { R, O, Y, G, B, I, V }` is represented by a u8 at runtime (see for yourself here: http://is.gd/YkUY0l http://is.gd/YkUY0l), which means that you're only saving a single byte in your `Piece` struct by doing that manual optimization. What was the magnitude of the speedup that you saw?
  - Gankro 12y ago
    There have been a few proposals for advanced bit-packing stuff, but most of it has been postponed as back-compat for later. That said, by default enum/struct layout is undefined, so it's possible the compiler could be taught to optimize your usecase correctly. For instance Option<&T> is the same size as &T because &T is strictly non-zero, and we can therefore use 0 for None.
  - kaoD 12y ago
    Check kibwen's post (my sibling). It's [dead] for some reason but it answers your question. I'll reproduce it here: > Hm, an enum like `enum Color { R, O, Y, G, B, I, V }` is represented by a u8 at runtime (see for yourself here: http://is.gd/YkUY0l http://is.gd/YkUY0l), which means that you're only saving a single byte in your `Piece` struct by doing that manual optimization. What was the magnitude of the speedup that you saw?
  - nightpool 12y ago
    FYI both kaoD and Kibwen's post seem to be dead because they included a link to a URL shortener (seems a little melodramatic on HNs part...) so I'll reproduce it here w/o the URL shortlink and see if that helps >Hm, an enum like `enum Color { R, O, Y, G, B, I, V }` is represented by a u8 at runtime (see for yourself here[1]), which means that you're only saving a single byte in your `Piece` struct by doing that manual optimization. What was the magnitude of the speedup that you saw? [1]: http://play.rust-lang.org/?code=%23%5Ballow(dead_code)%5D%0Aenum%20Color%20%7B%20R%2C%20O%2C%20Y%2C%20G%2C%20B%2C%20I%2C%20V%20%7D%0A%0Afn%20main()%20%7B%0A%20%20%20%20println!(%22%7B%7D%22%2C%20std%3A%3Amem%3A%3Asize_of%3A%3A%3CColor%3E())%3B%20%20%2F%2F%20size%20in%20bytes%0A%7D http://play.rust-lang.org/?code=%23%5Ballow(dead_code)%5D%0A...
    - iamdanfox 12y ago
      Ah that's good to know, looks like I should switch it back! The manual u8 stuff was pretty marginal. (It was also before I discovered the `PartialEq` and `Copy` traits, so please forgive my Rust inexperience!)
  - deleted 12y ago
    [deleted]
mike_hearn 12y ago
Could you post the Scala version as well, for comparison?
- iamdanfox 12y ago
  Sure: https://github.com/iamdanfox/QwirkleSolver https://github.com/iamdanfox/QwirkleSolver The Rust version has had some algorithm improvements to reach 0.015s, but it was conceptually identical when it was solving in 0.7s.
  - thom 12y ago
    Obviously this is mostly for kicks, but there's a lesson in the 45x speedup improving the algorithm vs the 4x improvement changing technologies. :)
  - mike_hearn 12y ago
    Taking a quick look, it seems the program starts up, runs once and then quits. I'm wondering if the JIT actually compiled all of the app. Being JVM based Scala is very profile guided, so normally for benchmarks you want to repeat the same operation in a loop until elapsed time stabilises. That said, if your use case involves running once for a few seconds and then quitting, ahead of time compilers like rustc will always beat a profile guided JITC. So this may be an unfair point.

kibwen 12y ago

Performance is an area where Rust still has a lot of low-hanging fruit to pick, so I'm happy to hear that you managed to make your version fast. Did you have to make any design compromises to that end? We're very interested in optimizing the typical use cases.

iamdanfox 12y ago
I have currently got some bit-swizzling [1] going on to fit the concept of a Piece into u8. (one of 6 colours and one of 6 shapes). I'd like to turn this back into a nice enum if I can! Introducing laziness by writing an iterator was actually one of the biggest single improvements (I couldn't figure out the syntax for a while, but lifetimes worked much better than I was expecting)! [1]: https://github.com/iamdanfox/qwirkler/blob/master/src/piece.rs https://github.com/iamdanfox/qwirkler/blob/master/src/piece....
- kibwen 12y ago
  Hm, an enum like `enum Color { R, O, Y, G, B, I, V }` is represented by a u8 at runtime (see for yourself here: http://is.gd/YkUY0l http://is.gd/YkUY0l), which means that you're only saving a single byte in your `Piece` struct by doing that manual optimization. What was the magnitude of the speedup that you saw?
- Gankro 12y ago
  There have been a few proposals for advanced bit-packing stuff, but most of it has been postponed as back-compat for later. That said, by default enum/struct layout is undefined, so it's possible the compiler could be taught to optimize your usecase correctly. For instance Option<&T> is the same size as &T because &T is strictly non-zero, and we can therefore use 0 for None.
- kaoD 12y ago
  Check kibwen's post (my sibling). It's [dead] for some reason but it answers your question. I'll reproduce it here: > Hm, an enum like `enum Color { R, O, Y, G, B, I, V }` is represented by a u8 at runtime (see for yourself here: http://is.gd/YkUY0l http://is.gd/YkUY0l), which means that you're only saving a single byte in your `Piece` struct by doing that manual optimization. What was the magnitude of the speedup that you saw?
- nightpool 12y ago
  FYI both kaoD and Kibwen's post seem to be dead because they included a link to a URL shortener (seems a little melodramatic on HNs part...) so I'll reproduce it here w/o the URL shortlink and see if that helps >Hm, an enum like `enum Color { R, O, Y, G, B, I, V }` is represented by a u8 at runtime (see for yourself here[1]), which means that you're only saving a single byte in your `Piece` struct by doing that manual optimization. What was the magnitude of the speedup that you saw? [1]: http://play.rust-lang.org/?code=%23%5Ballow(dead_code)%5D%0Aenum%20Color%20%7B%20R%2C%20O%2C%20Y%2C%20G%2C%20B%2C%20I%2C%20V%20%7D%0A%0Afn%20main()%20%7B%0A%20%20%20%20println!(%22%7B%7D%22%2C%20std%3A%3Amem%3A%3Asize_of%3A%3A%3CColor%3E())%3B%20%20%2F%2F%20size%20in%20bytes%0A%7D http://play.rust-lang.org/?code=%23%5Ballow(dead_code)%5D%0A...
  - iamdanfox 12y ago
    Ah that's good to know, looks like I should switch it back! The manual u8 stuff was pretty marginal. (It was also before I discovered the `PartialEq` and `Copy` traits, so please forgive my Rust inexperience!)
- deleted 12y ago
  [deleted]

mike_hearn 12y ago

Could you post the Scala version as well, for comparison?

iamdanfox 12y ago
Sure: https://github.com/iamdanfox/QwirkleSolver https://github.com/iamdanfox/QwirkleSolver The Rust version has had some algorithm improvements to reach 0.015s, but it was conceptually identical when it was solving in 0.7s.
- thom 12y ago
  Obviously this is mostly for kicks, but there's a lesson in the 45x speedup improving the algorithm vs the 4x improvement changing technologies. :)
- mike_hearn 12y ago
  Taking a quick look, it seems the program starts up, runs once and then quits. I'm wondering if the JIT actually compiled all of the app. Being JVM based Scala is very profile guided, so normally for benchmarks you want to repeat the same operation in a loop until elapsed time stabilises. That said, if your use case involves running once for a few seconds and then quitting, ahead of time compilers like rustc will always beat a profile guided JITC. So this may be an unfair point.