Single-pass min/max calculation for page bounds below threshold

perfloop/parquet-go · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_2624dwdrfq

Verdict

REFUTED · settled 2026-07-19

What happened: The current amd64 implementation is already the intended hybrid, not an unoptimized two-pass algorithm: boundsInt64 dispatches to combinedBoundsInt64 at 1MiB and above. Its checked-in source documentation records that the combined kernel wins for memory-bound 10MiB inputs but the separate min/max kernels are faster for cache-resident 4KiB inputs, with a crossover around 256KiB. A local native verification on base 988b7b98 used the existing BenchmarkBoundsInt64 sweep (10 runs per arm): changing only the Int64 cutoff from 1MiB to 256KiB moved the 256KiB median from 4086 ns/op to 4380 ns/op (about 7.2% slower). This falsifies the claimed below-threshold single-pass win at the proposed target; the apparent doubled scan is a deliberate, documented throughput tradeoff rather than an inefficient-algorithm opportunity.

Hypothesis

When writing data pages in ColumnWriter.writeDataPage, if writePageStats is enabled, ColumnWriter.makePageStatistics invokes page.Bounds() to calculate the min/max values for page headers and metadata. For non-vectorized paths (sizes below combinedBoundsThreshold), the bounds methods (e.g. boundsInt32, boundsInt64, etc.) call minInt32(data) followed by maxInt32(data). This performs two separate linear scans over the entire slice. By combining the min and max calculations into a single loop pass (e.g. a single-pass combined bounds loop), we halve the memory bandwidth/load instructions for these bounds calculations. The proof target is a benchmark comparing the throughput and CPU instructions of page.Bounds() on primitive slices of varying lengths below combinedBoundsThreshold.

Change to test: In page_bounds_amd64.go, optimize boundsInt32, boundsInt64, boundsUint32, boundsUint64, boundsFloat32, and boundsFloat64 to compute both min and max in a single pass of the slice instead of making two independent linear scans (one for min and one for max) when the slice size is below the combinedBoundsThreshold. Or, alternatively, lower combinedBoundsThreshold or always run a single-pass loop that computes both min and max simultaneously, which reduces memory bandwidth pressure and halves the number of memory reads on the hot-path page stats generation.

Where it lives

perfloop/parquet-go · writer.go

Evidence

Timeline