Skip to content

perf(cpp): reduce scalar predictor reconstruction in SPRINTZ decode #1114

Open

Description

@ColinLeeo

Language

C++

Description

After #1110 added batch decoding to SPRINTZ, each decoded block is still reconstructed by a scalar loop of eight steps in recalculate(): inverse zigzag, then either the delta cumulation or the FIRE predictor update, and for FLOAT/DOUBLE a memcpy between int32/int64 bit patterns and the floating-point value per element.

  • cpp/src/encoding/int32_sprintz_decoder.h:175
  • cpp/src/encoding/int64_sprintz_decoder.h:176
  • cpp/src/encoding/float_sprintz_decoder.h:169
  • cpp/src/encoding/double_sprintz_decoder.h:166

Stubbing recalculate() out and re-running cpp/bench_mark/sprintz_batch_decode_benchmark.cc (2M values, batch capacity 129, best of 5, Apple Silicon Release) shows it accounts for a meaningful share of decode time:

  • INT32 smooth: 266M → 348M values/s (about 24% of decode time)
  • DOUBLE smooth: 205M → 246M values/s (about 17%)

It is not the dominant cost, but it is the largest remaining scalar section of the decode path.

Possible directions:

  • Fuse reconstruction with the batch copy so values are written to the caller's buffer once instead of reconstructed into current_buffer_ and copied out.
  • SIMD the zigzag + delta path: zigzag is elementwise, and the delta scheme is a prefix sum over exactly 8 values.
  • The FIRE scheme has a loop-carried dependency (each prediction needs the previous reconstructed value), so it likely stays scalar; at minimum avoid the per-element branch on predict_scheme_.
  • FLOAT/DOUBLE currently convert between bit patterns and values per element; the delta/FIRE arithmetic operates entirely on the integer bit patterns, so the conversions can happen once at the end of the block rather than in the predictor loop.

Any change must keep the decoded values bit-exact; the existing SprintzCodecTest differential and Java-golden tests (cpp/test/encoding/sprintz_codec_test.cc) are the guardrail.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions