To finish this trilogy of benchmarks, I’ll give you the results for two faster algorithms (shell sort and merge sort) and tell you why C is not slower after all.
But first I have to add a small, but nevertheless important, reason for ArrayList’s slowness to my discussion in the last post: ArrayList use a System.Object[] array for internal storage of its contents. This simply means that a lot of extra boxing/unboxing is going on and thus ArrayLists impose lots of overhead. I’ll come back to this a later.
I did not even think about this, but when invoked without any flags, gcc uses -O0 by default, which translates to “just do the fasted compilation possible, don’t think about code performace and do not alter the code in any way.” This is very practical for debugging, but of course not for production use. A friend of mine pointed this out, when we were discussing the results of my tests. Obviously mcs/mono do optimize the execution. With -O3 I got totally different results.
Here is a table of all average execution times I got on my machine. Please note that they are just approximations.
| C (gcc) | C (gcc -O3) | Mono C# (Array) | Mono C# (ArrayList) | |
|---|---|---|---|---|
| Initialization | 0.018/0.100 | 0.018 | 0.075/0.23 | 0.12/1.13 |
| Array[List].Sort() | - | - | 1.5/32 | 0.89/20.5 |
| BubbleSort | 43 | 22 | 35 | too long |
| InsertionSort | 32 | 7.7 | 19 | too long |
| InsertionSort (optimized) | 25 | 13.5 | 18.5 | 7m 24s |
| BinaryInsertionSort | 23 | 7.0 | 17 | too long |
| BinaryInsertionSort (optimized) | 6.2 | 6.5 | 7.1 | 7.8 |
| BinaryInsertionSort (no recursion) | 6.5 | 6.4 | 6.0 | 7.8 |
| ShellSort (value set 1) | 7.5 | 4.2 | 5.8 | 2m 20s |
| ShellSort (value set 2) | 0.09/4.6 | 0.056/3.3 | 0.15/5.5 | 1.6/61 |
| MergeSort | 0.054/1.091 | 0.045/0.917 | 0.132/1.66 | 0.78/21 |
| MergeSort (no recursion) | 3.3 | 3.3 | - | - |
The “optimized” algorithms are the ones with memmove, Array.Copy(), etc. Where two values are given, the first one is for 100.000 items and the second one for 2.000.000 items. A discussion of gcc’s perfomance with optimizations turned on (especially in the case of the optimized insertion sort) is out of scope for this small series.
So there are only two questions left: Why is Array.Sort() so slow, and why is ArrayList.Sort() faster. The answer to the former one: Array.Sort() uses the IComparable interface. This means boxing and function calls, i.e. loss in efficency. To get a feeling for the impact of (un)boxing, I tested morge sort (version 2) with an object[]-array of 100.000 (boxed) integers. It was considerably (about 3 times) slower than the version with an (not boxed) integer array.
The answer to the latter question is probably, that the values are already boxed in an ArrayList, so there is only the overhead of function calls.
To sum this up: With .NET one should really look out for (unintentional) boxing of value types. This might get (at least a bit) easier with the inclusion of generics in .NET 2.0. Until then, one has to watch out for this pitfall, especially when writing performance ciritical code.
-
If you are worried about the performance of System.Array or System.Collections.ArrayList you should know that C# does allow you to create pointer-based arrays of value types. These are allocated on the stack instead of the managed heap, and there will certainly be no boxing isues. I haven’t done any benchmarks but I expect you could achieve results similar to optimised C. Check out the ‘unsafe’ keyword in the documentation.
1 comment
Comments feed for this article
Trackback link: http://caramdir.at/blog/2004/08/sorting-in-mono-3-fast-sorts-the-revenge-of-c/trackback/