Introduction
About two years ago I evaluated the performance of ~20 compilers and interpreters on sudoku solving, matrix multiplication, pattern matching and dictionary operations. Two years later, I decide update a small part of the benchmark on Sudoku solving. I choose this problem because it is practically and algorithmically interesting, and simple enough to be easily ported to multiple languages. Meanwhile, I am also adding two new programming languages: Mozilla’s Rust and Google’s Dart. They are probably the most promising languages announced in the past two years.
Results
In this small benchmark, I am implementing Sudoku solvers in multiple programming languages. The algorithm, adapted from Guenter Stertenbrink’s solver, was first implemented in C and then ported to other languages. The C source code briefly describes the method. For more information about Sudoku solving in general, please see my other post.
Before I show the results, there are a couple of caveats to note:
- Solving Sudoku is NP-hard. The choice of the solving algorithm will dramatically affect the speed. For example, my Rust implementation is ~2500 times faster than the one in the Rust official repository. For a language benchmark, we must implement exactly the same algorithm.
- I am mostly familiar with C but am pretty much a newbie in other programming languages. I am sure some implementations are not optimal. If you can improve the code, please send me a pull request. I am happy to replace with a better version.
The following table shows the CPU time for solving 20 hard Sudokus repeated 50 500 times (thus 1000 10000 Sudokus in total). The programs, which are freely available, are compiled and run on my Mac laptop with a 2.66GHz Core i7 CPU.
Compiler/VM | Version | Language | Option | CPU time (sec) |
---|---|---|---|---|
clang | 425.0.27 (3.2svn) | C | -O2 | 8.92 |
llvm-gcc | 4.2.1 | C | -O2 | 9.23 |
dmd | 2.062 | D2 | -O -release -noboundscheck | 11.54 11.47 |
rust | 0.6 | Rust | –opt-level 3 | 11.51 |
java | 1.6.0_37 | Java | -d64 | 11.57 |
go | 1.1beta 20130406 | Go | (default) -gcflags -B | 14.96 13.78 |
dart | 0.4.4.4-r20810 | Dart | 21.42 | |
v8 | 3.16.3 | Javascript | 28.19 | |
luajit | 2.0.1 | Lua | 30.66 | |
pypy | 2.0-beta-130405 | Python | 44.29 |
In this small benchmark, C still takes the crown of speed, Other statically typed languages are about twice as slow but Rust and D are very close to C. It is pretty amazing that Rust as a new language is that performant given the developers have not put too much efforts on speed so far.
Among dynamically typed languages, Dart, V8 and LuaJIT are similar in speed, about 3 times as slow as C. 3 times is arguably not much to many applications. I really hope some day I can use a handy dynamically typed language for most programming. Pypy is slower here, but it is more than twice as fast as the version two years ago.
Related resources
- Old benchmark results.
- Sudoku solver source code based on the same algorithm.
- Online Sudoku solver using the same algorithm.
- Third-party sudoku solvers.
- Reddit discussions.
- Hacker News discussions.
Update
- I forgot to use `-release’ with dmd. The new result looks much better. Sorry for my mistake.
- Mac ships gcc-4.2.1 only due to licensing issues. I have just tried both gcc 4.7.2 and gcc 4.8 from MacPorts. The executables compiled by them take 0.99 second to run, slower than gcc-4.2.1.
- Updated to the latest Go compiled from the repository.
- Updated the Python implementation (thanks to Rob Smallshire).
- Updated the Dart implementation (thanks to jwendel).
- Updated the Rust implementation (thanks to dotdash).
- Made input 10 times larger to reduce the fraction of time spent on VM startup. Dart/V8/LuaJIT have short VM startup time, but Java is known to have a long startup.
- Updated the Go implementation (thanks to Sébastien Paolacci).
- Updated the Python implementation.