- Part 1 - Journey through the internals of .NET Sort
- Part 2 - Everything you wanted to know about Sorting in .NET - part I
- Part 3 - Everything you wanted to know about Sorting in .NET part 3
- Part 4 - Everything you wanted to know about Sorting in .NET part 2
- Part 5 - This Article
- Part 6 - Everything you wanted to know about Sorting in .NET part 5
- Part 7 - Everything you wanted to know about Sorting in .NET part 4
This contract tells the compiler and macro certaing
properties of the code it is applied to.
« NEED EXPERT HERE »
- STATIC_CONTRACT_SO_TOLERANT It means that the function can cope with Stack Overflow exception. When the function is SO_TOLERANT SO_TOLERANT disables stack guard and stack probing this function doesnt generate any global state and can just die + we cant actually check if SO will be violated?
There are couple of cases when you code cannot tollerate stack overflow:
- your code updates global state that neesd to be cleaned up
If you want to have a function that is SO Intollerant you need to use SO Probe to propely clean up resources generated by this function. SO probe is generated by using macto SO_INTOLERANT_XXX
SO probe - is a tool to identify if there is enough space on SO to do the operation. For instance during object allocation Stack Probe is used to determine if tthere is more than enough space on the Stack.
IF SO probing is disabled all the code is considere SO Intolerant. IF there is SO in intolerant code the proces is killed IF there is so in tolertant code and GC mode is preemptive the proces is killed If there is a SO in Cooperative mode the domain is unloaded (by GC) or the process is killed if this is a default domain
There are two types of SO - hard and soft (soft is when Stack Probe is acctive) https://github.com/dotnet/coreclr/blob/35da2c8a07d7aef8bd4c874b81241bab52af83ce/src/inc/ex.h#L132
INTOLLERANT is the default state
- STATIC_CONTRACT_GC_NOTRIGGER - this function cannot trigger
Garbage Collectionif this is also coop mode
Why you need to block GC?
STATIC_CONTRACT_THROWS - this function can throw Exception Why would you block exception throws?
GC MODE on Entry? https://github.com/dotnet/coreclr/blob/32f0f9721afb584b4a14d69135bea7ddc129f755/src/inc/contract.h#L33
VALIDATEOBJECT is a diffferent
FCALL - not sure what it does but I would assume that it is just a check if args and params are Valid somehow - maybe null check etc «EXPERT ADVICE NEEDED HERE»
_ASSERTE -> https://msdn.microsoft.com/en-us/library/ezb1wyez.aspx
All right, now we are getting to something meaty. First thing to spot here - TODO mentioning that VB non zero based array support was not added and is not supported. If this is non zero based array we just return with False
Another two preconditions which may force the code to end prematurely.
- first checkin if the sorted array contain only primitive types
- second type of key is verified if has the same type as the items… wait what? arent’t we sorting array? Sure we are and that is why
itemsin this scenario is null thus we dont check the other preconditions. TrySZSort not only supports arrays with only items but also by SortedList that is implementation of IDictionary - has both keys and items. Entry point for this function is here
You cannot sort SortedList but when it is created it Uses
Array.Sort to generate initial sorted state. When new items are inserted Binary Serach is used to idenfity the index and place to insert new item.
left == right - cover scenario when slice of arrays is being sorted that has a length of
right have the same value in that case.
But what is
0xfffffffff? and why right is checked for it?
0xfffffffff is a represantion of
-1 in Two complement system. How is
To create value in two complement:
- take one complement value
- add + 1
if we take 32 bits values
then 1 in Binary will be -> 0x00000001 = 00000000 00000000 00000000 00000001
-1in the one complement is the opposite = 0xFFFFFFFE -> 11111111 11111111 11111111 1111110
to make it two complement we need to add +1 so
0xFFFFFFFE + 1 = 0xFFFFFFFF
To check if that is the correct value we do arithmetic
-1 = 0
Why then use
0xfffffffff instead of
-1. I got help from a friend krzaq with this one.
right argument is of type
UINT32. It is a unsiged value for which
-1 doesn’t exist. But in order to still be able to check if it is
-1 you have to use
-1 might work it would be depend on the compiler implementation how situation like that is handled. With
0xfffffffff you can be sure that code works correclty. more-details
I also checked how will compiler behave in scenario with 0xFFFFFFFF using Compiler Explorer
This switch statement is used to check which generic implementation of IntrospectiveSort will be used.
To find what does ELEMENT_TYPE_I1 there are two resources.
Based on that we get this nice mapping
IntPTR and UINTPTr is not supported.
For Float and Double there is a special case.
Before doing any sorting there is a Function
This function in O(n) iterates through the list and moves all the
NULL values to the left changing list start position to be the first element that is not
NULL. Why not treating
NULL as a value < 0 and just sort it with the rest of values? There is a crucial note for that.
Prepass is required to get rid of unspecified behaviour. If comparison to NaN always yields false then
1 >= Nan = false and
Nan >= 1 = false. It makes it imossible to make ‘deterministic’ comparisons.
This operation is O(n). Later on
IntroSort (more on it soon) algorithm is used to sort. It has oworst and average O(nlogn) so the complexity of doing
O(nlogn) + O(n). nlogn is bigger than O(n) so the overall complexity is O(nlogn) as with Big O notation the most significant component is taking over.
We have covered special scenario of Double types.
primitive type is simple integer, IntrospectiveSort function is called without any other logic.
Is it time to get to the sorting algorithm itself - yes it is.