2 releases
0.1.1  Nov 15, 2023 

0.1.0  Nov 15, 2023 
#194 in Science
92KB
2K
SLoC
PTRHash
PTRHash is a fast and space efficient minimal perfect hash function that maps
a list of n
distinct keys into [n]
. It is an adaptation of PTHash, and
written in Rust.
I'm keeping a blogpost with remarks, ideas, implementation notes, and experiments at https://curiouscoding.nl/posts/ptrhash.
Contact
Feel free to make issues and/or PRs, reach out on twitter @curious_coding, or on matrix @curious_coding:matrix.org.
Performance
PTRHash supports up to $2^40$ keys. For default parameters $\alpha = 0.98$, $c=9$, constructing a MPHF of $n=10^9$ integer keys gives:
 Construction takes
19s
on myi710750H
(3.6GHz
) using6
threads:5s
to sort hashes,12s
to find pilots.
 Memory usage is
2.69bits/key
:2.46bits/key
for pilots,0.24bits/key
for remapping.
 Queries take:
18ns/key
when indexing sequentially,8.2ns/key
when streaming with prefetching,2.9ns/key
when streaming with prefetching, using4
threads.
 When giving up on minimality of the hash and allowing values up to $n/\alpha$,
query times slightly improve:
14ns/key
when indexing sequentially,7.5ns/key
when streaming using prefetching,2.8ns/key
when streaming with prefetching, using4
threads.
Query throughput per thread fully saturates the prefetching bandwidth of each core, and multithreaded querying fully saturates the DDR4 memory bandwidth.
Algorithm
Parameters:
 Given are $n < 2^40 \approx 10^11$ keys.
 We partition into $P$ parts each consisting of $\approx 200000$ keys.
 Each part consists of $B$ buckets and $S$ slots, with $S$ a power of $2$.
 The total number of buckets $B\cdot P$ is roughly $n/\log n \cdot c$, for a parameter $c\sim 8$.
 The total number of slots is $S \cdot P$ is roughly $n / \alpha, for a parameter $\alpha \sim 0.98$.
Query:
Given a key $x$, compute in order:
 $h = h(x)$, the hash of the key which is uniform in $[0, 2^{64})$.
 $part = \left\lfloor \frac {P\cdot h}{2^{64}} \right\rfloor$, the part of the key.
 $h' = (P\cdot h) \mod 2^{64}$.
 We split buckets into large and small buckets. (This speeds up construction.) Specifically we map $\beta = 0.6$ of elements into $\gamma = 0.3$ of buckets:
$$bucket = B\cdot part + \begin{cases} \left\lfloor \frac{\gamma B}{\beta 2^{64}} h'\right\rfloor& \text{if } h' < \beta \cdot 2^{64} \ \left\lfloor\gamma B + \frac{(1\gamma)B}{(1\beta)2^{64}} h'\right\rfloor & \text{if } h' \geq \beta \cdot 2^{64}. \ \end{cases}$$
 Look up the pilot $p$ for the bucket $bucket$.
 For some
64
bit mixing constant $C$, the slot is:
$$ slot = part \cdot S + ((h \oplus (C \cdot p)) \cdot C) \mod S $$
Compared to PTHash
PTRHash extends it in a few ways:

8bit pilots: Instead of allowing pilots to take any integer value, we restrict them to
[0, 256)
and store them asVec<u8>
directly, instead of requiring a compact or dictionary encoding. 
Displacing: To get all pilots to be small, we use displacing, similar to cuckoo hashing: Whenever we cannot find a collisionfree pilot for a bucket, we find the pilot with the fewest collisions and displace all colliding buckets, which are pushed on a queue after which they will search for a new pilot.

Partitioning: To speed up construction, we partition all keys/hashes into parts such that each part contains $S=2^k$ slots, which we choose to be roughly the size of the L1 cache. This significantly speeds up construction since all reads of the
taken
bitvector are now very local.This brings the benefit that the only global memory needed is to store the hashes for each part. The sorting, bucketing, and slot filling is perpart and needs comparatively little memory.

Remap encoding: We use a partitioned EliasFano encoding that encoding chunks of
44
integers into a single cacheline. This takes `30%more space for remapping, but replaces the three reads needed by (global) EliasFano encoding by a single read.
Usage
use ptr_hash::{PtrHash, PtrHashParams};
let n = 1_000_000_000;
let keys = ptr_hash::util::generate_keys(n);
let mphf = <PtrHash>::new(&keys, PtrHashParams::default());
let sum = mphf.index_stream::<32, true>(&keys).sum::<usize>();
assert_eq!(sum, (n * (n  1)) / 2);
// Get the minimal index of a key.
let key = 0;
let idx = mphf.index_minimal(&key);
assert!(idx < n);
// Get the nonminimal index of a key. Slightly faster.
let _idx = mphf.index(&key);
// An iterator over the indices of the keys.
// 32: number of iterations ahead to prefetch.
// true: remap to a minimal key in [0, n).
let indices = mphf.index_stream::<32, true>(&keys);
assert_eq!(indices.sum::<usize>(), (n * (n  1)) / 2);
// Test that all items map to different indices
let mut taken = vec![false; n];
for key in keys {
let idx = mphf.index_minimal(&key);
assert!(!taken[idx]);
taken[idx] = true;
}
Dependencies
~8–40MB
~631K SLoC