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:
- Run on a MacBook Pro Retina 15”, May 2015, 2.8 GHz Intel Core i7
- all scripts run in a single thread
- pre-generated numbers: each script used the exact same 100’000 number list
- Time measurement was done with language functions, and only the sorting time was taken: time to read and build the number list does not count
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 |