yo_common/

wyhash.rs

//! wyhash, the shard's key hash.
//!
//! Written here rather than pulled in. aki measured wyhash at 1.95 ns against
//! fnv1a's 5.39 ns on the same keys (L13), and the whole index probe budget is
//! 4 ns, so the hash is not a place to accept a dependency's version churn.
//!
//! This is wyhash final version 3 with the default secret, which is the variant
//! every other implementation calls `wyhash` today. The test vectors at the
//! bottom are the reference vectors from the C implementation, so a change that
//! alters a hash value fails the build rather than silently repartitioning
//! every existing `.yo` file.

/// The default secret from the reference implementation.
const SECRET: [u64; 4] = [
    0x2d35_8dcc_aa6c_78a5,
    0x8bb8_4b93_962e_acc9,
    0x4b33_a62e_d433_d4a3,
    0x4d5a_2da5_1de1_aa47,
];

/// 64x64 to 128 multiply, returning the low and high halves.
#[inline(always)]
fn mum(a: u64, b: u64) -> (u64, u64) {
    let r = (a as u128).wrapping_mul(b as u128);
    (r as u64, (r >> 64) as u64)
}

#[inline(always)]
fn mix(a: u64, b: u64) -> u64 {
    let (lo, hi) = mum(a, b);
    lo ^ hi
}

#[inline(always)]
fn r8(p: &[u8]) -> u64 {
    u64::from_le_bytes([p[0], p[1], p[2], p[3], p[4], p[5], p[6], p[7]])
}

#[inline(always)]
fn r4(p: &[u8]) -> u64 {
    u32::from_le_bytes([p[0], p[1], p[2], p[3]]) as u64
}

#[inline(always)]
fn r3(p: &[u8], k: usize) -> u64 {
    ((p[0] as u64) << 16) | ((p[k >> 1] as u64) << 8) | (p[k - 1] as u64)
}

/// Hash `key` with `seed`.
///
/// The shard uses seed 0. A seed is exposed because the bloom and hyperloglog
/// types need independent hash families over the same bytes.
#[inline]
pub fn wyhash(key: &[u8], seed: u64) -> u64 {
    let len = key.len();
    let mut seed = seed ^ mix(seed ^ SECRET[0], SECRET[1]);
    let a: u64;
    let b: u64;

    if len <= 16 {
        if len >= 4 {
            // Two overlapping 4 byte reads from each end. The `(len >> 3) << 2`
            // term is 0 for 4..=7 and 4 for 8..=15, which is what makes the
            // pairs overlap rather than repeat for the short lengths.
            let q = (len >> 3) << 2;
            a = (r4(key) << 32) | r4(&key[q..]);
            b = (r4(&key[len - 4..]) << 32) | r4(&key[len - 4 - q..]);
        } else if len > 0 {
            a = r3(key, len);
            b = 0;
        } else {
            a = 0;
            b = 0;
        }
    } else {
        // Offsets into `key` rather than a re-sliced cursor. The tail read below
        // deliberately reaches back over bytes the loop already consumed, which
        // a shrinking slice would make unrepresentable.
        let mut off = 0usize;
        let mut i = len;

        if i >= 48 {
            let mut see1 = seed;
            let mut see2 = seed;
            while i >= 48 {
                seed = mix(r8(&key[off..]) ^ SECRET[1], r8(&key[off + 8..]) ^ seed);
                see1 = mix(
                    r8(&key[off + 16..]) ^ SECRET[2],
                    r8(&key[off + 24..]) ^ see1,
                );
                see2 = mix(
                    r8(&key[off + 32..]) ^ SECRET[3],
                    r8(&key[off + 40..]) ^ see2,
                );
                off += 48;
                i -= 48;
            }
            seed ^= see1 ^ see2;
        }

        while i > 16 {
            seed = mix(r8(&key[off..]) ^ SECRET[1], r8(&key[off + 8..]) ^ seed);
            off += 16;
            i -= 16;
        }

        // off + i == len, so this is the last 16 bytes of the key.
        a = r8(&key[len - 16..]);
        b = r8(&key[len - 8..]);
    }

    let (a, b) = mum(a ^ SECRET[1], b ^ seed);
    mix(a ^ SECRET[0] ^ (len as u64), b ^ SECRET[1])
}

/// Hash with the shard's seed.
///
/// Every key placement decision in the engine goes through this, so that a
/// change of seed is one edit rather than a search.
#[inline(always)]
pub fn hash_key(key: &[u8]) -> u64 {
    wyhash(key, 0)
}

/// The 8 high bits of a hash, as the index bucket stores them.
///
/// Zero means empty in a bucket, so a hash whose top byte is zero is given tag
/// 1 instead. The collision cost of folding one value into another is one extra
/// key comparison on 1 in 256 probes, and the alternative is a separate
/// occupancy word and a second load.
#[inline(always)]
pub const fn tag_of(hash: u64) -> u8 {
    let t = (hash >> 56) as u8;
    if t == 0 { 1 } else { t }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Appends `n` in decimal.
    fn push_num(out: &mut Vec<u8>, n: u32) {
        if n >= 10 {
            push_num(out, n / 10);
        }
        out.push(b'0' + (n % 10) as u8);
    }

    /// Vectors produced by the reference C implementation.
    ///
    /// Generated by compiling upstream `wyhash.h` at WYHASH_CONDOM 1 with the
    /// default secret and hashing a fixed byte pattern, `buf[i] = (i*7+13) % 251`,
    /// at every length where the algorithm changes shape: the 4, 16, 48 and 16
    /// again boundaries, and either side of each. Two seeds per length, because
    /// the seed feeds both the prologue and the tail mix and a bug can hide in
    /// one and not the other.
    ///
    /// These are a conformance lock, not a quality claim. If one of them moves,
    /// every existing `.yo` file has been repartitioned and the change is not
    /// shippable.
    #[test]
    fn reference_vectors() {
        const VECTORS: &[(usize, u64, u64)] = &[
            (0, 0, 0x93228a4de0eec5a2),
            (0, 0xdeadbeefcafe1234, 0x503eb6b76bdddf6a),
            (1, 0, 0xb743f05e0334871c),
            (1, 0xdeadbeefcafe1234, 0xa6d34f7586585149),
            (2, 0, 0x28b8761367a2c6fe),
            (2, 0xdeadbeefcafe1234, 0xfb04ad55c47b05d5),
            (3, 0, 0x51f03dcee96db0fa),
            (3, 0xdeadbeefcafe1234, 0xb3b1e9b933f562dc),
            (4, 0, 0x63e00718a6d4f4b7),
            (4, 0xdeadbeefcafe1234, 0x4855ac52ab265d8f),
            (5, 0, 0x9ef5dce95adebad0),
            (5, 0xdeadbeefcafe1234, 0x8e3109951c14d448),
            (7, 0, 0x78f6520add84ac5e),
            (7, 0xdeadbeefcafe1234, 0x1d55d13730d8415c),
            (8, 0, 0x98bbb3a2b3bba145),
            (8, 0xdeadbeefcafe1234, 0x1d7d14601c86064f),
            (9, 0, 0x8a4336709aa03e64),
            (9, 0xdeadbeefcafe1234, 0xa6114ea701c654b9),
            (15, 0, 0x398099ca2f2dfcd5),
            (15, 0xdeadbeefcafe1234, 0x07400d0acd97aa2f),
            (16, 0, 0x31692917ca3ab597),
            (16, 0xdeadbeefcafe1234, 0xb8ff17cdb0d4b1a8),
            (17, 0, 0x1cde6dc1d5cb836a),
            (17, 0xdeadbeefcafe1234, 0x3c83b9dfecbe18a4),
            (18, 0, 0x7d6c4fc7691eec86),
            (18, 0xdeadbeefcafe1234, 0x2e41d8a4f547009b),
            (31, 0, 0x559ac6703ac3d00e),
            (31, 0xdeadbeefcafe1234, 0x7490b7565d08d3aa),
            (32, 0, 0x869edcb7f8c6e88d),
            (32, 0xdeadbeefcafe1234, 0xfde153bdc921f628),
            (33, 0, 0x25a357dbecbab818),
            (33, 0xdeadbeefcafe1234, 0x75d4db744c1ad719),
            (47, 0, 0x26a8fa17ae56094e),
            (47, 0xdeadbeefcafe1234, 0xc7abd5000339a9db),
            (48, 0, 0xc7f0608db098eb0d),
            (48, 0xdeadbeefcafe1234, 0x8b90c58340ad764c),
            (49, 0, 0xd3f0a40ba8f9b1a6),
            (49, 0xdeadbeefcafe1234, 0x132f911560ef3fa5),
            (63, 0, 0x325a689473b1c1a5),
            (63, 0xdeadbeefcafe1234, 0x6b7f55c7b078e75c),
            (64, 0, 0x3d6436f595468fea),
            (64, 0xdeadbeefcafe1234, 0x6421f0f5d6084af7),
            (65, 0, 0x37d6f92314dcc53b),
            (65, 0xdeadbeefcafe1234, 0xfcf7ea1b14bfc627),
            (95, 0, 0x648820b80a4835b4),
            (95, 0xdeadbeefcafe1234, 0xc379879b80991aae),
            (96, 0, 0x31105c4a5a7062f0),
            (96, 0xdeadbeefcafe1234, 0xb55bf2517b5725fb),
            (97, 0, 0x8d28a022c26475ab),
            (97, 0xdeadbeefcafe1234, 0xbf1d8e4618c274db),
            (127, 0, 0xf58addc6ccbb43d7),
            (127, 0xdeadbeefcafe1234, 0xca48f21107ab1ce0),
            (128, 0, 0x2d766ba73db255df),
            (128, 0xdeadbeefcafe1234, 0x913fedabb47d5cad),
            (200, 0, 0xe11fd2a4ab654ef4),
            (200, 0xdeadbeefcafe1234, 0x592bbccac660734e),
            (255, 0, 0x54ad42c80e00a501),
            (255, 0xdeadbeefcafe1234, 0x67f85b63c0948ebf),
            (299, 0, 0x5ffcff99c0b5fa98),
            (299, 0xdeadbeefcafe1234, 0x7aa342b1566d19f8),
        ];

        let mut buf = [0u8; 300];
        for (i, b) in buf.iter_mut().enumerate() {
            *b = ((i * 7 + 13) % 251) as u8;
        }
        for &(len, seed, want) in VECTORS {
            assert_eq!(
                wyhash(&buf[..len], seed),
                want,
                "length {len} seed {seed:#x} does not match the reference"
            );
        }
    }

    /// Every length from 0 to 200 must at least be reachable without panicking.
    /// The index arithmetic around 16, 17, 48 and 49 is where the bounds get
    /// interesting, and a panic there would be an availability bug.
    #[test]
    fn all_lengths_up_to_200() {
        let buf: Vec<u8> = (0..200u32).map(|i| (i % 251) as u8).collect();
        for n in 0..=200 {
            let _ = wyhash(&buf[..n], 0);
        }
    }

    #[test]
    fn tag_is_never_zero() {
        // A hash whose top byte is zero must still produce a usable tag.
        assert_eq!(tag_of(0x00ff_ffff_ffff_ffff), 1);
        assert_eq!(tag_of(0xab00_0000_0000_0000), 0xab);
    }

    /// Not a quality claim, just a smoke check that the low bits used for
    /// bucket selection are not obviously degenerate for sequential keys, which
    /// is the shape a benchmark loop produces.
    #[test]
    fn sequential_keys_spread_over_buckets() {
        // What both assertions actually depend on is the ratio of keys to
        // buckets, not the size of either. A hundred keys per bucket is what
        // makes an empty bucket damning and three times the mean a real
        // outlier, so Miri keeps the ratio and shrinks the table. Sixty four
        // buckets and sixty four hundred keys is the same claim about the same
        // low bits at a fifteenth of the interpreted work.
        let (buckets, keys): (usize, u32) = if cfg!(miri) {
            (64, 6_400)
        } else {
            (1024, 100_000)
        };
        let mut counts = vec![0u32; buckets];
        let mut k = Vec::with_capacity(16);
        for i in 0..keys {
            // The key is built by hand into a buffer that gets reused rather
            // than through `format!`. Same bytes, and under Miri, which charges
            // per operation rather than per instruction, the formatting
            // machinery was most of what this test cost.
            k.clear();
            k.extend_from_slice(b"key:");
            push_num(&mut k, i);
            counts[(hash_key(&k) as usize) & (buckets - 1)] += 1;
        }
        let max = *counts.iter().max().unwrap();
        let mean = keys / buckets as u32;
        assert!(max < mean * 3, "worst bucket {max} against mean {mean}");
        assert!(counts.iter().all(|&c| c > 0), "some bucket got nothing");
    }
}