Count the Bytes, Not the FLOPs

2 days ago

The article describes how tsbootstrap's batched design, which materialized a large intermediate tensor (160 MB for 10,000 observations and 2,000 replicates), caused memory-bound performance issues due to low arithmetic intensity, leading to slower performance than the incumbent library.
A fused, streaming path was implemented using kernel fusion to avoid materializing the full replicate tensor, reducing memory traffic by keeping the working set in cache and only storing the final statistics (e.g., 16 kB instead of 160 MB).
A second performance wall was addressed by eliminating O(B) seed object allocations through a counter-based random number generator (Philox-4x32-10), reducing setup time from 13.1 ms to 0.55 ms for small workloads and ensuring bitwise reproducibility.
The redesign achieved speedups of 3.1x to 20x on sustained workloads compared to the incumbent, with the fused path winning all 16 benchmark cells, though the materializing path still remains slower.
Key principles: never materialize arrays only consumed by reductions, fuse operations to minimize memory traffic, and derive state rather than carrying it, leading to significant performance gains through subtraction rather than addition of complexity.

Hasty Briefsbeta