wgtmac commented on code in PR #48345:
URL: https://github.com/apache/arrow/pull/48345#discussion_r3951168775
##########
cpp/src/parquet/decoder.cc:
##########
@@ -2372,6 +2373,147 @@ class ByteStreamSplitDecoder<FLBAType> : public
ByteStreamSplitDecoderBase<FLBAT
}
};
+// ----------------------------------------------------------------------
+// ALP decoder (Adaptive Lossless floating-Point)
+
+template <typename DType>
+class AlpDecoder : public TypedDecoderImpl<DType> {
+ public:
+ using Base = TypedDecoderImpl<DType>;
+ using T = typename DType::c_type;
+
+ explicit AlpDecoder(const ColumnDescriptor* descr, ::arrow::MemoryPool* pool)
+ : Base(descr, Encoding::ALP), pool_(pool) {
+ static_assert(std::is_same<T, float>::value || std::is_same<T,
double>::value,
+ "ALP only supports float and double types");
+ }
+
+ void SetData(int num_values, const uint8_t* data, int len) final {
+ Base::SetData(num_values, data, len);
+ if (num_values > 0 && len <= 0) {
+ throw ParquetException("ALP SetData: num_values=" +
std::to_string(num_values) +
+ " but len=" + std::to_string(len));
+ }
+ // `num_values` is the page's level count, which includes nulls, while the
ALP
+ // payload holds only the non-null values. Its own header is the authority
on
+ // how many, so take the count from there.
+ if (len > 0) {
+ PARQUET_ASSIGN_OR_THROW(
+ reader_, ::arrow::util::alp::AlpCodec<T>::VectorReader::Open(data,
len));
+ total_values_ = reader_.num_elements();
+ if (total_values_ > num_values) {
Review Comment:
This compares the ALP non-null count with the page slot count. A corrupt
optional page can therefore leave encoded values unread without an error.
Please reject the page if the decoder is not exhausted after all definition
levels are consumed.
##########
cpp/src/arrow/util/alp/alp_codec_internal.h:
##########
@@ -0,0 +1,267 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// High-level codec interface for ALP compression
+
+#pragma once
+
+#include <cstddef>
+#include <cstdint>
+#include <vector>
+
+#include "arrow/result.h"
+#include "arrow/status.h"
+#include "arrow/util/alp/alp_internal.h"
+#include "arrow/util/alp/alp_sampler_internal.h"
+#include "arrow/util/visibility.h"
+
+namespace arrow::util::alp {
+
+// ----------------------------------------------------------------------
+// AlpCodec
+
+/// \class AlpCodec
+/// \brief High-level interface for ALP compression
+///
+/// AlpCodec is an interface for Adaptive Lossless floating-Point Compression
+/// (ALP) (https://dl.acm.org/doi/10.1145/3626717). For encoding, it samples
+/// the data and applies decimal compression (Alp) to floating point values.
+/// This class acts as a wrapper around the vector-based interfaces of
+/// AlpSampler and Alp.
+///
+/// \tparam T the floating point type (float or double)
+template <typename T>
+class ARROW_EXPORT AlpCodec {
+ public:
+ /// Type alias for the sampler result containing encoding presets
+ using AlpSamplerResult = typename AlpSampler<T>::AlpSamplerResult;
+
+ /// \brief Create a sampling preset from input data
+ ///
+ /// This samples the input data and generates an encoding preset that can be
+ /// reused for encoding. Pre-computing the preset lets you keep sampling out
+ /// of a benchmark loop, or encode multiple batches with one preset.
+ ///
+ /// \param[in] input pointer to the input data to sample
+ /// \param[in] num_elements number of elements to sample
+ /// \return the sampling result containing the encoding preset, or
+ /// Status::Invalid if `num_elements < 0`.
+ static Result<AlpSamplerResult> CreateSamplingPreset(const T* input,
+ int64_t num_elements);
+
+ /// \brief Encode floating point values using a pre-computed preset
+ ///
+ /// This encodes the data using a preset that was previously computed via
+ /// CreateSamplingPreset(). This avoids the sampling overhead during
encoding.
+ ///
+ /// \param[in] input pointer to the input to encode
+ /// \param[in] num_elements number of elements to encode
+ /// \param[in] preset the pre-computed sampling result from
CreateSamplingPreset()
+ /// \param[in] vector_size number of elements per vector (must be a power of
2
+ /// in the inclusive range [2^kMinLogVectorSize,
2^kMaxLogVectorSize],
+ /// i.e. 8 to 32768)
+ /// \param[out] output pointer to the memory region we will encode into.
+ /// Must be at least GetMaxCompressedSize(num_elements,
vector_size) bytes.
+ /// Behavior is undefined if `output` is smaller.
+ /// \param[in,out] output_size on input, the size of `output` in bytes; on
output,
+ /// the actual size of the encoded data. Must satisfy
+ /// `*output_size >= GetMaxCompressedSize(num_elements,
vector_size)`;
+ /// undersizing leads to undefined behavior (a partial write
to
+ /// `output` and an out-of-bounds write of the header).
+ /// \return Status::OK on success, or Status::Invalid if any precondition is
+ /// violated: `num_elements >= 0`, `num_elements <= INT32_MAX`, and
+ /// `vector_size` a power of two in
+ /// `[2^kMinLogVectorSize, 2^kMaxLogVectorSize]`.
+ static Status EncodeWithPreset(const T* input, int64_t num_elements,
+ const AlpSamplerResult& preset, int32_t
vector_size,
+ uint8_t* output, int64_t* output_size);
+
+ /// \brief Encode floating point values using ALP decimal compression
+ ///
+ /// \param[in] input pointer to the input to encode
+ /// \param[in] num_elements number of elements to encode
+ /// \param[in] vector_size number of elements per vector (must be a power of
2
+ /// in the inclusive range [2^kMinLogVectorSize,
2^kMaxLogVectorSize],
+ /// i.e. 8 to 32768)
+ /// \param[out] output pointer to the memory region we will encode into.
+ /// Must be at least GetMaxCompressedSize(num_elements,
vector_size) bytes.
+ /// Behavior is undefined if `output` is smaller.
+ /// \param[in,out] output_size on input, the size of `output` in bytes; on
output,
+ /// the actual size of the encoded data. Must satisfy
+ /// `*output_size >= GetMaxCompressedSize(num_elements,
vector_size)`;
+ /// undersizing leads to undefined behavior (a partial write
to
+ /// `output` and an out-of-bounds write of the header).
+ /// \return Status::OK on success, or Status::Invalid if any precondition is
+ /// violated: `num_elements >= 0`, `num_elements <= INT32_MAX`, and
+ /// `vector_size` a power of two in
+ /// `[2^kMinLogVectorSize, 2^kMaxLogVectorSize]`.
+ static Status Encode(const T* input, int64_t num_elements, int32_t
vector_size,
+ uint8_t* output, int64_t* output_size);
+
+ /// \brief Convenience overload with default vector_size = kAlpVectorSize.
+ /// Same preconditions and error returns as the four-argument
overload.
+ static Status Encode(const T* input, int64_t num_elements, uint8_t* output,
+ int64_t* output_size);
+
+ /// \brief Decode floating point values
+ ///
+ /// \param[in] num_elements number of elements the caller expects, which is
+ /// also the capacity of `output` in elements. The ALP header
+ /// embedded in `input` carries its own count, and decoding fails
+ /// unless the two are equal: a smaller header count would leave
+ /// part of `output` unwritten, and a larger one would overrun it.
+ /// \param[in] input pointer to the compressed data
+ /// \param[in] input_size size of the compressed data in bytes
+ /// \param[out] output pointer to the memory region we will decode into.
+ /// The caller is responsible for ensuring this is big enough
+ /// to hold num_elements values.
+ /// \return Status::OK on success, or an error if the compressed data is
malformed
+ /// \tparam TargetType the type that is used to store the output.
+ /// May not be a narrowing conversion from T.
+ template <typename TargetType>
+ static Status Decode(int32_t num_elements, const uint8_t* input, int64_t
input_size,
+ TargetType* output);
+
+ /// \brief Get the maximum compressed size for a given number of elements
+ ///
+ /// \param[in] num_elements number of elements to compress
+ /// \param[in] vector_size number of elements per vector (must be a power of
2
+ /// in the inclusive range [2^kMinLogVectorSize,
2^kMaxLogVectorSize],
+ /// i.e. 8 to 32768)
+ /// \return the maximum size of the compressed buffer in bytes, or
+ /// Status::Invalid if `num_elements < 0` or `vector_size` is not a
+ /// power of two in `[2^kMinLogVectorSize, 2^kMaxLogVectorSize]`.
+ static Result<int64_t> GetMaxCompressedSize(int64_t num_elements, int32_t
vector_size);
+
+ /// \brief Random access to the vectors of one compressed buffer
+ ///
+ /// `Open` reads the header and validates the whole offset chain once. A
caller
+ /// can then decode any single vector on its own, so serving a batch of
values
+ /// costs work in proportion to the batch rather than to the buffer, and
needs
+ /// scratch for one vector rather than for the whole buffer.
+ class VectorReader {
Review Comment:
`parquet_shared` calls these out-of-line methods, but Windows cannot see
their symbols.
Please export the `VectorReader` methods. Then verify that the MinGW shared
build links `Open`, `VectorLength`, and `DecodeVector`.
##########
cpp/src/parquet/parquet.thrift:
##########
@@ -637,6 +637,14 @@ enum Encoding {
Support for INT32, INT64 and FIXED_LEN_BYTE_ARRAY added in 2.11.
*/
BYTE_STREAM_SPLIT = 9;
+
+ /** Adaptive Lossless floating-Point (ALP) encoding for FLOAT and DOUBLE.
+ Losslessly converts decimal-like floating-point values to integers via
+ decimal scaling, then applies Frame of Reference (FOR) encoding and
+ bit-packing; values that cannot be converted losslessly are stored as
+ exceptions. See Encodings.md for the detailed specification.
+ */
+ ALP = 10;
Review Comment:
Please run `cpp/build-support/update-thrift.sh` and commit the updated
`cpp/src/generated/parquet_types.h` and `cpp/src/generated/parquet_types.cpp`.
##########
cpp/src/arrow/util/alp/alp.cc:
##########
@@ -0,0 +1,1051 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "arrow/util/alp/alp_internal.h"
+
+#include <algorithm>
+#include <bit>
+#include <cmath>
+#include <cstring>
+#include <functional>
+#include <map>
+#include <span>
+
+#include "arrow/util/alp/alp_constants_internal.h"
+#include "arrow/util/bit_stream_utils_internal.h"
+#include "arrow/util/bit_util.h"
+#include "arrow/util/bpacking_internal.h"
+#include "arrow/util/endian.h"
+#include "arrow/util/logging.h"
+#include "arrow/util/ubsan.h"
+
+namespace arrow::util::alp {
+
+namespace {
+
+// The ALP wire format is little-endian, so every multi-byte field is
converted on
+// the way in and out. The bit-packed values need no conversion of their own:
+// bit_util::BitWriter writes them little-endian and arrow::internal::unpack
reads
+// them back the same way, so those bytes are copied verbatim.
+//
+// On a little-endian host both helpers below are a plain memcpy.
+template <typename T>
+void StoreLittleEndianArray(const T* values, int64_t num_values, uint8_t*
output) {
+ if constexpr (ARROW_LITTLE_ENDIAN == 1) {
+ std::memcpy(output, values, static_cast<size_t>(num_values) * sizeof(T));
+ } else {
+ for (int64_t i = 0; i < num_values; ++i) {
+ util::SafeStore(output + i * sizeof(T),
bit_util::ToLittleEndian(values[i]));
+ }
+ }
+}
+
+template <typename T>
+void LoadLittleEndianArray(const uint8_t* input, int64_t num_values, T*
values) {
+ if constexpr (ARROW_LITTLE_ENDIAN == 1) {
+ std::memcpy(values, input, static_cast<size_t>(num_values) * sizeof(T));
+ } else {
+ for (int64_t i = 0; i < num_values; ++i) {
+ values[i] = bit_util::FromLittleEndian(util::SafeLoadAs<T>(input + i *
sizeof(T)));
+ }
+ }
+}
+
+} // namespace
+
+// ----------------------------------------------------------------------
+// AlpEncodedVectorInfo implementation (4 bytes)
+
+void AlpEncodedVectorInfo::Store(std::span<uint8_t> output_buffer) const {
+ ARROW_CHECK(output_buffer.size() >= static_cast<size_t>(GetStoredSize()))
+ << "alp_vector_info_output_too_small: " << output_buffer.size() << " vs "
+ << GetStoredSize();
+
+ uint8_t* ptr = output_buffer.data();
+
+ // exponent, factor: 1 byte each
+ *ptr++ = exponent_;
+ *ptr++ = factor_;
+
+ // num_exceptions: 2 bytes
+ util::SafeStore(ptr, bit_util::ToLittleEndian(num_exceptions_));
+}
+
+Result<AlpEncodedVectorInfo> AlpEncodedVectorInfo::Load(
+ std::span<const uint8_t> input_buffer) {
+ if (input_buffer.size() < static_cast<size_t>(GetStoredSize())) {
+ return Status::Invalid("ALP vector info buffer too small: ",
input_buffer.size(),
+ " < ", GetStoredSize());
+ }
+
+ AlpEncodedVectorInfo result{};
+ const uint8_t* ptr = input_buffer.data();
+
+ // exponent, factor: 1 byte each
+ result.exponent_ = *ptr++;
+ result.factor_ = *ptr++;
+
+ // num_exceptions: 2 bytes
+ result.num_exceptions_ =
bit_util::FromLittleEndian(util::SafeLoadAs<uint16_t>(ptr));
+
+ return result;
+}
+
+// ----------------------------------------------------------------------
+// AlpEncodedForVectorInfo implementation (templated, 5/9 bytes)
+
+template <typename T>
+void AlpEncodedForVectorInfo<T>::Store(std::span<uint8_t> output_buffer) const
{
+ ARROW_CHECK(output_buffer.size() >= static_cast<size_t>(GetStoredSize()))
+ << "alp_for_vector_info_output_too_small: " << output_buffer.size() << "
vs "
+ << GetStoredSize();
+
+ uint8_t* ptr = output_buffer.data();
+
+ // frame_of_reference: 4 bytes for float, 8 bytes for double
+ util::SafeStore(ptr, bit_util::ToLittleEndian(frame_of_reference_));
+ ptr += sizeof(frame_of_reference_);
+
+ // bit_width: 1 byte
+ *ptr = bit_width_;
+}
+
+template <typename T>
+Result<AlpEncodedForVectorInfo<T>> AlpEncodedForVectorInfo<T>::Load(
+ std::span<const uint8_t> input_buffer) {
+ if (input_buffer.size() < static_cast<size_t>(GetStoredSize())) {
+ return Status::Invalid("ALP FOR vector info buffer too small: ",
input_buffer.size(),
+ " < ", GetStoredSize());
+ }
+
+ AlpEncodedForVectorInfo<T> result{};
+ const uint8_t* ptr = input_buffer.data();
+
+ // frame_of_reference: 4 bytes for float, 8 bytes for double
+ result.frame_of_reference_ = bit_util::FromLittleEndian(
+ util::SafeLoadAs<typename AlpEncodedForVectorInfo<T>::ExactType>(ptr));
+ ptr += sizeof(result.frame_of_reference_);
+
+ // bit_width: 1 byte
+ result.bit_width_ = *ptr;
+ if (result.bit_width_ > sizeof(typename
AlpEncodedForVectorInfo<T>::ExactType) * 8) {
+ return Status::Invalid("ALP FOR bit_width out of range: ",
result.bit_width_);
+ }
+
+ return result;
+}
+
+// Explicit template instantiations for AlpEncodedForVectorInfo
+template class AlpEncodedForVectorInfo<float>;
+template class AlpEncodedForVectorInfo<double>;
+
+// ----------------------------------------------------------------------
+// AlpEncodedVector implementation
+
+template <typename T>
+void AlpEncodedVector<T>::Store(std::span<uint8_t> output_buffer) const {
+ const int64_t overall_size = GetStoredSize();
+ ARROW_CHECK(static_cast<int64_t>(output_buffer.size()) >= overall_size)
+ << "alp_bit_packed_vector_store_output_too_small: " <<
output_buffer.size()
+ << " vs " << overall_size;
+
+ int64_t offset = 0;
+
+ // Store AlpInfo (4 bytes)
+ alp_info_.Store({output_buffer.data() + offset,
AlpEncodedVectorInfo::kStoredSize});
+ offset += AlpEncodedVectorInfo::kStoredSize;
+
+ // Store ForInfo
+ for_info_.Store(
+ {output_buffer.data() + offset,
AlpEncodedForVectorInfo<T>::kStoredSize});
+ offset += AlpEncodedForVectorInfo<T>::kStoredSize;
+
+ // Store data section
+ StoreDataOnly({output_buffer.data() + offset, output_buffer.size() -
offset});
+}
+
+template <typename T>
+void AlpEncodedVector<T>::StoreDataOnly(std::span<uint8_t> output_buffer)
const {
+ const int64_t data_size = GetDataStoredSize();
+ // Internal invariants: caller must provide adequate buffer and consistent
metadata.
+ // These are programmer errors (not data errors), so CHECK is appropriate.
+ ARROW_CHECK(static_cast<int64_t>(output_buffer.size()) >= data_size)
+ << "alp_bit_packed_vector_store_data_output_too_small: " <<
output_buffer.size()
+ << " vs " << data_size;
+
+ ARROW_CHECK(static_cast<size_t>(alp_info_.num_exceptions()) ==
exceptions_.size() &&
+ static_cast<size_t>(alp_info_.num_exceptions()) ==
+ exception_positions_.size())
+ << "alp_bit_packed_vector_store_num_exceptions_mismatch: "
+ << alp_info_.num_exceptions() << " vs " << exceptions_.size() << " vs "
+ << exception_positions_.size();
+
+ int64_t offset = 0;
+
+ // Compute bit_packed_size from num_elements and bit_width
+ const int64_t bit_packed_size =
+ bit_util::BytesForBits(int64_t{num_elements_} * for_info_.bit_width());
+
+ // Store all successfully compressed values first.
+ std::memcpy(output_buffer.data() + offset, packed_values_.data(),
bit_packed_size);
+ offset += bit_packed_size;
+
+ // Store exception positions.
+ const int64_t exception_position_size =
+ alp_info_.num_exceptions() * sizeof(AlpConstants::PositionType);
+ StoreLittleEndianArray(exception_positions_.data(),
alp_info_.num_exceptions(),
+ output_buffer.data() + offset);
+ offset += exception_position_size;
+
+ // Store exception values.
+ const int64_t exception_size = alp_info_.num_exceptions() * sizeof(T);
+ StoreLittleEndianArray(exceptions_.data(), alp_info_.num_exceptions(),
+ output_buffer.data() + offset);
+ offset += exception_size;
+
+ // Internal invariant: total bytes written must match precomputed size.
+ ARROW_CHECK(offset == data_size)
+ << "alp_bit_packed_vector_data_size_mismatch: " << offset << " vs " <<
data_size;
+}
+
+namespace {
+
+/// \brief Range-check the metadata fields that size or steer the decode
+///
+/// `exponent` and `factor` index the power-of-ten tables, whose own bounds are
+/// asserted with ARROW_DCHECK and so go unchecked in a release build, and
+/// `num_exceptions` counts writes into an output of `num_elements` slots.
+template <typename T>
+Status ValidateVectorInfo(const AlpEncodedVectorInfo& alp_info, int32_t
num_elements) {
+ using Constants = AlpTypedConstants<T>;
+ if (alp_info.exponent() > Constants::kMaxExponent) {
+ return Status::Invalid("ALP exponent ",
static_cast<int>(alp_info.exponent()),
+ " exceeds ",
static_cast<int>(Constants::kMaxExponent));
+ }
+ // The encoder scales by 10^(exponent - factor), so factor <= exponent is
+ // what keeps that power non-negative, i.e. keeps the encoded value an
+ // integer the decode can invert. Bounding the factor by the already-checked
+ // exponent also keeps the power-of-ten table index in range.
+ if (alp_info.factor() > alp_info.exponent()) {
+ return Status::Invalid("ALP factor ", static_cast<int>(alp_info.factor()),
+ " exceeds exponent ",
static_cast<int>(alp_info.exponent()));
+ }
+ if (alp_info.num_exceptions() > num_elements) {
+ return Status::Invalid("ALP vector has ", alp_info.num_exceptions(),
+ " exceptions but only ", num_elements, " elements");
+ }
+ return Status::OK();
+}
+
+/// \brief Check that every exception position indexes the vector it belongs to
+///
+/// The patch step writes `output[position]`, so one past the end is an
+/// out-of-bounds write. Take the maximum first: a reduction still vectorizes,
+/// where a bounds check inside the patch loop would not.
+Status ValidateExceptionPositions(
+ std::span<const AlpConstants::PositionType> exception_positions,
+ int32_t num_elements) {
+ AlpConstants::PositionType max_position = 0;
+ for (const AlpConstants::PositionType position : exception_positions) {
+ max_position = std::max(max_position, position);
+ }
+ if (!exception_positions.empty() && max_position >= num_elements) {
+ return Status::Invalid("ALP exception position ", max_position,
+ " is outside a vector of ", num_elements, "
elements");
+ }
+ return Status::OK();
+}
+
+} // namespace
+
+template <typename T>
+Result<AlpEncodedVector<T>> AlpEncodedVector<T>::Load(
+ std::span<const uint8_t> input_buffer, int32_t num_elements) {
+ if (num_elements > (1 << AlpConstants::kMaxLogVectorSize)) {
+ return Status::Invalid("ALP element count too large: ", num_elements, " >
",
+ (1 << AlpConstants::kMaxLogVectorSize));
+ }
+
+ AlpEncodedVector<T> result;
+ int64_t input_offset = 0;
+
+ // Load AlpInfo (4 bytes)
+ ARROW_ASSIGN_OR_RAISE(AlpEncodedVectorInfo alp_info,
+ AlpEncodedVectorInfo::Load({input_buffer.data() +
input_offset,
+
AlpEncodedVectorInfo::kStoredSize}));
+ input_offset += AlpEncodedVectorInfo::kStoredSize;
+ result.set_alp_info(alp_info);
+
+ // Load ForInfo
+ ARROW_ASSIGN_OR_RAISE(
+ AlpEncodedForVectorInfo<T> for_info,
+ AlpEncodedForVectorInfo<T>::Load(
+ {input_buffer.data() + input_offset,
AlpEncodedForVectorInfo<T>::kStoredSize}));
+ input_offset += AlpEncodedForVectorInfo<T>::kStoredSize;
+ result.set_for_info(for_info);
+
+ result.set_num_elements(num_elements);
+
+ RETURN_NOT_OK(ValidateVectorInfo<T>(alp_info, num_elements));
+
+ const int64_t overall_size = GetStoredSize(alp_info, for_info, num_elements);
+
+ if (static_cast<int64_t>(input_buffer.size()) < overall_size) {
+ return Status::Invalid("ALP compressed vector buffer too small: ",
+ input_buffer.size(), " < ", overall_size);
+ }
+
+ // Compute bit_packed_size from num_elements and bit_width
+ const int64_t bit_packed_size =
+ bit_util::BytesForBits(int64_t{num_elements} * for_info.bit_width());
+
+ // TODO(GH-48701): resize() zero-initializes before memcpy overwrites.
Consider
+ // using uninitialized storage if this shows up in decode-path profiling.
+ result.mutable_packed_values().resize(bit_packed_size);
+ std::memcpy(result.mutable_packed_values().data(), input_buffer.data() +
input_offset,
+ bit_packed_size);
+ input_offset += bit_packed_size;
+
+ result.mutable_exception_positions().resize(alp_info.num_exceptions());
+ const int64_t exception_position_size =
+ alp_info.num_exceptions() * sizeof(AlpConstants::PositionType);
+ LoadLittleEndianArray(input_buffer.data() + input_offset,
alp_info.num_exceptions(),
+ result.mutable_exception_positions().data());
+ input_offset += exception_position_size;
+ RETURN_NOT_OK(ValidateExceptionPositions(result.exception_positions(),
num_elements));
+
+ result.mutable_exceptions().resize(alp_info.num_exceptions());
+ LoadLittleEndianArray(input_buffer.data() + input_offset,
alp_info.num_exceptions(),
+ result.mutable_exceptions().data());
+ return result;
+}
+
+template <typename T>
+int64_t AlpEncodedVector<T>::GetStoredSize() const {
+ return GetStoredSize(alp_info_, for_info_, num_elements_);
+}
+
+template <typename T>
+int64_t AlpEncodedVector<T>::GetStoredSize(const AlpEncodedVectorInfo&
alp_info,
+ const AlpEncodedForVectorInfo<T>&
for_info,
+ int32_t num_elements) {
+ const int64_t bit_packed_size =
+ bit_util::BytesForBits(int64_t{num_elements} * for_info.bit_width());
+ return AlpEncodedVectorInfo::kStoredSize +
AlpEncodedForVectorInfo<T>::kStoredSize +
+ bit_packed_size +
+ alp_info.num_exceptions() * (sizeof(AlpConstants::PositionType) +
sizeof(T));
+}
+
+template <typename T>
+bool AlpEncodedVector<T>::operator==(const AlpEncodedVector<T>& other) const {
+ if (alp_info_ != other.alp_info_ || for_info_ != other.for_info_ ||
+ num_elements_ != other.num_elements_) {
+ return false;
+ }
+ if (packed_values_.size() != other.packed_values_.size() ||
+ !std::equal(packed_values_.begin(), packed_values_.end(),
+ other.packed_values_.begin())) {
+ return false;
+ }
+ if (exceptions_.size() != other.exceptions_.size() ||
+ !std::equal(exceptions_.begin(), exceptions_.end(),
other.exceptions_.begin())) {
+ return false;
+ }
+ if (exception_positions_.size() != other.exception_positions_.size() ||
+ !std::equal(exception_positions_.begin(), exception_positions_.end(),
+ other.exception_positions_.begin())) {
+ return false;
+ }
+ return true;
+}
+
+// ----------------------------------------------------------------------
+// AlpEncodedVectorView implementation
+
+template <typename T>
+Result<AlpEncodedVectorView<T>> AlpEncodedVectorView<T>::LoadView(
+ std::span<const uint8_t> input_buffer, int32_t num_elements) {
+ if (num_elements > (1 << AlpConstants::kMaxLogVectorSize)) {
+ return Status::Invalid("ALP view element count too large: ", num_elements,
" > ",
+ (1 << AlpConstants::kMaxLogVectorSize));
+ }
+
+ AlpEncodedVectorView<T> result;
+ int64_t input_offset = 0;
+
+ // Load AlpInfo (4 bytes)
+ ARROW_ASSIGN_OR_RAISE(AlpEncodedVectorInfo alp_info,
+ AlpEncodedVectorInfo::Load({input_buffer.data() +
input_offset,
+
AlpEncodedVectorInfo::kStoredSize}));
+ input_offset += AlpEncodedVectorInfo::kStoredSize;
+ result.set_alp_info(alp_info);
+
+ // Load ForInfo
+ ARROW_ASSIGN_OR_RAISE(
+ AlpEncodedForVectorInfo<T> for_info,
+ AlpEncodedForVectorInfo<T>::Load(
+ {input_buffer.data() + input_offset,
AlpEncodedForVectorInfo<T>::kStoredSize}));
+ input_offset += AlpEncodedForVectorInfo<T>::kStoredSize;
+ result.set_for_info(for_info);
+
+ result.set_num_elements(num_elements);
+
+ const int64_t overall_size =
+ AlpEncodedVector<T>::GetStoredSize(alp_info, for_info, num_elements);
+
+ if (static_cast<int64_t>(input_buffer.size()) < overall_size) {
+ return Status::Invalid("ALP view buffer too small: ", input_buffer.size(),
" < ",
+ overall_size);
+ }
+
+ // Load data section (after metadata)
+ RETURN_NOT_OK(result.ResetDataOnly(
+ {input_buffer.data() + input_offset, input_buffer.size() -
input_offset}, alp_info,
+ for_info, num_elements));
+
+ return result;
+}
+
+template <typename T>
+Result<AlpEncodedVectorView<T>> AlpEncodedVectorView<T>::LoadViewDataOnly(
+ std::span<const uint8_t> input_buffer, const AlpEncodedVectorInfo&
alp_info,
+ const AlpEncodedForVectorInfo<T>& for_info, int32_t num_elements) {
+ AlpEncodedVectorView<T> result;
+ RETURN_NOT_OK(result.ResetDataOnly(input_buffer, alp_info, for_info,
num_elements));
+ return result;
+}
+
+template <typename T>
+Status AlpEncodedVectorView<T>::ResetDataOnly(std::span<const uint8_t>
input_buffer,
+ const AlpEncodedVectorInfo&
alp_info,
+ const
AlpEncodedForVectorInfo<T>& for_info,
+ int32_t num_elements) {
+ if (num_elements > (1 << AlpConstants::kMaxLogVectorSize)) {
+ return Status::Invalid("ALP view data element count too large: ",
num_elements, " > ",
+ (1 << AlpConstants::kMaxLogVectorSize));
+ }
+
+ RETURN_NOT_OK(ValidateVectorInfo<T>(alp_info, num_elements));
+
+ set_alp_info(alp_info);
+ set_for_info(for_info);
+ set_num_elements(num_elements);
+
+ const int64_t data_size =
+ for_info.GetDataStoredSize(num_elements, alp_info.num_exceptions());
+ if (static_cast<int64_t>(input_buffer.size()) < data_size) {
+ return Status::Invalid("ALP view data buffer too small: ",
input_buffer.size(), " < ",
+ data_size);
+ }
+
+ int64_t input_offset = 0;
+
+ // Compute bit_packed_size from num_elements and bit_width
+ const int64_t bit_packed_size =
+ bit_util::BytesForBits(int64_t{num_elements} * for_info.bit_width());
+
+ // Zero-copy for packed values (bytes have no alignment requirements)
+ set_packed_values(
+ {input_buffer.data() + input_offset,
static_cast<size_t>(bit_packed_size)});
+ input_offset += bit_packed_size;
+
+ // Copy exception positions into aligned storage to avoid UB from misaligned
access.
+ // resize() only reallocates when this view held a smaller vector before, so
a
+ // caller walking a buffer pays for the largest vector rather than for each
one.
+ const int64_t exception_position_size =
+ alp_info.num_exceptions() * sizeof(AlpConstants::PositionType);
+ exception_positions_.resize(alp_info.num_exceptions());
+ LoadLittleEndianArray(input_buffer.data() + input_offset,
alp_info.num_exceptions(),
+ exception_positions_.data());
+ input_offset += exception_position_size;
+ RETURN_NOT_OK(ValidateExceptionPositions(exception_positions_,
num_elements));
+
+ // Copy exception values into aligned storage to avoid UB from misaligned
access.
+ exceptions_.resize(alp_info.num_exceptions());
+ LoadLittleEndianArray(input_buffer.data() + input_offset,
alp_info.num_exceptions(),
+ exceptions_.data());
+
+ return Status::OK();
+}
+
+template <typename T>
+int64_t AlpEncodedVectorView<T>::GetStoredSize() const {
+ return AlpEncodedVector<T>::GetStoredSize(alp_info_, for_info_,
num_elements_);
+}
+
+template class AlpEncodedVectorView<float>;
+template class AlpEncodedVectorView<double>;
+
+template class AlpEncodedVector<float>;
+template class AlpEncodedVector<double>;
+
+// ----------------------------------------------------------------------
+// Internal helper classes
+
+namespace {
+
+/// \brief Helper class for encoding/decoding individual values
+template <typename T>
+class AlpInlines {
+ public:
+ using Constants = AlpTypedConstants<T>;
+ using ExactType = typename Constants::FloatingToExact;
+ using SignedExactType = typename Constants::FloatingToSignedExact;
+
+ /// \brief Check if float is a special value that cannot be converted
+ static inline bool IsImpossibleToEncode(const T n) {
+ // The two limit comparisons already cover both infinities: the encoding
+ // limits are finite, so +infinity compares above kEncodingUpperLimit and
+ // -infinity below kEncodingLowerLimit.
+ return std::isnan(n) || n > Constants::kEncodingUpperLimit ||
+ n < Constants::kEncodingLowerLimit ||
+ (n == 0.0 && std::signbit(n)); // Verification for -0.0
+ }
+
+ /// \brief Round a float to the nearest integer using the magic-number
technique
+ static inline SignedExactType FastRound(T n) {
+ if (n >= 0) {
+ n = n + Constants::kMagicNumber - Constants::kMagicNumber;
+ } else {
+ n = n - Constants::kMagicNumber + Constants::kMagicNumber;
+ }
+ return static_cast<SignedExactType>(n);
+ }
+
+ /// \brief Fast way to round float to nearest integer
+ static inline SignedExactType NumberToInt(T n) {
+ if (IsImpossibleToEncode(n)) {
+ return static_cast<SignedExactType>(Constants::kEncodingUpperLimit);
+ }
+ return FastRound(n);
+ }
+
+ /// \brief Convert a float into an int using encoding options
+ static inline SignedExactType EncodeValue(
+ const T value, const AlpExponentAndFactor exponent_and_factor) {
+ const T tmp_encoded_value = value *
+
Constants::GetExponent(exponent_and_factor.exponent) *
+
Constants::GetFactor(exponent_and_factor.factor);
+ return NumberToInt(tmp_encoded_value);
+ }
+
+ /// \brief Reconvert an int to a float using encoding options
+ static inline T DecodeValue(const SignedExactType encoded_value,
+ const AlpExponentAndFactor exponent_and_factor) {
+ // The cast to T is needed to prevent a signed integer overflow.
+ return static_cast<T>(encoded_value) *
+ AlpConstants::GetFactor(exponent_and_factor.factor) *
+ Constants::GetFactor(exponent_and_factor.exponent);
+ }
+};
+
+/// \brief Helper struct for tracking compression combinations
+struct AlpCombination {
+ AlpExponentAndFactor exponent_and_factor;
+ int64_t num_appearances{0};
+ int64_t estimated_compression_size{0};
+};
+
+/// \brief Compare two ALP combinations to determine which is better
+///
+/// Return true if c1 is a better combination than c2. Criteria, in order:
+/// 1. Higher number of appearances as the best combination across sampled
vectors.
+/// 2. Smaller estimated compression size.
+/// 3. Larger exponent.
+/// 4. Larger factor.
+///
+/// Criteria 3 and 4 are deterministic tie-breaks taken verbatim from the ALP
+/// paper (Afroozeh et al., SIGMOD 2023, ยง3.1.2): "If two combinations appeared
+/// the same amount of times, we prioritize combinations with higher exponents
+/// and higher factors." The paper does not justify this preference further;
+/// it is preserved here so the encoder's output matches the reference
algorithm.
+bool CompareAlpCombinations(const AlpCombination& c1, const AlpCombination&
c2) {
+ return (c1.num_appearances > c2.num_appearances) ||
+ (c1.num_appearances == c2.num_appearances &&
+ (c1.estimated_compression_size < c2.estimated_compression_size)) ||
+ ((c1.num_appearances == c2.num_appearances &&
+ c1.estimated_compression_size == c2.estimated_compression_size) &&
+ (c2.exponent_and_factor.exponent < c1.exponent_and_factor.exponent))
||
+ ((c1.num_appearances == c2.num_appearances &&
+ c1.estimated_compression_size == c2.estimated_compression_size &&
+ c2.exponent_and_factor.exponent == c1.exponent_and_factor.exponent)
&&
+ (c2.exponent_and_factor.factor < c1.exponent_and_factor.factor));
+}
+
+} // namespace
+
+// ----------------------------------------------------------------------
+// AlpCompression implementation
+
+template <typename T>
+std::optional<int64_t> AlpCompression<T>::EstimateCompressedSize(
+ const std::vector<T>& input_vector, const AlpExponentAndFactor
exponent_and_factor,
+ const bool penalize_exceptions) {
+ // Dry compress a vector (ideally a sample) to estimate ALP compression size
+ // given an exponent and factor.
+ SignedExactType max_encoded_value =
std::numeric_limits<SignedExactType>::min();
+ SignedExactType min_encoded_value =
std::numeric_limits<SignedExactType>::max();
+
+ // Split encode/decode/compare into separate passes over small batches so the
+ // compiler can vectorize the encode and decode passes independently.
+ static constexpr int kBatchSize = 8;
+ const size_t n = input_vector.size();
+ int64_t num_exceptions = 0;
+
+ size_t i = 0;
+ for (; i + kBatchSize <= n; i += kBatchSize) {
+ SignedExactType encoded_values[kBatchSize];
+ T decoded_values[kBatchSize];
+
+ // Pass 1: Encode (vectorizable: multiply + magic-number round)
+ for (int j = 0; j < kBatchSize; j++) {
+ encoded_values[j] =
+ AlpInlines<T>::EncodeValue(input_vector[i + j], exponent_and_factor);
+ }
+ // Pass 2: Decode (vectorizable: int->float cast + multiply)
+ for (int j = 0; j < kBatchSize; j++) {
+ decoded_values[j] =
+ AlpInlines<T>::DecodeValue(encoded_values[j], exponent_and_factor);
+ }
+ // Pass 3: Compare and accumulate min/max/exceptions
+ for (int j = 0; j < kBatchSize; j++) {
+ if (decoded_values[j] == input_vector[i + j]) {
+ max_encoded_value = std::max(encoded_values[j], max_encoded_value);
+ min_encoded_value = std::min(encoded_values[j], min_encoded_value);
+ } else {
+ num_exceptions++;
+ }
+ }
+ }
+ // Scalar tail for remaining elements
+ for (; i < n; i++) {
+ const SignedExactType encoded_value =
+ AlpInlines<T>::EncodeValue(input_vector[i], exponent_and_factor);
+ const T decoded_value =
+ AlpInlines<T>::DecodeValue(encoded_value, exponent_and_factor);
+ if (decoded_value == input_vector[i]) {
+ max_encoded_value = std::max(encoded_value, max_encoded_value);
+ min_encoded_value = std::min(encoded_value, min_encoded_value);
+ } else {
+ num_exceptions++;
+ }
+ }
+
+ const int64_t num_non_exceptions =
+ static_cast<int64_t>(input_vector.size()) - num_exceptions;
+
+ // We penalize combinations which yield almost all exceptions.
+ if (penalize_exceptions && num_non_exceptions < 2) {
+ return std::nullopt;
+ }
+
+ // Evaluate factor/exponent compression size (we optimize for FOR).
+ const ExactType delta = (static_cast<ExactType>(max_encoded_value) -
+ static_cast<ExactType>(min_encoded_value));
+
+ const int32_t estimated_bits_per_value =
static_cast<int32_t>(std::bit_width(delta));
+ int64_t estimated_compression_size =
+ static_cast<int64_t>(input_vector.size()) * estimated_bits_per_value;
+ estimated_compression_size +=
+ num_exceptions * (kExactTypeBitSize +
(sizeof(AlpConstants::PositionType) * 8));
+ return estimated_compression_size;
+}
+
+template <typename T>
+AlpEncodingParameters AlpCompression<T>::CreateEncodingParameters(
+ const std::vector<std::vector<T>>& vectors_sampled) {
+ // Find the best combinations of factor-exponent from each sampled vector.
+ // This function is called once per segment.
+ // This operates over ALP first level samples.
+ static constexpr size_t kMaxCombinationCount =
+ (Constants::kMaxExponent + 1) * (Constants::kMaxExponent + 2) / 2;
+
+ std::map<AlpExponentAndFactor, int64_t> best_k_combinations_hash;
+
+ // Find the best exponent/factor combination for a single sampled vector by
+ // trying all (exponent, factor) pairs and picking the one that minimizes
+ // estimated compression size. Returns {best_combination, best_size_bits}.
+ auto find_best_for_vector =
+ [](const std::vector<T>& sampled_vector) -> std::pair<AlpCombination,
int64_t> {
+ const int64_t num_samples = sampled_vector.size();
+ const AlpExponentAndFactor worst_case{Constants::kMaxExponent,
+ Constants::kMaxExponent};
+ // Start with worst possible total bits.
+ const int64_t worst_total_bits =
+ (num_samples * (kExactTypeBitSize + sizeof(AlpConstants::PositionType)
* 8)) +
+ (num_samples * kExactTypeBitSize);
+
+ AlpCombination best{worst_case, 0, worst_total_bits};
+ int64_t best_size_bits = std::numeric_limits<int64_t>::max();
+
+ for (uint8_t exp_idx = 0; exp_idx <= Constants::kMaxExponent; exp_idx++) {
+ for (uint8_t factor_idx = 0; factor_idx <= exp_idx; factor_idx++) {
+ const AlpExponentAndFactor current{exp_idx, factor_idx};
+ std::optional<int64_t> size =
+ EstimateCompressedSize(sampled_vector, current,
/*penalize_exceptions=*/true);
+ if (!size.has_value()) {
+ continue;
+ }
+ const AlpCombination candidate{current, 0, *size};
+ if (CompareAlpCombinations(candidate, best)) {
+ best = candidate;
+ best_size_bits = std::min(best_size_bits, *size);
+ }
+ }
+ }
+ return {best, best_size_bits};
+ };
+
+ int64_t best_compressed_size_bits = std::numeric_limits<int64_t>::max();
+ for (const std::vector<T>& sampled_vector : vectors_sampled) {
+ auto [best, size_bits] = find_best_for_vector(sampled_vector);
+ best_k_combinations_hash[best.exponent_and_factor]++;
+ best_compressed_size_bits = std::min(best_compressed_size_bits, size_bits);
+ }
+
+ // Convert our hash to a Combination vector to be able to sort.
+ // Note that this vector should mostly be small (< 10 combinations).
+ std::vector<AlpCombination> best_k_combinations;
+ best_k_combinations.reserve(
+ std::min(best_k_combinations_hash.size(), kMaxCombinationCount));
+ for (const auto& [exponent_and_factor, num_appearances] :
best_k_combinations_hash) {
+ best_k_combinations.emplace_back(AlpCombination{
+ exponent_and_factor, num_appearances,
+ 0 // Compression size is irrelevant since we compare different
vectors.
+ });
+ }
+ std::sort(best_k_combinations.begin(), best_k_combinations.end(),
+ CompareAlpCombinations);
+
+ // Save k' best combinations.
+ const uint8_t num_combinations_to_keep = std::min(
+ AlpConstants::kMaxCombinations,
static_cast<uint8_t>(best_k_combinations.size()));
+ std::vector<AlpExponentAndFactor> combinations;
+ combinations.reserve(num_combinations_to_keep);
+ for (uint8_t i = 0; i < num_combinations_to_keep; i++) {
+ combinations.push_back(best_k_combinations[i].exponent_and_factor);
+ }
+
+ const int64_t best_compressed_size_bytes =
+ bit_util::BytesForBits(best_compressed_size_bits);
+ return {combinations, best_compressed_size_bytes};
+}
+
+template <typename T>
+std::vector<T> AlpCompression<T>::CreateSample(std::span<const T> input) {
+ // Sample equidistant values within a vector; skip a fixed number of values.
+ const int32_t idx_increments = std::max<int32_t>(
+ 1, static_cast<int32_t>(std::ceil(static_cast<double>(input.size()) /
+
AlpConstants::kSamplerSamplesPerVector)));
+ std::vector<T> vector_sample;
+ vector_sample.reserve(std::ceil(input.size() /
static_cast<double>(idx_increments)));
+ for (size_t i = 0; i < input.size(); i += idx_increments) {
+ vector_sample.push_back(input[i]);
+ }
+ return vector_sample;
+}
+
+template <typename T>
+AlpExponentAndFactor AlpCompression<T>::FindBestExponentAndFactor(
+ std::span<const T> input, const std::vector<AlpExponentAndFactor>&
combinations) {
+ // Find the best factor-exponent combination from within the best k
combinations.
+ // This search is ALP's second-level sampling.
+ if (combinations.size() == 1) {
+ return combinations.front();
+ }
+
+ const std::vector<T> sample_vector = CreateSample(input);
+
+ AlpExponentAndFactor best_exponent_and_factor;
+ int64_t best_total_bits = std::numeric_limits<int64_t>::max();
+ int64_t worse_total_bits_counter = 0;
+
+ // Try each K combination to find the one which minimizes compression size.
+ // penalize_exceptions=false because this is second-level sampling: the
preset
+ // already filtered out bad combinations during first-level sampling, so we
+ // just pick whichever pre-vetted combination compresses this vector best.
+ for (const AlpExponentAndFactor& exponent_and_factor : combinations) {
+ std::optional<int64_t> estimated_compression_size = EstimateCompressedSize(
+ sample_vector, exponent_and_factor, /*penalize_exceptions=*/false);
+
+ // Skip exponents and factors which result in many exceptions.
+ if (!estimated_compression_size.has_value()) {
+ continue;
+ }
+
+ // If current compression size is worse or equal than current best
combination.
+ if (estimated_compression_size >= best_total_bits) {
+ worse_total_bits_counter += 1;
+ // Early exit strategy.
+ if (worse_total_bits_counter ==
AlpConstants::kSamplingEarlyExitThreshold) {
+ break;
+ }
+ continue;
+ }
+ // Otherwise replace the best and continue trying with next combination.
+ best_total_bits = estimated_compression_size.value();
+ best_exponent_and_factor = exponent_and_factor;
+ worse_total_bits_counter = 0;
+ }
+ return best_exponent_and_factor;
+}
+
+template <typename T>
+typename AlpCompression<T>::EncodingResult AlpCompression<T>::EncodeVector(
+ std::span<const T> input_vector, AlpExponentAndFactor exponent_and_factor)
{
+ if (input_vector.empty()) {
+ return EncodingResult{{}, {}, {}, 0, 0};
+ }
+
+ std::vector<SignedExactType> encoded_integers;
+ encoded_integers.reserve(input_vector.size());
+ std::vector<T> exceptions;
+ std::vector<AlpConstants::PositionType> exception_positions;
+
+ // Encoding Float/Double to SignedExactType(Int32, Int64).
+ // Encode all values regardless of correctness to recover original
floating-point.
+ int64_t input_offset = 0;
+ for (const T input : input_vector) {
+ const SignedExactType encoded_value =
+ AlpInlines<T>::EncodeValue(input, exponent_and_factor);
+ const T decoded_value =
+ AlpInlines<T>::DecodeValue(encoded_value, exponent_and_factor);
+ encoded_integers.push_back(encoded_value);
+ // Detect exceptions using a predicated comparison.
+ if (decoded_value != input) {
+ exception_positions.push_back(
+ static_cast<AlpConstants::PositionType>(input_offset));
+ }
+ input_offset++;
+ }
+
+ // Finding first non-exception value.
+ SignedExactType first_non_exception_value = 0;
+ AlpConstants::PositionType exception_offset = 0;
+ for (const AlpConstants::PositionType exception_position :
exception_positions) {
+ if (exception_offset != exception_position) {
+ first_non_exception_value = encoded_integers[exception_offset];
+ break;
+ }
+ exception_offset++;
+ }
+
+ // Use first non-exception value as placeholder for all exception values.
+ for (const AlpConstants::PositionType exception_position :
exception_positions) {
+ const T actual_value = input_vector[exception_position];
+ encoded_integers[exception_position] = first_non_exception_value;
+ exceptions.push_back(actual_value);
+ }
+
+ // Analyze FOR.
+ const auto [min_it, max_it] =
+ std::minmax_element(encoded_integers.begin(), encoded_integers.end());
+ const auto frame_of_reference = static_cast<ExactType>(*min_it);
+
+ for (SignedExactType& encoded_integer : encoded_integers) {
+ // Use SafeCopy to avoid strict aliasing violation when converting between
+ // signed and unsigned integer types of the same size.
+ ExactType unsigned_value = util::SafeCopy<ExactType>(encoded_integer);
+ unsigned_value -= frame_of_reference;
+ encoded_integer = util::SafeCopy<SignedExactType>(unsigned_value);
+ }
+
+ const ExactType min_max_diff =
+ (static_cast<ExactType>(*max_it) - static_cast<ExactType>(*min_it));
+ return EncodingResult{encoded_integers, exceptions, exception_positions,
min_max_diff,
+ frame_of_reference};
+}
+
+template <typename T>
+typename AlpCompression<T>::BitPackingResult
AlpCompression<T>::BitPackIntegers(
+ std::span<const SignedExactType> integers, const uint64_t min_max_diff) {
+ uint8_t bit_width = 0;
+
+ if (min_max_diff > 0) {
+ bit_width = static_cast<uint8_t>(std::bit_width(min_max_diff));
+ }
+ const int32_t bit_packed_size = static_cast<int32_t>(
+ bit_util::BytesForBits(bit_width *
static_cast<int64_t>(integers.size())));
+
+ std::vector<uint8_t> packed_integers(bit_packed_size);
+ if (bit_width > 0) { // Only execute BP if writing data.
+ // Use Arrow's BitWriter for packing (loop-based).
+ arrow::bit_util::BitWriter writer(packed_integers.data(), bit_packed_size);
+ for (size_t i = 0; i < integers.size(); ++i) {
+ writer.PutValue(static_cast<uint64_t>(integers[i]), bit_width);
+ }
+ writer.Flush(false);
+ }
+ return {packed_integers, bit_width, bit_packed_size};
+}
+
+template <typename T>
+AlpEncodedVector<T> AlpCompression<T>::CompressVector(
+ const T* input_vector, int32_t num_elements, const AlpEncodingParameters&
preset) {
+ // Compress by finding a fitting exponent/factor, encode input, and bitpack.
+ const std::span<const T> input_span{input_vector,
static_cast<size_t>(num_elements)};
+ const AlpExponentAndFactor exponent_and_factor =
+ FindBestExponentAndFactor(input_span, preset.combinations);
+ const EncodingResult encoding_result = EncodeVector(input_span,
exponent_and_factor);
+ const BitPackingResult bitpacking_result =
+ BitPackIntegers(encoding_result.encoded_integers,
encoding_result.min_max_diff);
+
+ // Build the result with split metadata
+ AlpEncodedVector<T> result;
+
+ // ALP metadata (4 bytes)
+ result.mutable_alp_info().set_exponent(exponent_and_factor.exponent);
+ result.mutable_alp_info().set_factor(exponent_and_factor.factor);
+ result.mutable_alp_info().set_num_exceptions(
+ static_cast<uint16_t>(encoding_result.exceptions.size()));
+
+ // FOR metadata
+
result.mutable_for_info().set_frame_of_reference(encoding_result.frame_of_reference);
+ result.mutable_for_info().set_bit_width(bitpacking_result.bit_width);
+
+ result.set_num_elements(num_elements);
+ result.set_packed_values(bitpacking_result.packed_integers);
+ result.set_exceptions(encoding_result.exceptions);
+ result.set_exception_positions(encoding_result.exception_positions);
+ return result;
+}
+
+template <typename T>
+void AlpCompression<T>::BitUnpackIntegers(std::span<const uint8_t>
packed_integers,
+ const AlpEncodedForVectorInfo<T>&
for_info,
+ int32_t num_elements, ExactType*
output) {
+ if (for_info.bit_width() > 0) {
+ // Arrow's unpack handles arbitrary sizes: SIMD for complete batches,
+ // then unpack_exact for the remainder. No need to manually split.
+ const arrow::internal::UnpackOptions opts{
+ .batch_size = static_cast<int>(num_elements),
+ .bit_width = for_info.bit_width(),
+ };
+ arrow::internal::unpack(packed_integers.data(), output, opts);
+ } else {
+ std::memset(output, 0, num_elements * sizeof(ExactType));
+ }
+}
+
+template <typename T>
+template <typename TargetType>
+void AlpCompression<T>::DecodeVector(std::span<ExactType> input_vector,
+ const AlpEncodedVectorInfo& alp_info,
+ const AlpEncodedForVectorInfo<T>&
for_info,
+ int32_t num_elements, TargetType*
output_vector) {
+ // Fused unFOR + decode loop - reduces memory traffic by avoiding
+ // intermediate write-then-read of the unFOR'd values.
+ const ExactType* data = input_vector.data();
+ const ExactType frame_of_ref = for_info.frame_of_reference();
+
+#pragma GCC unroll AlpConstants::kLoopUnrolls
Review Comment:
These currently break Clang and MSVC builds under `-Werror`. Please make the
ALP sources compile cleanly with both Clang and MSVC.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
