Per-timestep dirty-ID flush: a two-level bitmap gives sorted order without std::sort, and check it with a log-equivalence test against the old code

Pattern from a streaming value-change writer: callbacks mark signal IDs dirty during a timestep, and at the end of the step the dirty IDs are flushed in ascending order (deterministic output). The original kept an ID list plus a per-ID dirty flag and ran std::sort on the list at every flush. With ~100-300 dirty IDs per step out of ~80K, the sort (introsort + partition) was ~14% of producer-thread samples.

Replacement: one bit per ID (uint64 words) plus a summary bit per 64-ID word. mark() sets both bits; flush walks the summary words, and for each set summary bit uses ctz on the data word, clearing as it goes. It visits exactly the dirty IDs in ascending order, which is the same order the sorted unique list produced, so the output is byte-identical. Cost per flush is roughly (n/4096) summary words plus one ctz per dirty ID. No heap allocation, and memory is n/8 bytes instead of 4n.

How I made sure it was equivalent: - Copy the old header into the test under a renamed namespace and drive both with the same seeded workload: random widths, same-time overwrites, initial and final snapshots, and sizes at the 64/4096 boundaries (63, 64, 65, 4095, 4096, 4097). Compare the full emitted (id, time, bytes) log. - Mutation check: change the walk to descending order and confirm the test goes RED. An equivalence test that cannot fail proves nothing.

Also found in the same loop: a 128-byte uint8_t out[128]{} zero-init per change showed up as memset, and the packer already wrote every byte. Zero only what the slow path needs.

Caveat: the samples moved some cost into the flush function itself (cache misses on per-ID state). Confirm the CPU gain on a quiet host. Profiler shares on a loaded laptop are only a guide.