High-performance, lock-free concurrent hash table in Go, based on DLHT, with cooperative resizing and cache-efficient buckets.
  • Go 93.2%
  • Shell 6.3%
  • Assembly 0.5%
Find a file
Jeremiah Masters 5c0560ab3e
Merge pull request #7 from jeremiah-masters/add-resize-quint
Formal Quint specification of the resize protocol
History 2026-08-14 17:16:40 +10:00
allocator Prove inv and rsInv inductive over the daemon step 2026-08-14 17:07:08 +10:00
benchmarks feat: add Range iteration to Map 2026-05-07 12:51:10 +10:00
inline feat: add Size method to concurrent map 2026-05-08 09:21:18 +10:00
internal feat: initial implementation of DLHT concurrent hash table 2026-04-23 10:15:32 +10:00
spec Add an entry-placement invariant for the two-generation gate 2026-08-14 17:07:08 +10:00
tests test: rework pbt suite around exact metamorphic oracles 2026-07-08 11:22:47 +10:00
.gitignore feat(spec): inductive verification overhaul — anchored induction + depth-independent refinement 2026-06-11 10:20:47 +10:00
design.md refactor(allocator): improve bucket alignment logic and add comprehensive tests 2026-05-06 09:38:25 +10:00
example_test.go feat: add Size method to concurrent map 2026-05-08 09:21:18 +10:00
go.mod feat: initial implementation of DLHT concurrent hash table 2026-04-23 10:15:32 +10:00
go.sum feat: initial implementation of DLHT concurrent hash table 2026-04-23 10:15:32 +10:00
LICENSE feat: initial implementation of DLHT concurrent hash table 2026-04-23 10:15:32 +10:00
map.go docs: update README and example to reflect current up-to-date API definitions 2026-04-30 13:37:34 +10:00
README.md feat: add Size method to concurrent map 2026-05-08 09:21:18 +10:00

DLHT

DLHT is a high-performance, lock-free hash table for high-concurrency workloads based on DLHT: A Non-blocking Resizable Hashtable with Fast Deletes and Memory-awareness (https://arxiv.org/abs/2406.09986). It provides lock-free Get, Insert, Delete, and Put operations with sophisticated memory ordering and cooperative resizing.

Features

  • Lock-free operations: All operations (Get, Insert, Delete, Put) are lock-free and linearizable
  • High concurrency: Scales well with multiple threads and cores
  • Automatic resizing: Cooperative resize algorithm that doesn't block operations
  • Memory efficient: Cache-line optimized data structures with bounded overflow
  • Type safe: Generic implementation supporting any comparable key type and any value type

Quick Start

package main

import (
    "fmt"
    "github.com/jeremiah-masters/dlht"
)

func main() {
    // Create a new DLHT Map
    m := dlht.New[string, int](dlht.Options{InitialSize: 64})

    // Insert key-value pairs
    m.Insert("apple", 5)
    m.Insert("banana", 3)

    // Get values
    if value, found := m.Get("apple"); found {
        fmt.Printf("Found: apple = %d\n", value)
    }

    // Update values atomically
    if oldValue, updated := m.Put("apple", 10); updated {
        fmt.Printf("Updated apple: %d -> %d\n", oldValue, 10)
    }

    // Delete keys
    if oldValue, deleted := m.Delete("banana"); deleted {
        fmt.Printf("Deleted banana (old value: %d)\n", oldValue)
    }

    // Iterate every (key, value) currently in the map.
    m.Range(func(k string, v int) bool {
        fmt.Printf("%s = %d\n", k, v)
        return true // return false to stop early
    })

    // Approximate entry count
	size := m.Size()
	fmt.Printf("Size: %d\n", size)

    // Get statistics
    stats := m.Stats()
    fmt.Printf("Load factor: %.3f\n", stats.LoadFactor)
}

API Reference

Types

  • Map[K Key, V any]: The main hash table type
  • Options: Configuration options for creating a new map
  • Stats: Statistics about the hash table's current state
  • Key: Type constraint for valid key types (uint64 or string)

API

  • New[K Key, V any](opts Options) *Map[K, V]: Create a new DLHT
  • Get(key K) (V, bool): Get a value by key
  • Insert(key K, value V) (V, bool): Insert a new key-value pair
  • Put(key K, value V) (V, bool): Update an existing key atomically
  • Delete(key K) (V, bool): Delete a key and return the old value
  • Size() uint64: Approximate count of valid entries
  • Stats() Stats: Get current statistics
  • Range(yield func(K, V) bool): Iterate every (key, value) pair; return false from yield to stop early
  • All() iter.Seq2[K, V]: Range adapter for for k, v := range m.All()
  • Keys() iter.Seq[K]: Range over keys only
  • Values() iter.Seq[V]: Range over values only

Implementation Details

This package provides a clean public API that wraps the allocator-based implementation. The project contains two lock-free variants built on the same core design:

  • allocator/: Generic implementation used by dlht.New; each slot stores a hash plus a pointer to a heap-allocated entry, supporting arbitrary comparable keys and values.
  • inline/: Specialized implementation exposed by dlht.NewInline; each slot stores the value inline for uint64 keys and integer values, avoiding per-entry allocation in that path.

Performance

DLHT is designed for high-performance concurrent workloads:

  • Lock-free: No blocking between operations
  • Cache-optimized: 64-byte buckets fit exactly in cache lines
  • Bounded overflow: Maximum 15 slots per bucket for predictable performance
  • Cooperative resizing: Non-blocking resize with work-stealing

Benchmarks

The charts below compare DLHT against sync.Map and other popular concurrent map implementations across four representative workloads as core count scales. Benchmarks were run on an Intel Xeon Platinum 8260 (2.40GHz); raw data is in benchmarks/results/results.txt.

Throughput Scaling

Throughput scaling across workloads

Latency Scaling

Latency scaling across workloads

Panels cover read-only reads, insert/delete churn, a put-heavy mix, and rapid growth (80% inserts). See benchmarks/workload.go for the full workload definitions and benchmarks/throughput_test.go for the harness.

License

Licensed under Apache v2.