Opensource internals

SipHash's Field Order Is a SIMD Hint: How Rust's Default Hasher Vectorises Itself

4 min read Jay Hubbert

Rust's SipHash declares its state fields in the order v0, v2, v1, v3 so that the compiler can find two independent SIMD lanes and vectorise the compression round.

TL;DR: SipHash’s four state words are v0, v1, v2, v3. Rust declares them as v0, v2, v1, v3 — and the comment says why: “v0, v2 and v1, v3 show up in pairs in the algorithm, and simd implementations of SipHash will use vectors of v02 and v13. By placing them in this order in the struct, the compiler can pick up on just a few simd optimizations by itself.” A field order is a vectorisation hint.

The state

rust 
// library/core/src/hash/sip.rs:62-94

#[derive(Debug, Clone, Copy)]
#[repr(C)]
struct State {
    // v0, v2 and v1, v3 show up in pairs in the algorithm,
    // and simd implementations of SipHash will use vectors
    // of v02 and v13. By placing them in this order in the struct,
    // the compiler can pick up on just a few simd optimizations by itself.
    v0: u64,
    v2: u64,
    v1: u64,
    v3: u64,
}

macro_rules! compress {
    ($state:expr) => {{ compress!($state.v0, $state.v1, $state.v2, $state.v3) }};
    ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => {{
        $v0 = $v0.wrapping_add($v1);
        $v2 = $v2.wrapping_add($v3);
        $v1 = $v1.rotate_left(13);
        $v1 ^= $v0;
        $v3 = $v3.rotate_left(16);
        $v3 ^= $v2;
        $v0 = $v0.rotate_left(32);

        $v2 = $v2.wrapping_add($v1);
        $v0 = $v0.wrapping_add($v3);
        $v1 = $v1.rotate_left(17);
        $v1 ^= $v2;
        $v3 = $v3.rotate_left(21);
        $v3 ^= $v0;
        $v2 = $v2.rotate_left(32);
    }};
}

Read the field order: v0, v2, v1, v3. Not v0, v1, v2, v3.

The algorithm interleaves the four words as two independent pairs: v0 accumulates from v1 and v3, v2 accumulates from v3 and v1. The rounds are ARX (add, rotate, xor) operations, and the two pairs have no data dependency between them within a round. A SIMD implementation would put v0 and v2 in one 128-bit lane and v1 and v3 in the other.

By declaring the struct in the order v0, v2, v1, v3, the two lanes are contiguous in memory, so LLVM’s SLP vectoriser can find them without having to prove the reordering itself. A naive field order would require the vectoriser to shuffle.

The comment is unusually explicit about the reasoning: “the compiler can pick up on just a few simd optimizations by itself”.

The round function is deliberately written as a macro

The compress! macro takes the four words as parameters, so the same code can be instantiated over a single State or over four separate locals (which is what the unrolled tail handling does). The macro also avoids re-reading the struct fields between rounds.

The tail, without a memcpy

rust 
// library/core/src/hash/sip.rs:115-144

/// Loads a u64 using up to 7 bytes of a byte slice. It looks clumsy but the
/// `copy_nonoverlapping` calls that occur (via `load_int_le!`) all have fixed
/// sizes and avoid calling `memcpy`, which is good for speed.
#[inline]
unsafe fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 {

The comment says it all: the awkward-looking code is written so that every load is a fixed-size copy_nonoverlapping, which LLVM turns into a single mov instead of a call to memcpy.

The prefix-free string hack

rust 
// library/core/src/hash/sip.rs:302-308

#[inline]
fn write_str(&mut self, s: &str) {
    // This hasher works byte-wise, and `0xFF` cannot show up in a `str`,
    // so just hashing the one extra byte is enough to be prefix-free.
    self.write(s.as_bytes());
    self.write_u8(0xFF);
}

Hashing "ab" followed by "c" must not collide with "a" followed by "bc". The standard fix is to hash the length, which costs 8 bytes of hashing. Rust’s fix costs one byte: 0xFF cannot appear in a str, so appending it makes the encoding prefix-free without a length field.

Why SipHash at all?

The default RandomState uses SipHash-1-3 because HashMap is exposed to attacker-controlled keys. A non-keyed hash like FxHash is trivially collided: an attacker can find keys that all land in the same bucket and turn a lookup into a linear scan. SipHash’s keyed construction makes that require knowledge of the (random, per-thread, per-map) key.

The compiler does not use SipHash — rustc_data_structures has its own FxHash, which is a multiply-xor-shift hash:

The reason is the opposite: inside a compiler, the keys are not attacker-controlled, and the compiler hashes millions of small keys during a build. DoS resistance is worthless there; speed is everything.

Where it lives

  • library/core/src/hash/sip.rs — the state layout, the compression macro, the tail handling.
  • library/core/src/hash/mod.rs — the Hasher trait.
  • library/std/src/hash/random.rs — RandomState.
  • compiler/rustc_data_structures/src/fx.rs — the compiler’s own hash.

Takeaway

There is a class of performance hint that lives below the level of algorithms: the order of struct fields. Because LLVM’s SLP vectoriser works on adjacent values, putting v0 next to v2 — rather than in “natural” order — lets it discover a two-lane SIMD computation that it would otherwise have to prove. The cost is zero and the effect is measurable. It is also a lovely reminder that in a systems language, the source layout is part of the design.

RustInternalsStdPerformanceHashingSimd