[NicoJuicy]

The algorithm is faster, it's not about the underlying framework.

Eg, if they test this against SortedDictionary in cotnet core, they should also implement the mentioned algorithm in dotnet core.

I think what they mean is, their algorithm is faster than the red-black tree algorithm.

[lozenge]

But there's nothing preventing Microsoft from changing SortedDictionary to use an AVL tree. The asymptotic complexity of all the operations would be the same.

[wmccullough]

I'm actually tempted to do a PR against dotnet to see if they'd accept this improvement. My guess is that just like with Roslyn, customers have come to count on the implementation, bugs and all, and it may not be accepted.

[kristianp]

But they didn't, did they? Their performance optimizations have usually been at a lower level, fixing inefficient code and speeding hot paths, e.g.:

https://blogs.msdn.microsoft.com/dotnet/2017/06/07/performan...

[wmccullough]

Maybe I misunderstood, but I could swear they reworked a ton of their algorithms as part of this effort.