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

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 Benchmark

Adding a million keys

Add and resize

Updating a million keys

Removing a million keys

Add and resize

Get string benchmark using XXHash3StringHasher

Add string benchmark