use std::collections::HashSet;
use std::hash::{BuildHasherDefault, Hasher};
use std::sync::{Mutex, PoisonError};
use rayon::prelude::*;
use super::word::KmerWord;
const SHARD_BITS: u32 = 8;
const SHARDS: usize = 1 << SHARD_BITS;
const BUFFER_LEN: usize = 512;
#[inline]
const fn mix64(mut x: u64) -> u64 {
x ^= x >> 30;
x = x.wrapping_mul(0xbf58_476d_1ce4_e5b9);
x ^= x >> 27;
x = x.wrapping_mul(0x94d0_49bb_1331_11eb);
x ^ (x >> 31)
}
#[derive(Default, Clone, Copy)]
pub struct KmerHasher(u64);
impl Hasher for KmerHasher {
#[inline]
fn finish(&self) -> u64 {
self.0
}
fn write(&mut self, bytes: &[u8]) {
for &b in bytes {
self.write_u64(u64::from(b));
}
}
#[inline]
fn write_u64(&mut self, x: u64) {
self.0 = mix64(self.0.rotate_left(5) ^ x);
}
#[inline]
#[allow(clippy::cast_possible_truncation)]
fn write_u128(&mut self, x: u128) {
self.write_u64(x as u64);
self.write_u64((x >> 64) as u64);
}
#[inline]
fn write_usize(&mut self, x: usize) {
self.write_u64(x as u64);
}
}
pub type KmerBuildHasher = BuildHasherDefault<KmerHasher>;
#[inline]
#[allow(clippy::cast_possible_truncation)]
fn shard_of<W: KmerWord>(word: W) -> usize {
(word.fold64().wrapping_mul(0x9e37_79b9_7f4a_7c15) >> (64 - SHARD_BITS)) as usize
}
pub struct ShardedSet<W> {
shards: Vec<Mutex<HashSet<W, KmerBuildHasher>>>,
}
impl<W: KmerWord> ShardedSet<W> {
pub fn new() -> Self {
Self {
shards: (0..SHARDS)
.map(|_| Mutex::new(HashSet::default()))
.collect(),
}
}
pub fn buffer(&self) -> ShardBuffer<'_, W> {
ShardBuffer {
set: self,
pending: (0..SHARDS).map(|_| Vec::new()).collect(),
}
}
fn flush(&self, shard: usize, words: &mut Vec<W>) {
let mut set = self.shards[shard]
.lock()
.unwrap_or_else(PoisonError::into_inner);
set.extend(words.drain(..));
}
fn len_all(&self) -> usize {
self.shards
.iter()
.map(|s| s.lock().unwrap_or_else(PoisonError::into_inner).len())
.sum()
}
#[cfg(test)]
pub fn len(&self) -> usize {
self.len_all()
}
pub fn into_sorted_vec(self) -> Vec<W> {
let total = self.len_all();
let mut words = Vec::with_capacity(total);
for shard in self.shards {
words.extend(shard.into_inner().unwrap_or_else(PoisonError::into_inner));
}
words.par_sort_unstable();
words
}
}
pub struct ShardBuffer<'a, W: KmerWord> {
set: &'a ShardedSet<W>,
pending: Vec<Vec<W>>,
}
impl<W: KmerWord> ShardBuffer<'_, W> {
#[inline]
pub fn insert(&mut self, word: W) {
let shard = shard_of(word);
let buffer = &mut self.pending[shard];
if buffer.capacity() == 0 {
buffer.reserve_exact(BUFFER_LEN);
}
buffer.push(word);
if buffer.len() >= BUFFER_LEN {
self.set.flush(shard, buffer);
}
}
}
impl<W: KmerWord> Drop for ShardBuffer<'_, W> {
fn drop(&mut self) {
for (shard, buffer) in self.pending.iter_mut().enumerate() {
if !buffer.is_empty() {
self.set.flush(shard, buffer);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_sharded_set_dedups_and_sorts() {
let set = ShardedSet::<u64>::new();
{
let mut buf = set.buffer();
for i in (0..5000u64).rev() {
buf.insert(i % 1234);
}
}
assert_eq!(set.len(), 1234);
let words = set.into_sorted_vec();
assert_eq!(words, (0..1234).collect::<Vec<u64>>());
}
#[test]
fn test_sharded_set_concurrent_inserts() {
let set = ShardedSet::<u128>::new();
(0..64u128).into_par_iter().for_each_init(
|| set.buffer(),
|buf, t| {
for i in 0..10_000u128 {
buf.insert((i + t * 100) << 70);
}
},
);
let words = set.into_sorted_vec();
assert_eq!(words.len(), 10_000 + 63 * 100);
assert!(words.windows(2).all(|w| w[0] < w[1]));
}
#[test]
fn test_shards_are_spread() {
let mut counts = vec![0usize; SHARDS];
for i in 0..(SHARDS as u64 * 64) {
counts[shard_of(i)] += 1;
}
assert!(counts.iter().all(|&c| c > 0));
}
}