How is Array.Sort in C# so super-fast?

Question

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?

Community · Accepted Answer · 2017-05-23 10:30:33Z

22

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.

edited May 23, 2017 at 10:30

CommunityBot

11 silver badge

answered May 28, 2011 at 15:11

Hans Passant

946k151 gold badges1.8k silver badges2.6k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Shay Ben-Moshe Over a year ago

That explains so much, thank you! I will have to retry it with the optimizing enabled.

Uwe Keim · Accepted Answer · 2011-05-28 14:12:01Z

6

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

answered May 28, 2011 at 14:12

Uwe Keim

40.9k61 gold badges193 silver badges308 bronze badges

5 Comments

Hans Passant Over a year ago

It is, ArraySortHelper<>.QuickSort was written in C#.

richardtallent Over a year ago

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<T>.Sort() method to the MS.NET version. If they have similar performance characteristics, just look at the Mono code.

Uwe Keim Over a year ago

Thanks, @ja72 The best free tool since recently. The ReSharper guys just released their own, free tool dotPeek, too.

John Alexiou Over a year ago

@Uwe - Well that didn't take long.. :-)

Paul Michalik Over a year ago

@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...

Collectives™ on Stack Overflow

How is Array.Sort in C# so super-fast?

2 Answers 2

1 Comment

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related