Sorting in Mono 2 – memmove in C#?

After I realized (as described in the first part of this series), that Mono was faster than I had imagined, I continued my benchmarks with the two versions of insertion sort and wondered if .NET could somehow counter the efficency of memmove.

Insertion Sort

Again, explanations and C source code can be found in fejj’s original post. A description of the testing procedure is in my first article. The unoptimzied C code finished after about 32 seconds. Converting the code to C# was again very straightforward and I won’t bore you with listings.

Mono arrays finished even better than last time. Only 19 seconds! The ArrayList again was so slow, that I aborted the test.

So, how could I optimize the C# code to “counter” C’s memmove? “Luckily”, the optimized C code takes 25s to sort the 100.000-item-array, which is still slower than the unoptimzed C# code! At first I thought that there was no way to do something like memmove in C# as it is a very low-level operation and the .NET Framework is all about abstraction. I didn’t even bother looking through the docs. But I did take I closer look at the memberlist of the ArrayList class. Two interesting functions caught my attention: GetRange() and SetRange(). The former returns an ArrayList, but “does not create copies of the elements: the new System.Collections.ArrayList instance is a view window into the source list.” (from MonoDoc). The latter takes and ICollection and a startindex and copies the values from the collection to itself. If the implementation was done well and recognized that the source and the target were the same, then it could speed up things quite a bit. And indeed, it did so. Insertion sort on ArrayLists was now down to 7 minutes and 24 seconds…

After this success, I thought that I might take a closer look at System.Array and found the Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length) method. From the docs: “[The function] Copies the specified number of elements from a source array starting at the specified source index to a destination array starting at the specified destination index. [...] If sourceArray and destinationArray are the same array, [Copy()] copies the source elements safely to their destination as if the copy were done through an intermediate array.“. Looks promising, but in this case it only sped up execution by about 0.5 seconds. Not much, but this technique might prove to be of good use later.

Binary Insertion Sort

fejj’s code (without memmove) takes 23s, C# Arrays are again faster, but only by 6 seconds, and ArrayLists are again far too slow. Plugging in the optimizations I got a bigger improvement than last time: 6.2s (C), 7.1s (C#), 7.8s (ArrayList). The world is normal again! C code is faster than C# code! This is also the first algorithm, here ArrayLists can compete with ordinary arrays. Supposedly get/set operations are very slow with ArrayLists as the optimized binary insertion sort has very few of them compered to all former algorithms. This is probably due to the fact that the System.Array indexer can be directly mapped to a few assembler instructions (like C arrays), while when using an ArrayList there is an additional method call, which produces quite a lot of machine instructions. And of course there is the second checking of list bounds and the internal version bumping.

Eliminating the recursion only speeds up the C# array version (don’t ask me why), so that it runs in about 6.0s.