> so it performs almost on par with the mutable dictionary.

I notice you have a comment that says "This trie is now the fastest immutable dictionary I'm aware of". Unfortunately I have to make you aware that my implementation is faster, sorry! ;)

Here's the add-items benchmark:

BenchmarkDotNet=v0.13.5, OS=Windows 11 (10.0.22621.1265/22H2/2022Update/SunValley2)
AMD Ryzen Threadripper PRO 3995WX 64-Cores, 1 CPU, 128 logical and 64 physical cores
.NET SDK=6.0.300
[Host] : .NET 6.0.5 (6.0.522.21309), X64 RyuJIT AVX2
DefaultJob : .NET 6.0.5 (6.0.522.21309), X64 RyuJIT AVX2

| Method | N | Mean |
|-------------------------- |------- |---------------:|
| SysColImmutableDictionary | 100 | 32.315 μs |
| SasaTrie | 100 | 8.007 μs |
| SysColDictionary | 100 | 1.440 μs |
| LangExtHashMap | 100 | 7.512 μs |
|-------------------------- |------- |---------------:|
| SysColImmutableDictionary | 1000 | 524.368 μs |
| SasaTrie | 1000 | 140.537 μs |
| SysColDictionary | 1000 | 17.395 μs |
| LangExtHashMap | 1000 | 125.663 μs |
|-------------------------- |------- |---------------:|
| SysColImmutableDictionary | 10000 | 7,598.532 μs |
| SasaTrie | 10000 | 2,055.220 μs |
| SysColDictionary | 10000 | 301.683 μs |
| LangExtHashMap | 10000 | 1,842.514 μs |
|-------------------------- |------- |---------------:|
| SysColImmutableDictionary | 100000 | 129,811.705 μs |
| SasaTrie | 100000 | 46,752.702 μs |
| SysColDictionary | 100000 | 6,103.999 μs |
| LangExtHashMap | 100000 | 37,869.597 μs |

* SysColImmutableDictionary = System.Collections.Immutable.ImmutableDictionary

* SysColDictionary = System.Collections.Generic.Dictionary

My other benchmarks are still running, so I won't share them all, but we actually trade blows, your ContainsKey appears to be faster, my collection iteration is twice as fast as yours. I suspect if I removed my struct wrapper it would be a bit quicker, but wouldn't be a real-world fair comparison.

We're both much faster than Microsoft's ImmutableCollections though!

I am certainly interested in what that technique is with the nested Node<Node<Node<Node<... and why it works. Do you have any more detail on that? You might also want to look into the data-structure I use: CHAMP [1]. I notice you use HAMT, CHAMP is a more efficient version of HAMT. It has better data-locality, which is much more efficient especially when working with value-types.

With regards to the 'deriving' question: Yeah, I'm working on a more general solution now, as well as a way to do monad-transformers properly. I've also figured out a way to do infinite tail-recursion for my monadic types, which I'll be deploying in the next major update.

[1] https://michael.steindorfer.name/publications/phd-thesis-eff...

* EDIT *

Here's the full suite of benchmarks, but I've trimmed them down to just the 10,000 item tests and removed the error and deviations for clarity:

+-----------------------+----------------+
| Add 10000 items (value type) |
+-----------------------+----------------+
| SasaTrie | 2,055.220 μs |
| LangExtHashMap | 1,842.514 μs |
+-----------------------+----------------+
| Add 10000 items (reference type) |
+-----------------------+----------------+
| SasaTrie | 2,988.663 μs |
| LangExtHashMap | 2,905.552 μs |
+-----------------------+----------------+
| ContainsKey (10000 value items map) |
+-----------------------+----------------+
| SasaTrie | 173,215.0 ns |
| LangExtHashMap | 235,577.2 ns |
+-----------------------+----------------+
| ContainsKey (10000 reference map) |
+-----------------------+----------------+
| SasaTrie | 518.789 μs |
| LangExtHashMap | 549.952 μs |
+-----------------------+----------------+
| Iterate (10000 value items map) |
+-----------------------+----------------+
| SasaTrie | 457,819.0 ns |
| LangExtHashMap | 227,632.7 ns |
+-----------------------+----------------+
| Iterate (10000 references map) |
+-----------------------+----------------+
| SasaTrie | 712,623.1 ns |
| LangExtHashMap | 519,250.7 ns |
+-----------------------+----------------+
| Random remove (10000 value items map) |
+-----------------------+----------------+
| SasaTrie | 2,276,772.4 ns |
| LangExtHashMap | 1,765,042.9 ns |
+-----------------------+----------------+
| Random remove (10000 references map |
+-----------------------+----------------+
| SasaTrie | 2,946.775 μs |
| LangExtHashMap | 2,576.813 μs |
+-----------------------+----------------+