Bitmap costs and experiments

What it costs

Setting, clearing or testing a bit is 1 ns, 4 cycles at 4 GHz, a thousandth of a budget. The next set bit within a word is 1–2 ns; each empty word after it is about 1 ns, 1 ns per 64 things against the flag scan’s 1 ns per 8; with a summary word a search reads at most three words, 3–5 ns. The flag scan adds a mispredict, 4–5 ns, at each flag it stops on. The bitmap’s one extra cost is in a pool, where alloc reads up to three words and a stack’s pop reads one.

Worked example: 64 instruments, find the next with work

At 14:32:05.000 a burst arrives, and the strategy thread on core 3 drains 30 updates that the feed thread on core 2 has just decoded. They fall on three instruments, ids 5, 42 (BTC-USDT-PERP) and 61, and for each update the strategy sets its instrument’s bit in a u64 called dirty, 30 ORs of 1 ns. After the batch it visits each dirty instrument to look at its quotes and zeroes dirty with one store. The visit is three rounds of trailing_zeros and w &= w - 1, 2–4 cycles each, and a loop exit that may mispredict, the count varying from batch to batch: 2–8 ns, under 1% of a budget.

With dirty: [bool; 64] the strategy clears a 64-byte line and scans all 64 flags, 8 ns, branching on each. The predictor, having learned that flags are clear, mispredicts at 5, 42 and 61: 45–60 cycles, 11–15 ns. The scan costs 19–23 ns, about 2% of a budget and three to ten times the bitmap. With 20 dirty in no pattern a predictor can learn, it mispredicts at about each, 300–400 cycles, and costs 83–108 ns, a tenth of a budget, against the bitmap’s 10–25 ns. Both are small beside the re-pricing that follows, but the bitmap’s cost follows the work and the scan’s the surprises, and surprises multiply in a burst, when the budget is tightest.

Seeing it

Marked #[inline(never)] while looking, since rustc emits a function this small only where it is called, the helper prints with cargo asm --lib next_set_bit_above. Built with RUSTFLAGS="-C target-cpu=native", which lets the compiler use every instruction the build machine has, a current x86-64 part shows tzcnt, lzcnt and popcnt, and for_each’s loop as a tzcnt, the closure’s work and a blsr, which is w &= w - 1 in one instruction. Without the flag the compiler targets the x86-64 of 2003, which had none of these: trailing_zeros becomes a mov of 64 for the zero case and a rep bsf, “bit scan forward” in an encoding newer cores run as tzcnt; leading_zeros a bsr, which gives an index rather than a count, and an xor with 63; count_ones about twenty shifts, ANDs, adds and a multiply. The flag scan is a cmp byte ptr [...], 0 and a jne per flag, with no SIMD. Under perf stat -e branches,branch-misses over a million batches of random flags, the scan should miss about once per set flag and the bitmap once per batch.

Read more: Henry S. Warren, Jr., Hacker’s Delight, 2nd edition (Addison-Wesley, 2012): chapter 2 on the rightmost bits of a word, and chapter 5 on counting bits and zeros. Josh Aas, “Understanding the Linux 2.6.8.1 CPU Scheduler” (Silicon Graphics, 2005), for the O(1) scheduler’s priority bitmap and sched_find_first_bit.