Rehashing and dense arrays

Load factor and the rehash

The load factor is the share of buckets in use, entries divided by buckets. The fuller the table, the more often a group is full and the probe goes on, so hashbrown lets it reach 7/8 and no further, keeping at least one bucket in eight empty so that every probe ends. An insert that would pass 7/8 first rehashes: it allocates a table with twice the buckets, recomputes every entry’s position, since a position is the hash’s low bits and a bigger table uses more of them, moves each entry across and frees the old table, an allocation plus work in proportion to the entries. A map from u32 to Position holds 114,688 entries in 131,072 buckets of 40 bytes; the next insert allocates 262,144 buckets, over 10 MB fresh from mmap whose 2,600-odd pages each fault on first write at 0.5–1 µs, and re-hashes and moves all 114,688. At around 100,000 entries a rehash costs 1–5 ms, one to five thousand budgets, all paid by the insert that tipped it. Spread over every insert the cost is constant, and it still makes the tail. HashMap::with_capacity(n) at startup means no rehash at all, if n was right.

The pointer chase and the unpredictable address

Two more costs come from where things sit. One is the value. A map to Box<Position>, or to a value owning a String or Vec, stores a pointer in the bucket, and reaching the value is a second load that cannot start until the first returns, to wherever the allocator put it: 3.5–4 ns from L2, 10–40 ns from L3, 80–100 ns from DRAM. A large value stored inline avoids the chase but makes every bucket large, spreading the table over more lines, an eighth or more of them empty.

The other is the address. A good hash function puts keys that are close together into buckets that are not; that is its job. Instruments 41 and 42 land on unrelated lines, and nothing the program touched recently tells the prefetcher where the next lookup goes. The working set is the whole table: for 64 positions, 128 buckets of 40 bytes and 144 control bytes, 5,264 bytes over 83 lines, any of which a burst of other work may have evicted.

The dense array indexed by a small integer id

When the keys are, or can be made, the integers 0 to N − 1, the key is the index and the map disappears. The desk’s 64 positions become a Vec<Position> whose element i is instrument i’s. Finding instrument 42 is the base address plus 42 × 32, a shift and an add, and one load: 1 ns from L1, 4 cycles, a tenth of a percent of a budget, with no hash, probe, key comparison, collision or growth. The one check is Rust’s bounds check, a test before every v[i] that the index is below the length: a compare and an always-predicted branch, close to free. The 64 positions are 2 KB in 32 lines, small enough to stay in L1 beside everything else.

The small integers come from interning: replacing each distinct value of a kind, here a symbol string, with a small integer that stands for it, recorded once in a table. At startup the program gives each symbol in its instrument list the next unused integer, 0 first, and BTC-USDT-PERP gets 42; the type is InstrumentId, an alias for u32 named for what it means. The Interner keeps a HashMap from symbol to id, used at startup and wherever a string is still read, in the decoder of a venue that names the instrument in every message, and names, indexed by id, so that a log line or an order message can say BTC-USDT-PERP without hashing. From the decoder on, nothing names an instrument by its string: the wire message’s 4-byte id chooses whose state an update goes to, and indexes the position array and the flags marking instruments with orders pending.

use std::collections::HashMap;

pub type InstrumentId = u32; // 0..N, assigned at startup

#[derive(Clone, Copy, Default)]
#[repr(C)]
pub struct Position { pub instrument: InstrumentId, _pad: u32, pub qty: i64, pub avg_price: i64, pub realised: i64 }

/// Startup only: venue symbol to dense id, and back.
pub struct Interner { ids: HashMap<String, InstrumentId>, names: Vec<String> }

impl Interner {
    pub fn new() -> Self { Interner { ids: HashMap::new(), names: Vec::new() } }
    /// The id for `name`, the next unused one the first time it is seen.
    pub fn intern(&mut self, name: &str) -> InstrumentId {
        if let Some(&id) = self.ids.get(name) { return id; }
        let id = self.names.len() as InstrumentId;
        self.ids.insert(name.to_owned(), id);
        self.names.push(name.to_owned());
        id
    }
    pub fn id(&self, name: &str) -> Option<InstrumentId> { self.ids.get(name).copied() }
    pub fn name(&self, id: InstrumentId) -> &str { &self.names[id as usize] }
    pub fn len(&self) -> usize { self.names.len() }
}

/// The hot path's lookup: the id is the index. Built once, for n instruments.
pub struct Positions { by_id: Vec<Position> }

impl Positions {
    pub fn new(n: usize) -> Self {
        Positions { by_id: (0..n as u32).map(|id| Position { instrument: id, ..Default::default() }).collect() }
    }
    pub fn get_mut(&mut self, id: InstrumentId) -> &mut Position { &mut self.by_id[id as usize] }
    pub fn qty(&self, id: InstrumentId) -> i64 { self.by_id[id as usize].qty }
}