Awesome

Faster.Map

The goal of Faster.Map is to create a more efficient and performant alternative to the Dictionary and ConcurrentDictionary classes provided by .NET. These standard collections are widely used for key-value pair storage in .NET applications, but they have certain limitations, particularly in high-performance and concurrent scenarios.

Available Implementations:

• DenseMap with SIMD Instructions: Harnesses SIMD (Single Instruction, Multiple Data) instructions for parallel processing, resulting in accelerated lookup times. Ideal for scenarios demanding high throughput and optimal CPU utilization.

• RobinHoodMap with Linear Probing: Employs linear probing to resolve hash collisions, reducing the likelihood of clustering and improving access speed. Suitable for applications where a balance between performance and simplicity is required.

• CMap is a high-performance, thread-safe, lockfree concurrent hashmap that uses open addressing, quadratic probing, and Fibonacci hashing to manage key-value pairs. The default load factor is set to 0.5, meaning the hash map will resize when it is half full. Note: this hashmap will only allocate once while resizing.

• Installation:

You can include Faster.Map in your C# project via NuGet Package Manager:

Install-Package Faster.Map

Basic Usage

Default Hasher

By default, DenseMap uses the DefaultHasher<TKey>, which computes hashes based on the .NET GetHashCode method and uses Knuth's Multiplicative Hashing

var map = new DenseMap<int, string>();
map.Emplace(1, "Value One");
map.Emplace(2, "Value Two");

if (map.Get(1, out var value))
{
    Console.WriteLine($"Key 1 has value: {value}");
}

map.Remove(1);

Custom Hasher

By default, Faster.Map provides four built-in hashers, each optimized for different performance characteristics:

DefaultHasher GxHasher XxHash3StringHasher XxHash3Hasher

You can provide your own IHasher<TKey> implementation to customize hash computation.

Step 1: Implement a Custom Hasher

public class CustomIntHasher : IHasher<int>
{
    public ulong ComputeHash(int key)
    {
        return (ulong)(key * 2654435761); // Multiplicative hashing
    }
}

Step 2: Use the Custom Hasher in DenseMap

var customHasher = new CustomIntHasher();
var map = new DenseMap<int, string>(customHasher);

map.Emplace(1, "Value One");
map.Emplace(42, "Value Two");

if (map.Get(42, out var value))
{
    Console.WriteLine($"Key 42 has value: {value}");
}

map.Update(42, "Updated Value Two");
map.Remove(1);

Advanced Example: Hashing Strings with XxHash

Custom String Hasher

public class XxHash3StringHasher : IHasher<string>
{
    public ulong ComputeHash(string key)
    {
        return XxHash3.HashToUInt64(MemoryMarshal.AsBytes(key.AsSpan()));
    }
}

Using the String Hasher

var stringHasher = new XxHash3StringHasher();
var stringMap = new DenseMap<string, int>(stringHasher);

stringMap.Emplace("Hello", 100);
stringMap.Emplace("World", 200);

if (stringMap.Get("Hello", out var value))
{
    Console.WriteLine($"Key 'Hello' has value: {value}");
}

stringMap.Remove("World");

Tested on platforms:

• x86
• x64
• arm
• arm64

Benchmark

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3880/23H2/2023Update/SunValley3)
12th Gen Intel Core i5-12500H, 1 CPU, 16 logical and 12 physical cores
.NET SDK 9.0.100-preview.2.24157.14
  [Host]     : .NET 9.0.0 (9.0.24.12805), X64 RyuJIT AVX2
  DefaultJob : .NET 9.0.0 (9.0.24.12805), X64 RyuJIT AVX2

Get Uint Benchmark

Adding a million keys

Add and resize

Updating a million keys

Removing a million keys

Get String Benchmark

This benchmark compares the performance of different hash map implementations for various input sizes. The Mean (ms) column represents the average time taken for each operation. The fastest implementation for each input size is highlighted in bold.

🏆 indicates the fastest implementation for each input size.

Add string benchmark

🏆 indicates the fastest implementation for each input size.