massa_models/
prehash.rs

1// Copyright (c) 2022 MASSA LABS <info@massa.net>
2
3use std::collections::{HashMap, HashSet};
4use std::hash::{BuildHasherDefault, Hasher};
5use std::marker::PhantomData;
6
7impl PreHashed for massa_hash::Hash {}
8
9/// A trait indicating that its carrier is already a hash with at least 64 bits
10/// and doesn't need to be re-hashed for hash-table purposes
11pub trait PreHashed {}
12
13/// A `Hasher` for `PreHashed` keys that is faster because it avoids re-hashing hashes but simply truncates them.
14/// Note: when truncating, it takes the last 8 bytes of the key instead of the first 8 bytes.
15/// This is done to circumvent biases induced by first-byte manipulations in addresses related to the thread assignment process
16pub struct HashMapper<T: PreHashed> {
17    source: PhantomData<T>,
18    hash: u64,
19}
20
21/// Default implementation for `HashMapper` (zero hash)
22impl<T: PreHashed> Default for HashMapper<T> {
23    fn default() -> Self {
24        HashMapper {
25            source: Default::default(),
26            hash: Default::default(),
27        }
28    }
29}
30
31/// `Hasher` implementation for `HashMapper`
32impl<T: PreHashed> Hasher for HashMapper<T> {
33    /// finish the hashing process and return the truncated `u64` hash
34    #[inline]
35    fn finish(&self) -> u64 {
36        self.hash
37    }
38
39    /// write the bytes of a `PreHashed` key into the `HashMapper`
40    /// Panics if `bytes.len()` is strictly lower than 8
41    /// Note: the truncated `u64` is completely overwritten by the last 8 items of "bytes" at every call
42    #[inline]
43    fn write(&mut self, bytes: &[u8]) {
44        // assumes bytes.len() is at least 8, otherwise panics
45        self.hash = u64::from_ne_bytes(
46            bytes[bytes.len().checked_sub(8).unwrap()..]
47                .try_into()
48                .unwrap(),
49        );
50    }
51}
52
53/// `BuildHasherDefault` specialization for `HashMapper`
54pub type BuildHashMapper<T> = BuildHasherDefault<HashMapper<T>>;
55
56/// `HashMap` specialization for `PreHashed` keys
57/// This hashmap is about 2x faster than the default `HashMap`
58pub type PreHashMap<K, V> = HashMap<K, V, BuildHashMapper<K>>;
59
60/// `HashSet` specialization for `PreHashed` keys
61/// This hashset is about 2x faster than the default `HashSet`
62pub type PreHashSet<T> = HashSet<T, BuildHashMapper<T>>;
63
64/// Trait allowing pre-allocations
65pub trait CapacityAllocator {
66    /// pre-allocate with a given capacity
67    fn with_capacity(capacity: usize) -> Self;
68}
69
70impl<K: PreHashed, V> CapacityAllocator for PreHashMap<K, V> {
71    /// pre-allocate with a given capacity
72    fn with_capacity(capacity: usize) -> Self {
73        PreHashMap::with_capacity_and_hasher(capacity, BuildHashMapper::default())
74    }
75}
76
77impl<K: PreHashed> CapacityAllocator for PreHashSet<K> {
78    /// pre-allocate with a given capacity
79    fn with_capacity(capacity: usize) -> Self {
80        PreHashSet::with_capacity_and_hasher(capacity, BuildHashMapper::default())
81    }
82}
massa_models/prehash.rs

massa_models/
prehash.rs
