Change immutable map implementation

[Horusiath]

Right now our IImmutableMap<TKey, TValue> implementation is based on AVL trees. It's used i.e. in child actors containers. However it has some known perf issues when it comes to adding new child actors. Also current impl doesn't support range queries, which will be highly desirable i.e. in Akka.Cluster.Tools plugin.

The idea is to switch implementation to Red-Black trees (like the ones used in Scala implementation). Any other ideas? @akkadotnet/developers

[rogeralsing]

We should give this a try imo. the AVL tree is horribly slow when inserting a lot of children.

[Aaronontheweb]

Related? #1202

[kbaldyga]

Hi, I have been playing with the Red-Black tree implementation for the last few days. It's not complete yet, but you can check out the current code here: https://github.com/kbaldyga/Tree

Before (if) I start working on a pull-request integrating this with akka.net, I have few questions:

• Is F# code acceptable?
• I don't know much about akka.net. @rogeralsing, when you are saying "AVL tree is horribly slow when inserting a lot of children", is there a specific number of children you have in mind? Hundreds? Thousands? Millions? What is the desired speed improvement? 5%? 500%? Doesn't matter, as long as it fixes the null reference exception?
• @Horusiath what would be the interface for those range queries you have in mind? Would you like to see a 1-to-1 copy of the current scala implementation? Something different?

[Aaronontheweb]

Is F# code acceptable?

It'd need to be in C# so we can integrate it into the core library (C#)

[boekabart]

The AVL null ref exception is fixed in PR #1645 . Other reasons obviously stand.

[Aaronontheweb]

Resolved as part of #1676