Skip to main content

olean_export/env/
table.rs

1use super::term::{Expr, ExprId, Id, Level, Name};
2use hashbrown::{hash_table::Entry, HashTable};
3use parking_lot::{Mutex, MutexGuard};
4use rustc_hash::FxBuildHasher;
5use std::{
6    hash::{BuildHasher, Hash},
7    ops::Index,
8    sync::{
9        atomic::{AtomicUsize, Ordering::Relaxed},
10        OnceLock,
11    },
12};
13
14const SHARDS: usize = 256;
15
16const CHUNK: usize = 1 << 14;
17
18#[derive(Debug)]
19pub(super) struct Shard<T> {
20    nodes: Vec<T>,
21    index: HashTable<u32>,
22}
23
24fn hash<T: Hash>(t: &T) -> u64 {
25    FxBuildHasher.hash_one(t)
26}
27
28/// The shard of a hash. Fx hashes are weak in their middle bits, so mix them first.
29const fn shard_of(h: u64) -> usize {
30    (h.wrapping_mul(0x9e37_79b9_7f4a_7c15) >> 56) as usize % SHARDS
31}
32
33fn id(n: usize) -> u32 {
34    u32::try_from(n).expect("table overflow")
35}
36
37/// A hash-consing arena split into locked shards so that every decoding thread can intern
38/// into it at once.
39#[derive(Debug)]
40pub(super) struct Shared<T>(Vec<Mutex<Shard<T>>>);
41
42impl<T: Hash + Eq> Shared<T> {
43    /// A table with room for about `n` nodes, whose id 0 is `zero`.
44    pub(super) fn new(zero: T, n: usize) -> Self {
45        let mut shards: Vec<_> = (0..SHARDS)
46            .map(|_| Shard {
47                nodes: Vec::with_capacity(n / SHARDS),
48                index: HashTable::with_capacity(n / SHARDS),
49            })
50            .collect();
51        shards[0].index.insert_unique(hash(&zero), 0, |_| 0);
52        shards[0].nodes.push(zero);
53        Self(shards.into_iter().map(Mutex::new).collect())
54    }
55
56    pub(super) fn intern(&self, t: T) -> Id<T> {
57        let h = hash(&t);
58        let k = shard_of(h);
59        let mut g = self.0[k].lock();
60        let s = &mut *g;
61        let nodes = &mut s.nodes;
62        let i = match s.index.entry(
63            h,
64            |&i| nodes[i as usize] == t,
65            |&i| hash(&nodes[i as usize]),
66        ) {
67            Entry::Occupied(e) => *e.get() as usize,
68            Entry::Vacant(e) => {
69                e.insert(id(nodes.len()));
70                nodes.push(t);
71                nodes.len() - 1
72            }
73        };
74        drop(g);
75        Id::new(id(i * SHARDS + k))
76    }
77
78    pub(super) fn freeze(self) -> Table<T> {
79        Table(self.0.into_iter().map(Mutex::into_inner).collect())
80    }
81}
82
83impl<T> Table<T> {
84    pub(super) fn thaw(self) -> Shared<T> {
85        Shared(self.0.into_iter().map(Mutex::new).collect())
86    }
87}
88
89/// A hash-consing arena: structurally equal nodes get the same id. Ids are interleaved
90/// across shards, so they are nearly but not exactly dense.
91#[derive(Debug)]
92pub struct Table<T>(pub(super) Vec<Shard<T>>);
93
94impl<T: Hash + Eq> Table<T> {
95    pub fn get(&self, t: &T) -> Option<Id<T>> {
96        let h = hash(t);
97        let k = shard_of(h);
98        let s = &self.0[k];
99        let i = s.index.find(h, |&i| s.nodes[i as usize] == *t)?;
100        Some(Id::new(id(*i as usize * SHARDS + k)))
101    }
102
103    /// The number of nodes.
104    #[must_use]
105    pub fn len(&self) -> usize {
106        self.0.iter().map(|s| s.nodes.len()).sum()
107    }
108
109    #[must_use]
110    pub fn is_empty(&self) -> bool {
111        self.len() == 0
112    }
113
114    /// One past the largest id, for arrays indexed by id.
115    #[must_use]
116    pub fn bound(&self) -> usize {
117        self.0.iter().map(|s| s.nodes.len()).max().unwrap_or(0) * SHARDS
118    }
119}
120
121impl<T> Index<Id<T>> for Table<T> {
122    type Output = T;
123    fn index(&self, i: Id<T>) -> &T {
124        let i = i.index();
125        &self.0[i % SHARDS].nodes[i / SHARDS]
126    }
127}
128
129#[derive(Debug)]
130pub(super) struct Chunk {
131    nodes: Vec<Expr>,
132    ranks: Vec<u32>,
133}
134
135/// Expressions, interned through a sharded index but stored in chunks that each thread fills
136/// on its own, so that a term sits near its subterms in memory.
137///
138/// Equal terms can differ in binder names. The copy from the earliest module in import order
139/// wins, whatever order the modules were decoded in.
140pub(super) struct SharedExprs {
141    index: Vec<Mutex<HashTable<u32>>>,
142    chunks: Slots,
143    next: AtomicUsize,
144}
145
146const PAGE: usize = 512;
147
148type Slot = OnceLock<Box<Mutex<Chunk>>>;
149
150/// A slot for every chunk an id can name, allocated a page at a time as chunks are claimed.
151struct Slots(Box<[OnceLock<Box<[Slot]>>]>);
152
153impl Slots {
154    fn new() -> Self {
155        Self(
156            (0..=u32::MAX as usize / CHUNK / PAGE)
157                .map(|_| OnceLock::new())
158                .collect(),
159        )
160    }
161
162    fn get(&self, k: usize) -> &Slot {
163        let page = self.0.get(k / PAGE).expect("table overflow");
164        &page.get_or_init(|| (0..PAGE).map(|_| OnceLock::new()).collect())[k % PAGE]
165    }
166
167    /// The chunks claimed, in id order.
168    fn into_chunks(self) -> impl Iterator<Item = Chunk> {
169        self.0
170            .into_vec()
171            .into_iter()
172            .filter_map(OnceLock::into_inner)
173            .flat_map(<[_]>::into_vec)
174            .map_while(OnceLock::into_inner)
175            .map(|c| c.into_inner())
176    }
177}
178
179impl SharedExprs {
180    pub(super) fn new(n: usize) -> Self {
181        Self {
182            index: (0..SHARDS)
183                .map(|_| Mutex::new(HashTable::with_capacity(n / SHARDS)))
184                .collect(),
185            chunks: Slots::new(),
186            next: AtomicUsize::new(0),
187        }
188    }
189
190    fn chunk(&self, k: usize) -> MutexGuard<'_, Chunk> {
191        self.chunks
192            .get(k)
193            .get()
194            .expect("chunk is published before its ids")
195            .lock()
196    }
197
198    /// Run `f` on node `i` and its rank.
199    fn with<R>(&self, i: u32, f: impl FnOnce(&mut Expr, &mut u32) -> R) -> R {
200        let i = i as usize;
201        let mut g = self.chunk(i / CHUNK);
202        let c = &mut *g;
203        let r = f(&mut c.nodes[i % CHUNK], &mut c.ranks[i % CHUNK]);
204        drop(g);
205        r
206    }
207
208    /// Intern `e` from module `rank`, adding it to the chunk `cursor` if it is new.
209    #[allow(clippy::significant_drop_tightening)]
210    pub(super) fn intern(&self, e: Expr, rank: u32, cursor: &mut Option<usize>) -> ExprId {
211        let h = hash(&e);
212        let mut index = self.index[shard_of(h)].lock();
213        let entry = index.entry(
214            h,
215            |&i| self.with(i, |n, _| *n == e),
216            |&i| self.with(i, |n, _| hash(n)),
217        );
218        let i = match entry {
219            Entry::Occupied(o) => {
220                let i = *o.get();
221                self.with(i, |n, r| {
222                    if rank < *r {
223                        *n = e;
224                        *r = rank;
225                    }
226                });
227                i
228            }
229            Entry::Vacant(v) => {
230                let (k, mut c) = match cursor.map(|k| (k, self.chunk(k))) {
231                    Some((k, c)) if c.nodes.len() < CHUNK => (k, c),
232                    _ => {
233                        let k = self.next.fetch_add(1, Relaxed);
234                        self.chunks.get(k).get_or_init(|| {
235                            Box::new(Mutex::new(Chunk {
236                                nodes: Vec::with_capacity(CHUNK),
237                                ranks: Vec::with_capacity(CHUNK),
238                            }))
239                        });
240                        *cursor = Some(k);
241                        (k, self.chunk(k))
242                    }
243                };
244                let i = id(k * CHUNK + c.nodes.len());
245                c.nodes.push(e);
246                c.ranks.push(rank);
247                v.insert(i);
248                i
249            }
250        };
251        Id::new(i)
252    }
253
254    /// The expressions, plus the index and ranks [`Env::reload`] needs to intern more.
255    pub(super) fn freeze(self) -> (Exprs, Vec<HashTable<u32>>, Vec<Vec<u32>>) {
256        let (nodes, ranks) = self
257            .chunks
258            .into_chunks()
259            .map(|c| (c.nodes, c.ranks))
260            .unzip();
261        let index = self.index.into_iter().map(Mutex::into_inner).collect();
262        (Exprs(nodes), index, ranks)
263    }
264
265    pub(super) fn thaw(exprs: Exprs, index: Vec<HashTable<u32>>, ranks: Vec<Vec<u32>>) -> Self {
266        let n = exprs.0.len();
267        let chunks = Slots::new();
268        for (k, (nodes, ranks)) in exprs.0.into_iter().zip(ranks).enumerate() {
269            chunks
270                .get(k)
271                .set(Box::new(Mutex::new(Chunk { nodes, ranks })))
272                .expect("chunk is set once");
273        }
274        Self {
275            index: index.into_iter().map(Mutex::new).collect(),
276            chunks,
277            next: AtomicUsize::new(n),
278        }
279    }
280}
281
282/// Expressions by id. Ids come in chunks, each filled by one decoding thread, with gaps.
283#[derive(Debug, Default)]
284pub struct Exprs(pub(super) Vec<Vec<Expr>>);
285
286impl Exprs {
287    /// The number of expressions.
288    #[must_use]
289    pub fn len(&self) -> usize {
290        self.0.iter().map(Vec::len).sum()
291    }
292
293    #[must_use]
294    pub fn is_empty(&self) -> bool {
295        self.len() == 0
296    }
297
298    /// One past the largest id, for arrays indexed by id.
299    #[must_use]
300    pub const fn bound(&self) -> usize {
301        self.0.len() * CHUNK
302    }
303}
304
305impl Index<ExprId> for Exprs {
306    type Output = Expr;
307    fn index(&self, i: ExprId) -> &Expr {
308        let i = i.index();
309        &self.0[i / CHUNK][i % CHUNK]
310    }
311}
312
313/// The tables every module of one load interns into.
314pub(super) struct Tables {
315    pub(super) names: Shared<Name>,
316    pub(super) levels: Shared<Level>,
317    pub(super) exprs: SharedExprs,
318}