yo_common/
eq.rs

1//! Comparing two byte strings without leaving the function.
2//!
3//! `a == b` on two slices ends up in the platform's `memcmp`. That is the right
4//! answer for a megabyte and the wrong one for a key: a profile of `SADD` on
5//! the wire had seven percent of the command inside `_platform_memcmp` and the
6//! stub that reaches it, comparing nineteen bytes. The call itself, the length
7//! dispatch inside it and the return are most of that, and none of it is the
8//! comparison.
9//!
10//! So this compares in machine words and stays inline. A key or a member is
11//! almost always shorter than a cache line, and the shapes that matter are the
12//! ones a benchmark and a real workload agree on: `key:000000000001` at
13//! fourteen bytes, `member:000000000001` at nineteen, a session id at thirty
14//! two.
15//!
16//! # The last word overlaps
17//!
18//! A comparison of nineteen bytes reads bytes 0..8, 8..16 and then 11..19,
19//! which covers the whole string with three loads and no tail loop. The middle
20//! five bytes are read twice, which costs nothing and is what keeps the shape
21//! branch free. Below eight bytes the same trick runs on four byte words, and
22//! below four it is a loop of at most three bytes, which is shorter than any
23//! cleverness would be.
24//!
25//! # This is equality and not ordering
26//!
27//! There is no `cmp` here on purpose. Nothing on the hot path needs to know
28//! which of two keys sorts first, and a word wise ordering would have to
29//! byte swap on a little endian machine to get the answer right, which is the
30//! sort of subtlety that is worth avoiding when nothing is asking for it.
31
32/// The eight bytes at `at`, as a machine word.
33#[inline(always)]
34fn w8(s: &[u8], at: usize) -> u64 {
35    u64::from_ne_bytes([
36        s[at],
37        s[at + 1],
38        s[at + 2],
39        s[at + 3],
40        s[at + 4],
41        s[at + 5],
42        s[at + 6],
43        s[at + 7],
44    ])
45}
46
47/// The four bytes at `at`, as a half word.
48#[inline(always)]
49fn w4(s: &[u8], at: usize) -> u32 {
50    u32::from_ne_bytes([s[at], s[at + 1], s[at + 2], s[at + 3]])
51}
52
53/// Whether `a` and `b` hold the same bytes.
54///
55/// The same answer as `a == b` and the same cost model as `memcmp` for a long
56/// string, without the call for a short one.
57#[inline]
58#[must_use]
59pub fn bytes_eq(a: &[u8], b: &[u8]) -> bool {
60    let n = a.len();
61    if n != b.len() {
62        return false;
63    }
64    if n >= 8 {
65        let mut at = 0;
66        while at + 8 < n {
67            if w8(a, at) != w8(b, at) {
68                return false;
69            }
70            at += 8;
71        }
72        // The last whole word, which reaches back over bytes already compared
73        // when the length is not a multiple of eight.
74        return w8(a, n - 8) == w8(b, n - 8);
75    }
76    if n >= 4 {
77        return w4(a, 0) == w4(b, 0) && w4(a, n - 4) == w4(b, n - 4);
78    }
79    let mut at = 0;
80    while at < n {
81        if a[at] != b[at] {
82            return false;
83        }
84        at += 1;
85    }
86    true
87}
88
89#[cfg(test)]
90mod tests {
91    use super::bytes_eq;
92
93    /// Every length from nothing to past two words, equal and then not equal at
94    /// every position in turn.
95    ///
96    /// The overlapping last word is the part worth being thorough about: a
97    /// difference in the bytes that get read twice has to be found, and so does
98    /// one in the bytes that are only read by the overlapping load.
99    #[test]
100    fn it_agrees_with_the_slice_comparison_at_every_length_and_position() {
101        for n in 0..40usize {
102            let a: Vec<u8> = (0..n).map(|i| (i % 251) as u8).collect();
103            assert!(bytes_eq(&a, &a.clone()), "{n} bytes against itself");
104            for at in 0..n {
105                let mut b = a.clone();
106                b[at] ^= 0x80;
107                assert!(!bytes_eq(&a, &b), "{n} bytes differing at {at}");
108                assert_eq!(bytes_eq(&a, &b), a == b);
109            }
110        }
111    }
112
113    #[test]
114    fn a_different_length_is_never_equal() {
115        for n in 0..40usize {
116            let a = vec![b'x'; n];
117            let b = vec![b'x'; n + 1];
118            assert!(!bytes_eq(&a, &b));
119            assert!(!bytes_eq(&b, &a));
120        }
121    }
122
123    #[test]
124    fn nothing_is_the_same_as_nothing() {
125        assert!(bytes_eq(b"", b""));
126        assert!(bytes_eq(&[], &[]));
127    }
128}
yo_common/eq.rs

yo_common/
eq.rs
