Monday, January 15, 2007

Sudoku Benchmarking / .NET 2.0, Java 5 and Java 6 Results

Brian Deacon asked me to add Sudoku Solver benchmark results for .NET 2.0 and the latest Java releases, so I am happy to provide those numbers (plus this finally gave me a reason to download and install Java 6).

.NET 2.0 and Java 6 both have improved a lot, and for the first time .NET without NGEN overtakes Java (not applying NGEN is the fairest-possible comparison between .NET and Java in my opinion - and in this case it's a very close match), but both still don't quite reach C++ performance:

RankPlatformExecution Time
(for several thousand valid solutions)
1.C++ (MSVC)250ms
2.C# (.NET 2.0) with NGEN375ms
3.C# (.NET 1.1) with NGEN390ms
4.C# (.NET 2.0)406ms
5.Java (Java 6)422ms
6.Java (Java 5 Update 10)657ms
7.Java (Java 1.4.2)680ms
8.C# (.NET 1.1)790ms

What I did here was to feed the Sudoku solver with a sparsely populated puzzle that has thousands of valid solutions (Sudoku purists will point out that this is a non-well-formed puzzle). The algorithm uses a slightly optimized brute force approach (my intention was runtime comparison, not building a hyperfast solver algorithm) - so it finds all the solutions. Of course I took care to apply exactly the equivalent language constructs on all platforms, most importantly when it came to dynamic memory allocation.

The usual one-solution, human-solvable puzzles are being processed at a rate of about 60,000 valid solutions per second (C++ version on my 2.4GHz Athlon) - but the time it takes to solve one of those can hardly be measured, and I didn't want to inject the same puzzle a thousand times for the benchmark. There are harder puzzles though with one solution but a larger search space, which means it takes longer to solve them.

And as I have mentioned before: I doubt that there is a lot of optimization potential for Java Hotspot other but compiling the algorithm's main method (which only consists of a few lines of code anyway) to native code as soon as possible. Dynamic memory allocation only happens for storing away solution arrays, and those are not going to be garbage collected until the end, so there is not a lot of optimizing potential on the memory management side. The .NET CLR should JIT all of the code at startup anyway. I did some tests to go sure, and the numbers did not change neither under Java and nor under .NET even after running the same stack of puzzles many times in a row.

Previos Posts: