powered by Slim Framework
Follow @NesbittBrian rss

A "quick" microbenchmark

Feb 8, 2012

The other day I decided to do some microbenchmarking across several different languages. I used an array of 1 M integers and applied the quicksort sorting algorithm as the test code and also included the native language sort routines where applicable.

I wrote the runner using Cake and Coffeescript which compiles to Javascript and runs on node.js. Cake is a very simple build system and is similar to make/rake, as you probably already guessed.

Each respective test will run the sort algorithm 5 times (some only 3 because they take so long already it doesn't matter) and the minimum execution time is printed. I ran each one a few times and took an eyeball average of those runs. I am not that interested in a +/- of a few milliseconds when sorting 1 M integers. I am way more interested in orders of magnitude.

Results

LanguageVersionTime in milliseconds
1C++MS 16.00.30319.01 for 80x8675
2C# Array.Sort().NET 3.5100
3Java1.6.0_23105
4Groovy api (aka java)1.8.5110
5Java Arrays.sort()1.6.0_23121
6C#.NET 3.5126
7Scala2.9.1.final128
8Node.js (v8)0.6.7175
9Chrome JavaScript16.0.912.77182
10Ruby api array.sort!1.9.2p290250
11Firefox JavaScript10.0271
12IE JavaScript9.0.8112.16421307
13IE JavaScript api sort()9.0.8112.16421375
14Node.js (v8) api sort()0.6.7480
15Chrome JavaScript api sort()16.0.912.77520
16Python api sort()3.1.3814
17PHP api sort()5.3.81441
18Firefox JavaScript api sort()10.03490
19Ruby1.9.2p2903520
20Groovy1.8.54100
21Python3.1.38100
22PHP5.3.89700

Things I will take away from this exercise

Switching between too many languages during a day is tough and not very efficient. I haven't done much coding in some of these languages, or not at least for awhile. I didn't try to use the adopted paradigms in each language. I did try to keep the overall structure the same for each language. When you do a google search for quicksort some of the hits for ruby, python, javascript and scala show these "elegant" 1-3 liners of code that make me think I am looking at perl. Needless to say, I tried a few but they ran quite a bit slower than my bloated version. Thats not to say that some performance tuning could be done for each language's nuances, but as I mentioned, I am interested in the orders of magnitude comparison rather than a pure speed test.

It was interesting to see how easy some of the features were to find in some languages compared to others. Command line parameters, random numbers, benchmarking code etc. Lets take a look at command line parameters in each language. They are all similar (some variation of an arg[sv] array) but yet different (array offset, parsing, brackets, semi-colon). Its these subtle differences that make a lot of language context switching difficult.

C++                      int len = atoi(argv[1]);
C#                       var len = int.Parse(args[0]);
java:                    int len = Integer.parseInt(args[0]);
scala:                   val len = Integer.parseInt(args(0))
php:                     $len = $argv[1];
node.js (coffeescript):  len = process.argv[2]
groovy:                  len = args[0].toInteger()
python:                  alen = int(sys.argv[1])     # len is a reserved word
ruby:                    len = ARGV[0].to_i

A small but effective change included changing pivot = arr[(left+right) / 2] to pivot = arr[(left+right) >> 1]. In some languages it generated a noticeable increase in performance. As well it prevented a necessary cast/floor to an int preventing an array lookup of arr[3.5].

Pythons top google links are tied to v2 rather than v3. Using the old print statement rather than the print() function is pretty frustrating as you view the examples from google and the code seems correct. The error message was not at all helpful either. I have seen this in other languages/frameworks as well.

Then we have the browser wars, aka the js engine war. Chrome posted the best time for the quicksort. For some reason I was expecting some overhead compared to node.js but the in browser version was pretty much identical in both test cases. IE was the most consistent and by far had the best time using the Array API sort(). Firefox was really slow on the API call... no idea why. It was slow enough that I actually got the warning saying the script was running too long. During the algorithm Firefox was "Not Responding" as well. I didn't bother running the code in older versions as that wasn't the goal of this exercise.

Consective runs in IE and FireFox produced consistent results. However, this was not true for Chrome. Chrome's performance decreased by about double for the second run and a little more after that to what seemed to be a ceiling. It probably has to do with GC since on a page refresh the time returned back to the fast time.

Groovy gets to piggy back off of the JVM for API calls.

Most of the API sorts were faster. This is not surprising since the api would generally be running in the interpreters native language and are generally written in c++ so the sorts are running native code at that point. I was surprised that the quicksort algorithm was faster than the API calls for Java and JavaScript. In Java it is somewhat negligible and if you look at the source the Arrays sort() API is a "tuned" quicksort. Without spending too much time on it, it appears that the v8 implementation is doing a Quicksort written in js but makes extra calls to the required compare function among other things. The compare is necessary as by default the method sorts the elements alphabetically which is obviously not what we wanted. I assume this is where the overhead comes from, but that seems expensive as its almost 3x longer.

I was also surprised at how well all of the JavaScript engines did compared to the other main stream (server) languages. The node.js v8 implementation was 10x - 25x faster than most of them and was less than 2x Java/C#.

You can view the code for each implementation on github.

Although I did have the idea before seeing this, the following blog post provided some good information http://stronglytypedblog.blogspot.com/2009/07/java-vs-scala-vs-groovy-performance.html

You can see the results with PHP 5.4 ... A "quick" microbenchmark update PHP 5.4

CoffeeScript : Why is function binding not the default?  Home A "quick" microbenchmark update PHP 5.4  
blog comments powered by Disqus