hirpdag_hashconsing/
tableshared_sharded.rs

1use crate::reference::*;
2use crate::table::*;
3use array_init::array_init;
4
5const N_SHARDS: usize = 8;
6
7type DefaultHasher = std::hash::BuildHasherDefault<std::collections::hash_map::DefaultHasher>;
8
9pub struct TableSharedSharded<D, R, T, HB = DefaultHasher>
10where
11    D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
12    R: Reference<D>,
13    T: Table<D, R>,
14    HB: std::hash::BuildHasher + Default + Clone,
15{
16    inner: [std::sync::Mutex<T>; N_SHARDS],
17    hash_builder: HB,
18
19    phantom_d: std::marker::PhantomData<D>,
20    phantom_r: std::marker::PhantomData<R>,
21}
22
23impl<D, R, T, HB> TableSharedSharded<D, R, T, HB>
24where
25    D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
26    R: Reference<D>,
27    T: Table<D, R>,
28    HB: std::hash::BuildHasher + Default + Clone,
29{
30    fn get_shard(&self, hash: u64) -> &std::sync::Mutex<T> {
31        let mask = (N_SHARDS - 1) as u64;
32        let index = hash & mask;
33        &self.inner[index as usize]
34    }
35}
36
37#[inline]
38fn make_hash<K: std::hash::Hash + ?Sized>(
39    hash_builder: &impl std::hash::BuildHasher,
40    val: &K,
41) -> u64 {
42    use std::hash::Hasher;
43    let mut state = hash_builder.build_hasher();
44    val.hash(&mut state);
45    state.finish()
46}
47
48impl<D, R, T, HB> TableShared<D, R, T> for TableSharedSharded<D, R, T, HB>
49where
50    D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
51    R: Reference<D>,
52    T: Table<D, R>,
53    HB: std::hash::BuildHasher + Default + Clone,
54{
55    fn get(&self, data: &D) -> Option<R> {
56        let hash = make_hash(&self.hash_builder, &data);
57
58        let shard = self.get_shard(hash);
59        let guard = shard.lock().unwrap();
60        guard.get(hash, data)
61    }
62
63    fn get_or_insert<CF>(&self, data: D, creation_meta: CF) -> R
64    where
65        CF: FnOnce(&mut D),
66    {
67        let hash = make_hash(&self.hash_builder, &data);
68
69        let shard = self.get_shard(hash);
70        let mut guard = shard.lock().unwrap();
71        guard.get_or_insert(hash, data, creation_meta)
72    }
73}
74
75pub struct BuildTableSharedSharded<D, R, T, TB, HB> {
76    table_builder: TB,
77    hash_builder: HB,
78
79    phantom_d: std::marker::PhantomData<D>,
80    phantom_r: std::marker::PhantomData<R>,
81    phantom_t: std::marker::PhantomData<T>,
82}
83
84impl<D, R, T, TB, HB> BuildTableSharedSharded<D, R, T, TB, HB>
85where
86    D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
87    R: Reference<D>,
88    T: Table<D, R>,
89    TB: BuildTable<D, R, Table = T> + Default + Clone,
90    HB: std::hash::BuildHasher + Default + Clone,
91{
92    pub fn with_builders(table_builder: TB, hash_builder: HB) -> Self {
93        Self {
94            table_builder: table_builder,
95            hash_builder: hash_builder,
96
97            phantom_d: std::marker::PhantomData,
98            phantom_r: std::marker::PhantomData,
99            phantom_t: std::marker::PhantomData,
100        }
101    }
102}
103
104impl<D, R, T, TB, HB> Clone for BuildTableSharedSharded<D, R, T, TB, HB>
105where
106    D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
107    R: Reference<D>,
108    T: Table<D, R>,
109    TB: BuildTable<D, R, Table = T> + Default + Clone,
110    HB: std::hash::BuildHasher + Default + Clone,
111{
112    fn clone(&self) -> Self {
113        Self {
114            table_builder: self.table_builder.clone(),
115            hash_builder: self.hash_builder.clone(),
116
117            phantom_d: std::marker::PhantomData,
118            phantom_r: std::marker::PhantomData,
119            phantom_t: std::marker::PhantomData,
120        }
121    }
122}
123
124impl<D, R, T, TB, HB> Default for BuildTableSharedSharded<D, R, T, TB, HB>
125where
126    D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
127    R: Reference<D>,
128    T: Table<D, R>,
129    TB: BuildTable<D, R, Table = T> + Default + Clone,
130    HB: std::hash::BuildHasher + Default + Clone,
131{
132    fn default() -> Self {
133        Self {
134            table_builder: TB::default(),
135            hash_builder: HB::default(),
136
137            phantom_d: std::marker::PhantomData,
138            phantom_r: std::marker::PhantomData,
139            phantom_t: std::marker::PhantomData,
140        }
141    }
142}
143
144impl<D, R, T, TB, HB> BuildTableShared<D, R, T> for BuildTableSharedSharded<D, R, T, TB, HB>
145where
146    D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
147    R: Reference<D>,
148    T: Table<D, R>,
149    TB: BuildTable<D, R, Table = T> + Default + Clone,
150    HB: std::hash::BuildHasher + Default + Clone,
151{
152    type TableSharedType = TableSharedSharded<D, R, T, HB>;
153
154    fn build_tableshared(&self) -> TableSharedSharded<D, R, T, HB> {
155        let shards: [std::sync::Mutex<T>; N_SHARDS] =
156            array_init(|_| std::sync::Mutex::new(self.table_builder.build_table()));
157        TableSharedSharded::<D, R, T, HB> {
158            inner: shards,
159            hash_builder: self.hash_builder.clone(),
160
161            phantom_d: std::marker::PhantomData,
162            phantom_r: std::marker::PhantomData,
163        }
164    }
165}
hirpdag_hashconsing/tableshared_sharded.rs

hirpdag_hashconsing/
tableshared_sharded.rs
