1 use crate::fx::{FxHashMap, FxHasher};
2 use crate::sync::{Lock, LockGuard};
3 use smallvec::SmallVec;
4 use std::borrow::Borrow;
5 use std::collections::hash_map::RawEntryMut;
6 use std::hash::{Hash, Hasher};
9 #[derive(Clone, Default)]
10 #[cfg_attr(parallel_compiler, repr(align(64)))]
11 struct CacheAligned<T>(T);
13 #[cfg(parallel_compiler)]
14 // 32 shards is sufficient to reduce contention on an 8-core Ryzen 7 1700,
15 // but this should be tested on higher core count CPUs. How the `Sharded` type gets used
16 // may also affect the ideal nunber of shards.
17 const SHARD_BITS: usize = 5;
19 #[cfg(not(parallel_compiler))]
20 const SHARD_BITS: usize = 0;
22 pub const SHARDS: usize = 1 << SHARD_BITS;
24 /// An array of cache-line aligned inner locked structures with convenience methods.
26 pub struct Sharded<T> {
27 shards: [CacheAligned<Lock<T>>; SHARDS],
30 impl<T: Default> Default for Sharded<T> {
32 fn default() -> Self {
33 Self::new(|| T::default())
39 pub fn new(mut value: impl FnMut() -> T) -> Self {
40 // Create a vector of the values we want
41 let mut values: SmallVec<[_; SHARDS]> =
42 (0..SHARDS).map(|_| CacheAligned(Lock::new(value()))).collect();
44 // Create an unintialized array
45 let mut shards: mem::MaybeUninit<[CacheAligned<Lock<T>>; SHARDS]> =
46 mem::MaybeUninit::uninit();
49 // Copy the values into our array
50 let first = shards.as_mut_ptr() as *mut CacheAligned<Lock<T>>;
51 values.as_ptr().copy_to_nonoverlapping(first, SHARDS);
53 // Ignore the content of the vector
56 Sharded { shards: shards.assume_init() }
60 /// The shard is selected by hashing `val` with `FxHasher`.
62 pub fn get_shard_by_value<K: Hash + ?Sized>(&self, val: &K) -> &Lock<T> {
63 if SHARDS == 1 { &self.shards[0].0 } else { self.get_shard_by_hash(make_hash(val)) }
66 /// Get a shard with a pre-computed hash value. If `get_shard_by_value` is
67 /// ever used in combination with `get_shard_by_hash` on a single `Sharded`
68 /// instance, then `hash` must be computed with `FxHasher`. Otherwise,
69 /// `hash` can be computed with any hasher, so long as that hasher is used
70 /// consistently for each `Sharded` instance.
72 pub fn get_shard_by_hash(&self, hash: u64) -> &Lock<T> {
73 let hash_len = mem::size_of::<usize>();
74 // Ignore the top 7 bits as hashbrown uses these and get the next SHARD_BITS highest bits.
75 // hashbrown also uses the lowest bits, so we can't use those
76 let bits = (hash >> (hash_len * 8 - 7 - SHARD_BITS)) as usize;
77 let i = bits % SHARDS;
81 pub fn lock_shards(&self) -> Vec<LockGuard<'_, T>> {
82 (0..SHARDS).map(|i| self.shards[i].0.lock()).collect()
85 pub fn try_lock_shards(&self) -> Option<Vec<LockGuard<'_, T>>> {
86 (0..SHARDS).map(|i| self.shards[i].0.try_lock()).collect()
90 pub type ShardedHashMap<K, V> = Sharded<FxHashMap<K, V>>;
92 impl<K: Eq, V> ShardedHashMap<K, V> {
93 pub fn len(&self) -> usize {
94 self.lock_shards().iter().map(|shard| shard.len()).sum()
98 impl<K: Eq + Hash + Copy> ShardedHashMap<K, ()> {
100 pub fn intern_ref<Q: ?Sized>(&self, value: &Q, make: impl FnOnce() -> K) -> K
105 let hash = make_hash(value);
106 let mut shard = self.get_shard_by_hash(hash).lock();
107 let entry = shard.raw_entry_mut().from_key_hashed_nocheck(hash, value);
110 RawEntryMut::Occupied(e) => *e.key(),
111 RawEntryMut::Vacant(e) => {
113 e.insert_hashed_nocheck(hash, v, ());
120 pub fn intern<Q>(&self, value: Q, make: impl FnOnce(Q) -> K) -> K
125 let hash = make_hash(&value);
126 let mut shard = self.get_shard_by_hash(hash).lock();
127 let entry = shard.raw_entry_mut().from_key_hashed_nocheck(hash, &value);
130 RawEntryMut::Occupied(e) => *e.key(),
131 RawEntryMut::Vacant(e) => {
133 e.insert_hashed_nocheck(hash, v, ());
141 fn make_hash<K: Hash + ?Sized>(val: &K) -> u64 {
142 let mut state = FxHasher::default();
143 val.hash(&mut state);