Subscribe to SpeedisaVirus' Digital Mixing Pot        RSS Feed

NQueens Solution Time in C++, C#, Java, and Python

Icon Leave Comment
Now that the fall semester is over and I am on winter break I have some time on my hands. I decided to use this time to play with code. This exploration was a simple comparison between languages and an exercise in comparing syntax. All too commonly there are debates about why this or that language is faster another. I chose to use the N-Queens problem as it is computationally complex and would show performance differences with small steps in growth of the problem. I know I did not use the most efficient algorithm. I also did not make any optimizations or considerations the implementing languages. The algorithm is a simple and basic recursive backtracking algorithm that might be used in a low level college course.

Disclaimer: This was not done as a scientific matter of fact. I did not use the best means of timing. I understand that there are granularity differences between the timing mechanisms I used however they should be accurate enough to show the relations I wanted to see. I did this for myself and have decided to share it.

The languages I chose to look at were C++, C#, Java, Python, and Jython. Jython was an afterthought since it was just a few clicks away I tossed it in. The following is the problem solving pseudo code.

Find solution( column)
	If column == board size
		Solution found
		For each row
			Board[row,col] = true
			If location is valid
				Find solutions(column + 1)
			Board[row,col] = false

Determination on valid moves was O(n). The system specs include an E2180 Pentium, 2GB Ram, and Win7 Professional 64 bit. I closed all irrelevant programs and processes and ran each case through the cmd prompt. C++ and C# was written and compiled in Visual Studio 2010 Beta. Java, Python, and Jython were written in NetBeans 6.8. My JVM is version 6.0.18, Python 2.6.4, and Jython 2.5.1. For each case, (starting at board size 8 to board size 15) a for loop ran solving for all solutions 5 times reporting the time to solve in each iteration. Time to find all possible solutions for a board was reported using built in mechanisms and is reported in milliseconds.

Posted Image

In some senses these languages are apple to oranges if looking at them in a performance context. C++ is a pure compiled language. Java and C# are both VM languages utilizing Just in Time compilation. From preliminary reading I would say Jython falls in the same category as Java and C# as well since it runs on the JVM in Java byte code form. Perhaps I am mistaken though. Python on the other hand is a more purely interpreted language. The results are more or less as expected based on this.

C++ is the winner as this problem scales. It clearly grows at the slowest rate. Java was not that far behind however and was typically 80% to 84% as fast as C++. The third most efficient language was C# which was between 78% and 85% as fast as Java, almost the same gap between Java and C++. The performance gap between C# and Java was closing as the problem set became larger but not at a fast rate. This simply tells me that either the JVM is more mature and efficient than the .NET platform or there are some code optimizations that C# would really benefit from that isn’t as big of a deal for the JVM.

The Python family code was not in the same league when it comes to quickly running this algorithm. Much to my surprise though, the interpreted CPython was much faster than Jython. I suspected that the use of the JVM and JIT that comes with it would have given Jython at least equal performance if not better than the non-compiled Python code. Since the time to find all solutions grew pretty quickly for these two languages I only ran up to a 12x12 board since a 13x13 board was taking about 6 minutes to find solutions in Python. Jython ran at approximately 38% of the speed as the Python code and Python ran at about 1% the speed of C++. I suspect the Python code could gain a fair bit of performance through the use of a JIT compiler like Psycho but I don’t know just how much.

Posted Image

Jython was significantly slower on the first pass at solving the problem than subsequent passes. This seems to be attributed to the JVM warming up from what I am reading online however Java didn't exhibit this behavior. After the first iteration of 5 the solutions were found 17% faster. Still, I’m a bit surprised by just how slow it was overall despite claims that it should run at approximately the same speed as CPython on the Jython homepage. This must be a particularly challenging problem family for Jython.

As a final disclaimer I want to reiterate that this was not scientific or really indicative of anything. If I rewrote the code to take advantage of each language’s strengths things could look very different. Using one approach in a certain language may not be that great in another. Raw numbers are not an indication of what makes one language “better” than another anyway. They each have their own strengths in the core language and the libraries available to them. Anyway you slice it, this was all about "keeping my head in the game" over break, learning some new stuff, and it has done that.

I noticed there were some NQueens snippets for some languages but not others. If I get to it and it's appropriate I'll submit the source for those later.

0 Comments On This Entry


February 2015

222324252627 28

Recent Entries

Search My Blog

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)