8

Hey, I have been trying to find an answer (both on stackoverflow and google) to the question how Array.Sort in C# is so fast. I didn't find one.

No matters which algorithm I used I didn't manage to sort big arrays faster than it. I know it uses Quick Sort, but it must be very optimized.

Does anybody know how did they make it so fast?

Shay Ben Moshe
  • 1,298
  • 3
  • 12
  • 27

2 Answers2

21

It is standard quicksort code, written in C#. You can find it in ArraySortHelper<>.QuickSort with, say, Reflector.

A pretty standard mistake when profiling code is to do so with the JIT optimizer disabled. Which will happen when you run the Debug build or have a debugger attached. This won't happen when you profile the Array.Sort() method, it was pre-jitted by ngen.exe when .NET was installed on your machine. The optimizer has a great affect on the quality of the generated machine code. Check this answer for the kind of optimizations it performs.

You can debug release quality machine code but that requires changing an option. First switch to the Release configuration. Then Tools + Options, Debugging, General, untick "Suppress JIT optimization on module load". Beware of the pitfalls, you'll see the effects of inlining, code hoisting and elimination of local variables.

Community
  • 1
  • 1
Hans Passant
  • 922,412
  • 146
  • 1,693
  • 2,536
5

You could use ILSpy to disassemble the code. I would expect native methods in the inner sorting code to speed up things.

Uwe Keim
  • 39,551
  • 56
  • 175
  • 291
  • 1
    It is, ArraySortHelper<>.QuickSort was written in C#. – Hans Passant May 28 '11 at 15:03
  • 3
    I suspect native methods are *not* used. There's not that much performance benefit in native code for swapping object references in an array, and there's *no* benefit on the comparison side since it's delegated to the appropriate Comparer method. An interesting exercise would be to compare the performance of the Mono's implementation of the BCL's `List.Sort()` method to the MS.NET version. If they have similar performance characteristics, just look at the Mono code. – richardtallent May 28 '11 at 15:09
  • Thanks, @ja72 The best free tool since recently. The ReSharper guys just released their own, free tool [dotPeek](http://www.jetbrains.com/decompiler/), too. – Uwe Keim May 28 '11 at 15:56
  • 1
    @Uwe - Well that didn't take long.. :-) – John Alexiou May 28 '11 at 16:03
  • 1
    @Uwe Keim .. I didn't know that exactly as I wrote the comment, I just assumed there is no native code involved. That would impose strict limitations when using Array.Sort in environments with limited access to resources with probably no gain in performance. My comment was meant more ironically - people should start to understand that the assumption "native code is faster than managed code" does not hold automatically... – Paul Michalik Jun 04 '11 at 10:56