yo_index/
bucket.rs

1//! The 64 byte index bucket.
2//!
3//! One cache line, seven entries, one link. Laid out exactly as `05` section
4//! 2.1 specifies:
5//!
6//! | Offset | Size | Field   | Meaning                                  |
7//! |--------|------|---------|------------------------------------------|
8//! | 0      | 7x1  | `tag`   | 8 high bits of the hash, 0 means empty   |
9//! | 7      | 1    | `flags` | bit 0 overflow present                   |
10//! | 8      | 7x7  | `addr`  | 56 bit address, 4 bit space, 52 bit offset |
11//! | 57     | 7    | `link`  | 56 bit address of the overflow bucket    |
12//!
13//! The probe is the reason for the shape. Seven tags fit in the first eight
14//! bytes, so comparing all of them is one load and three arithmetic operations
15//! with no branches and no SIMD intrinsics. aki measured the tag prefilter at
16//! 3.31 ns against 4.77 ns without it (L13), and the whole point is that the
17//! common case dereferences a key exactly once instead of up to seven times.
18
19use yo_common::{Addr, CACHE_LINE};
20
21/// Entries in one bucket.
22pub const SLOTS: usize = 7;
23
24/// A tag value of zero means the slot is empty.
25pub const EMPTY: u8 = 0;
26
27/// Bit 0 of `flags`: this bucket has an overflow bucket on its link.
28const FLAG_OVERFLOW: u8 = 1;
29
30/// Broadcast constant for the SWAR byte compare.
31const ONES: u64 = 0x0101_0101_0101_0101;
32/// Low seven bits of every lane.
33const LOW7: u64 = 0x7f7f_7f7f_7f7f_7f7f;
34/// High bit of each of the seven tag lanes. Lane 7 is `flags` and is never a
35/// match, which is what keeps a search for the empty tag from finding it.
36const LANES: u64 = 0x0080_8080_8080_8080;
37
38/// One index bucket.
39#[repr(C, align(64))]
40#[derive(Clone, Copy)]
41pub struct Bucket {
42    tags: [u8; SLOTS],
43    flags: u8,
44    addrs: [[u8; 7]; SLOTS],
45    link: [u8; 7],
46}
47
48const _: () = {
49    assert!(size_of::<Bucket>() == CACHE_LINE);
50    assert!(align_of::<Bucket>() == CACHE_LINE);
51};
52
53impl Default for Bucket {
54    fn default() -> Bucket {
55        Bucket::EMPTY
56    }
57}
58
59impl Bucket {
60    /// A bucket with no entries.
61    pub const EMPTY: Bucket = Bucket {
62        tags: [EMPTY; SLOTS],
63        flags: 0,
64        addrs: [[0; 7]; SLOTS],
65        link: [0; 7],
66    };
67
68    /// The seven tags and the flags byte, as one little endian word.
69    #[inline(always)]
70    fn tag_word(&self) -> u64 {
71        // The pointer has to come from the whole bucket rather than from
72        // `self.tags`. A pointer derived from a seven byte array carries
73        // provenance over seven bytes, and reading eight through it is
74        // undefined behaviour even though the eighth byte is the very next
75        // field of the same struct. Miri catches it under stacked borrows,
76        // nothing else does, and the two versions compile to the same load.
77        let base: *const u8 = core::ptr::from_ref(self).cast();
78        // SAFETY: `Bucket` is `repr(C)` with `tags` at offset 0 followed by
79        // `flags`, so the first eight bytes are inside the bucket and are
80        // initialised. An unaligned read is used because the compiler is free
81        // to pick either and this makes the intent explicit.
82        unsafe { base.cast::<u64>().read_unaligned().to_le() }
83    }
84
85    /// A bitmask over the seven slots whose tag equals `tag`.
86    ///
87    /// Bit `i` of the result is set when slot `i` matches. This is the whole
88    /// prefilter: one load, an xor, a subtract, an and, and a shift.
89    #[inline(always)]
90    pub fn match_tag(&self, tag: u8) -> SlotMask {
91        let word = self.tag_word();
92        let x = word ^ (ONES.wrapping_mul(tag as u64));
93        // Set the high bit of every lane whose byte is zero, meaning the tag
94        // matched. The obvious `(x - ONES) & !x & LANES` is wrong here: a
95        // borrow out of one lane walks into the next, so a slot holding 0x01
96        // reports a match whenever the slot below it matched. That is fine in a
97        // hash table whose control bytes have a reserved high bit, and it is
98        // not fine here, where a tag is any of 256 values. So take the version
99        // that cannot carry: masking off the high bits before the add keeps
100        // every lane's sum under 0x100.
101        let z = !((x & LOW7).wrapping_add(LOW7) | x | LOW7);
102        SlotMask(z & LANES)
103    }
104
105    /// A bitmask over the seven slots that are empty.
106    #[inline(always)]
107    pub fn match_empty(&self) -> SlotMask {
108        self.match_tag(EMPTY)
109    }
110
111    /// Whether every slot is occupied.
112    #[inline(always)]
113    pub fn is_full(&self) -> bool {
114        self.match_empty().is_empty()
115    }
116
117    /// The tag in slot `i`.
118    #[inline(always)]
119    pub fn tag(&self, i: usize) -> u8 {
120        self.tags[i]
121    }
122
123    /// The address in slot `i`.
124    #[inline(always)]
125    pub fn addr(&self, i: usize) -> Addr {
126        Addr::from_bits(read56(&self.addrs[i]))
127    }
128
129    /// Put `addr` under `tag` in slot `i`.
130    ///
131    /// # Panics
132    ///
133    /// If `tag` is zero, which would make an occupied slot read as empty.
134    #[inline(always)]
135    pub fn set(&mut self, i: usize, tag: u8, addr: Addr) {
136        assert_ne!(tag, EMPTY, "an occupied slot cannot carry the empty tag");
137        self.tags[i] = tag;
138        write56(&mut self.addrs[i], addr.to_bits());
139    }
140
141    /// Replace the address in an occupied slot, keeping its tag.
142    #[inline(always)]
143    pub fn set_addr(&mut self, i: usize, addr: Addr) {
144        debug_assert_ne!(self.tags[i], EMPTY);
145        write56(&mut self.addrs[i], addr.to_bits());
146    }
147
148    /// Empty slot `i`.
149    ///
150    /// Tombstone free (`05` section 2.3). The tag goes back to zero and the
151    /// address is cleared so that a stale address cannot be followed by a
152    /// probe that races a concurrent split in a future revision.
153    #[inline(always)]
154    pub fn clear(&mut self, i: usize) {
155        self.tags[i] = EMPTY;
156        self.addrs[i] = [0; 7];
157    }
158
159    /// The link to this bucket's overflow bucket, if it has one.
160    #[inline(always)]
161    pub fn link(&self) -> Option<u64> {
162        if self.flags & FLAG_OVERFLOW == 0 {
163            return None;
164        }
165        Some(read56(&self.link))
166    }
167
168    /// Whether this bucket has an overflow bucket.
169    #[inline(always)]
170    pub fn has_overflow(&self) -> bool {
171        self.flags & FLAG_OVERFLOW != 0
172    }
173
174    /// Attach an overflow bucket.
175    #[inline]
176    pub fn set_link(&mut self, target: u64) {
177        write56(&mut self.link, target);
178        self.flags |= FLAG_OVERFLOW;
179    }
180
181    /// Detach the overflow bucket.
182    #[inline]
183    pub fn clear_link(&mut self) {
184        self.link = [0; 7];
185        self.flags &= !FLAG_OVERFLOW;
186    }
187
188    /// How many slots are occupied. Diagnostics only, not on the probe path.
189    pub fn occupancy(&self) -> u32 {
190        self.tags.iter().filter(|&&t| t != EMPTY).count() as u32
191    }
192}
193
194impl core::fmt::Debug for Bucket {
195    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
196        f.debug_struct("Bucket")
197            .field("tags", &self.tags)
198            .field("occupancy", &self.occupancy())
199            .field("link", &self.link())
200            .finish()
201    }
202}
203
204/// A set of matching slots, iterated lowest first.
205#[derive(Debug, Clone, Copy, PartialEq, Eq)]
206pub struct SlotMask(u64);
207
208impl SlotMask {
209    /// Whether nothing matched.
210    #[inline(always)]
211    pub const fn is_empty(self) -> bool {
212        self.0 == 0
213    }
214
215    /// The lowest matching slot, or `None`.
216    #[inline(always)]
217    pub const fn first(self) -> Option<usize> {
218        if self.0 == 0 {
219            None
220        } else {
221            Some((self.0.trailing_zeros() / 8) as usize)
222        }
223    }
224
225    /// How many slots matched.
226    #[inline(always)]
227    pub const fn count(self) -> u32 {
228        self.0.count_ones()
229    }
230}
231
232impl Iterator for SlotMask {
233    type Item = usize;
234
235    #[inline(always)]
236    fn next(&mut self) -> Option<usize> {
237        if self.0 == 0 {
238            return None;
239        }
240        let i = (self.0.trailing_zeros() / 8) as usize;
241        self.0 &= self.0 - 1;
242        Some(i)
243    }
244}
245
246#[inline(always)]
247fn read56(b: &[u8; 7]) -> u64 {
248    // Assembled byte by byte rather than as a masked 8 byte read. The last
249    // address in a bucket ends one byte before the link, so an 8 byte read from
250    // the final slot would run into it, and the branch to avoid that costs more
251    // than this does. The compiler turns this into a load and a shift on every
252    // target that allows unaligned access.
253    u64::from_le_bytes([b[0], b[1], b[2], b[3], b[4], b[5], b[6], 0])
254}
255
256#[inline(always)]
257fn write56(b: &mut [u8; 7], v: u64) {
258    let x = v.to_le_bytes();
259    b.copy_from_slice(&x[..7]);
260}
261
262#[cfg(test)]
263mod tests {
264    use super::*;
265    use yo_common::Space;
266
267    #[test]
268    fn a_bucket_is_one_cache_line() {
269        assert_eq!(size_of::<Bucket>(), 64);
270        assert_eq!(align_of::<Bucket>(), 64);
271    }
272
273    #[test]
274    fn field_offsets_match_the_specification() {
275        let b = Bucket::EMPTY;
276        let base = (&b as *const Bucket).addr();
277        assert_eq!((&raw const b.tags).addr() - base, 0);
278        assert_eq!((&raw const b.flags).addr() - base, 7);
279        assert_eq!((&raw const b.addrs).addr() - base, 8);
280        assert_eq!((&raw const b.link).addr() - base, 57);
281    }
282
283    #[test]
284    fn an_empty_bucket_matches_nothing_and_is_all_free() {
285        let b = Bucket::EMPTY;
286        assert!(b.match_tag(1).is_empty());
287        assert!(b.match_tag(255).is_empty());
288        assert_eq!(b.match_empty().count(), SLOTS as u32);
289        assert!(!b.is_full());
290    }
291
292    #[test]
293    fn set_then_find() {
294        let mut b = Bucket::EMPTY;
295        let a = Addr::new(Space::Arena, 0x1234_5678);
296        b.set(3, 0xAB, a);
297        let m = b.match_tag(0xAB);
298        assert_eq!(m.count(), 1);
299        assert_eq!(m.first(), Some(3));
300        assert_eq!(b.addr(3), a);
301        assert_eq!(b.tag(3), 0xAB);
302    }
303
304    #[test]
305    fn every_slot_round_trips_every_space() {
306        for &space in Space::ALL {
307            for i in 0..SLOTS {
308                let mut b = Bucket::EMPTY;
309                let a = Addr::new(space, yo_common::MAX_OFFSET);
310                b.set(i, 0x5A, a);
311                assert_eq!(b.addr(i), a, "slot {i} space {space:?}");
312                assert_eq!(b.match_tag(0x5A).first(), Some(i));
313            }
314        }
315    }
316
317    /// The last address ends at byte 57 and the link starts there. A widened
318    /// read of the final slot would pick up link bytes, so this is the test
319    /// that catches it.
320    #[test]
321    fn the_last_slot_does_not_bleed_into_the_link() {
322        let mut b = Bucket::EMPTY;
323        let a = Addr::new(Space::Arena, 0xABCD);
324        b.set(SLOTS - 1, 0x11, a);
325        b.set_link(yo_common::MAX_OFFSET);
326        assert_eq!(b.addr(SLOTS - 1), a);
327        assert_eq!(b.link(), Some(yo_common::MAX_OFFSET));
328    }
329
330    /// And the reverse: writing the link must not disturb the last address.
331    #[test]
332    fn the_link_does_not_bleed_into_the_last_slot() {
333        let mut b = Bucket::EMPTY;
334        b.set_link(u64::MAX >> 8);
335        let a = Addr::new(Space::Graph, 7);
336        b.set(SLOTS - 1, 0x22, a);
337        assert_eq!(b.link(), Some(u64::MAX >> 8));
338        assert_eq!(b.addr(SLOTS - 1), a);
339    }
340
341    #[test]
342    fn all_seven_slots_are_independent() {
343        let mut b = Bucket::EMPTY;
344        for i in 0..SLOTS {
345            b.set(
346                i,
347                (i as u8) + 1,
348                Addr::new(Space::Arena, (i as u64 + 1) * 16),
349            );
350        }
351        assert!(b.is_full());
352        for i in 0..SLOTS {
353            assert_eq!(b.tag(i), (i as u8) + 1);
354            assert_eq!(b.addr(i).offset(), (i as u64 + 1) * 16);
355            assert_eq!(b.match_tag((i as u8) + 1).first(), Some(i));
356        }
357    }
358
359    #[test]
360    fn duplicate_tags_all_report() {
361        let mut b = Bucket::EMPTY;
362        b.set(1, 0x77, Addr::new(Space::Arena, 16));
363        b.set(4, 0x77, Addr::new(Space::Arena, 32));
364        b.set(6, 0x77, Addr::new(Space::Arena, 48));
365        let m = b.match_tag(0x77);
366        assert_eq!(m.count(), 3);
367        assert_eq!(m.collect::<Vec<_>>(), vec![1, 4, 6]);
368    }
369
370    /// A tag equal to the flags byte must not produce a phantom eighth slot.
371    /// This is why the lane mask covers seven lanes and not eight.
372    #[test]
373    fn the_flags_byte_is_never_a_match() {
374        let mut b = Bucket::EMPTY;
375        b.set_link(1); // sets flags to 1
376        assert!(
377            b.match_tag(1).is_empty(),
378            "flags leaked into the tag search"
379        );
380        assert_eq!(b.match_empty().count(), SLOTS as u32);
381        // And with flags at zero, searching for the empty tag must still find
382        // seven slots rather than eight.
383        let c = Bucket::EMPTY;
384        assert_eq!(c.match_empty().count(), SLOTS as u32);
385    }
386
387    #[test]
388    fn clear_frees_the_slot() {
389        let mut b = Bucket::EMPTY;
390        b.set(2, 0x99, Addr::new(Space::Arena, 64));
391        assert_eq!(b.match_empty().count(), 6);
392        b.clear(2);
393        assert!(b.match_tag(0x99).is_empty());
394        assert_eq!(b.match_empty().count(), 7);
395        assert_eq!(b.addr(2), Addr::NONE);
396    }
397
398    #[test]
399    fn links_attach_and_detach() {
400        let mut b = Bucket::EMPTY;
401        assert_eq!(b.link(), None);
402        assert!(!b.has_overflow());
403        b.set_link(4096);
404        assert!(b.has_overflow());
405        assert_eq!(b.link(), Some(4096));
406        b.clear_link();
407        assert_eq!(b.link(), None);
408        assert!(!b.has_overflow());
409    }
410
411    #[test]
412    #[should_panic(expected = "empty tag")]
413    fn setting_the_empty_tag_is_refused() {
414        let mut b = Bucket::EMPTY;
415        b.set(0, EMPTY, Addr::new(Space::Arena, 16));
416    }
417
418    /// Exhaustive: for every occupancy pattern and every tag, the SWAR mask
419    /// must agree with a byte by byte scan. 128 patterns times 256 tags is
420    /// cheap and it covers every borrow interaction the subtract can produce.
421    #[test]
422    fn swar_agrees_with_a_plain_scan() {
423        for pattern in 0u32..128 {
424            let mut b = Bucket::EMPTY;
425            for i in 0..SLOTS {
426                if pattern & (1 << i) != 0 {
427                    // Tags 1..=7 by slot, so patterns differ in content too.
428                    b.set(i, (i as u8) + 1, Addr::new(Space::Arena, 16));
429                }
430            }
431            // Every tag natively. Under Miri the tags that mean something plus
432            // the ones that exercise the high bit of the SWAR word, which is
433            // where a match either works or does not: a hundred and twenty
434            // eight patterns against two hundred and fifty six tags is thirty
435            // two thousand laps of an interpreter to prove something a couple
436            // of thousand already proves.
437            const MIRI_TAGS: [u8; 14] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0x40, 0x7f, 0x80, 0xff];
438            let tags: Vec<u8> = if cfg!(miri) {
439                MIRI_TAGS.to_vec()
440            } else {
441                (0..=255u8).collect()
442            };
443            for tag in tags {
444                let want: Vec<usize> = (0..SLOTS).filter(|&i| b.tags[i] == tag).collect();
445                let got: Vec<usize> = b.match_tag(tag).collect();
446                assert_eq!(got, want, "pattern {pattern:#b} tag {tag}");
447            }
448        }
449    }
450}
yo_index/bucket.rs

yo_index/
bucket.rs
