Sparse IDs and lookup experiments

When the venue’s ids are sparse

Some venues send integers, but not small ones. CME, the Chicago futures exchange, names each instrument in its market data by a security id, a 32-bit integer in its message schema, unique to the instrument and not reused until after it expires, so the desk’s 64 instruments arrive as 64 numbers scattered over two billion. Such ids are sparse: integers with gaps so wide that an array indexed by them would need 2³¹ entries, 8 GB at 4 bytes each, nearly all empty. Two structures, built at startup, map them to 0..N.

The first is a sorted Vec<u32> of the desk’s venue ids, each with its InstrumentId beside it. A binary search, looking at the middle and keeping the half the id must be in, finds one among 64 in six halvings over four lines of L1: about 6 ns if the core guesses each halving, up to about 30 ns if it guesses each wrong at 15–20 cycles a miss. The second is a two-level table: the id’s top 16 bits index a first table naming a second-level block, allocated only for top halves that occur, and its bottom 16 bits index that block, which holds the InstrumentId. That is two dependent loads, 2 ns with both lines in L1, where the few lines the desk’s ids touch will stay. It is the shape of the processor’s page tables, for the same reason: a huge key range, mostly unused. Either way the translation happens once, in the decoder.

Where a hash map is right

A HashMap is right wherever its costs are not paid per update: at startup, as in the Interner; for configuration; on threads off the hot path, such as a risk report; and for keys with no small-integer form, such as the order ids a venue assigns. Even then a key can often be made: a gateway that writes each order’s pool slot index into the client order id it sends, its own label for the order, which the venue echoes in every acknowledgement, turns the lookup on acknowledgement into an index. Where a map stays, with_capacity keeps it from rehashing in the loop. The order-book chapter applies the same dense array to prices, which are integers once counted in ticks.

What it costs

A SipHash HashMap<u32, Position> hit costs 20–50 ns, 80–200 cycles, 2–5% of a budget, with the table warm, and 50–100 ns cold in L3, where two lines miss; an FxHash or ahash hit 5–15 ns, 0.5–1.5%. A boxed value adds 3.5–100 ns, and a rehash at around 100,000 entries 1–5 ms to one insert. The dense array costs 1 ns, 4 cycles, 0.1% of a budget, and 10–40 ns with its one line in L3; translating a sparse id, 6–30 ns by binary search and 2 ns by a two-level table. For 64 positions, 2 KB in 32 lines against 5,264 bytes in 83.

Worked example: 10 million lookups of position by instrument

The strategy thread on core 3 replays a recorded session of 10 million updates and looks up the position of each update’s instrument, mostly 42:

The max is the cold case, 50–100 ns for the map after a lull has evicted its lines against 10–40 ns for the array. The replay’s total is not the point; the share of each update’s budget is, and a strategy rarely finds one thing per update: it finds the position, the risk limit, its orders waiting at the venue and the last quote, all by instrument. Four SipHash lookups are 80–200 ns, up to a fifth of a budget spent finding things before any deciding; four array loads are 4 ns, 0.4%.

Seeing it

Count both with the lab’s lookup binary, one structure at a time on core 3:

perf stat -e instructions,cycles,L1-dcache-load-misses -- taskset -c 3 ./lookup map 10000000
perf stat -e instructions,cycles,L1-dcache-load-misses -- taskset -c 3 ./lookup array 10000000

Divide each count by 10 million; cycles over 4 is nanoseconds at 4 GHz. Make each lookup’s id depend on the previous result, or the core overlaps them. Expect 80–200 cycles a lookup for the SipHash map and about 4 for the array, and a wider gap in instructions: the map’s lookup carries SipHash’s rounds, sixty-odd add, rol and xor on x86-64, before the group compare’s pcmpeqb and pmovmskb. L1-dcache-load-misses stays near zero for both while the loop only looks up, since 5 KB and 2 KB both fit in L1; run the strategy’s other work between lookups, or sweep a buffer larger than L1, and the misses rise towards two a lookup for the map and one for the array.

The array’s assembly is short enough to read whole. So small a function is inlined where it is used and has no symbol of its own, so a wrapper keeps one (inlining comes later in this chapter):

#[inline(never)] // its own symbol, so that cargo asm can find it
pub fn qty_of(p: &Positions, id: InstrumentId) -> i64 { p.qty(id) }

cargo install cargo-show-asm provides cargo asm, and cargo asm --lib qty_of prints:

mov  rax, rdi                        ; &Positions
mov  edi, esi                        ; the id
mov  rsi, qword ptr [rax + 16]       ; the length
cmp  rsi, rdi
jbe  .LBB13_2                        ; to panic_bounds_check
mov  rax, qword ptr [rax + 8]        ; the pointer
shl  rdi, 5                          ; id × 32
mov  rax, qword ptr [rax + rdi + 8]  ; qty
ret

The cmp and jbe are the bounds check, the shl the multiply by the 32-byte stride, and the last mov the lookup, its + 8 the offset of qty in declared order, which #[repr(C)] keeps; without it rustc puts qty at offset 0. In a loop the length and pointer are loaded once, before it, leaving a compare, a branch and a mov per lookup.

Read more: Matt Kulukundis, “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”, CppCon 2017, Google’s account of SwissTable, built up a measured step at a time. The hashbrown documentation on docs.rs, and Abseil’s design notes at abseil.io/about/design/swisstables, which explain the control bytes and the 16-wide SSE comparison. Jean-Philippe Aumasson and Daniel J. Bernstein, “SipHash: a fast short-input PRF”, INDOCRYPT 2012 (Cryptology ePrint Archive 2012/351), which proposes SipHash and argues that hash tables should switch to it to resist hash flooding.