TPHT

KO | EN

gitlite — search

#framework #animation #go #tensorflow #ios #security #computer-vision #pytorch #developer-tools #git

(★ 9)

Tiny Pointer Hash Table

파일 탐색기

ZIP 다운로드

- plot_latency.py
- plot_tradeoff.py
- run_latency.sh
- run_space_eff.sh
- tpht_latency.c
- tpht_space_eff.c
- INTERNALS.md
- run_tpht_tests.sh
- tpht_test.c
- tpht_test_api_edges.c
- tpht_test_churn.c
- tpht_test_common.c
- tpht_test_common.h
- tpht_test_config.c
- tpht_test_constructors.c
- tpht_test_deterministic.c
- tpht_test_modules.h
- tpht_test_random_model.c
- tpht_test_saturation.c
- tpht_test_threads.c
- check_config_branches.sh
- tsan.supp
.gitignore
CMakeLists.txt
LICENSE
README.md
THIRD-PARTY-NOTICES.md
tpht.c
tpht.h

# CDN으로 사용하기

jsDelivr

jsDelivr는 공개 GitHub 리포지토리를 별도 설정 없이 CDN으로 즉시 서빙합니다. 버전과 파일을 고르면 웹페이지에 바로 붙일 수 있는 링크와 예시 코드가 만들어집니다.

버전

파일

링크

예시

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

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](https://dl.acm.org/doi/10.14778/3819518.3819542) ·
> [arXiv:2607.28892](https://arxiv.org/abs/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.

> **Status:** tentative release.  Extensively tested, but young — the API may
> still move.  If you hit a bug, please
> [open an issue](https://github.com/Xilinion/TPHT/issues); reports are very
> welcome.

## Quick start

```c
#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;
}
```

```sh
cc -std=c11 -O2 -I. tpht.c your_file.c -o your_program
```

## The eight types

```
flatten_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:

```c
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_bytes
```

Keys 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:

```c
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);
```

## What to expect

- **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](docs/INTERNALS.md)).
- **`insert` appends duplicates**; `put`/`update` overwrite.  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 or resizable?

**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.

## SIMD

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](docs/INTERNALS.md).

## Tests and benchmarks

```sh
./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 figure
```

## More

Design and internals — block layout, quotienting, overflow handling, the
concurrent resize, hashing, SIMD modes, test architecture — are in
[docs/INTERNALS.md](docs/INTERNALS.md).

## References

- Xilin Tang, Yuqi Mai, William Kuszmaul, Alex Conway.
  *Succinct and Fast Tiny Pointer Hash Tables.* PVLDB 19(9), 2026.
  [doi:10.14778/3819518.3819542](https://dl.acm.org/doi/10.14778/3819518.3819542),
  [arXiv:2607.28892](https://arxiv.org/abs/2607.28892).
- [TinyPtr](https://github.com/Xilinion/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

## License

TPHT is released under the [BSD 2-Clause License](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](THIRD-PARTY-NOTICES.md).

TPHT

파일 탐색기

# CDN으로 사용하기

Was this content helpful?

Recent Feedback

Download README