SimdQuickHeap

A high-performance C#/.NET priority queue inspired by the 2026 SimdQuickHeap paper.

What Is This?

SimdQuickHeap<TElement, TPriority> is a fast priority queue for .NET.

A priority queue is the data structure you use when you always want to take the "most urgent" item first. For example:

• the next task a scheduler should run
• the next event in a simulation
• the next cheapest node in a graph search
• the next message or job with the smallest priority value

.NET already has PriorityQueue<TElement, TPriority>. SimdQuickHeap is built for cases where the queue gets large and performance starts to matter.

Why It Is Different

Most heaps store items in one tree-like array. SimdQuickHeap uses a layout from the paper SimdQuickHeap: The QuickHeap Reconsidered:

• pivots are stored next to each other in memory
• items live in dedicated buckets between those pivots
• integer priority comparisons can be done in chunks with SIMD CPU instructions
• large buckets are partitioned quickly instead of bubbling one item at a time

In simple terms: it organizes memory so modern CPUs can compare and move many priorities at once.

Current Status

This repo is usable today for large online priority queues with default int or long priorities.

It currently includes:

• net8.0 and net10.0 targets
• generic SimdQuickHeap<TElement, TPriority>
• min-priority behavior by default
• custom comparer support
• Enqueue, Dequeue, TryDequeue, Peek, TryPeek
• Push and Pop aliases
• capacity helpers: EnsureCapacity, TrimExcess, Clear
• lock-based synchronized wrapper
• SIMD pivot scanning for default integer priorities
• SIMD-assisted partitioning for int and long priorities
• AVX2 packed partitioning for SimdQuickHeap<int, int>
• .NET 10 AVX-512 compress-store path for SimdQuickHeap<int, int>
• BenchmarkDotNet benchmark suite
• GitHub Actions build, test, and package workflow

Quick Start

using SimdQuickHeap;

var heap = new SimdQuickHeap<string, int>();

heap.Enqueue("compile", 20);
heap.Enqueue("ship", 10);
heap.Enqueue("benchmark", 30);

string next = heap.Dequeue();

Console.WriteLine(next); // ship

Lower priority values come out first by default, just like a min-heap.

API At A Glance

var heap = new SimdQuickHeap<int, int>(capacity: 100_000);

heap.Enqueue(42, priority: 10);
heap.Push(99, priority: 5);

int best = heap.Dequeue();

if (heap.TryDequeue(out int item, out int priority))
{
    Console.WriteLine($"{item} had priority {priority}");
}

if (heap.TryPeek(out int nextItem, out int nextPriority))
{
    Console.WriteLine($"Next: {nextItem}, priority {nextPriority}");
}

Custom ordering is supported:

IComparer<int> highestFirst = Comparer<int>.Create((left, right) => right.CompareTo(left));
var maxQueue = new SimdQuickHeap<string, int>(highestFirst);

When To Use It

Good fits:

• large task schedulers
• event simulation
• large graph workloads
• pathfinding queues
• interleaved push/pop workloads
• bulk enqueue followed by many pops
• default int or long priorities

Less ideal fits:

• tiny queues under a few thousand items
• one-shot batch sorting where List.Sort is enough
• heavy custom comparer workloads
• floating-point priority workloads where NaN behavior must match .NET exactly
• workloads that require true decrease-key handles

For Dijkstra-style algorithms, use reinsertion plus lazy deletion. That is the approach used by .NET's PriorityQueue too, and it avoids handle overhead.

Benchmark Results

Benchmarks were run with BenchmarkDotNet on .NET 10.0.7, x64 RyuJIT, AVX2 hardware.

Configuration: 1 launch, 1 warmup, 3 measured iterations. These are practical direction numbers, not a final academic benchmark paper.

Mixed Workload: 70% Push, 30% Pop

This is the most realistic priority queue shape for schedulers and simulations.

Size	PriorityQueue	SimdQuickHeap	Binary heap	4-ary heap	SortedSet	SortedDictionary
1,000	9.122 us	22.890 us	9.548 us	9.089 us	46.391 us	116.283 us
10,000	268.036 us	225.743 us	279.573 us	271.788 us	893.015 us	1,718.333 us
100,000	2,768.723 us	2,307.906 us	3,173.822 us	3,096.644 us	14,928.945 us	33,247.396 us

At 100,000 operations, SimdQuickHeap was about 17% faster than PriorityQueue<TElement, TPriority> on this machine.

Push Everything, Then Pop Everything

This stresses the full drain path.

Size	PriorityQueue	SimdQuickHeap	Binary heap	4-ary heap	Queue + List.Sort
1,000	40.905 us	42.948 us	31.041 us	46.322 us	27.749 us
10,000	749.218 us	464.211 us	728.265 us	766.593 us	659.951 us
100,000	9,383.464 us	4,780.002 us	9,349.505 us	10,450.365 us	7,662.619 us

At 100,000 items, SimdQuickHeap was roughly 2x faster than PriorityQueue<TElement, TPriority>.

Queue + List.Sort is included only as a batch baseline. It is not an online priority queue because it cannot efficiently answer "give me the next item now" while new items keep arriving.

Run The Benchmarks

dotnet run -c Release --project benchmarks\SimdQuickHeap.Benchmarks\SimdQuickHeap.Benchmarks.csproj -- --filter "*CollectionComparisonBenchmark*"

Run a smaller filtered benchmark:

dotnet run -c Release --project benchmarks\SimdQuickHeap.Benchmarks\SimdQuickHeap.Benchmarks.csproj -- --filter "*PushPopBenchmark*PushPopAll*"

Benchmark results are written to BenchmarkDotNet.Artifacts/results.

Build And Test

Restore:

dotnet restore SimdQuickHeap.sln --configfile NuGet.Config

Build:

dotnet build SimdQuickHeap.sln -c Release --configfile NuGet.Config --no-restore

Run tests:

dotnet run -c Release --project tests\SimdQuickHeap.Tests\SimdQuickHeap.Tests.csproj --framework net8.0 --no-build
dotnet run -c Release --project tests\SimdQuickHeap.Tests\SimdQuickHeap.Tests.csproj --framework net10.0 --no-build

Create a package:

dotnet pack src\SimdQuickHeap\SimdQuickHeap.csproj -c Release --no-build -o artifacts

GitHub Actions

The workflow builds, tests, and packs the project on every push to main, every pull request to main, and every v* tag.

It installs both .NET 8 and .NET 10, then verifies both target frameworks.

How Close Is It To The Paper?

Implemented:

• adjacent pivot storage
• dedicated buckets between pivots
• median-of-three pivot selection
• duplicate-safe partitioning
• small-bucket cutoff
• SIMD pivot scanning for integer priorities
• SIMD-assisted bucket partitioning
• AVX2 path for packed int priorities and elements
• .NET 10 AVX-512 compress-store path for SimdQuickHeap<int, int>

Not implemented:

• stable decrease-key handles
• full rebalancing strategy
• fully SIMD floating-point priority path

Floating-point priorities intentionally use comparer-based logic so .NET NaN ordering remains correct.

Roadmap

• More Dijkstra and graph benchmark coverage
• More real scheduler and simulation workloads
• AVX-512 hardware validation on a real AVX-512 host
• NuGet publishing pipeline
• More docs and examples
• Additional tuning for small queues

License

MIT. See LICENSE.