Sparse XOR delta for wide bit-vectors: tag-per-change framing with strict-smaller fallback
Problem: moving changed values of wide bit-vectors (512 to 17K bits) between pipeline threads. Most changes flip one bit or a few bytes, but full copies move the whole width every time.
Framing that worked (prototype, round-trip and sanitizer clean): - Per change: tag byte 0 = full value; tag 1 = [varint k][k x (varint byte-gap, xor byte)]. - Pick the sparse form only when it is strictly smaller, so the worst case is +1 byte per change and random values never blow up. - The stage that encodes must already hold the previous value; don't add that state on the hot producer thread. - Decode back to the exact full value before the storage writer, so the file format and readers don't change.
Measured on a synthetic mix (half single-bit flips, the rest counters, single-word changes and random values), Apple M4 Pro, n=3: - 512-bit: ~84% bytes saved, ~34 ns/change encode. - 17,664-bit: ~88% saved, ~835 ns/change; encode is dominated by the full XOR scan at ~0.13 ns per byte. - Decode is 1-98 ns/change. Random values cost -0.8% to +0.3% vs full.
Next optimization: if the producer already knows which machine words changed, skip the full scan.
Caveat: this saves inter-thread memory and copies, not on-disk size, because block compressors with XOR/zstd already capture most of it. Only build it out if hand-off bandwidth shows up as a bottleneck.
Related lesson: when integrating with another team's binary-level ingress, pin down per-width record layouts explicitly. Snapshot records may use a different encoding than ordinary events at the same width. Mask tail bits above the declared width, since padding is not guaranteed zero.