Journey through the .NET internals - Sorting
This article is Part 1 in a 5-Part Series.
- Part 1 - This Article
- Part 2 - List.Sort internals
- Part 3 - Array.Sort && TrySZSort
- Part 4 - Managed vs Unmanaged code and interop
- Part 5 - Calling Conventions
Welcome to my new series about Sorting and .NET Internals. It has started as a simple question Hey, I wonder how sorting implementation looks like in .NET?. This was planned as one one blog post, quick wrap up and another topic. But when I started reading, I just couldn’t stop asking question Why?. This series is a journey through the code starting with List.Sort() and ending at IntroSort algorithm.
To make it more manageable, I divided this work to two chapters:
Chapter I- .NET internals - fromList<T>.Sort()toTrySZSort- A journey through the code. Starting with
List<T>.Sort()and ending on assembly code level. If you are interested in how .NET and CLR work internally or whatFCall,QCall,P/Invoke,marshallingis. This is must have chapter for you. If you are not interested in .NET internals, you can jump straight ahead toChapter II.
- A journey through the code. Starting with
Chapter II- Sorting in the real world - IntroSort- Going to the details of sorting in the real world. Focusing on Quicksort but also discussing other algorithms pros/cons and trade-offs. This will serve as a great introduciton to explanation why .NET uses
IntroSort. We are also going to discuss .NET implementation ofIntroSort.
- Going to the details of sorting in the real world. Focusing on Quicksort but also discussing other algorithms pros/cons and trade-offs. This will serve as a great introduciton to explanation why .NET uses
Today there is only first part available. Next parts publication is planned to happen in 1-2 weeks time.
Chapter I - .NET Internals:
System.Collections.Generic.List<T>.Sort()_version++- keeping enumaration save from unwanted change
Array.Sort && TrySZSort[System.Security.SecuritySafeCritical]and[ReliabilityContract]Array.CreateInstancevsnew[]- Visual Basic and the world of non one based arrays
Managed vs Unmanaged code and interop- why part of the sorting is in unmanaged code?
- P/Invoke vs InternallCall
- Calling CLR from managed code
- FCall and QCall
How functions communicate on the assemlby level- calling conventions
- fastcall vs cdecl
- [
FCall and __fastcall] (in the making)- stubs and frames
garbage collectionandexceptioninnative CLR codeNanPrePass- Why
0xffffffff= -1
Chapter II - Sorting in the real world - IntoSort:
- Basics Of Quicksort
- Overview of search algorithms - strength and weaknesses
- IntroSort
- CLR implementation