A hand full of Queens

Or: SML/Moscow ML is faster than C++/GCC

Inspired by a remark by Peter about the abysmal performance of exceptions on the .NET platform. I decided to check it for myself with a micro-benchmark. I also decided to check the performance of C++ exceptions, just for the fun of it.

The micro-benchmark is to find a solution to the N-queen problem using backtracking, with exceptions used as backtracking. I tested four different languages (SML, O’Caml, C#, and C++) and five different language implementations (MLton, Moscow ML, O’Caml, Mono, and GCC). The results are a bit surprising, and definately deserves further investigation. The graph below shows the running times for the five different executables:

Graph showing running times for the different executables

From the graph we see that O’Caml and MLton are way faster than the rest (and O’Caml has a small edge compared to MLton), Moscow ML is faster than Mono, and my C++ program is slow as a slug. I’ve tried various small tweaks to make the C++ version faster, but nothing really helps. For instance, at first we might notice that there are a tiny algorithmic difference between the C++ version and the other versions, namely the order in which a new position is compared with the already determined positions. But changing this order have no real effect (I’ve tried to change C++ program in various ways, and I tried to change the other programs). Still, the C++ performance is so bad that it looks suspicious. I’m open to suggestions for how to improve the C++ program.

Now I just have to test the SML version with the MLKit and SML/NJ, test the C# version with Microsoft’s runtime, test the C++ version with Visual C++ and Intel’s C++ compiler, and make a Java version of the benchmark and test it with … Any volunteers?

The programs used in the benchmark are here: queens.sml, queens.ml, queens.cs (ran mono with option --optimize=all) , and queens.cpp (compiled with option -O3).

Leave a Reply

Your email address will not be published. Required fields are marked *