FSharp.HashCollections

Persistent hash based map implementation

Made for my own purposes the goal is to allow faster lookup table performance in F#. After testing some the built in F# Map and other collection implementations across the .NET ecosystem and not being totally satisfied with either the performance and/or the API compromises exposed I decided to code my own for both fun and profit. This is the end result implemented as a customised/optimised HAMT (Hash Mapped Array Trie) for the .NET runtime.

Goals

1. More efficient persistent collection type where F#'s Map type isn't fast enough.
   • At time of writing this was the fastest immutable collections library in the .NET ecosystem I could find (including BCL classes). See Performance Benchmarks for details.
   • Tailor the algorithms used to the .NET ecosystem to achieve better performance.
2. Allow a range of key types and equality logic to be used even if provided by consumers without sacrificing performance (e.g. no need for keys to be comparable).
   • Custom equality comparers can be provided, unlike the standard F# Map/Set data types.
3. Provide an idiomatic API to F#. The library ideally should allow C# usage/interop if required.
   • HashMap and HashSet static classes are usable from C# as wrappers. Performance optimisations (e.g. inlining) are applied at compile time where possible.
4. Maintainable to an average F# developer.
   • For example minimising inheritance/object hierarchies and casting (unlike some other impl's I've seen), performant whilst still idiomatic code, etc.
   • Use F# strengths to increase performance further (e.g. inlining + DU's to avoid method calls and copying overhead affecting struct key performance).
5. Performance at least at the same scale as other languages of the same class/abstraction level (e.g JVM, etc).

TLDR; Benefits of immutable collections while minimising the cost (e.g. performance, maintainable code, idiomatic code, etc).

Use Cases

• Large collections at acceptable performance (e.g. 500,000+ elements).
• Immutability of large/deep object graphs without the associated performance cost of changing data deep in the hierarchy.
  • A common pattern when changing data deep in nested records. Instead of using the record copy syntax to change these flatten out of object and use HashMaps instead joining by key. Often useful to store a large hierarchy of state and update it in an atomic fashion.
• Where the key type of the Map would otherwise not work with standard F# collections since it does not implement IComparable.

Collection Types Provided

All collections are persisted/immutable by nature so any Add/Remove operation produces a new collection instance. Most methods mirror the F# built in Map and Set module (e.g. Map.tryFind vs HashMap.tryFind) allowing in many cases this library to be used as a drop in replacement where appropriate.

• HashMap (Similar to F#'s Map in behaviour).

Operation	Complexity
TryFind	O(log32n)
Add	O(log32n)
Remove	O(log32n)
Count	O(1)
Equals	O(n)

Example Usage:

open FSharp.HashCollections
let hashMapResult = HashMap.empty |> HashMap.add k v |> HashMay.tryFind k // Result is ValueSome(v)

• HashSet (Similar to F#'s Set in behaviour).

Operation	Complexity
Contains	O(log32n)
Add	O(log32n)
Remove	O(log32n)
Count	O(1)
Equals	O(n)

Example Usage:

open FSharp.HashCollections
let hashMapResult = HashSet.empty |> HashSet.add k |> HashSet.contains k // Result is true

Equality customisation

By default any "empty" seeded HashSet/Map uses F# HashIdentity.Structural comparison to determine equality and calculate hashcodes. This is in line with the F# collection types.

In addition all collection types allow custom equality to be assigned if required. The equality is encoded as a type on the collection so equality and hashing operations are consistent. Same collection types with different equality comparers can not be used interchangeably by operations provided. To use:

// Uses the default equality template provided.
let defaultIntHashMap : HashMap<int, int64> = HashMap.empty

// Uses a custom equality template provided by the type parameter.
let customEqIntHashMap : HashMap<int, int64, CustomEqualityComparer> = HashMap.emptyWithComparer

Any equality comparer specified in the type signature must:

• Have a parameterless public constructor.
• Implement IEqualityComparer<> for either the contents (HashSet) or the key (HashMap).
• (Optional): Be a struct type. This is recommended for performance as it produces more optimised equality checking code at runtime.

An example with the type "Int" for the custom equality comparer (which in testing exhibits slightly faster perf than the default):

type IntEqualityTemplate =
    struct end
    interface System.Collections.Generic.IEqualityComparer<int> with
        member __.Equals(x: int, y: int): bool = x = y
        member __.GetHashCode(obj: int): int = hash obj // Or just obj

module Usage =
    // Type is HashMap<int, int64, IntEqualityTemplate>
    let empty = HashMap.emptyWithComparer<_, int64, IntEqualityTemplate>

Performance Benchmarks

TryFind on HashMap

Keys are of type int32 where "GetHashMap" represents this library's HashMap collection.

All are using F# HashIdentity.Structural comparison.

See ReadBenchmark

BenchmarkDotNet=v0.13.1, OS=arch 
AMD Ryzen 7 3700X, 1 CPU, 16 logical and 8 physical cores
.NET SDK=6.0.403
  [Host]     : .NET 6.0.11 (6.0.1122.52304), X64 RyuJIT DEBUG
  DefaultJob : .NET 6.0.11 (6.0.1122.52304), X64 RyuJIT

Method	CollectionSize	Mean	Error	StdDev
GetHashMap	10	11.49 ns	0.091 ns	0.081 ns
GetImToolsHashMap	10	31.58 ns	0.190 ns	0.169 ns
GetFSharpMap	10	26.97 ns	0.208 ns	0.194 ns
GetFSharpXHashMap	10	129.21 ns	0.806 ns	0.754 ns
GetSystemCollectionsImmutableMap	10	21.80 ns	0.325 ns	0.304 ns
GetFSharpDataAdaptiveMap	10	22.95 ns	0.234 ns	0.219 ns
GetFSharpxChampMap	10	72.75 ns	0.439 ns	0.367 ns
GetLangExtMap	10	24.83 ns	0.218 ns	0.193 ns
GetHashMap	100	11.75 ns	0.120 ns	0.112 ns
GetImToolsHashMap	100	44.99 ns	0.358 ns	0.317 ns
GetFSharpMap	100	47.45 ns	0.418 ns	0.391 ns
GetFSharpXHashMap	100	148.55 ns	0.919 ns	0.815 ns
GetSystemCollectionsImmutableMap	100	33.26 ns	0.246 ns	0.230 ns
GetFSharpDataAdaptiveMap	100	44.84 ns	0.400 ns	0.374 ns
GetFSharpxChampMap	100	83.54 ns	1.017 ns	0.951 ns
GetLangExtMap	100	31.26 ns	0.264 ns	0.247 ns
GetHashMap	1000	11.67 ns	0.090 ns	0.084 ns
GetImToolsHashMap	1000	69.63 ns	0.974 ns	0.911 ns
GetFSharpMap	1000	71.16 ns	0.762 ns	0.713 ns
GetFSharpXHashMap	1000	161.89 ns	0.539 ns	0.450 ns
GetSystemCollectionsImmutableMap	1000	49.93 ns	0.489 ns	0.458 ns
GetFSharpDataAdaptiveMap	1000	67.05 ns	0.725 ns	0.678 ns
GetFSharpxChampMap	1000	84.44 ns	1.061 ns	0.992 ns
GetLangExtMap	1000	31.00 ns	0.312 ns	0.292 ns
GetHashMap	100000	33.47 ns	0.376 ns	0.314 ns
GetImToolsHashMap	100000	216.79 ns	4.285 ns	4.009 ns
GetFSharpMap	100000	177.11 ns	2.074 ns	1.940 ns
GetFSharpXHashMap	100000	231.84 ns	4.178 ns	6.627 ns
GetSystemCollectionsImmutableMap	100000	162.46 ns	2.537 ns	2.374 ns
GetFSharpDataAdaptiveMap	100000	154.96 ns	2.743 ns	2.566 ns
GetFSharpxChampMap	100000	114.73 ns	1.243 ns	1.163 ns
GetLangExtMap	100000	61.52 ns	0.609 ns	0.570 ns
GetHashMap	500000	35.67 ns	0.622 ns	0.582 ns
GetImToolsHashMap	500000	528.33 ns	10.475 ns	12.063 ns
GetFSharpMap	500000	327.39 ns	6.410 ns	11.881 ns
GetFSharpXHashMap	500000	336.89 ns	5.012 ns	4.688 ns
GetSystemCollectionsImmutableMap	500000	359.41 ns	7.174 ns	11.787 ns
GetFSharpDataAdaptiveMap	500000	324.83 ns	6.091 ns	5.982 ns
GetFSharpxChampMap	500000	122.62 ns	1.997 ns	2.137 ns
GetLangExtMap	500000	67.00 ns	1.128 ns	1.055 ns
GetHashMap	750000	38.42 ns	0.513 ns	0.428 ns
GetImToolsHashMap	750000	639.63 ns	12.341 ns	14.691 ns
GetFSharpMap	750000	429.89 ns	8.344 ns	10.247 ns
GetFSharpXHashMap	750000	446.19 ns	5.108 ns	4.778 ns
GetSystemCollectionsImmutableMap	750000	440.76 ns	8.714 ns	10.035 ns
GetFSharpDataAdaptiveMap	750000	364.25 ns	7.225 ns	6.758 ns
GetFSharpxChampMap	750000	128.73 ns	2.571 ns	3.848 ns
GetLangExtMap	750000	72.10 ns	1.426 ns	1.334 ns
GetHashMap	1000000	41.58 ns	0.804 ns	0.752 ns
GetImToolsHashMap	1000000	716.12 ns	13.576 ns	12.699 ns
GetFSharpMap	1000000	478.64 ns	9.391 ns	11.877 ns
GetFSharpXHashMap	1000000	426.63 ns	4.339 ns	4.059 ns
GetSystemCollectionsImmutableMap	1000000	506.48 ns	9.872 ns	9.695 ns
GetFSharpDataAdaptiveMap	1000000	395.59 ns	5.966 ns	5.581 ns
GetFSharpxChampMap	1000000	132.05 ns	2.585 ns	4.319 ns
GetLangExtMap	1000000	79.30 ns	1.577 ns	2.408 ns
GetHashMap	5000000	155.94 ns	0.957 ns	0.799 ns
GetImToolsHashMap	5000000	1,138.25 ns	18.869 ns	17.650 ns
GetFSharpMap	5000000	823.41 ns	10.984 ns	10.274 ns
GetFSharpXHashMap	5000000	475.15 ns	6.462 ns	6.044 ns
GetSystemCollectionsImmutableMap	5000000	826.09 ns	15.213 ns	14.230 ns
GetFSharpDataAdaptiveMap	5000000	579.94 ns	6.645 ns	6.216 ns
GetFSharpxChampMap	5000000	285.59 ns	3.235 ns	3.026 ns
GetLangExtMap	5000000	234.92 ns	3.571 ns	3.341 ns
GetHashMap	10000000	159.87 ns	2.199 ns	1.950 ns
GetImToolsHashMap	10000000	1,345.84 ns	26.844 ns	26.364 ns
GetFSharpMap	10000000	957.82 ns	14.825 ns	13.868 ns
GetFSharpXHashMap	10000000	509.87 ns	9.244 ns	8.647 ns
GetSystemCollectionsImmutableMap	10000000	960.39 ns	18.921 ns	17.699 ns
GetFSharpDataAdaptiveMap	10000000	672.11 ns	9.232 ns	8.636 ns
GetFSharpxChampMap	10000000	291.37 ns	3.615 ns	3.381 ns
GetLangExtMap	10000000	237.09 ns	3.173 ns	2.968 ns

Add on HashMap

Scenario: Adding 50 elements on top of a pre-defined collection with a collection size as specified, average time of each of the 50 inserts:

See AddBenchmark

OfSeq on HashMap

See OfSeq Benchmark

An outside .NET ecosystem comparison.

This section is simply a guide to give a ballpark comparison figure on performance with implementations from other languages that have standard HAMT implementations for my own technical selection evaluation.

TL;DR: The "Get" method where performance is significantly better as the collection scales up. For example at 10,000,000 FSharp collection is approx 3.59 faster, and 1.73x faster at building the initial hashmap.

• TryFind: Measures fetching every key inside a collection of a given size (total milliseconds).
• OfSeq: Measures building a HashMap of the given collection size (total milliseconds).

Lang	Operation	100	1000	10000	100000	500000	1000000	5000000	10000000	50000000
F#	TryFind	0	0	0	5	37	94	495	1142	9346
Scala	TryFind	0	0	3	17	111	256	1863	4111	32318
F#	OfSeq	0	0	3	30	146	219	1321	3080	19160
Scala	OfSeq	0	0	5	49	163	387	2516	5347	43827

Platforms tested: Dotnet version: 5.0.301, Scala code runner version 2.13.6-20210529-211702.

Note that most of the optimisation work I have done is around the "Get" method given my use case (lots of reads, fewer but still significant write load with large collections 500,000+ items).

Design decisions that may affect consumers of this library

Any of these decisions may change in the future as I gain knowledge, change my mind, etc. It doesn't list all the tweaks, and changes caused by benchmarking just the things that affect consumers. Many besides equality checking shouldn't affect the API dramatically; and if they do it should remain easy to port code to the new API as appropriate.

1. Writing in F# vs C#

   • Performance tweaks found in my trial and error experiments (structs, inlining, etc) are easier to unlock and use in F# requiring less code. Inlining is used for algorithm sharing across collection types, avoiding struct copying with returned results, etc.

2. Count is a O(1) operation. This requires an extra bit of space per tree and minor overhead during insert and removal but allows other operations on the read side to be faster (e.g isEmpty, count, intersect, etc.).

   • ✅ Lower time complexity for existence and count operations.
   • ❌ Slightly more work required when inserting and removing elements keeping track of addition or removal success.

3. NetCoreApp3.1 only or greater. This allows the use of .NET intrinsics and other performance enhancements.

   • ✅ Faster implementation.
   • ❌ Only Net Core 3.1 compatible or greater.