Testing basic datastructures in various programming languages
proycon | november 20, 2009 | 
Link
Have you ever wondered how your favourite programming language compares to others in terms of speed? How does for example Python compare to Ruby, PHP, Java or Perl? And how do all these scripting languages compare to actual compiled C++ code?
In most programming tasks, a central role is played by data structures such as arrays/lists, and hashes/dictionaries. I was curious how the performance of precisely such data structures differs across different languages. To test this, I wrote a series of basic data tests in all of the aforementioned programming languages, and I timed the execution of each test.
Besides a benchmark study, it was also a nice exercise to write essentially the same script in many different languages.
I will summarize some of the results of my experiments. I ran all tests 10 times on a Intel Core 2 Duo (Macbook Pro 5,3), running a 64-bit Ubuntu Linux 9.10. All times are in seconds and of course machine specific. C++ code was compiled with gcc 4.4.1, and for Java the Sun JDK 1.6.0 was used.
You can run all tests yourself, download the scripts and sources, inspecting the sources may also provide valuable insight in seeing how the tasks are implemented in the various languages.
Note that this is something I fairly quickly set up, so it may be that a few tests can be implemented more efficiently.
Test 1a/2a: Creating a new list of many integers:
Instantiating an array/list of two million integers (0 to 1999999). Note that all types except the C array are dynamically extendable.
| C Array* | 0.014 |
| C++ STL Vector | 0.032 |
| Ruby 1.9 Array | 0.217 |
| Perl Array | 0.307 |
| Python 3 List | 0.392 |
| Python 2.6 List | 0.441 |
| Java Vector | 0.61 |
| PHP5 Array | 0.795 |
| Ruby 1.8 Array | 1.142 |
Test 2c: Test if a value is in the list
Locating a value in the list, the value will be found half-way
| C++ STL Vector | 0.0 |
| Java Vector | 0.02 |
| Python 2.6 List | 0.02 |
| Ruby 1.9 Array | 0.04 |
| Ruby 1.8 Array | 0.051 |
| Python 3 Array | 0.07 |
| PHP5 Array | 0.07 |
| Perl 5.10 Array (using grep) | 1.458 |
Test 2e: Sorting a list
A sort is done on a list of two million random integers.
| Ruby 1.8 Array | 0.33 |
| Ruby 1.9 Array | 0.363 |
| STL sort on C Array | 0.423 |
| C++ STL Vector | 0.798 |
| Python 2.6 List | 1.47 |
| Python 3 List | 1.617 |
| Java Vector | 1.692 |
| Perl Array | 4.475 |
| PHP5 Array | 6.819 |
Test 2f: Polling all elements in a list
The value of each list item is retrieved during iteration over all items.
| C++ STL Vector | 0.007 |
| Ruby 1.9 Array | 0.132 |
| Java Vector | 0.281 |
| Perl 5.10 Array | 0.286 |
| Ruby 1.8 Array | 0.514 |
| Python 3 List | 0.523 |
| Python 2.6 List | 0.524 |
| PHP5 Array | 0.746 |
Test 2g: Setting all elements in a list
Set all items in a list to zero
| C Array | 0.01 |
| C++ STL Vector | 0.01 |
| Java Vector | 0.093 |
| Ruby 1.9 Array | 0.18 |
| Python 3 List | 0.529 |
| Perl Array | 0.537 |
| Python 2.6 List | 0.552 |
| PHP5 Array | 0.763 |
| Ruby 1.8 Array | 0.969 |
Test 2h: Inserting 10 elements
Ten insertions in the middle of an array of two million.
| Ruby 1.8 Array | 0.033 |
| C++ STL Vector | 0.035 |
| Ruby 1.9 Array | 0.044 |
| Python 3 List | 0.073 |
| Python 2.6 List | 0.078 |
| Java Vector | 0.079 |
| PHP5 Array | 13.204 |
Test 2i: Delete 10 elements
Ten deletions in the middle of an array of two million.
| C++ STL Vector | 0.03 |
| Ruby 1.8 Array | 0.03 |
| Ruby 1.9 Array | 0.034 |
| Python 3 List | 0.071 |
| Java Vector | 0.073 |
| Python 2.6 List | 0.085 |
Test 3a: Creating map of two million integers (key==value)
| C++ TR1 Unordered Map | 0.495 |
| Python 3 Dictionary (unordered) | 0.499 |
| Python 2.6 Dictionary (unordered) | 0.576 |
| Ruby 1.9 Hash (unordered) | 0.7 |
| Ruby 1.8 Hash (unordered) | 1.537 |
| C++ STL Map (ordered) | 1.791 |
| Perl Hash | 2.235 |
| Java HashMap | 3.249 |
Test 3b: Check if a key exists in map
Check if a key exists in the map: Less than 0.001 second for all languages
Test 3e/3f: Polling all elements in map
Retrieving the values of all elements
| C++ TR1 Unordered Map (no iterator) | 0.094 |
| Java HashMap (using iterator) | 0.099 |
| Java HashMap (without iterator) | 0.231 |
| Python 3 Dictionary (items() method) | 0.265 |
| Python 2.6 Dictionary (iteritems() method) | 0.27 |
| C++ STL Map (ordered, no iterator) | 1.044 |
| Perl Hash | 2.84 |
| Ruby 1.9 Hash (each() method) | 7.671 |
| Python 2.6 Dictionary (items() method) | 7.93 |
| Ruby 1.8 Hash (each() method) | 12.117 |
Test 3h: Setting all elements in map
Setting all elements in the map to zero
| C++ TR1 Unordered Map | 0.097 |
| Java HashMap | 0.306 |
| Python 3 Dictionary | 0.335 |
| Ruby 1.9 Hash | 0.383 |
| Python 2.6 Dictionary | 0.404 |
| C++ STL Map (ordered) | 1.055 |
| Ruby 1.8 Hash | 1.247 |
| Perl 5.10 Hash | 6.049 |
|
:
Comments
- mihxil | maart 23, 2010 A java vector is synchronized. Shouldn't you have used an ArrayList or so? Not sure it would have made much difference. But that's my point.
Feel free to leave a comment as well:
