Our great sponsors
-
-
F#
Discontinued Please file issues or pull requests here: https://github.com/dotnet/fsharp (by fsharp)
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
-
-
Collections.Pooled
Fast, low-allocation ports of List, Dictionary, HashSet, Stack, and Queue using ArrayPool and Span.
I believe the article is slightly incorrect, at least today. If you look at the source code of ImmutableDictonary, it first uses a specialized AVL tree on the int32 hash of the key and then for hash collisions it stores another AVL tree, so it is not just a direct tree on the keys as the article alleges. The first AVL tree on the int32 hashes is specialized to int32 so comparisons are very fast.
The builtin fsharp collections actually are just "immutable", not persistent as you mention. (Ref: https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/map.fs. This is just an AVL tree that returns a copy on mutations: https://github.com/fsharp/fsharp/blob/577d06b9ec7192a6adafefd09ade0ed10b13897d/src/fsharp/FSharp.Core/map.fs#L118)
In practice you don't know which one is faster except for very large n. Would be interesting to benchmark the clojure data structures with jmh and the .net immutable data structures with benchmarkdotnet for different n and compare the results.
You can gain some perf using https://github.com/jtmueller/Collections.Pooled