Performance of Rust and Dart in Sudoku Solving • Hacker News Board

Re: Performance of Rust and Dart in Sudoku Solving

#51

Post by pcwalton » Sat, Apr 06, 2013, 4:29 PM UTC

4ad wrote: post #18

robotmay wrote: post #3

I'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.

You're complaining about Go syntax, which is one of the most readable languages out there but you like rust which looks like line noise?[1] Sometimes I have a hard time convincing myself people don't post troll comments on HN. [1] https://github.com/mozilla/rust/blob/master/src/libsyntax/pa...

That file is very ugly (it's one of the oldest files in the repository) and does not reflect the current programming style. The indentation is all over the place, the type names are not CamelCased, there isn't enough use of methods—`str::len()` is ugly compared to `"foo".len()`—and so on.

(Of course, this isn't an excuse: we sorely need to refactor the compiler.)

Re: Performance of Rust and Dart in Sudoku Solving

#52

Post by pcwalton » Sat, Apr 06, 2013, 4:34 PM UTC

zura wrote: post #11

pjmlp wrote: post #5

Earlier quoted context omitted.

A nice ML influenced system programming language, that even has generics, who would guess that?!

And 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?

We actually have partaken in long, long debates about the syntax, and the current syntax is one that everyone seemed to be OK with, modulo a few compromises here and there.

Usually people who say Rust looks like line noise are concerned about `@` and `~`. These are there for a reason: they're the Rust versions of the smart pointers `shared_ptr` and `unique_ptr` in C++. Unlike in C++, you have to use them: there is no other way to allocate memory. So `shared_ptr` and `unique_ptr` would be all over the codebase in Rust code if we didn't abbreviate them, and making them one character was the easiest way to do that.

I actually think that one of the reasons few people write exception-safe code in C++ is that `shared_ptr` and `unique_ptr` (especially if you don't use `using namespace std;`) are so long that `new` and `delete` end up being more convenient…

Re: Performance of Rust and Dart in Sudoku Solving

#53

Post by zura » Sat, Apr 06, 2013, 4:38 PM UTC

pjmlp wrote: post #41

Symmetry wrote: post #34

Earlier quoted context omitted.

Rust's memory management is both (relatively) deterministic and automatic, in that it's easy to figure out exactly when objects are being destroyed if you care but you don't have to do anything yourself to ensure that they're destroyed properly. This is in contrast to C or C++ where you have deterministic destruction but you have to clean up things you have to clean up things on the heap yourself, or Go or Java where…

> This is in contrast to C or C++ where you have deterministic destruction but you have to clean up things you have to clean up things on the heap yourself, or Go or Java where you can't be sure at all when the garbage collector is going to harvest something. This is a false belief many C and C++ developers have. If you use the standard malloc()/free() or new/delete pairs, you are only certain at which point the memo…

Besides pure memory, there are other types of resources as well, which are deterministically destroyed/closed/freed (automatically, in C++ RAII usage).

Also, in C/C++ your performance critical loop/execution is not interrupted by harvesting GC passing nearby.

AFAIK, one of the main reason people come up with custom allocators is that the system new/delete (malloc/free) are expensive to call. E.g. it is much faster to pseudo-allocate memory from system pre-allocated static memory, in your app.

Re: Performance of Rust and Dart in Sudoku Solving

#54

Post by blinkingled » Sat, Apr 06, 2013, 4:46 PM UTC

Better 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

Re: Performance of Rust and Dart in Sudoku Solving

#55

Post by pjmlp » Sat, Apr 06, 2013, 4:56 PM UTC

zura wrote: post #53

pjmlp wrote: post #41

Earlier quoted context omitted.

> This is in contrast to C or C++ where you have deterministic destruction but you have to clean up things you have to clean up things on the heap yourself, or Go or Java where you can't be sure at all when the garbage collector is going to harvest something. This is a false belief many C and C++ developers have. If you use the standard malloc()/free() or new/delete pairs, you are only certain at which point the memo…

Besides pure memory, there are other types of resources as well, which are deterministically destroyed/closed/freed (automatically, in C++ RAII usage). Also, in C/C++ your performance critical loop/execution is not interrupted by harvesting GC passing nearby. AFAIK, one of the main reason people come up with custom allocators is that the system new/delete (malloc/free) are expensive to call. E.g. it is much faster to…

> Besides pure memory, there are other types of resources as well, which are deterministically destroyed/closed/freed (automatically, in C++ RAII usage).

In reference counting languages, the destroy method, callback, whatever it is named, takes care of this.

In GC languages, there is usually scope, defer, try, with, using, or whatever it might be called.

> Also, in C/C++ your performance critical loop/execution is not interrupted by harvesting GC passing nearby.

Code in a way that no GC is triggered in those sections, quite easy to track down with profilers.

Not able to do that? Just surround the code block with a gc.disable()/gc.enable() or similar.

> AFAIK, one of the main reason people come up with custom allocators is that the system new/delete (malloc/free) are expensive to call. E.g. it is much faster to pseudo-allocate memory from system pre-allocated static memory, in your app.

Which funny enough is slower than in languages with automatic memory management, because the memory runtime just do a pointer increment when allocating.

Re: Performance of Rust and Dart in Sudoku Solving

#56

Post by pcwalton » Sat, Apr 06, 2013, 5:33 PM UTC

I 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

Re: Performance of Rust and Dart in Sudoku Solving

#57

Post by elteto » Sat, Apr 06, 2013, 5:35 PM UTC

hamax wrote: post #33

My 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

Just curious, are you factoring in the VM warmup time for Java?

Re: Performance of Rust and Dart in Sudoku Solving

#58

Post by azakai » Sat, Apr 06, 2013, 6:45 PM UTC

SeanDav wrote: post #21

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

Results 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

Re: Performance of Rust and Dart in Sudoku Solving

#59

Post by coldtea » Sat, Apr 06, 2013, 7:33 PM UTC

PuerkitoBio wrote: post #47

coldtea wrote: post #45

Earlier quoted context omitted.

Sounds like natural selection.

Selection, yes. Natural? Do you somehow imply that technology that "wins" mass adoption is "better"? Or that it gains mass adoption based on rational analysis of its "value"? There are quite a few unnatural forces at play, here...

>Selection, yes. Natural? Do you somehow imply that technology that "wins" mass adoption is "better"?

No, just that it's more fit.

Which is the exact same thing natural selection in nature implies. An animal that spreads is not "better" -- it's just more fit for it's environment.

For an OS "more fit" can mean: faster, consuming less memory and with more control over it, usable in more situations and more hardware, cheaper to run, leveraging existing libraries, etc. It doesn't have to be "better" as in "less prone to crash", "safer" etc.

The parent mentioned SUN experimenting with a Java OS. What a joke would that be, given that SUN's experiments with a similarly needy application (a Java web browser) ended in utter failure, with a slow as molasses outcome.

Sure, it would run better with the resources we have now. But a C OS like linux also runs much better with the resources we have now -- so the gap remains.

It's not like we have exhausted the need for speed in an OS (on the contrary). It's not also like, apart from MS Windows of old, we have much problems with the core OS crashing or having security issues.

In fact, I haven't seen a kernel panic on OS X for like 3-4 years. And my Linux machines don't seem to have any kernel problems either -- except sometimes with the graphics drivers.

So, no, I don't think we're at the point where a GC OS would make sense for actual use.

ARC, an example the parent gives, fine as it might be, doesn't cover all cases in Objective-C. Tons of performance critical, lower level stuff still happens in C-land, and needs manual resource management, it's just transparent to the Cocoa level.

Re: Performance of Rust and Dart in Sudoku Solving

#60

Post by attractivechaos » Sat, Apr 06, 2013, 9:05 PM UTC

yaakov34 wrote: post #20

A 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 genera…

Finding and understanding computational algorithms is part of my daily work. I know what time complexity means. By saying NP-hard, I mean an NxN sudoku cannot be solved in time polynomial to N.

Most sophisticated sudoku solving algorithms, including mine, do not assume the grid has a solution or one solution. They test and give all possible solutions. I am really trying to solve an NPC problem.

That said, your comment still tells me something I do not know - you seems to say that given a sudoku that is known to have one solution, there may be polynomial algorithms. This reminds me of someone who left a comment in my blog, saying that if the solution is unique, at each step there are at most two choices with the exact cover matrix. He couldn't prove that, but his program run happily on tens of thousands of Sudokus without problems. This does not necessarily solve sudoku in polynomial time, but may make solvers faster for unique sudokus.