The Fastest .NET Dictionary… With F#
summary
A custom F# dictionary claims faster reads than System.Collections.Generic.Dictionary and FrozenDictionary by iterative engineering: using BenchmarkDotNet, dotTrace, vTune to guide changes, eliminating allocations via EqualityComparer.GetHashCode and EqualityComparer.Equals, replacing mod with Fibonacci hashing (power‑of‑two buckets), moving from separate chaining to open addressing, then a byte list (embedded buckets + byte "next" offsets) and finally a shift‑and‑mask uniquifier that yields near‑perfect hashing for strings and beats FrozenDictionary for many string workloads.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 3:12Benchmarking .NET collections
- 6:26Starting the experiment
- 7:29Naive dictionary flaws
- 11:18Eliminating allocations
- 14:08Fibonacci hashing
- 18:03String keys performance
- 22:21Cache misses reduction
- 26:18Linear probing problems
- 29:37Robin Hood hashing
- 31:21Byte list approach
- 34:56Frozen dictionary race
- 36:41Struct of arrays
- 39:53Perfect hash functions
- 49:56Next steps for .NET
- 51:42Optimization lessons
- 54:49Q&A
related talks
01h 03mF# for Performance-Critical Code
01h 04mTurbocharged: Writing High-Performance C# and .NET Code
01h 09mPatterns for high-performance C#
56mState of the .NET Performance
01h 14mTurbocharged: Writing High-performance C# and .NET code
59mWriting (in)efficient C#
57mF# Code I Love
01h 00mF# for the C# Developer - F#, the .NET Runtime, and Aesthetics