swisstable
v0.0.43SwissTable-inspired hash maps for OCaml
riot add swisstable swisstable = "0.0.43" - Last release
- May 15, 2026
- License
- Apache-2.0
- Dependencies
- 3
- Dependents
- 0
- Installs
- 0
- Published versions
- 31
- Owner
-
@leostera
README Expand Collapse
SwissTable HashMap
A high-performance hash map implementation based on Google's SwissTable algorithm (from the hashbrown Rust crate).
Overview
This package implements a hash table using the SwissTable design, which provides:
- Lower memory overhead: 1 byte per entry vs 8+ bytes in traditional hash tables
- Better cache locality: Control bytes stored separately for SIMD-friendly scanning
- Fast lookups: Parallel scanning of control bytes with bit manipulation tricks
- Efficient iteration: Dense bucket array for fast sequential access
Algorithm Details
Control Bytes (Tags)
Each bucket has a 1-byte control tag:
EMPTY = 0xFF(255) - Bucket never usedDELETED = 0x80(128) - Tombstone for removed entriesFULL = 0-127- Stores top 7 bits of hash for fast filtering
Group-Based Scanning
Control bytes are scanned in groups of 8 using bit-parallel operations:
- Load 8 control bytes into an int64
- Use bit tricks to find matches in parallel
- Return bitmask of matching positions
- Check actual keys only for matches
Triangular Probing
Uses quadratic probing with increasing stride:
- First probe: position + 1 group
- Second probe: position + 2 groups
- Third probe: position + 3 groups
- etc.
Guaranteed to visit all buckets since table size is power-of-2.
Load Factor
- Target: 87.5% (7/8 buckets filled)
- Small tables (<8 buckets): keep ≥1 empty slot
- Resize when:
len > capacity * 7 / 8
Usage
open Std
let map = Swisstable.create () in
(* Insert key-value pairs *)
let _ = Swisstable.insert map "alice" 100 in
let _ = Swisstable.insert map "bob" 87 in
(* Lookup *)
match Swisstable.get map "alice" with
| Some score -> Printf.printf "Alice: %d\n" score
| None -> Printf.printf "Not found\n"
(* Remove *)
let old_value = Swisstable.remove map "bob" in
(* Iterate *)
Swisstable.iter (fun key value ->
Printf.printf "%s: %d\n" key value
) map
API Compatibility
The API is designed to be compatible with Kernel.Collections.HashMap, making it easy to swap implementations.
Implementation Status
- Package structure
- C hash functions (using OCaml's caml_hash_mix_intnat)
- Tag module (control bytes)
- BitMask module (bit scanning)
- Group module (parallel matching)
- ProbeSeq module (probing)
- RawTable module (core operations)
- Public API with Cell-wrapped references
- Iterator support (into_iter, to_mut_iter)
- Mirror control bytes for wrap-around probing
- Comprehensive basic tests (24 tests passing)
- Stress tests
- Benchmarks vs HashMap
Important Notes
Key Stability
CRITICAL: When using string keys created via string concatenation (e.g., "key" ^ string_of_int i), you MUST reuse the same string object for lookups. OCaml's polymorphic hash function (caml_hash_mix_intnat) can produce different hashes for string objects with the same content but different memory addresses.
Hash Randomization
OCaml's caml_hash_mix_intnat uses per-process randomization, meaning the same key can hash to different values across different program runs. This is intentional for security (to prevent hash-flooding DoS attacks) but means:
- Probe sequences vary between runs
- Edge cases (like tables full of tombstones) can occur unpredictably
- The implementation includes probe limits to prevent infinite loops
Good:
let keys = Array.init 100 (fun i -> "key" ^ string_of_int i) in
for i = 0 to 99 do
Swisstable.insert map (Array.get keys i) i
done;
for i = 0 to 99 do
Swisstable.get map (Array.get keys i) (* Uses same string object *)
done
Bad:
for i = 0 to 99 do
Swisstable.insert map ("key" ^ string_of_int i) i
done;
for i = 0 to 99 do
Swisstable.get map ("key" ^ string_of_int i) (* Creates NEW string, may hash differently! *)
done
This is a general issue with OCaml's polymorphic hash and affects all hash-based data structures that use it.
Performance
Expected improvements over Hashtbl-based HashMap:
- 2-3x faster lookups (fewer cache misses)
- 50% less memory overhead
- Faster iteration (dense layout)
Trade-offs:
- More complex implementation
- Resize is more expensive (full rehash)
- Slightly slower for tiny maps (<4 elements)
Integration Plan
Once validated with comprehensive tests and benchmarks:
- Standalone usage: Can be used directly via
swisstablepackage - Optional in Std: Add as
Collections.SwisstableHashMap - Eventual replacement: Replace
HashMapin kernel if performance gains are significant
References
SwissTable HashMap
A high-performance hash map implementation based on Google's SwissTable algorithm (from the hashbrown Rust crate).
Overview
This package implements a hash table using the SwissTable design, which provides:
- Lower memory overhead: 1 byte per entry vs 8+ bytes in traditional hash tables
- Better cache locality: Control bytes stored separately for SIMD-friendly scanning
- Fast lookups: Parallel scanning of control bytes with bit manipulation tricks
- Efficient iteration: Dense bucket array for fast sequential access
Algorithm Details
Control Bytes (Tags)
Each bucket has a 1-byte control tag:
EMPTY = 0xFF(255) - Bucket never usedDELETED = 0x80(128) - Tombstone for removed entriesFULL = 0-127- Stores top 7 bits of hash for fast filtering
Group-Based Scanning
Control bytes are scanned in groups of 8 using bit-parallel operations:
- Load 8 control bytes into an int64
- Use bit tricks to find matches in parallel
- Return bitmask of matching positions
- Check actual keys only for matches
Triangular Probing
Uses quadratic probing with increasing stride:
- First probe: position + 1 group
- Second probe: position + 2 groups
- Third probe: position + 3 groups
- etc.
Guaranteed to visit all buckets since table size is power-of-2.
Load Factor
- Target: 87.5% (7/8 buckets filled)
- Small tables (<8 buckets): keep ≥1 empty slot
- Resize when:
len > capacity * 7 / 8
Usage
open Std
let map = Swisstable.create () in
(* Insert key-value pairs *)
let _ = Swisstable.insert map "alice" 100 in
let _ = Swisstable.insert map "bob" 87 in
(* Lookup *)
match Swisstable.get map "alice" with
| Some score -> Printf.printf "Alice: %d\n" score
| None -> Printf.printf "Not found\n"
(* Remove *)
let old_value = Swisstable.remove map "bob" in
(* Iterate *)
Swisstable.iter (fun key value ->
Printf.printf "%s: %d\n" key value
) map
API Compatibility
The API is designed to be compatible with Kernel.Collections.HashMap, making it easy to swap implementations.
Implementation Status
- Package structure
- C hash functions (using OCaml's caml_hash_mix_intnat)
- Tag module (control bytes)
- BitMask module (bit scanning)
- Group module (parallel matching)
- ProbeSeq module (probing)
- RawTable module (core operations)
- Public API with Cell-wrapped references
- Iterator support (into_iter, to_mut_iter)
- Mirror control bytes for wrap-around probing
- Comprehensive basic tests (24 tests passing)
- Stress tests
- Benchmarks vs HashMap
Important Notes
Key Stability
CRITICAL: When using string keys created via string concatenation (e.g., "key" ^ string_of_int i), you MUST reuse the same string object for lookups. OCaml's polymorphic hash function (caml_hash_mix_intnat) can produce different hashes for string objects with the same content but different memory addresses.
Hash Randomization
OCaml's caml_hash_mix_intnat uses per-process randomization, meaning the same key can hash to different values across different program runs. This is intentional for security (to prevent hash-flooding DoS attacks) but means:
- Probe sequences vary between runs
- Edge cases (like tables full of tombstones) can occur unpredictably
- The implementation includes probe limits to prevent infinite loops
Good:
let keys = Array.init 100 (fun i -> "key" ^ string_of_int i) in
for i = 0 to 99 do
Swisstable.insert map (Array.get keys i) i
done;
for i = 0 to 99 do
Swisstable.get map (Array.get keys i) (* Uses same string object *)
done
Bad:
for i = 0 to 99 do
Swisstable.insert map ("key" ^ string_of_int i) i
done;
for i = 0 to 99 do
Swisstable.get map ("key" ^ string_of_int i) (* Creates NEW string, may hash differently! *)
done
This is a general issue with OCaml's polymorphic hash and affects all hash-based data structures that use it.
Performance
Expected improvements over Hashtbl-based HashMap:
- 2-3x faster lookups (fewer cache misses)
- 50% less memory overhead
- Faster iteration (dense layout)
Trade-offs:
- More complex implementation
- Resize is more expensive (full rehash)
- Slightly slower for tiny maps (<4 elements)
Integration Plan
Once validated with comprehensive tests and benchmarks:
- Standalone usage: Can be used directly via
swisstablepackage - Optional in Std: Add as
Collections.SwisstableHashMap - Eventual replacement: Replace
HashMapin kernel if performance gains are significant