Performance of immutable collections in .NET

This page summarizes the projects mentioned and recommended in the original post on reddit.com/r/dotnet

Our great sponsors
  • SonarQube - Static code analysis for 29 languages.
  • talent.io - Download talent.io’s Tech Salary Report
  • Scout APM - Less time debugging, more time building
  • .NET Runtime

    .NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.

    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.

  • F#

    Please file issues or pull requests here: https://github.com/dotnet/fsharp (by fsharp)

    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)

  • SonarQube

    Static code analysis for 29 languages.. Your projects are multi-language. So is SonarQube analysis. Find Bugs, Vulnerabilities, Security Hotspots, and Code Smells so you can release quality code every time. Get started analyzing your projects today for free.

  • jmh

    https://openjdk.org/projects/code-tools/jmh

    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.

  • Collections.Pooled

    Fast, low-allocation ports of List, Dictionary, HashSet, Stack, and Queue using ArrayPool and Span.

    You can gain some perf using https://github.com/jtmueller/Collections.Pooled

NOTE: The number of mentions on this list indicates mentions on common posts plus user suggested alternatives. Hence, a higher number means a more popular project.

Suggest a related project

Related posts