use std::hash::{Hash, Hasher};
use rayon::prelude::*;
use rustc_hash::{FxHashMap, FxHasher};
const NONE: u32 = u32::MAX;
const SHARDS: usize = 256;
fn hash(key: &[u32]) -> u64 {
let mut h = FxHasher::default();
key.hash(&mut h);
h.finish()
}
#[derive(Default)]
pub(crate) struct Chunk {
pub ids: Vec<u32>,
words: Vec<u32>,
ends: Vec<u32>,
hashes: Vec<u64>,
heads: FxHashMap<u64, u32>,
next: Vec<u32>,
}
impl Chunk {
pub fn push(&mut self, key: &[u32]) {
let h = hash(key);
let head = self.heads.get(&h).copied().unwrap_or(NONE);
let mut i = head;
while i != NONE {
if self.key(i as usize) == key {
self.ids.push(i);
return;
}
i = self.next[i as usize];
}
let id = self.ends.len() as u32;
self.words.extend_from_slice(key);
self.ends.push(self.words.len() as u32);
self.hashes.push(h);
self.next.push(head);
self.heads.insert(h, id);
self.ids.push(id);
}
pub fn key(&self, i: usize) -> &[u32] {
let start = if i == 0 { 0 } else { self.ends[i - 1] as usize };
&self.words[start..self.ends[i] as usize]
}
pub fn hash_of(&self, i: usize) -> u64 {
self.hashes[i]
}
pub fn keys_only(&mut self) {
*self = Chunk {
words: std::mem::take(&mut self.words),
ends: std::mem::take(&mut self.ends),
..Chunk::default()
};
self.words.shrink_to_fit();
self.ends.shrink_to_fit();
}
pub fn len(&self) -> usize {
self.ends.len()
}
}
pub(crate) fn merge(chunks: &[Chunk]) -> (Vec<u32>, Vec<&[u32]>) {
let mut offsets = Vec::with_capacity(chunks.len() + 1);
offsets.push(0);
for c in chunks {
offsets.push(offsets.last().unwrap() + c.len());
}
let n = *offsets.last().unwrap();
let key = |p: usize| {
let c = offsets.partition_point(|&o| o <= p) - 1;
chunks[c].key(p - offsets[c])
};
let shard_of: Vec<u8> = chunks
.par_iter()
.flat_map_iter(|c| c.hashes.iter().map(|h| (h >> 56) as u8))
.collect();
let mut order: Vec<u32> = (0..n as u32).into_par_iter().collect();
order.par_sort_unstable_by_key(|&p| (shard_of[p as usize], p));
let mut parts = Vec::with_capacity(SHARDS);
let mut buf = vec![0u32; n];
let mut rest: &mut [u32] = &mut buf;
let mut lo = 0;
for s in 0..SHARDS {
let len = order[lo..].partition_point(|&p| shard_of[p as usize] as usize == s);
let (part, tail) = rest.split_at_mut(len);
parts.push((&order[lo..lo + len], part));
rest = tail;
lo += len;
}
parts.into_par_iter().for_each(|(pos, out)| {
let mut seen: FxHashMap<&[u32], u32> = FxHashMap::default();
for (&p, o) in pos.iter().zip(out) {
*o = *seen.entry(key(p as usize)).or_insert(p);
}
});
let mut first = vec![0u32; n];
for (&p, &f) in order.iter().zip(&buf) {
first[p as usize] = f;
}
let mut distinct = 0u32;
for (p, &f) in first.iter().enumerate() {
if f == p as u32 {
buf[p] = distinct;
distinct += 1;
}
}
order
.par_iter_mut()
.zip(&first)
.for_each(|(o, &f)| *o = buf[f as usize]);
let global = ℴ
let ids = chunks
.par_iter()
.zip(&offsets)
.flat_map_iter(|(c, &off)| c.ids.iter().map(move |&i| global[off + i as usize]))
.collect();
let table = (0..n)
.into_par_iter()
.filter(|&p| first[p] == p as u32)
.map(key)
.collect();
(ids, table)
}
#[cfg(test)]
mod tests {
use super::*;
fn reference(queries: &[Vec<Vec<u32>>]) -> (Vec<u32>, Vec<Vec<u32>>) {
let mut global: FxHashMap<Vec<u32>, u32> = FxHashMap::default();
let mut table = Vec::new();
let mut ids = Vec::new();
for chunk in queries {
for k in chunk {
ids.push(*global.entry(k.clone()).or_insert_with(|| {
table.push(k.clone());
table.len() as u32 - 1
}));
}
}
(ids, table)
}
#[test]
fn matches_the_sequential_merge() {
let mut r = 0x9e3779b97f4a7c15u64;
let mut next = move |m: u64| {
r ^= r << 13;
r ^= r >> 7;
r ^= r << 17;
r % m
};
for nkeys in [1, 7, 300, 20_000] {
let queries: Vec<Vec<Vec<u32>>> = (0..40)
.map(|_| {
(0..next(500))
.map(|_| {
let v = next(nkeys);
vec![v as u32; 1 + (v % 5) as usize]
})
.collect()
})
.collect();
let chunks: Vec<Chunk> = queries
.iter()
.map(|q| {
let mut c = Chunk::default();
for k in q {
c.push(k);
}
c
})
.collect();
let (ids, table) = merge(&chunks);
let table: Vec<Vec<u32>> = table.into_iter().map(|k| k.to_vec()).collect();
assert_eq!((ids, table), reference(&queries));
}
}
#[test]
fn hash_collisions_within_a_chunk_are_resolved() {
let mut c = Chunk::default();
c.push(&[1, 2]);
c.heads.insert(hash(&[3]), 0);
c.push(&[3]);
c.push(&[1, 2]);
c.push(&[3]);
assert_eq!(c.ids, [0, 1, 0, 1]);
}
}