Language array processing speed comparison with ‘selectionsort’2015-12-29

Recently I implemented the very simple Selection Sort algorithm for solving some unrelated problem in PHP. After doing some simple tests to check if the algorithm was working, I gave it something to bite on: I produced a list with 100’000 integer numbers, which I fed the algorithm, and started the script.

After 10 minutes I decided to stop the still running script, as I thought something must be wrong with my algorithm. So I re-checked the code again, and came to the conclusion that the code must be correct. So what was happening here? Sorting some random 100’000 numbers with Selection Sort should surely not take that much time, even if the algorithm’s performance is O(n2)?

Selection Sort is spending most of its time with array access: fetching an element at index, swap element X with element Y: It searches for the smallest element on each array loop and swaps it with the end of the sorted part of the list. So this algorithm’s speed depends highly on the array index access speed. For programming languages that support native, in-line memory arrays (e.g. C, C++, Java), this should be a piece of cake. But what about the interpreted languages such as PHP, Python, Ruby?

So I decided to implement the very same algorithm in different programming languages, just to check if it was really the speed of the PHP script. The result was somewhat surprising: Not that I hadn’t expected different results, but the scale of the differences is frappant. I never guessed that script/language speed would be THAT different!

I have collected the test results below. My test setup was as follows:

The test results

for executing selectionsort only on a list with 100’000 pre-generated int numbers

Language Compiler version sort time compiler flags
C++ Apple LLVM version 6.0 (clang-600.0.57) 3.54s g++ -O2
java javac 1.7.0_71 4.02s  
nodejs 0.12.0 4.05s  
groovy 2.4.1 127.71s groovyc -> jvm bytecode
ruby 2.2.1p85 276.91s  
python 3.4.3 382.77s  
php 5.5.30 441.08s  
php, SplFixedArray 5.5.30 407.88s  
php 7 7.0.1 160.78s  
php 7, SplFixedArray 7.0.1 171.92s