Faster.Map 5.0.3

dotnet add package Faster.Map --version 5.0.3
NuGet\Install-Package Faster.Map -Version 5.0.3
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package.
<PackageReference Include="Faster.Map" Version="5.0.3" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add Faster.Map --version 5.0.3
#r "nuget: Faster.Map, 5.0.3"
#r directive can be used in F# Interactive and Polyglot Notebooks. Copy this into the interactive tool or source code of the script to reference the package.
// Install Faster.Map as a Cake Addin
#addin nuget:?package=Faster.Map&version=5.0.3

// Install Faster.Map as a Cake Tool
#tool nuget:?package=Faster.Map&version=5.0.3

Faster.Map

The goal of Faster is to provide an incredible fast hashmap, faster than the default in .net which is currently the dictionary. During the years we've tried lots of different types of hashmaps for example robinhood hashing or hashmaps using quadratic probing. All of them have beat the dictionary in terms of performance. But since the release of SIMD instructions in dotNetCore we tried a different approach which is well described in https://abseil.io/about/design/swisstables or https://faultlore.com/blah/hashbrown-tldr/

High level concepts of DenseMap to keep in mind:

  • open-addressing
  • searches in parallel using SIMD
  • first come first serve collision resolution
  • chunked (SIMD) triangular (quadratic-ish) probing
  • tombstones to avoid backshifts
  • The default loadfactor is 0.9
  • It's mindblowingly fast
  1. Install nuget package Faster.Map to your project.
dotnet add package Faster.Map

How to use

DenseMap Example

private DenseMap<uint, uint> _map = new DenseMap<uint, uint>(16);
 _map.Emplace(1, 50); 
 _map.Remove(1);
 _map.Get(1, out var result);
 _map.Update(1, 51);
 _map.AddOrUpdate(1, 50);

 ref var x = _map.GetOrAdd(1);

Tested on platforms:

  • x86
  • x64
  • arm
  • arm64

Benchmark


BenchmarkDotNet v0.13.8, Windows 11 (10.0.22621.2428/22H2/2022Update/SunValley2)
12th Gen Intel Core i5-12500H, 1 CPU, 16 logical and 12 physical cores
.NET SDK 8.0.100-rc.1.23463.5
  [Host]     : .NET 8.0.0 (8.0.23.41904), X64 RyuJIT AVX2
  DefaultJob : .NET 8.0.0 (8.0.23.41904), X64 RyuJIT AVX2

### Retrieving a million random generated keys

| Method         | Mean      | Error     | StdDev    | Code Size | Allocated |
|--------------- |----------:|----------:|----------:|----------:|----------:|
| DenseMap       |  5.191 ms | 0.0668 ms | 0.0592 ms |     276 B |       6 B |
| SlimDictionary |  9.589 ms | 0.1804 ms | 0.1687 ms |     393 B |      12 B |
| Dictionary     | 16.974 ms | 0.7074 ms | 2.0859 ms |     400 B |      12 B |

### Adding a million keys

| Method         | Mean     | Error    | StdDev   | Median   | Code Size | Allocated  |
|--------------- |---------:|---------:|---------:|---------:|----------:|-----------:|
| DenseMap       | 12.64 ms | 0.376 ms | 1.108 ms | 13.81 ms |     383 B |      736 B |
| Dictionary     | 16.57 ms | 0.454 ms | 1.317 ms | 16.65 ms |     741 B |      736 B |
| DictionarySlim | 22.62 ms | 0.449 ms | 0.876 ms | 22.44 ms |     367 B |      736 B |

### Updating a million keys
| Method        | Mean      | Error     | StdDev    |
| DenseMap      |  5.271 ms | 0.0498 ms | 0.0416 ms |
| DictionarySlim| 11.188 ms | 0.1745 ms | 0.1457 ms |

### Removing a million keys

| Method         | Mean      | Error     | StdDev    |
|--------------- |----------:|----------:|----------:|
| DenseMap       |  8.811 ms | 0.1762 ms | 0.4321 ms |
| SlimDictionary | 13.150 ms | 0.2602 ms | 0.6134 ms |
| Dictionary     | 17.063 ms | 0.3516 ms | 1.0313 ms |

### Add and resize
| Method         | Mean     | Error    | StdDev   | Median   |
|--------------- |---------:|---------:|---------:|---------:|
| DenseMap       | 14.19 ms | 0.722 ms | 2.119 ms | 14.98 ms |
| Dictionary     | 31.30 ms | 0.624 ms | 1.590 ms | 30.98 ms |
| DictionarySlim | 22.63 ms | 0.451 ms | 0.980 ms | 22.55 ms |

Product Compatible and additional computed target framework versions.
.NET net8.0 is compatible.  net8.0-android was computed.  net8.0-browser was computed.  net8.0-ios was computed.  net8.0-maccatalyst was computed.  net8.0-macos was computed.  net8.0-tvos was computed.  net8.0-windows was computed. 
Compatible target framework(s)
Included target framework(s) (in package)
Learn more about Target Frameworks and .NET Standard.
  • net8.0

    • No dependencies.

NuGet packages (2)

Showing the top 2 NuGet packages that depend on Faster.Map:

Package Downloads
Faster.Ioc

Package Description

UPSRestApi

UpsRestApi library for .Net used to access UPS API Catalog to browse products and view documentation.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
5.0.3 369 11/18/2023
5.0.2 160 10/29/2023
5.0.1 97 10/29/2023
5.0.0 126 10/28/2023
4.2.1 261 9/2/2023
4.2.0 1,368 4/24/2023
4.1.6 208 4/24/2023
4.1.5 317 3/19/2023
4.1.4 313 3/14/2023
4.1.3 263 3/14/2023
4.1.2 236 3/14/2023
4.1.1 830 3/10/2023
4.1.0 275 3/9/2023
4.0.9 261 3/9/2023
4.0.8 253 3/9/2023
4.0.7 285 3/6/2023
4.0.6 304 3/3/2023
4.0.5 293 3/1/2023
4.0.4 366 2/24/2023
4.0.3 327 2/23/2023
4.0.2 1,098 1/7/2023
4.0.1 362 1/6/2023
4.0.0 345 1/4/2023
3.0.4.2 687 12/22/2022
3.0.3.9 1,000 12/9/2022
3.0.3.8 725 11/8/2022
3.0.3.7 484 10/27/2022
3.0.3.6 501 10/18/2022
3.0.3.5 403 10/18/2022
3.0.3.4 1,057 9/20/2022
3.0.3.3 1,224 5/19/2022
3.0.3.2 453 5/17/2022
3.0.3.1 446 5/17/2022
3.0.3 448 5/17/2022
3.0.2 459 5/15/2022

Missing Resize in GetOrAdd method