[wmccullough]

> "It out performs Microsoft’s generic SortedDictionary<TKey, TValue> (which is actually a red-black tree) by a factor of 2 for inserts and a factor of 4 for searches."

I may have missed it, but I'd love to know the versions of .net framework this was performed against. I saw a really interesting post in MSDN about how they've been working on performance improvements for underlying data structures. I would love to see this up against dotnet core 2.1 or >. For reference, this was the post:

https://blogs.msdn.microsoft.com/dotnet/2018/04/18/performan...

[thrower123]

I'm not sure I've ever used a SortedDictionary in real code. Almost always just a Dictionary or often ConcurrentDictionary.

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