Internal Jenkins has submitted this change and it was merged.

Change subject: IMPALA-4123: Fast bit unpacking

IMPALA-4123: Fast bit unpacking

Adds utility functions for fast unpacking of batches of bit-packed
values. These support reading batches of any number of values provided
that the start of the batch is aligned to a byte boundary. Callers that
want to read smaller batches that don't align to byte boundaries will
need to implement their own buffering.

The unpacking code uses only portable C++ and no SIMD intrinsics, but is
fairly efficient because unpacking a full batch of 32 values compiles
down to 32-bit loads, shifts by constants, masks by constants, bitwise
ors when a value straddles 32-bit words and stores. Further speedups
should be possible using SIMD intrinsics.

Added unit tests for unpacking, exhaustively covering different
bitwidths with additional test dimensions (memory alignment, various
input sizes, etc).

Tested under ASAN to ensure the bit unpacking doesn't read past the end
of buffers.

Added microbenchmark that shows on average an 8-9x speedup over the
existing BitReader code.

Change-Id: I12db69409483d208cd4c0f41c27a78aeb6cd3622
Reviewed-by: Tim Armstrong <>
Tested-by: Internal Jenkins
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/
M be/src/benchmarks/
M be/src/exprs/
A be/src/testutil/mem-util.h
M be/src/util/CMakeLists.txt
A be/src/util/
A be/src/util/bit-packing.h
A be/src/util/bit-packing.inline.h
M be/src/util/bit-stream-utils.h
M be/src/util/bit-stream-utils.inline.h
M be/src/util/bit-util.h
M be/src/util/
13 files changed, 929 insertions(+), 84 deletions(-)

  Internal Jenkins: Verified
  Tim Armstrong: Looks good to me, approved

To view, visit
To unsubscribe, visit

Gerrit-MessageType: merged
Gerrit-Change-Id: I12db69409483d208cd4c0f41c27a78aeb6cd3622
Gerrit-PatchSet: 16
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Tim Armstrong <>
Gerrit-Reviewer: Internal Jenkins
Gerrit-Reviewer: Jim Apple <>
Gerrit-Reviewer: Tim Armstrong <>

Reply via email to