7 ms·
Performance of Rust and Dart in Sudoku Solving
- codygman 14y agoUpdate the Go example to use 1.1 :D
- idupree 14y agoY'know, That GCC is six years old.[1] Go, Rust, Dart and V8 didn't even exist when it was released. Maybe update that if anything? [1] http://gcc.gnu.org/releases.html http://gcc.gnu.org/releases.html
- danieldk 14y agoAnd since it's a Mac, it is probably llvm-gcc (GCC with an LLVM backend). A colleague/friend who is developing neural network software recently switched from gcc 4.2.1 to 4.5 (which is still old) and got a 50% speed increase without touching any code.
- SiVal 14y agoThat's the first thing I thought, too. I'd like to see both Go 1.1 and Go 1.0.3 for a comparison (on this benchmark). I'm hoping that before long we'll be able to count on Go being within a factor of 2 of plain C by most benchmarks. And I'd like to see CPython 3.3 in addition to PyPy. But it's quite interesting as is. Thanks.
- igouy 14y agoIt's been just 2 days since go1.1beta1 was released, the other language implementations seem more out-of-date than that.
- reneky 14y agoThere are more low-hanging performance fruits in the immature languages. That said, of course all should be up to date.
- igouy 14y agoSee danieldk's comment -- https://news.ycombinator.com/item?id=5502984 https://news.ycombinator.com/item?id=5502984
- codygman 14y agoThat doesn't negate the fact that I want to see the performance of go1.1 :D Truthfully though, I didn't notice the others were out of date. I bet OP will update them all :P
- robotmay 14y agoI'm really excited by Rust because it seems to be one of the most sensible language designs I've seen in a while. Go is nice but has some pretty odd syntax in places. I'm just waiting on Rust to hit 1.0 before I start playing with it more seriously.
- pjmlp 14y agoA nice ML influenced system programming language, that even has generics, who would guess that?!
- zura 14y agoAnd deterministic memory management, which is quite rare these days... :) But to be honest, skimming through Rust samples, I find its syntax somewhat noisy. It feels ad-hoc. Is there any document about justification of its syntax elements?
- neilk 14y agoUnlike most other language designers today, Rust's designer was more concerned about getting the concepts right than the syntax. So the syntax came late in the process, and as far as I know they did get inspiration from various sources. Possibly that is what bugs you. I don't think there is a single document about syntax choices. It's evolved a lot in the past three years.
- pjmlp 14y ago> And deterministic memory management, which is quite rare these days... :) Memory management should be automatic, either by reference counting or GC. I think it is a generation thing until mainstream OS adopt such kind of system programming languages. There are a few OS with such system programming languages, but it only counts when the likes of Apple, Microsoft and Google adopt such languages. Objective-C with ARC, C++11, C++/CX are already steps in that direction. >But to be honest, skimming through Rust samples, I find its syntax somewhat noisy. It feels ad-hoc. Is there any document about justification of its syntax elements? My only issue is the Perl like prefixes for pointer types. I think it pollutes a bit the ML language influence. On the other hand, I am starting to get used to it.
- lern_too_spel 14y agoJava 1.6 is more than 6 years old now too. I half expected to see a Turbo Pascal 4 benchmark mixed in there before I realized I was joking.
- dom96 14y agoIt would be nice to see a Nimrod benchmark.
- raphael_kimmig 14y agoI've tried it with go tip and go 1.0. T(go tip) / T(go 1.0.3) = 0.8 Thus one might expect go to take third place after clang and gcc. But keep in mind that e.g. java isn't the newest version either...
- kyrias 14y agoJust tried it myself with the C version and with 1.0.3, C: ./a.out < sudoku.txt 0.07s user 0.00s system 94% cpu 0.077 total Go: ./sudoku_v1 < sudoku.txt 0.06s user 0.01s system 88% cpu 0.079 total Which seems a bit interesting...
- acjohnson55 14y agoMan, PyPy got destroyed, let alone CPython! As a Python lover, that's pretty disheartening. I'm not an expert in many of these languages, but it would seem as though it should be possible to build a Python interpreter as fast as V8, even without using Numpy to accelerate the math. Anybody have any thoughts as to why PyPy is such a poor performer here?
- RivieraKid 14y agoPython just 8x slower than C and 4x slower than Java? That's actually pretty good result for Python.
- cdavid 14y agoI think LuaJIT is the outlier, not python. All other implementations got lots of resources to make them fast, except for LuaJIT.
- copx 14y agoPyPy simply isn't at the same level as V8 and LuaJIT yet. V8 is a professional, full-time project employing some of the best programmers money can buy. And LuaJIT.. well LuaJIT is written by a fucking genius 10x programmer. Let me quote him: " The reason why X is slow, is because X's implementation is slow, unoptimized or untuned. Language design just influences how hard it is to make up for it. There are no excuses. " Source: http://www.reddit.com/user/mikemike http://www.reddit.com/user/mikemike (that's his reddit account) Python (and Ruby for that matter) could reach a comparable performance level if people with the necessary skills invested the necessary amount of effort.
- cdavid 14y agoIndeed, that's what I meant, even though my phrasing was unclear. Thanks for clarifying.
- Symmetry 14y agoThat's actually an impressively good result. All that wonderful expressive power that Python has comes at a price in implementation complexity, and there are a lot of different cases that the JIT needs to handle with Python. Lua, by contrast, is pretty much Scheme in ALGOL's clothing and is ridiculously simple inside.
- shocks 14y agoObligatory programming language shootout link: http://benchmarksgame.alioth.debian.org/ http://benchmarksgame.alioth.debian.org/
- RivieraKid 14y agoAFAIK it's not obligatory.
- igouy 14y agoAnd was already referenced in the blog -- "Other statically typed languages are about twice as slow, which broadly agrees with Computer Benchmark Games." (Although I suppose that's some-kind-of appeal to authority?)
- igouy 14y agoThe project name changed 6 years ago. "The Virginia Tech shooting in April 2007 once again pushed gun violence into the media headlines. There was no wish to be associated with or to trivialise the slaughter behind the phrase shootout so the project was renamed back on 20th April 2007 - The Computer Language Benchmarks Game." http://benchmarksgame.alioth.debian.org/dont-jump-to-conclusions.php#history http://benchmarksgame.alioth.debian.org/dont-jump-to-conclus...
- shocks 14y agoThat is ridiculous.
- igouy 14y agoWhat is ridiculous? Understanding what a shootout is? http://en.wikipedia.org/wiki/Shootout http://en.wikipedia.org/wiki/Shootout
- shocks 14y agoChanging the name of a programming competition to not cause some kind of offence is ridiculous in my book. I understand what a shootout is. Do you understand what a programming competition is? I'll give you a clue, it does not involve murder nor does it advocate gun crime. Anyone that can construe a bad message from a programming competition called a 'shootout' is as bad as feminists claiming sciences lack of progress in the field of fluid mechanics is sexism. This kind of behaviour only encourages the ridiculous "politically correct" world we live in today.
- yaakov34 14y agoA small personal peeve: it doesn't make sense to say that Sudoku is NP-hard, as the linked post does (or NP-complete). First of all, this benchmark (as far as I can tell) uses only traditional 9x9 puzzles, of which there is a finite number. Problems with a finite input space are trivial from the point of view of complexity theory; in order to talk about any kind of completeness or hardness results, you need to generalize Sudoku by defining NxN problems in some way. Moreover, once you define NxN Sudoku (the generalization is easy), you need to pick the problem for which you want to prove a hardness result. The decision problem is typically defined as "given an instance of a problem, determine if there is a solution". For Sudoku, you would need to decide if a partial grid can be completed to a full grid, i.e. if the given puzzle is solvable. This has been proven to be NP-complete. However, this is not how the puzzle is usually done, including in this benchmark: you are given a puzzle which is known to have a solution, and the solution is known to be unique. You then need to find the solution. It's been shown that such a Sudoku problem is equivalent to the unambiguous satisfiability problem (given a logical formula which has a unique variable assignment that satisfies it, find that assignment). Now the unambiguous satisfiability problem is not known to be NP-complete when phrased as a decision problem. Anyway, don't just throw around terms like "NP-hard". :) EDIT: edited "unique satisfiability" to "unambiguous satisfiability". I believe this is the correct terminology for the "promise" version of the problem which I described, and to which Sudoku is equivalent. (The unique satisfiability problem is "decide if a logical formula has exactly one solution", where you are not told if it has more than one, none, or just one).
- ot 14y agoThis. Most of the time when people say "NP-hard" they actually mean "no algorithm substantially better than an exhaustive search is known".
- currymesurprise 14y agoThe Valiant-Vazirani theorem says that both Unique and Unambiguous SAT are NP-hard under randomized reductions. While this is not NP-hard under the usual definition, modern complexity theorists believe derandomization to be possible to a degree similar to their belief that P is not NP.
- 14y ago
- SeanDav 14y agoSince asm.js is also flavour of the month and not a million miles away from Rust and Dart in terms of target application, would be great to see this added.
- azakai 14y agoResults on my machine, normalized to C Native (C): 1.00 Firefox/SpiderMonkey: 1.38 Chrome/v8: 1.97 Firefox and Chrome are running on asm.js code from compiling the C source. edit: link: https://gist.github.com/kripken/5327216#file-sudoku-asm-js https://gist.github.com/kripken/5327216#file-sudoku-asm-js
- hamax 14y agoMy results with newer versions of gcc and go: gcc 4.7.2 o3 0.765s java openjdk 7 1.066s java openjdk 6 1.118s go 1.1b 1.653s rust 0.6 opt 3 1.659s go 1.0.2 2.127s dart 0.4.4.4 2.384s pypy PyPy 1.9.0 5.094s pypy PyPy 2.0b 5.319s (Intel(R) Core(TM) i7-3520M CPU @ 2.90GHz) Edit: Added java
- melling 14y agoIt looks like Go 1.1 might be faster than Java. That might help convince enterprise developers to adopt it.
- hamax 14y agoAdded java to the list. It's still faster then go.
- jfb 14y agoNo way would a microbenchmark ever change any responsible person's mind about tooling. There are a lot of reasons (some of them nearly respectable) to use Java; "it's faster than <X>" isn't one of them.
- saosebastiao 14y agoDon't be silly. Java is extensively used for speed. It is an extremely fast language with a few caveats (such as startup/warmup time).
- melling 14y agoOf course, I didn't mean to imply that any microbenchmark would change someone's mind. It's kind of absurd to think that's what I meant. Go should approach C/C++ in performance and often Java is promoted as about 2x slower than these two languages. Fast compilation and linking is another big plus. The formatting consistency is another. It's not a verbose language either.
- elteto 14y agoJust curious, are you factoring in the VM warmup time for Java?
- jeremyjh 14y agoI'm really excited about Rust's performance here, considering how young the compiler and its runtime are. It has to get much faster but that seems likely to be possible.
- blinkingled 14y agoBetter stats than time using Linux perf utility. Looks like if you can exclude Java's startup time they are all pretty much very competitive. Clang SVN wins and Go 1.1 native build beats gccgo-4.8. Hmm. * java version "1.7.0_17" - 485,284,671 cycles, 0.133074106 (0.0577s excl. startup) seconds time elapsed, 3.64% of all branches missed * clang svn -O2 - 49,227,286 cycles, 0.029045632 seconds time elapsed, 6.70% of all branches missed * gcc-4.8 -O2 -flto - 56,989,391 cycles, 0.029750578 seconds time elapsed, 6.48% of all branches missed * gccgo-4.8 -O2 -flto - 114,583,934 cycles, 0.061428897 seconds time elapsed, 2.96% of all branches missed * Go 1.1 Beta - 109,278,081 cycles, 0.048572937 seconds time elapsed, 2.62% of all branches missed
- gillianseed 14y agoWhy are you using -O2 instead of -O3?
- damien 14y agoOr -Ofast
- blinkingled 14y ago-O2 seems to be the most commonly used optimization level. That's what most of the distro software and the kernel etc uses. In the past except for maybe a handful things, O3 was an overkill. (O3/Ofast remind me of my Gentoo days! :)
- pcwalton 14y agoI added some optimizations to the Rust compiler on my branch, added inlining attributes to match the C version, removed I/O (we have performance problems there that are under active development) and reduced the integer sizes to 32 bit to match the C version more closely (see [1]) and got the time down to within 50%: C version: 0m1.305s Rust version: 0m1.871s I think the remaining time may be attributed to the fact that you used smaller integer widths for the various internal arrays in the C version and larger integer widths in the Rust version. Remember that Rust `int` types are the size of a register (like Go 1.1), so they're 64 bit on x86-64. You can use `i8`, `i16`, etc. for smaller integer widths. Bounds checks may also have some effect; we should add methods to allow them to be avoided. Finally, thanks for trying out Rust. Do you mind if we add this benchmark to our test suite? Edit: Updated the gist to use smaller integer widths, like the C version. Now Rust is within 33% of the C version: C version: 0m1.205s Rust version: 0m1.613s [1]: https://gist.github.com/pcwalton/5327090 https://gist.github.com/pcwalton/5327090
- deleted 14y ago[deleted]