Objective

Measure the best-achievable speedups of sum operations with our fully-fused method. (sum is canonical; mean and other statistics are trivially derivable.)

Compressors: logical + physical, where logical is one of {delta, FoR, JPEG/PNG predictors} and physical is one of {bitpacking, PFor}.

Fusion: logical transformation and the operation (sum) are fully fused - streamed in vector registers with no materialisation, not even to L1 buffers.

Investigation: narrowing logical to FoR

I initially targeted fusing delta, which gives good compression ratios while being relatively cheap compute-wise. After fusing it into bitpacking, performance tanked due to sequential dependencies:

x[3] depends on x[2] depends on x[1] depends on x[0]

Even with tricks like Sklansky prefix sums, the prefix-sum portion couldn’t be optimised enough (confirmed via ablation benchmarks). The other predictor-based transformations have even worse sequential dependencies, ruling them out.

FoR (Frame of Reference) offers a better trade-off: greater parallelisability over delta (no fine-grained sequential dependencies) at the expense of slightly worse compression ratios.

FoR compressibility

Full benchmarks: ‣

FoR window widths swept over {4, 8, 16, 32, 64, 128, 256}; I report the best window. Anchors (per-window minima) are stored as uncompressed metadata. I also explored hierarchical FoR (anchors as bitpacked deltas to a global minimum), but improvements were marginal.

Standalone physical vs. FoR+physical:

• Lossless: significant improvement on ETOPO1 (85% → 57% CR), moving it from “no speedup” to “speedup possible”. srtm_highres and worldclim also improve (58% → 37%, 39% → 21%). No improvement on Landsat/Sentinel due to high-frequency noise. Same results for bitpacking and PFor.
• Lossy (max pixel error = 0.1 * std, via LERC): PFor+FoR gives major gains on Landsat & Sentinel (e.g. Landsat band 2: 64% → 24% CR). Without loss, FoR did not help PFor on these datasets; loss unlocks the improvement. Bitpacking sees the same gains as lossless regardless of loss.

Is FoR enough?

The spreadsheet’s RHS columns show the relative benefit of fancier logical transformations over FoR:

• Lossless: less than 20% relative improvement on Landsat & Sentinel; up to 80% on DEMs & WorldClim.
• Lossy: benefit on Landsat/Sentinel increases to up to 60% vs. FoR+PFor, but still no benefit with bitpacking.