Industrial C implementation of Tiny Pointer Hash Tables, from the paper:
Xilin Tang, Yuqi Mai, William Kuszmaul, Alex Conway. Succinct and Fast Tiny Pointer Hash Tables. Proceedings of the VLDB Endowment (PVLDB) 19(9), 2026. doi:10.14778/3819518.3819542 · arXiv:2607.28892
Two variants: chained-tpht (tiny-pointer chains, tuned for space) and
flatten-tpht (64-byte home blocks, tuned for latency). To use it, copy
tpht.h and tpht.c into your project — C11 and the standard library are the
only requirements.
If you hit a bug, please open an issue; reports are very welcome.
#include "tpht.h"
int main(void) {
/* 64-bit keys, 3-byte values, room for 1024 pairs */
flatten_tpht64_t *t = flatten_tpht64_fixed_create(1024, 3);
uint64_t value;
flatten_tpht64_put(t, 42, 9001);
if (flatten_tpht64_get(t, 42, &value) == TPHT_OK) {
/* value == 9001 */
}
flatten_tpht64_destroy(t);
return 0;
}cc -std=c11 -O2 -I. tpht.c your_file.c -o your_programflatten_tpht32_t flatten_tpht64_t sequential flattened
flatten_conc_tpht32_t flatten_conc_tpht64_t concurrent flattened
chained_tpht32_t chained_tpht64_t sequential chained
chained_conc_tpht32_t chained_conc_tpht64_t concurrent chained
One type per (variant, key width, threading), so every code path is fixed at
compile time — no configuration test on any hot path. All eight come from the
one tpht.c and can be mixed freely in one program. Each type carries its own
constructors and operations:
flatten_tpht64_fixed_create(capacity, value_size);
flatten_tpht64_resizable_create(capacity, value_size);
flatten_tpht64_put / _insert / _update / _get / _remove / _destroy
flatten_tpht64_size / _capacity / _memory_bytesKeys are uint32_t or uint64_t by type. Values cross the API as uint64_t
and are truncated to the table's value size (1 to 8 bytes, chosen per table).
The remaining knobs live in an options struct, where zero means default:
tpht_options_t o = tpht_default_options();
o.resize_mode = TPHT_RESIZABLE; /* also: value_size, max_load_factor, hash_seed */
flatten_conc_tpht64_t *t = flatten_conc_tpht64_create(1 << 20, &o);- A table never fills up on you. Both fixed and resizable tables absorb overflow by growing internally; a write fails only on allocation failure or a structural ceiling (status-code details in docs/INTERNALS.md).
insertappends duplicates;put/updateoverwrite. In the flattened variant ~30 duplicates of one single key is the one structural ceiling — distinct keys never hit one, at any scale.- Concurrent tables are safe for any mix of operations from any number of threads and resize online: readers never block, writers lock one 64-byte block and pay at most a bounded slice of migration work.
Fixed is for sizes you can provision: fastest on every axis — no size
accounting on writes, and a right-sized table never rebuilds. Its overflow
absorb is an emergency mechanism, not a growth strategy: an under-provisioned
fixed table keeps working, but rebuilds at unpredictable breaking points into
the densest layout that fits, so lookups are measurably slower from then on.
Resizable is for sizes you cannot predict: it grows at a load-factor
threshold you control, keeps lookups near right-sized speed, and has O(1)
size() — paid for during the growth phase and in memory headroom.
Who waits when the table grows:
- Sequential: the write that triggers a rebuild performs the whole rebuild before returning — resizable puts that pause at your threshold, fixed at the breaking point.
- Concurrent resizable: nobody stalls — each write overlapping a resize pays one bounded stride of migration and proceeds; readers are never blocked.
- Concurrent fixed: same stride machinery, but the triggering write — whose key cannot fit until the larger geometry exists — waits for the resize to finish.
The flattened variant's fingerprint screening is vectorized — AVX-512, AVX2,
SSE2, and NEON are supported, with the best level the build allows picked
automatically and a portable scalar fallback everywhere else. Nothing to
configure: the default build does the right thing, and lookups benefit the
most. If your toolchain or target cannot use SIMD, -DTPHT_ENABLE_SIMD=0
forces the scalar fallback — correct, just slower to look up. What each level
does and how one is selected is described in
docs/INTERNALS.md.
./tests/run_tpht_tests.sh # exhaustive suite across all SIMD levels
./benchmarks/run_latency.sh # latency sweep -> results/*.csv (+ PDF if matplotlib)
./benchmarks/run_space_eff.sh # space efficiency -> results/*.csv
./benchmarks/plot_tradeoff.py # pair the two CSVs into a space-vs-throughput figureDesign and internals — block layout, quotienting, overflow handling, the concurrent resize, hashing, SIMD modes, test architecture — are in docs/INTERNALS.md.
- Xilin Tang, Yuqi Mai, William Kuszmaul, Alex Conway. Succinct and Fast Tiny Pointer Hash Tables. PVLDB 19(9), 2026. doi:10.14778/3819518.3819542, arXiv:2607.28892.
- TinyPtr: the paper's artifact evaluation code base.
- xxHash / XXH3 by Yann Collet: TPHT embeds a small dependency-free subset of XXH3 (BSD 2-Clause): https://github.com/Cyan4973/xxHash
TPHT is released under the BSD 2-Clause License: use it in anything, commercial or not, as long as the copyright notice and the disclaimer travel with the source or the binary's documentation. The embedded XXH3 subset is under the same license, held by Yann Collet — that and the public-domain splitmix64 finalizer are the only third-party pieces, both recorded in THIRD-PARTY-NOTICES.md.