prtkgaur commented on code in PR #48345: URL: https://github.com/apache/arrow/pull/48345#discussion_r3920941061
########## cpp/src/arrow/util/alp/alp_codec.h: ########## @@ -0,0 +1,191 @@ +// 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 "arrow/result.h" +#include "arrow/status.h" +#include "arrow/util/alp/alp.h" +#include "arrow/util/alp/alp_sampler.h" + +namespace arrow { +namespace util { +namespace 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 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. This is useful when you want to pre-compute the preset + /// outside of the benchmark loop or encode multiple batches with the same 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 + static 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 that is to be encoded + /// \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, + /// at most 2^kMaxLogVectorSize) + /// \param[out] output pointer to the memory region we will encode into. + /// Must be at least GetMaxCompressedSize(num_elements) bytes. + /// \param[in,out] output_size the actual size of the encoded data in bytes, Review Comment: The "bail out" wording meant setting `*output_size = 0` and returning `void`, so yes — the caller was expected to notice a 0. That's gone: `Encode` and `EncodeWithPreset` return `Status` now, and `num_elements` and `vector_size` are validated with `Status::Invalid`. Undersized `output` is the one thing still not checked. It's documented as a caller precondition — size the buffer from `GetMaxCompressedSize`, which returns `Result<int64_t>` — rather than validated on every call. Say if you'd rather it were checked. ########## cpp/src/arrow/util/alp/generate_reference_blobs.cc: ########## @@ -0,0 +1,165 @@ +// 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. + +// Generates ALP reference blobs for cross-implementation testing. +// Usage: compile, run, pipe output into Java test file. + +#include <cmath> +#include <cstdint> +#include <cstdio> +#include <cstring> +#include <cstdint> +#include <iostream> +#include <limits> +#include <string> +#include <vector> + +#include "arrow/util/alp/alp_codec.h" + +using namespace arrow::util::alp; + +static void printHex(const std::string& name, const uint8_t* data, size_t len) { Review Comment: No longer applies — the file is removed. ########## cpp/src/parquet/CMakeLists.txt: ########## @@ -442,6 +442,11 @@ add_parquet_benchmark(bloom_filter_benchmark SOURCES bloom_filter_benchmark.cc add_parquet_benchmark(column_reader_benchmark) add_parquet_benchmark(column_io_benchmark) add_parquet_benchmark(encoding_benchmark) +add_parquet_benchmark(encoding_alp_benchmark) + +add_executable(generate-alp-parquet + ${PROJECT_SOURCE_DIR}/src/arrow/util/alp/generate_alp_parquet.cc) Review Comment: Moved. The benchmark source lives in `cpp/src/parquet/` now and is registered with the ordinary `add_parquet_benchmark`, so there's no cross-directory reference left. ########## cpp/src/arrow/util/alp/alp.cc: ########## @@ -0,0 +1,965 @@ +// 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.h" + +#include <cmath> +#include <cstring> +#include <functional> +#include <iostream> +#include <map> + +#include "arrow/util/alp/alp_constants.h" +#include "arrow/util/bit_stream_utils_internal.h" +#include "arrow/util/bit_util.h" +#include "arrow/util/endian.h" +#include "arrow/util/bpacking_internal.h" +#include "arrow/util/logging.h" +#include "arrow/util/span.h" +#include "arrow/util/ubsan.h" + +namespace arrow { +namespace util { +namespace alp { + +// ALP serialization uses memcpy for multi-byte integers (frame_of_reference, +// num_exceptions, offsets) and assumes little-endian byte order on disk. +static_assert(ARROW_LITTLE_ENDIAN, + "ALP serialization assumes little-endian byte order"); + +// ---------------------------------------------------------------------- +// AlpEncodedVectorInfo implementation (non-templated, 4 bytes) + +void AlpEncodedVectorInfo::Store(arrow::util::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, num_exceptions_); +} + +Result<AlpEncodedVectorInfo> AlpEncodedVectorInfo::Load( + arrow::util::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_ = util::SafeLoadAs<int16_t>(ptr); + + return result; +} + +// ---------------------------------------------------------------------- +// AlpEncodedForVectorInfo implementation (templated, 5/9 bytes) + +template <typename T> +void AlpEncodedForVectorInfo<T>::Store(arrow::util::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, frame_of_reference_); + ptr += sizeof(frame_of_reference_); + + // bit_width: 1 byte + *ptr = bit_width_; +} + +template <typename T> +Result<AlpEncodedForVectorInfo<T>> AlpEncodedForVectorInfo<T>::Load( + arrow::util::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_ = 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(arrow::util::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(arrow::util::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 = + AlpEncodedForVectorInfo<T>::GetBitPackedSize(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); + std::memcpy(output_buffer.data() + offset, exception_positions_.data(), + exception_position_size); + offset += exception_position_size; + + // Store exception values. + const int64_t exception_size = alp_info_.num_exceptions() * sizeof(T); + std::memcpy(output_buffer.data() + offset, exceptions_.data(), exception_size); + 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; +} + +template <typename T> +Result<AlpEncodedVector<T>> AlpEncodedVector<T>::Load( + arrow::util::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); + + 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 = + AlpEncodedForVectorInfo<T>::GetBitPackedSize(num_elements, for_info.bit_width()); + + // TODO: 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); + std::memcpy(result.mutable_exception_positions().data(), + input_buffer.data() + input_offset, exception_position_size); + input_offset += exception_position_size; + + result.mutable_exceptions().resize(alp_info.num_exceptions()); + const int64_t exception_size = alp_info.num_exceptions() * sizeof(T); + std::memcpy(result.mutable_exceptions().data(), input_buffer.data() + input_offset, + exception_size); + 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 = + AlpEncodedForVectorInfo<T>::GetBitPackedSize(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( + arrow::util::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) + ARROW_ASSIGN_OR_RAISE( + AlpEncodedVectorView<T> data_view, + LoadViewDataOnly( + {input_buffer.data() + input_offset, input_buffer.size() - input_offset}, + alp_info, for_info, num_elements)); + + // Copy the loaded data into result + result.set_packed_values(data_view.packed_values()); + result.set_exception_positions(std::move(data_view.mutable_exception_positions())); + result.set_exceptions(std::move(data_view.mutable_exceptions())); + + return result; +} + +template <typename T> +Result<AlpEncodedVectorView<T>> AlpEncodedVectorView<T>::LoadViewDataOnly( + arrow::util::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)); + } + + AlpEncodedVectorView<T> result; + result.set_alp_info(alp_info); + result.set_for_info(for_info); + result.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 = + AlpEncodedForVectorInfo<T>::GetBitPackedSize(num_elements, for_info.bit_width()); + + // Zero-copy for packed values (bytes have no alignment requirements) + result.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. + // Exceptions are rare (typically < 5%), so the copy overhead is negligible. + const int64_t exception_position_size = + alp_info.num_exceptions() * sizeof(AlpConstants::PositionType); + result.mutable_exception_positions().resize(alp_info.num_exceptions()); + std::memcpy(result.mutable_exception_positions().data(), + input_buffer.data() + input_offset, exception_position_size); + input_offset += exception_position_size; + + // Copy exception values into aligned storage to avoid UB from misaligned access. + const int64_t exception_size = alp_info.num_exceptions() * sizeof(T); + result.mutable_exceptions().resize(alp_info.num_exceptions()); + std::memcpy(result.mutable_exceptions().data(), input_buffer.data() + input_offset, + exception_size); + + return result; +} + +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) { + // We do not have to check for positive or negative infinity, since + // std::numeric_limits<T>::infinity() > std::numeric_limits<T>::max() + // and vice versa for negative infinity. + 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 auto FastRound(T n) -> SignedExactType { + 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 auto NumberToInt(T n) -> SignedExactType { + 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. +/// First criteria is number of times it appears as best combination. +/// Second criteria is the estimated compression size. +/// Third criteria is bigger exponent. Review Comment: Done — the comment now quotes the ALP paper's §3.1.2 rule for the tie-break and says plainly that the paper doesn't justify it beyond that, rather than inventing a rationale the authors didn't give. ########## cpp/src/parquet/encoding_test.cc: ########## @@ -2660,4 +2595,419 @@ TEST(DeltaByteArrayEncodingAdHoc, ArrowDirectPut) { } } +// ---------------------------------------------------------------------- +// ALP encoding tests for float/double + +template <typename Type> +class TestAlpEncoding : public TestEncodingBase<Type> { + public: + using c_type = typename Type::c_type; + static constexpr int TYPE = Type::type_num; + static constexpr size_t kNumRoundTrips = 3; + + void CheckRoundtrip() override { + auto encoder = + MakeTypedEncoder<Type>(Encoding::ALP, /*use_dictionary=*/false, descr_.get()); + auto decoder = MakeTypedDecoder<Type>(Encoding::ALP, descr_.get()); + + for (size_t i = 0; i < kNumRoundTrips; ++i) { + encoder->Put(draws_, num_values_); + encode_buffer_ = encoder->FlushValues(); + + decoder->SetData(num_values_, encode_buffer_->data(), + static_cast<int>(encode_buffer_->size())); + int values_decoded = decoder->Decode(decode_buf_, num_values_); + ASSERT_EQ(num_values_, values_decoded); + + // Use memcmp for bit-exact comparison (important for -0.0, NaN bit patterns) + ASSERT_EQ(0, std::memcmp(draws_, decode_buf_, num_values_ * sizeof(c_type))); + } + } + + void CheckRoundtripSpaced(const uint8_t* valid_bits, + int64_t valid_bits_offset) override { + auto encoder = + MakeTypedEncoder<Type>(Encoding::ALP, /*use_dictionary=*/false, descr_.get()); + auto decoder = MakeTypedDecoder<Type>(Encoding::ALP, descr_.get()); + + int null_count = 0; + for (auto i = 0; i < num_values_; i++) { + if (!bit_util::GetBit(valid_bits, valid_bits_offset + i)) { + null_count++; + } + } + + for (size_t i = 0; i < kNumRoundTrips; ++i) { + encoder->PutSpaced(draws_, num_values_, valid_bits, valid_bits_offset); + encode_buffer_ = encoder->FlushValues(); + + decoder->SetData(num_values_ - null_count, encode_buffer_->data(), + static_cast<int>(encode_buffer_->size())); + auto values_decoded = decoder->DecodeSpaced(decode_buf_, num_values_, null_count, + valid_bits, valid_bits_offset); + ASSERT_EQ(num_values_, values_decoded); + + // Verify only valid values + for (int j = 0; j < num_values_; ++j) { + if (bit_util::GetBit(valid_bits, valid_bits_offset + j)) { + ASSERT_EQ(0, std::memcmp(&draws_[j], &decode_buf_[j], sizeof(c_type))) << j; + } + } + } + } + + void InitDataWithSpecialValues(int nvalues, int repeats) { + num_values_ = nvalues * repeats; + this->input_bytes_.resize(num_values_ * sizeof(c_type)); + this->output_bytes_.resize(num_values_ * sizeof(c_type)); + draws_ = reinterpret_cast<c_type*>(this->input_bytes_.data()); + decode_buf_ = reinterpret_cast<c_type*>(this->output_bytes_.data()); + + // Fill with mix of normal and special values + for (int i = 0; i < nvalues; ++i) { + if (i % 20 == 0) { + draws_[i] = std::numeric_limits<c_type>::quiet_NaN(); + } else if (i % 20 == 5) { + draws_[i] = std::numeric_limits<c_type>::infinity(); + } else if (i % 20 == 10) { + draws_[i] = -std::numeric_limits<c_type>::infinity(); + } else if (i % 20 == 15) { + draws_[i] = static_cast<c_type>(-0.0); + } else { + draws_[i] = static_cast<c_type>(i) * static_cast<c_type>(0.123); + } + } + + // Repeat pattern + for (int j = 1; j < repeats; ++j) { + for (int i = 0; i < nvalues; ++i) { + draws_[nvalues * j + i] = draws_[i]; + } + } + } + + void InitDataDecimalPattern(int nvalues, int repeats) { + num_values_ = nvalues * repeats; + this->input_bytes_.resize(num_values_ * sizeof(c_type)); + this->output_bytes_.resize(num_values_ * sizeof(c_type)); + draws_ = reinterpret_cast<c_type*>(this->input_bytes_.data()); + decode_buf_ = reinterpret_cast<c_type*>(this->output_bytes_.data()); + + // Decimal-like values that ALP compresses well + for (int i = 0; i < nvalues; ++i) { + draws_[i] = static_cast<c_type>(100.0 + i * 0.01); + } + + for (int j = 1; j < repeats; ++j) { + for (int i = 0; i < nvalues; ++i) { + draws_[nvalues * j + i] = draws_[i]; + } + } + } + + void ExecuteSpecialValues(int nvalues, int repeats) { + InitDataWithSpecialValues(nvalues, repeats); + CheckRoundtrip(); + } + + void ExecuteDecimalPattern(int nvalues, int repeats) { + InitDataDecimalPattern(nvalues, repeats); + CheckRoundtrip(); + } + + protected: + USING_BASE_MEMBERS(); +}; + +using AlpEncodedTypes = ::testing::Types<FloatType, DoubleType>; +TYPED_TEST_SUITE(TestAlpEncoding, AlpEncodedTypes); + +TYPED_TEST(TestAlpEncoding, BasicRoundTrip) { + // Test various sizes including edge cases + for (int values = 1; values < 32; ++values) { + ASSERT_NO_FATAL_FAILURE(this->Execute(values, 1)); + } + + // Test exactly vector size (1024) + ASSERT_NO_FATAL_FAILURE(this->Execute(1024, 1)); + + // Test just under and over vector size + ASSERT_NO_FATAL_FAILURE(this->Execute(1023, 1)); + ASSERT_NO_FATAL_FAILURE(this->Execute(1025, 1)); + + // Test multiple vectors + ASSERT_NO_FATAL_FAILURE(this->Execute(2048, 1)); + ASSERT_NO_FATAL_FAILURE(this->Execute(3000, 1)); +} + +TYPED_TEST(TestAlpEncoding, RoundTripWithRepeats) { + // Test with repeated patterns + ASSERT_NO_FATAL_FAILURE(this->Execute(100, 10)); + ASSERT_NO_FATAL_FAILURE(this->Execute(1024, 3)); +} + +TYPED_TEST(TestAlpEncoding, SpecialValues) { + // Test NaN, Inf, -Inf, -0.0 (these become exceptions in ALP) + ASSERT_NO_FATAL_FAILURE(this->ExecuteSpecialValues(100, 1)); + ASSERT_NO_FATAL_FAILURE(this->ExecuteSpecialValues(1024, 1)); + ASSERT_NO_FATAL_FAILURE(this->ExecuteSpecialValues(2000, 1)); +} + +TYPED_TEST(TestAlpEncoding, DecimalPatterns) { + // Test decimal-like values that ALP compresses efficiently + ASSERT_NO_FATAL_FAILURE(this->ExecuteDecimalPattern(100, 1)); + ASSERT_NO_FATAL_FAILURE(this->ExecuteDecimalPattern(1024, 1)); + ASSERT_NO_FATAL_FAILURE(this->ExecuteDecimalPattern(5000, 1)); +} + +TYPED_TEST(TestAlpEncoding, SpacedRoundTrip) { + // Test with null values at various probabilities + for (double null_prob : {0.0, 0.1, 0.5, 0.9}) { + ASSERT_NO_FATAL_FAILURE(this->ExecuteSpaced(100, 1, 0, null_prob)); + ASSERT_NO_FATAL_FAILURE(this->ExecuteSpaced(1024, 1, 0, null_prob)); + ASSERT_NO_FATAL_FAILURE(this->ExecuteSpaced(2000, 1, 0, null_prob)); + } + + // Test with offset + ASSERT_NO_FATAL_FAILURE(this->ExecuteSpaced(1024, 1, 7, 0.3)); + ASSERT_NO_FATAL_FAILURE(this->ExecuteSpaced(1024, 1, 64, 0.5)); +} + +TYPED_TEST(TestAlpEncoding, LargeDataset) { + // Test with large dataset (multiple pages worth) + ASSERT_NO_FATAL_FAILURE(this->Execute(100000, 1)); +} + +TYPED_TEST(TestAlpEncoding, RandomData) { + using c_type = typename TypeParam::c_type; + ::arrow::random::RandomArrayGenerator rag(42); + + // Spread the magnitude so values land on both sides of the ALP encodable + // window (`int64(v * 10^e * 10^-f)` overflows for large magnitudes and + // falls through to the exception path). The previous ±1000 range stayed + // entirely in encodable territory and never exercised the fallback. + std::shared_ptr<::arrow::Array> arr; + if constexpr (std::is_same_v<c_type, float>) { + arr = rag.Float32(10000, -1e30f, 1e30f); + } else { + arr = rag.Float64(10000, -1e30, 1e30); + } + + auto encoder = MakeTypedEncoder<TypeParam>(Encoding::ALP, false, this->descr_.get()); + ASSERT_NO_THROW(encoder->Put(*arr)); + auto buffer = encoder->FlushValues(); + + auto decoder = MakeTypedDecoder<TypeParam>(Encoding::ALP, this->descr_.get()); + decoder->SetData(static_cast<int>(arr->length()), buffer->data(), + static_cast<int>(buffer->size())); + + std::vector<c_type> output(arr->length()); + int decoded = decoder->Decode(output.data(), static_cast<int>(arr->length())); + ASSERT_EQ(decoded, arr->length()); + + // Verify round-trip + auto typed_arr = std::static_pointer_cast< + typename std::conditional<std::is_same_v<c_type, float>, + ::arrow::FloatArray, ::arrow::DoubleArray>::type>(arr); + ASSERT_EQ(0, std::memcmp(output.data(), typed_arr->raw_values(), Review Comment: Done at the site you flagged and the others where a value matcher is the right assertion. The ALP `memcmp`s that remain are the bit-exact float comparisons — the fixture round-trip helpers, the batched-decode test, and the special-value tests — where `-0.0` and `NaN` have to compare equal, which is also why `alp_test.cc` goes through an `IsBitwiseEqual` helper rather than `==`. ########## cpp/src/arrow/util/alp/alp_test.cc: ########## @@ -0,0 +1,1463 @@ +// 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 <cmath> +#include <cstdint> +#include <random> +#include <vector> + +#include <gtest/gtest.h> + +#include "arrow/testing/gtest_util.h" +#include "arrow/util/alp/alp.h" +#include "arrow/util/alp/alp_constants.h" +#include "arrow/util/alp/alp_sampler.h" +#include "arrow/util/alp/alp_codec.h" +#include "arrow/util/bit_stream_utils_internal.h" +#include "arrow/util/bpacking_internal.h" + +namespace arrow { +namespace util { +namespace alp { + +// ============================================================================ +// ALP Constants Tests +// ============================================================================ + +TEST(AlpConstantsTest, SamplerConstants) { + EXPECT_GT(AlpConstants::kSamplerVectorSize, 0); + EXPECT_GT(AlpConstants::kSamplerRowgroupSize, 0); + EXPECT_GT(AlpConstants::kSamplerSamplesPerVector, 0); +} + +// ============================================================================ +// AlpIntegerEncoding Tests +// ============================================================================ + +TEST(AlpIntegerEncodingTest, GetIntegerEncodingMetadataSize) { + // Verify helper returns correct sizes for kForBitPack + EXPECT_EQ(GetIntegerEncodingMetadataSize<float>(AlpIntegerEncoding::kForBitPack), + AlpEncodedForVectorInfo<float>::kStoredSize); + EXPECT_EQ(GetIntegerEncodingMetadataSize<double>(AlpIntegerEncoding::kForBitPack), + AlpEncodedForVectorInfo<double>::kStoredSize); + + // Verify actual byte sizes (frame_of_reference + bit_width, no reserved) + EXPECT_EQ(GetIntegerEncodingMetadataSize<float>(AlpIntegerEncoding::kForBitPack), 5); + EXPECT_EQ(GetIntegerEncodingMetadataSize<double>(AlpIntegerEncoding::kForBitPack), 9); +} + +// ============================================================================ +// ALP Compression Tests (Float) +// ============================================================================ + +class AlpCompressionFloatTest : public ::testing::Test { + protected: + void TestCompressDecompressFloat(const std::vector<float>& input) { + AlpCompression<float> compressor; + + // Compress + AlpEncodingParameters preset{}; // Default preset + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + // Decompress + std::vector<float> output(input.size()); + compressor.DecompressVector(encoded, AlpIntegerEncoding::kForBitPack, output.data()); + + // Verify + ASSERT_EQ(output.size(), input.size()); + for (size_t i = 0; i < input.size(); ++i) { + EXPECT_FLOAT_EQ(output[i], input[i]) << "Mismatch at index " << i; + } + } +}; + +TEST_F(AlpCompressionFloatTest, SimpleSequence) { + std::vector<float> input(64); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<float>(i + 1); + } + TestCompressDecompressFloat(input); +} + +TEST_F(AlpCompressionFloatTest, DecimalValues) { + std::vector<float> input(64); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<float>(i) + 0.5f; + } + TestCompressDecompressFloat(input); +} + +TEST_F(AlpCompressionFloatTest, SmallValues) { + std::vector<float> input(64); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = 0.001f * (i + 1); + } + TestCompressDecompressFloat(input); +} + +TEST_F(AlpCompressionFloatTest, MixedValues) { + std::vector<float> input = {100.5f, 200.25f, 300.125f, 400.0625f, + 500.03125f, 600.015625f, 700.0078125f, + 800.00390625f}; + TestCompressDecompressFloat(input); +} + +TEST_F(AlpCompressionFloatTest, RandomValues) { + std::mt19937 rng(42); + std::uniform_real_distribution<float> dist(0.0f, 1000.0f); + + std::vector<float> input(64); + for (auto& v : input) { + v = dist(rng); + } + + TestCompressDecompressFloat(input); +} + +// ============================================================================ +// ALP Compression Tests (Double) +// ============================================================================ + +class AlpCompressionDoubleTest : public ::testing::Test { + protected: + void TestCompressDecompressDouble(const std::vector<double>& input) { + AlpCompression<double> compressor; + + // Compress + AlpEncodingParameters preset{}; // Default preset + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + // Decompress + std::vector<double> output(input.size()); + compressor.DecompressVector(encoded, AlpIntegerEncoding::kForBitPack, output.data()); + + // Verify + ASSERT_EQ(output.size(), input.size()); + for (size_t i = 0; i < input.size(); ++i) { + EXPECT_DOUBLE_EQ(output[i], input[i]) << "Mismatch at index " << i; + } + } +}; + +TEST_F(AlpCompressionDoubleTest, SimpleSequence) { + std::vector<double> input(64); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<double>(i + 1); + } + TestCompressDecompressDouble(input); +} + +TEST_F(AlpCompressionDoubleTest, HighPrecision) { + std::vector<double> input(64); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = 1.123456789 * (i + 1); + } + TestCompressDecompressDouble(input); +} + +TEST_F(AlpCompressionDoubleTest, VerySmallValues) { + std::vector<double> input(64); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = 1e-10 * (i + 1); + } + TestCompressDecompressDouble(input); +} + +// ============================================================================ +// Integration Tests +// ============================================================================ + +TEST(AlpIntegrationTest, LargeFloatDataset) { + std::mt19937 rng(12345); + std::uniform_real_distribution<float> dist(-1000.0f, 1000.0f); + + std::vector<float> input(1024); + for (auto& v : input) { + v = dist(rng); + } + + AlpCompression<float> compressor; + AlpEncodingParameters preset{}; + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + std::vector<float> output(input.size()); + compressor.DecompressVector(encoded, AlpIntegerEncoding::kForBitPack, output.data()); + + for (size_t i = 0; i < input.size(); ++i) { + EXPECT_FLOAT_EQ(output[i], input[i]); + } +} + +TEST(AlpIntegrationTest, LargeDoubleDataset) { + std::mt19937 rng(12345); + std::uniform_real_distribution<double> dist(-1000.0, 1000.0); + + std::vector<double> input(1024); + for (auto& v : input) { + v = dist(rng); + } + + AlpCompression<double> compressor; + AlpEncodingParameters preset{}; + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + std::vector<double> output(input.size()); + compressor.DecompressVector(encoded, AlpIntegerEncoding::kForBitPack, output.data()); + + for (size_t i = 0; i < input.size(); ++i) { + EXPECT_DOUBLE_EQ(output[i], input[i]); + } +} + +// ============================================================================ +// AlpEncodedVectorInfo Serialization Tests +// ============================================================================ + +TEST(AlpEncodedVectorInfoTest, StoreLoadRoundTrip) { + // Test AlpEncodedVectorInfo (non-templated, 4 bytes) + AlpEncodedVectorInfo info{}; + info.set_exponent(5); + info.set_factor(3); + info.set_num_exceptions(10); + + std::vector<uint8_t> buffer(AlpEncodedVectorInfo::kStoredSize + 10); + info.Store({buffer.data(), buffer.size()}); + + ASSERT_OK_AND_ASSIGN(AlpEncodedVectorInfo loaded, + AlpEncodedVectorInfo::Load({buffer.data(), buffer.size()})); + EXPECT_EQ(info, loaded); + EXPECT_EQ(loaded.exponent(), 5); + EXPECT_EQ(loaded.factor(), 3); + EXPECT_EQ(loaded.num_exceptions(), 10); +} + +TEST(AlpEncodedForVectorInfoTest, StoreLoadRoundTripFloat) { + // Test AlpEncodedForVectorInfo<float> (6 bytes) + AlpEncodedForVectorInfo<float> info{}; + info.set_frame_of_reference(0x12345678U); + info.set_bit_width(12); + + std::vector<uint8_t> buffer(AlpEncodedForVectorInfo<float>::kStoredSize + 10); + info.Store({buffer.data(), buffer.size()}); + + ASSERT_OK_AND_ASSIGN(AlpEncodedForVectorInfo<float> loaded, + AlpEncodedForVectorInfo<float>::Load({buffer.data(), buffer.size()})); + EXPECT_EQ(info, loaded); + EXPECT_EQ(loaded.frame_of_reference(), 0x12345678U); + EXPECT_EQ(loaded.bit_width(), 12); +} + +TEST(AlpEncodedForVectorInfoTest, StoreLoadRoundTripDouble) { + // Test AlpEncodedForVectorInfo<double> (10 bytes) + AlpEncodedForVectorInfo<double> info{}; + info.set_frame_of_reference(0x123456789ABCDEF0ULL); + info.set_bit_width(20); + + std::vector<uint8_t> buffer(AlpEncodedForVectorInfo<double>::kStoredSize + 10); + info.Store({buffer.data(), buffer.size()}); + + ASSERT_OK_AND_ASSIGN(AlpEncodedForVectorInfo<double> loaded, + AlpEncodedForVectorInfo<double>::Load({buffer.data(), buffer.size()})); + EXPECT_EQ(info, loaded); + EXPECT_EQ(loaded.frame_of_reference(), 0x123456789ABCDEF0ULL); + EXPECT_EQ(loaded.bit_width(), 20); +} + +TEST(AlpEncodedVectorInfoTest, Size) { + // AlpEncodedVectorInfo is non-templated and fixed at 4 bytes + EXPECT_EQ(AlpEncodedVectorInfo::kStoredSize, 4); + EXPECT_EQ(AlpEncodedVectorInfo::GetStoredSize(), 4); +} + +TEST(AlpEncodedForVectorInfoTest, Size) { + // AlpEncodedForVectorInfo: float=5 bytes, double=9 bytes + // (frame_of_reference is 4 bytes for float, 8 bytes for double, + 1 byte for bit_width) + EXPECT_EQ(AlpEncodedForVectorInfo<float>::kStoredSize, 5); + EXPECT_EQ(AlpEncodedForVectorInfo<float>::GetStoredSize(), 5); + EXPECT_EQ(AlpEncodedForVectorInfo<double>::kStoredSize, 9); + EXPECT_EQ(AlpEncodedForVectorInfo<double>::GetStoredSize(), 9); +} + +// ============================================================================ +// Edge Case Tests +// ============================================================================ + +template <typename T> +class AlpEdgeCaseTest : public ::testing::Test { + protected: + void TestCompressDecompress(const std::vector<T>& input) { + AlpCompression<T> compressor; + AlpEncodingParameters preset{}; + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + std::vector<T> output(input.size()); + compressor.DecompressVector(encoded, AlpIntegerEncoding::kForBitPack, output.data()); + + ASSERT_EQ(output.size(), input.size()); + // Use memcmp for bit-exact comparison (important for -0.0, NaN) + EXPECT_EQ(std::memcmp(output.data(), input.data(), input.size() * sizeof(T)), + 0); + } +}; + +using EdgeCaseTestTypes = ::testing::Types<float, double>; +TYPED_TEST_SUITE(AlpEdgeCaseTest, EdgeCaseTestTypes); + +TYPED_TEST(AlpEdgeCaseTest, SingleElement) { + std::vector<TypeParam> input = {static_cast<TypeParam>(42.5)}; + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, EmptyInput) { + // Test zero elements - empty vector + // The wrapper API requires decomp_size to be a multiple of sizeof(T), + // and 0 is a valid multiple. This tests the boundary condition. + std::vector<TypeParam> input; + + int64_t max_size = AlpCodec<TypeParam>::GetMaxCompressedSize(0); + std::vector<uint8_t> buffer(max_size > 0 ? max_size : 8); // Ensure some buffer + int64_t comp_size = static_cast<int64_t>(buffer.size()); + + AlpCodec<TypeParam>::Encode(input.data(), 0, buffer.data(), &comp_size); + + // Decode zero elements + std::vector<TypeParam> output; + ASSERT_OK(AlpCodec<TypeParam>::template Decode<TypeParam>(0, buffer.data(), + comp_size, output.data())); + + // Both should be empty + EXPECT_EQ(input.size(), output.size()); + EXPECT_EQ(input.size(), 0); +} + +TYPED_TEST(AlpEdgeCaseTest, TwoElements) { + std::vector<TypeParam> input = {static_cast<TypeParam>(1.5), + static_cast<TypeParam>(2.5)}; + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, ExactVectorSize) { + // Test exactly kAlpVectorSize elements (1024) + std::vector<TypeParam> input(AlpConstants::kAlpVectorSize); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.1); + } + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, JustUnderVectorSize) { + // Test kAlpVectorSize - 1 elements (1023) + std::vector<TypeParam> input(AlpConstants::kAlpVectorSize - 1); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.1); + } + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, JustOverVectorSize) { + // Test kAlpVectorSize + 1 elements (1025) - requires multiple vectors + std::vector<TypeParam> input(AlpConstants::kAlpVectorSize + 1); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.1); + } + // For multi-vector, we need to process in chunks + AlpCompression<TypeParam> compressor; + AlpEncodingParameters preset{}; + + // Process first vector + auto encoded1 = compressor.CompressVector(input.data(), + AlpConstants::kAlpVectorSize, preset); + std::vector<TypeParam> output1(AlpConstants::kAlpVectorSize); + compressor.DecompressVector(encoded1, AlpIntegerEncoding::kForBitPack, output1.data()); + + // Process remaining element + auto encoded2 = compressor.CompressVector( + input.data() + AlpConstants::kAlpVectorSize, 1, preset); + std::vector<TypeParam> output2(1); + compressor.DecompressVector(encoded2, AlpIntegerEncoding::kForBitPack, output2.data()); + + // Verify + EXPECT_EQ(std::memcmp(output1.data(), input.data(), + AlpConstants::kAlpVectorSize * sizeof(TypeParam)), + 0); + EXPECT_EQ(std::memcmp(output2.data(), + input.data() + AlpConstants::kAlpVectorSize, + sizeof(TypeParam)), + 0); +} + +// ============================================================================ +// Special Values Tests +// ============================================================================ + +TYPED_TEST(AlpEdgeCaseTest, SpecialValues) { + // Test NaN, Inf, -Inf, -0.0 + std::vector<TypeParam> input = { + static_cast<TypeParam>(0.0), + static_cast<TypeParam>(-0.0), + std::numeric_limits<TypeParam>::infinity(), + -std::numeric_limits<TypeParam>::infinity(), + std::numeric_limits<TypeParam>::quiet_NaN(), + }; + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, NegativeZero) { + // -0.0 should be preserved bit-exactly + std::vector<TypeParam> input(100); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = (i % 2 == 0) ? static_cast<TypeParam>(0.0) + : static_cast<TypeParam>(-0.0); + } + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, AllNaN) { + // All NaN values - all become exceptions + std::vector<TypeParam> input(64); + for (auto& v : input) { + v = std::numeric_limits<TypeParam>::quiet_NaN(); + } + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, AllInfinity) { + // All infinity values + std::vector<TypeParam> input(64); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = (i % 2 == 0) ? std::numeric_limits<TypeParam>::infinity() + : -std::numeric_limits<TypeParam>::infinity(); + } + this->TestCompressDecompress(input); +} + +// ============================================================================ +// Compression Characteristics Tests +// ============================================================================ + +TYPED_TEST(AlpEdgeCaseTest, ConstantValues) { + // All same values - should compress very well (bitWidth = 0) + std::vector<TypeParam> input(1024); + std::fill(input.begin(), input.end(), static_cast<TypeParam>(123.456)); + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, MixedCompressibleAndExceptions) { + // Mix of compressible decimals and exceptions + std::vector<TypeParam> input(1024); + for (size_t i = 0; i < input.size(); ++i) { + if (i % 10 == 0) { + input[i] = std::numeric_limits<TypeParam>::quiet_NaN(); + } else if (i % 20 == 5) { + input[i] = std::numeric_limits<TypeParam>::infinity(); + } else { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.01); + } + } + this->TestCompressDecompress(input); +} + +// ============================================================================ +// Boundary Value Tests +// ============================================================================ + +TYPED_TEST(AlpEdgeCaseTest, MaxMinValues) { + std::vector<TypeParam> input = { + std::numeric_limits<TypeParam>::max(), + std::numeric_limits<TypeParam>::min(), + std::numeric_limits<TypeParam>::lowest(), + std::numeric_limits<TypeParam>::denorm_min(), + std::numeric_limits<TypeParam>::epsilon(), + -std::numeric_limits<TypeParam>::max(), + -std::numeric_limits<TypeParam>::min(), + -std::numeric_limits<TypeParam>::denorm_min(), + -std::numeric_limits<TypeParam>::epsilon(), + static_cast<TypeParam>(0.0)}; + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, Subnormals) { + // Test subnormal (denormalized) floating point values + std::vector<TypeParam> input(100); + TypeParam subnormal = std::numeric_limits<TypeParam>::denorm_min(); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = subnormal * static_cast<TypeParam>(i + 1); + } + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, LargeDecimals) { + // Test large decimal values that should still be compressible + std::vector<TypeParam> input(1024); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(1000000.0) + + static_cast<TypeParam>(i) * static_cast<TypeParam>(0.01); + } + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, SmallDecimals) { + // Test very small decimal values + std::vector<TypeParam> input(1024); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(0.000001) * static_cast<TypeParam>(i + 1); + } + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, NegativeValues) { + // Test negative values + std::vector<TypeParam> input(1024); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = -static_cast<TypeParam>(i) * static_cast<TypeParam>(0.5); + } + this->TestCompressDecompress(input); +} + +TYPED_TEST(AlpEdgeCaseTest, AlternatingSignValues) { + // Test values alternating between positive and negative + std::vector<TypeParam> input(1024); + for (size_t i = 0; i < input.size(); ++i) { + TypeParam sign = (i % 2 == 0) ? static_cast<TypeParam>(1.0) + : static_cast<TypeParam>(-1.0); + input[i] = sign * static_cast<TypeParam>(i) * static_cast<TypeParam>(0.1); + } + this->TestCompressDecompress(input); +} + +// ============================================================================ +// AlpEncodedVector Store/Load Tests +// ============================================================================ + +template <typename T> +class AlpEncodedVectorTest : public ::testing::Test {}; + +TYPED_TEST_SUITE(AlpEncodedVectorTest, EdgeCaseTestTypes); + +TYPED_TEST(AlpEncodedVectorTest, StoreLoadRoundTrip) { + // Create a sample encoded vector + AlpCompression<TypeParam> compressor; + AlpEncodingParameters preset{}; + + std::vector<TypeParam> input(64); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.5); + } + + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + // Store + std::vector<uint8_t> buffer(encoded.GetStoredSize()); + encoded.Store({buffer.data(), buffer.size()}); + + // Load (pass num_elements since it's not stored in the buffer) + ASSERT_OK_AND_ASSIGN( + auto loaded, + AlpEncodedVector<TypeParam>::Load( + {buffer.data(), buffer.size()}, static_cast<uint16_t>(input.size()))); + + // Verify metadata + EXPECT_EQ(encoded.alp_info(), loaded.alp_info()); + EXPECT_EQ(encoded.for_info(), loaded.for_info()); + + // Decompress loaded and verify + std::vector<TypeParam> output(input.size()); + compressor.DecompressVector(loaded, AlpIntegerEncoding::kForBitPack, output.data()); + + EXPECT_EQ(std::memcmp(output.data(), input.data(), input.size() * sizeof(TypeParam)), + 0); +} + +TYPED_TEST(AlpEncodedVectorTest, GetStoredSizeConsistency) { + AlpCompression<TypeParam> compressor; + AlpEncodingParameters preset{}; + + std::vector<TypeParam> input(128); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.25); + } + + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + // Verify GetStoredSize matches actual storage + std::vector<uint8_t> buffer(encoded.GetStoredSize()); + encoded.Store({buffer.data(), buffer.size()}); + + EXPECT_EQ(buffer.size(), encoded.GetStoredSize()); +} + +// ============================================================================ +// AlpEncodedVectorView Tests - Alignment Safety +// ============================================================================ + +// This test exercises AlpEncodedVectorView::LoadView which was previously +// vulnerable to undefined behavior from misaligned memory access (ubsan error). +// The old code used reinterpret_cast to create spans pointing directly into +// the buffer for exception_positions (uint16_t*) and exceptions (T*), which +// could violate alignment requirements when bit_packed_size was odd. +// +// The fix copies these into aligned std::vector storage. +TYPED_TEST(AlpEncodedVectorTest, ViewLoadWithExceptions) { + AlpCompression<TypeParam> compressor; + AlpEncodingParameters preset{}; + + // Create data with exceptions to ensure exception handling code path is hit. + // NaN, Inf, and -0.0 all become exceptions. + std::vector<TypeParam> input(64); + for (size_t i = 0; i < input.size(); ++i) { + if (i % 10 == 0) { + // Every 10th value is NaN - becomes an exception + input[i] = std::numeric_limits<TypeParam>::quiet_NaN(); + } else if (i % 10 == 5) { + // Some infinities - also exceptions + input[i] = std::numeric_limits<TypeParam>::infinity(); + } else { + // Normal compressible values + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.1); + } + } + + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + // Verify we actually have exceptions + EXPECT_GT(encoded.alp_info().num_exceptions(), 0) + << "Test requires exceptions to exercise alignment code path"; + + // Store to buffer + std::vector<uint8_t> buffer(encoded.GetStoredSize()); + encoded.Store({buffer.data(), buffer.size()}); + + // Load using zero-copy view - this was where the ubsan error occurred + ASSERT_OK_AND_ASSIGN( + auto view, + AlpEncodedVectorView<TypeParam>::LoadView( + {buffer.data(), buffer.size()}, static_cast<uint16_t>(input.size()))); + + // Verify view loaded correctly + EXPECT_EQ(view.alp_info(), encoded.alp_info()); + EXPECT_EQ(view.for_info(), encoded.for_info()); + EXPECT_EQ(view.num_elements(), input.size()); + EXPECT_EQ(view.exception_positions().size(), encoded.alp_info().num_exceptions()); + EXPECT_EQ(view.exceptions().size(), encoded.alp_info().num_exceptions()); + + // Decompress using the view - this exercises PatchExceptions with the + // std::vector members (previously spans that could be misaligned) + std::vector<TypeParam> output(input.size()); + compressor.DecompressVectorView(view, AlpIntegerEncoding::kForBitPack, output.data()); + + // Verify bit-exact reconstruction + EXPECT_EQ(std::memcmp(output.data(), input.data(), input.size() * sizeof(TypeParam)), + 0); +} + +// Test specifically designed to create misaligned buffer offsets. +// VectorInfo is 10 bytes for float, 14 for double. If bit_packed_size is odd, exception_positions +// starts at an odd offset (14 + odd = odd), violating uint16_t alignment. +TYPED_TEST(AlpEncodedVectorTest, ViewLoadWithMisalignedExceptions) { + AlpCompression<TypeParam> compressor; + AlpEncodingParameters preset{}; + + // Create a small vector with specific size to get odd bit_packed_size. + // 5 elements with bit_width=8 -> bit_packed_size=5 (odd) + // 7 elements with bit_width=8 -> bit_packed_size=7 (odd) + // 9 elements with bit_width=8 -> bit_packed_size=9 (odd) + // We want to ensure at least one exception exists. + std::vector<TypeParam> input = { + static_cast<TypeParam>(1.0), + static_cast<TypeParam>(2.0), + static_cast<TypeParam>(3.0), + std::numeric_limits<TypeParam>::quiet_NaN(), // Exception + static_cast<TypeParam>(5.0), + static_cast<TypeParam>(6.0), + std::numeric_limits<TypeParam>::infinity(), // Exception + }; + + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + // Verify we have exceptions + EXPECT_GE(encoded.alp_info().num_exceptions(), 2) + << "Expected at least 2 exceptions (NaN and Inf)"; + + // Store to buffer + std::vector<uint8_t> buffer(encoded.GetStoredSize()); + encoded.Store({buffer.data(), buffer.size()}); + + // Calculate where exceptions start to verify potential misalignment + const uint64_t alp_info_size = AlpEncodedVectorInfo::kStoredSize; + const uint64_t for_info_size = AlpEncodedForVectorInfo<TypeParam>::kStoredSize; + const uint64_t bit_packed_size = AlpEncodedForVectorInfo<TypeParam>::GetBitPackedSize( + static_cast<uint16_t>(input.size()), encoded.for_info().bit_width()); + const uint64_t exception_pos_offset = alp_info_size + for_info_size + bit_packed_size; + + // Log alignment info for debugging + SCOPED_TRACE("AlpInfo size: " + std::to_string(alp_info_size)); + SCOPED_TRACE("ForInfo size: " + std::to_string(for_info_size)); + SCOPED_TRACE("Bit packed size: " + std::to_string(bit_packed_size)); + SCOPED_TRACE("Exception pos offset: " + std::to_string(exception_pos_offset)); + SCOPED_TRACE("Offset is aligned: " + + std::to_string(exception_pos_offset % alignof(uint16_t) == 0)); + + // Load using view - with old code, this would trigger ubsan if misaligned + ASSERT_OK_AND_ASSIGN( + auto view, + AlpEncodedVectorView<TypeParam>::LoadView( + {buffer.data(), buffer.size()}, static_cast<uint16_t>(input.size()))); + + // Access exceptions explicitly - with old code using spans, this would + // be undefined behavior if the buffer wasn't properly aligned + EXPECT_EQ(view.exception_positions().size(), encoded.alp_info().num_exceptions()); + EXPECT_EQ(view.exceptions().size(), encoded.alp_info().num_exceptions()); + + // Verify exception positions are accessible and valid + for (size_t i = 0; i < view.exception_positions().size(); ++i) { + EXPECT_LT(view.exception_positions()[i], input.size()) + << "Exception position out of bounds at index " << i; + } + + // Decompress and verify + std::vector<TypeParam> output(input.size()); + compressor.DecompressVectorView(view, AlpIntegerEncoding::kForBitPack, output.data()); + + EXPECT_EQ(std::memcmp(output.data(), input.data(), input.size() * sizeof(TypeParam)), + 0); +} + +// Test with buffer allocated at intentionally odd offset to maximize +// chance of hitting misalignment issues on systems that don't crash. +TYPED_TEST(AlpEncodedVectorTest, ViewLoadFromMisalignedBuffer) { + AlpCompression<TypeParam> compressor; + AlpEncodingParameters preset{}; + + // Data with exceptions + std::vector<TypeParam> input(32); + for (size_t i = 0; i < input.size(); ++i) { + if (i % 8 == 0) { + input[i] = std::numeric_limits<TypeParam>::quiet_NaN(); + } else { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.5); + } + } + + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + EXPECT_GT(encoded.alp_info().num_exceptions(), 0); + + // Allocate buffer with extra byte, then use offset to create misaligned start + std::vector<uint8_t> oversized_buffer(encoded.GetStoredSize() + 16); + + // Try different offsets to hit various alignment scenarios + for (size_t offset = 0; offset < 8; ++offset) { + uint8_t* buffer_start = oversized_buffer.data() + offset; + arrow::util::span<uint8_t> buffer(buffer_start, encoded.GetStoredSize()); + + encoded.Store(buffer); + + // Load view from potentially misaligned buffer + ASSERT_OK_AND_ASSIGN( + auto view, + AlpEncodedVectorView<TypeParam>::LoadView( + {buffer_start, static_cast<size_t>(encoded.GetStoredSize())}, + static_cast<uint16_t>(input.size()))); + + // Decompress - this is where the fix matters + std::vector<TypeParam> output(input.size()); + compressor.DecompressVectorView(view, AlpIntegerEncoding::kForBitPack, output.data()); + + // Verify + EXPECT_EQ(std::memcmp(output.data(), input.data(), input.size() * sizeof(TypeParam)), + 0) + << "Failed at buffer offset " << offset; + } +} + +// ============================================================================ +// AlpCodec Tests +// ============================================================================ + +template <typename T> +class AlpCodecTest : public ::testing::Test { + protected: + void TestEncodeDecodeWrapper(const std::vector<T>& input) { + // Get max compressed size + int64_t max_comp_size = + AlpCodec<T>::GetMaxCompressedSize(input.size()); + std::vector<uint8_t> comp_buffer(max_comp_size); + + // Encode + int64_t comp_size = max_comp_size; + AlpCodec<T>::Encode(input.data(), + static_cast<int64_t>(input.size()), + comp_buffer.data(), &comp_size); + + EXPECT_GT(comp_size, 0); + EXPECT_LE(comp_size, max_comp_size); + + // Decode + std::vector<T> output(input.size()); + ASSERT_OK(AlpCodec<T>::template Decode<T>( + static_cast<int32_t>(input.size()), comp_buffer.data(), + comp_size, output.data())); + + // Verify + EXPECT_EQ(std::memcmp(output.data(), input.data(), input.size() * sizeof(T)), + 0); + } +}; + +TYPED_TEST_SUITE(AlpCodecTest, EdgeCaseTestTypes); + +TYPED_TEST(AlpCodecTest, SimpleSequence) { + std::vector<TypeParam> input(1024); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.1); + } + this->TestEncodeDecodeWrapper(input); +} + +TYPED_TEST(AlpCodecTest, MultipleVectors) { + // Test with multiple vectors worth of data + std::vector<TypeParam> input(3 * AlpConstants::kAlpVectorSize); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.01); + } + this->TestEncodeDecodeWrapper(input); +} + +TYPED_TEST(AlpCodecTest, SpecialValues) { + std::vector<TypeParam> input = { + static_cast<TypeParam>(0.0), + static_cast<TypeParam>(-0.0), + std::numeric_limits<TypeParam>::infinity(), + -std::numeric_limits<TypeParam>::infinity(), + std::numeric_limits<TypeParam>::quiet_NaN(), + static_cast<TypeParam>(1.5), + static_cast<TypeParam>(-2.5), + }; + this->TestEncodeDecodeWrapper(input); +} + +TYPED_TEST(AlpCodecTest, GetMaxCompressedSizeAdequate) { + // Verify GetMaxCompressedSize always provides enough space + const std::vector<size_t> test_sizes = {1, 10, 100, 1023, 1024, 1025, 2048, 5000}; + + for (const size_t size : test_sizes) { + std::vector<TypeParam> input(size); + for (size_t i = 0; i < size; ++i) { + // Mix of values to create a realistic scenario + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.123); + if (i % 7 == 0) { + input[i] = std::numeric_limits<TypeParam>::quiet_NaN(); + } + } + + int64_t max_comp_size = + AlpCodec<TypeParam>::GetMaxCompressedSize(static_cast<int64_t>(size)); + std::vector<uint8_t> comp_buffer(max_comp_size); + int64_t comp_size = max_comp_size; + + AlpCodec<TypeParam>::Encode(input.data(), static_cast<int64_t>(size), + comp_buffer.data(), &comp_size); + + EXPECT_LE(comp_size, max_comp_size) + << "Compressed size exceeded max for " << size << " elements"; + EXPECT_GT(comp_size, 0) + << "Compression produced 0 bytes for " << size << " elements"; + } +} + +TYPED_TEST(AlpCodecTest, WideningDecode) { + // Test decoding float data to double (widening conversion) + if constexpr (std::is_same_v<TypeParam, float>) { + std::vector<float> input(256); + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<float>(i) * 0.5f; + } + + int64_t max_comp_size = + AlpCodec<float>::GetMaxCompressedSize(static_cast<int64_t>(input.size())); + std::vector<uint8_t> comp_buffer(max_comp_size); + int64_t comp_size = max_comp_size; + + AlpCodec<float>::Encode(input.data(), static_cast<int64_t>(input.size()), + comp_buffer.data(), &comp_size); + + // Decode as double + std::vector<double> output(input.size()); + ASSERT_OK(AlpCodec<float>::template Decode<double>( + static_cast<int32_t>(input.size()), comp_buffer.data(), comp_size, + output.data())); + + // Verify values match (as double) + for (size_t i = 0; i < input.size(); ++i) { + EXPECT_DOUBLE_EQ(output[i], static_cast<double>(input[i])); + } + } +} + +// ============================================================================ +// Bit-Width Edge Cases Tests +// ============================================================================ + +TYPED_TEST(AlpEdgeCaseTest, ZeroBitWidth) { + // All identical values should result in bit_width=0 + std::vector<TypeParam> input(1024); + std::fill(input.begin(), input.end(), static_cast<TypeParam>(123.456)); + + AlpCompression<TypeParam> compressor; + AlpEncodingParameters preset{}; + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + // bit_width should be 0 for constant values + EXPECT_EQ(encoded.for_info().bit_width(), 0); + + // Verify round-trip + std::vector<TypeParam> output(input.size()); + compressor.DecompressVector(encoded, AlpIntegerEncoding::kForBitPack, output.data()); + EXPECT_EQ(std::memcmp(output.data(), input.data(), input.size() * sizeof(TypeParam)), + 0); +} + +TYPED_TEST(AlpEdgeCaseTest, SmallBitWidths) { + // Test small bit widths (1-8) + for (int bit_range = 1; bit_range <= 8; ++bit_range) { + std::vector<TypeParam> input(1024); + TypeParam base_value = static_cast<TypeParam>(1000.0); + + for (size_t i = 0; i < input.size(); ++i) { + input[i] = base_value + static_cast<TypeParam>(i % (1 << bit_range)) * + static_cast<TypeParam>(0.01); + } + + AlpCompression<TypeParam> compressor; + AlpEncodingParameters preset{}; + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + std::vector<TypeParam> output(input.size()); + compressor.DecompressVector(encoded, AlpIntegerEncoding::kForBitPack, output.data()); + + EXPECT_EQ(std::memcmp(output.data(), input.data(), input.size() * sizeof(TypeParam)), + 0) + << "Failed for bit_range=" << bit_range; + } +} + +TYPED_TEST(AlpEdgeCaseTest, LargeBitWidths) { + // Test large bit widths by creating data with large range + std::vector<TypeParam> input(1024); + for (size_t i = 0; i < input.size(); ++i) { + // Large spread of values + input[i] = static_cast<TypeParam>(i * 1000000.0); + } + + AlpCompression<TypeParam> compressor; + AlpEncodingParameters preset{}; + auto encoded = compressor.CompressVector(input.data(), input.size(), preset); + + std::vector<TypeParam> output(input.size()); + compressor.DecompressVector(encoded, AlpIntegerEncoding::kForBitPack, output.data()); + + EXPECT_EQ(std::memcmp(output.data(), input.data(), input.size() * sizeof(TypeParam)), + 0); +} + +// ============================================================================ +// Large Dataset Tests +// ============================================================================ + +TYPED_TEST(AlpCodecTest, VeryLargeDataset) { + // Test with 1 million elements + constexpr size_t kLargeSize = 1024 * 1024; + std::vector<TypeParam> input(kLargeSize); + + std::mt19937 rng(12345); + std::uniform_real_distribution<TypeParam> dist( + static_cast<TypeParam>(-1000.0), static_cast<TypeParam>(1000.0)); + + for (auto& v : input) { + v = dist(rng); + } + + this->TestEncodeDecodeWrapper(input); +} + +TYPED_TEST(AlpCodecTest, MultiplePages) { + // Test with data spanning multiple pages (each page has multiple vectors) + constexpr size_t kMultiPageSize = 100000; // ~100 vectors worth + std::vector<TypeParam> input(kMultiPageSize); + + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.001); + } + + this->TestEncodeDecodeWrapper(input); +} + +TYPED_TEST(AlpCodecTest, EncodeWithPreset) { + // Test that encoding with a pre-computed preset produces identical results + constexpr size_t kTestSize = 4096; // 4 vectors worth + std::vector<TypeParam> input(kTestSize); + + for (size_t i = 0; i < input.size(); ++i) { + input[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.123); + } + + // First, encode normally + const int64_t num_elements = static_cast<int64_t>(input.size()); + int64_t max_comp_size = AlpCodec<TypeParam>::GetMaxCompressedSize(num_elements); + std::vector<uint8_t> comp_buffer1(max_comp_size); + int64_t comp_size1 = max_comp_size; + + AlpCodec<TypeParam>::Encode(input.data(), num_elements, + comp_buffer1.data(), &comp_size1); + + // Now, use the preset-based API + auto preset = AlpCodec<TypeParam>::CreateSamplingPreset(input.data(), num_elements); + + std::vector<uint8_t> comp_buffer2(max_comp_size); + int64_t comp_size2 = max_comp_size; + + AlpCodec<TypeParam>::EncodeWithPreset(input.data(), num_elements, + preset, AlpConstants::kAlpVectorSize, + comp_buffer2.data(), &comp_size2); + + // Both should produce identical output + EXPECT_EQ(comp_size1, comp_size2); + EXPECT_EQ(std::memcmp(comp_buffer1.data(), comp_buffer2.data(), comp_size1), 0); + + // Verify the preset-based encoding can be decoded correctly + std::vector<TypeParam> output(input.size()); + ASSERT_OK(AlpCodec<TypeParam>::template Decode<TypeParam>( + static_cast<int32_t>(input.size()), comp_buffer2.data(), comp_size2, + output.data())); + + EXPECT_EQ(std::memcmp(output.data(), input.data(), input.size() * sizeof(TypeParam)), 0); +} + +TYPED_TEST(AlpCodecTest, PresetReuseAcrossBatches) { + // Test that a preset can be reused for multiple encode calls + constexpr size_t kBatchSize = 1024; + std::vector<TypeParam> batch1(kBatchSize), batch2(kBatchSize); + + // Two batches with similar data characteristics + for (size_t i = 0; i < kBatchSize; ++i) { + batch1[i] = static_cast<TypeParam>(i) * static_cast<TypeParam>(0.01); + batch2[i] = static_cast<TypeParam>(i + 1000) * static_cast<TypeParam>(0.01); + } + + // Create preset from first batch + const int64_t num_elements = static_cast<int64_t>(kBatchSize); + auto preset = AlpCodec<TypeParam>::CreateSamplingPreset(batch1.data(), num_elements); + + int64_t max_comp_size = AlpCodec<TypeParam>::GetMaxCompressedSize(num_elements); + + // Encode batch1 with preset + std::vector<uint8_t> comp1(max_comp_size); + int64_t comp_size1 = max_comp_size; + AlpCodec<TypeParam>::EncodeWithPreset(batch1.data(), num_elements, + preset, AlpConstants::kAlpVectorSize, + comp1.data(), &comp_size1); + + // Encode batch2 with same preset (reuse) + std::vector<uint8_t> comp2(max_comp_size); + int64_t comp_size2 = max_comp_size; + AlpCodec<TypeParam>::EncodeWithPreset(batch2.data(), num_elements, + preset, AlpConstants::kAlpVectorSize, + comp2.data(), &comp_size2); + + // Both should encode successfully + EXPECT_GT(comp_size1, 0); + EXPECT_GT(comp_size2, 0); + + // Decode and verify both batches + std::vector<TypeParam> output1(kBatchSize), output2(kBatchSize); + ASSERT_OK(AlpCodec<TypeParam>::template Decode<TypeParam>( + static_cast<int32_t>(kBatchSize), comp1.data(), comp_size1, output1.data())); + ASSERT_OK(AlpCodec<TypeParam>::template Decode<TypeParam>( + static_cast<int32_t>(kBatchSize), comp2.data(), comp_size2, output2.data())); + + EXPECT_EQ(std::memcmp(output1.data(), batch1.data(), kBatchSize * sizeof(TypeParam)), 0); Review Comment: These two aren't value comparisons — one asserts that encoding with an explicit preset produces byte-identical output to letting the codec pick, and the other that encoding the same input twice does. Both are claims about the bytes, so `memcmp` on the two buffers is the assertion I want. The value round-trips all go through the `IsBitwiseEqual` helper instead. ########## cpp/src/arrow/util/alp/generate_alp_parquet.cc: ########## Review Comment: Both removed. ########## cpp/src/arrow/util/alp/alp.h: ########## @@ -0,0 +1,795 @@ +// 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. + +// Adaptive Lossless floating-Point (ALP) compression implementation + +#pragma once + +#include <optional> +#include <vector> + +#include "arrow/result.h" +#include "arrow/status.h" +#include "arrow/util/alp/alp_constants.h" +#include "arrow/util/span.h" + +namespace arrow { +namespace util { +namespace alp { + +// ---------------------------------------------------------------------- +// ALP Overview +// +// IMPORTANT: For abstract interfaces or examples how to use ALP, consult +// alp_codec.h. +// This is our implementation of the adaptive lossless floating-point +// compression for decimals (ALP) (https://dl.acm.org/doi/10.1145/3626717). +// It works by converting a float into a decimal (if possible). The exponent +// and factor are chosen per vector. Each float is converted using +// c(f) = int64(f * 10^exponent * 10^-factor). The converted floats are then +// encoded via a delta frame of reference and bitpacked. Every exception, +// where the conversion/reconversion changes the value of the float, is stored +// separately and has to be patched into the decompressed vector afterwards. +// +// ========================================================================== +// ALP COMPRESSION/DECOMPRESSION PIPELINE +// ========================================================================== +// +// COMPRESSION FLOW: +// ----------------- +// +// Input: float/double array +// | +// v +// +------------------------------------------------------------------+ +// | 1. SAMPLING & PRESET GENERATION | +// | * Sample vectors from dataset | +// | * Try all exponent/factor combinations (e, f) | +// | * Select best k combinations for preset | +// +------------------------------------+-----------------------------+ +// | preset.combinations +// v +// +------------------------------------------------------------------+ +// | 2. PER-VECTOR COMPRESSION | +// | a) Find best (e,f) from preset for this vector | +// | b) Encode: encoded[i] = int64(value[i] * 10^e * 10^-f) | +// | c) Verify: if decode(encoded[i]) != value[i] -> exception | +// | d) Replace exceptions with placeholder value | +// +------------------------------------+-----------------------------+ +// | encoded integers + exceptions +// v +// +------------------------------------------------------------------+ +// | 3. FRAME OF REFERENCE (FOR) | +// | * Find min value in encoded integers | +// | * Subtract min from all values: delta[i] = encoded[i] - min | +// +------------------------------------+-----------------------------+ +// | delta values (smaller range) +// v +// +------------------------------------------------------------------+ +// | 4. BIT PACKING | +// | * Calculate bit_width = log2(max_delta) | +// | * Pack each value into bit_width bits | +// | * Result: tightly packed binary data | +// +------------------------------------+-----------------------------+ +// | packed bytes +// v +// +------------------------------------------------------------------+ +// | 5. SERIALIZATION (offset-based interleaved layout) | +// | [Header][Offsets...][Vector₀][Vector₁]... | +// | where each Vector = [AlpInfo|ForInfo|Data] | +// +------------------------------------------------------------------+ +// +// +// DECOMPRESSION FLOW: +// ------------------- +// +// Serialized bytes -> AlpEncodedVector::Load() +// | +// v +// +------------------------------------------------------------------+ +// | 1. BIT UNPACKING | +// | * Extract bit_width from metadata | +// | * Unpack each value from bit_width bits -> delta values | +// +------------------------------------+-----------------------------+ +// | delta values +// v +// +------------------------------------------------------------------+ +// | 2. REVERSE FRAME OF REFERENCE (unFOR) | +// | * Add back min: encoded[i] = delta[i] + frame_of_reference | +// +------------------------------------+-----------------------------+ +// | encoded integers +// v +// +------------------------------------------------------------------+ +// | 3. DECODE | +// | * Apply inverse formula: value[i] = encoded[i] * 10^-e * 10^f | +// +------------------------------------+-----------------------------+ +// | decoded floats (with placeholders) +// v +// +------------------------------------------------------------------+ +// | 4. PATCH EXCEPTIONS | +// | * Replace values at exception_positions[] with exceptions[] | +// +------------------------------------+-----------------------------+ +// | +// v +// Output: Original float/double array (lossless!) +// +// ========================================================================== + +// ---------------------------------------------------------------------- +// AlpMode + +/// \brief ALP compression mode +/// +/// Currently only ALP (decimal compression) is implemented. +enum class AlpMode { kAlp = 0 }; + +// ---------------------------------------------------------------------- +// AlpExponentAndFactor + +/// \brief Helper struct to encapsulate the exponent and factor +struct AlpExponentAndFactor { + uint8_t exponent{0}; + uint8_t factor{0}; + + bool operator==(const AlpExponentAndFactor& other) const { + return exponent == other.exponent && factor == other.factor; + } + + /// \brief Comparison operator for deterministic std::map ordering + bool operator<(const AlpExponentAndFactor& other) const { + if (exponent != other.exponent) return exponent < other.exponent; + return factor < other.factor; + } +}; + +// ---------------------------------------------------------------------- +// AlpEncodedVectorInfo (non-templated, ALP core metadata) + +/// \brief ALP-specific metadata for an encoded vector (non-templated) +/// +/// Contains the metadata specific to ALP's float-to-integer conversion: +/// - exponent/factor: parameters for decimal encoding +/// - num_exceptions: count of values that couldn't be losslessly encoded +/// +/// This struct is the same size regardless of the floating-point type (float/double). +/// It is separate from the integer encoding metadata (e.g., FOR) to allow +/// different integer encodings to be used in the future. +/// +/// Serialization format (4 bytes): +/// +/// +------------------------------------------+ +/// | AlpEncodedVectorInfo (4 bytes) | +/// +------------------------------------------+ +/// | Offset | Field | Size | +/// +---------+---------------------+----------+ +/// | 0 | exponent (uint8_t) | 1 byte | +/// | 1 | factor (uint8_t) | 1 byte | +/// | 2 | num_exceptions | 2 bytes | +/// +------------------------------------------+ +class AlpEncodedVectorInfo { + public: + AlpEncodedVectorInfo() = default; + AlpEncodedVectorInfo(uint8_t exponent, uint8_t factor, int16_t num_exceptions) + : exponent_(exponent), factor_(factor), num_exceptions_(num_exceptions) {} + + uint8_t exponent() const { return exponent_; } + uint8_t factor() const { return factor_; } + int16_t num_exceptions() const { return num_exceptions_; } + + void set_exponent(uint8_t exponent) { exponent_ = exponent; } + void set_factor(uint8_t factor) { factor_ = factor; } + void set_num_exceptions(int16_t num_exceptions) { num_exceptions_ = num_exceptions; } + + /// Size of the serialized portion (4 bytes, fixed) + static constexpr int64_t kStoredSize = + sizeof(uint8_t) + sizeof(uint8_t) + sizeof(int16_t); + static_assert(kStoredSize == 4, "AlpEncodedVectorInfo stored size must be 4 bytes"); + + /// \brief Store the ALP metadata into an output buffer + /// + /// \pre output_buffer.size() >= kStoredSize + void Store(arrow::util::span<uint8_t> output_buffer) const; + + /// \brief Load ALP metadata from an input buffer + /// + /// \return the loaded metadata, or Status::Invalid if the buffer is too small + static Result<AlpEncodedVectorInfo> Load(arrow::util::span<const uint8_t> input_buffer); + + /// \brief Get serialized size of the ALP metadata + static int64_t GetStoredSize() { return kStoredSize; } + + /// \brief Get exponent and factor as a combined struct + AlpExponentAndFactor GetExponentAndFactor() const { + return AlpExponentAndFactor{exponent_, factor_}; + } + + bool operator==(const AlpEncodedVectorInfo& other) const { + return exponent_ == other.exponent_ && factor_ == other.factor_ && + num_exceptions_ == other.num_exceptions_; + } + + bool operator!=(const AlpEncodedVectorInfo& other) const { return !(*this == other); } + + private: + uint8_t exponent_ = 0; + uint8_t factor_ = 0; + int16_t num_exceptions_ = 0; +}; + +// ---------------------------------------------------------------------- +// AlpEncodedForVectorInfo (templated, FOR integer encoding metadata) + +/// \brief FOR (Frame of Reference) encoding metadata for an encoded vector +/// +/// Contains the metadata specific to FOR bit-packing integer encoding: +/// - frame_of_reference: minimum value subtracted from all encoded integers +/// - bit_width: number of bits used to pack each delta value +/// +/// This struct is templated because frame_of_reference size depends on T: +/// - float: uint32_t frame_of_reference (4 bytes) +/// - double: uint64_t frame_of_reference (8 bytes) +/// +/// Serialization format for float (5 bytes): +/// +/// +------------------------------------------+ +/// | AlpEncodedForVectorInfo<float> (5B) | +/// +------------------------------------------+ +/// | Offset | Field | Size | +/// +---------+---------------------+----------+ +/// | 0 | frame_of_reference | 4 bytes | +/// | 4 | bit_width (uint8_t)| 1 byte | +/// +------------------------------------------+ +/// +/// Serialization format for double (9 bytes): +/// +/// +------------------------------------------+ +/// | AlpEncodedForVectorInfo<double> (9B) | +/// +------------------------------------------+ +/// | Offset | Field | Size | +/// +---------+---------------------+----------+ +/// | 0 | frame_of_reference | 8 bytes | +/// | 8 | bit_width (uint8_t)| 1 byte | +/// +------------------------------------------+ +/// +/// \tparam T the floating point type (float or double) +template <typename T> +class AlpEncodedForVectorInfo { + static_assert(std::is_same_v<T, float> || std::is_same_v<T, double>, + "AlpEncodedForVectorInfo only supports float and double"); + + public: + /// Use uint32_t for float, uint64_t for double (matches encoded integer size) + using ExactType = typename AlpTypedConstants<T>::FloatingToExact; + + AlpEncodedForVectorInfo() = default; + AlpEncodedForVectorInfo(ExactType frame_of_reference, uint8_t bit_width) + : frame_of_reference_(frame_of_reference), bit_width_(bit_width) {} + + ExactType frame_of_reference() const { return frame_of_reference_; } + uint8_t bit_width() const { return bit_width_; } + + void set_frame_of_reference(ExactType frame_of_reference) { + frame_of_reference_ = frame_of_reference; + } + void set_bit_width(uint8_t bit_width) { bit_width_ = bit_width; } + + /// Size of the serialized portion (5 bytes for float, 9 for double) + static constexpr int64_t kStoredSize = sizeof(ExactType) + 1; + + /// \brief Compute the bitpacked size in bytes from num_elements and bit_width + /// + /// \param[in] num_elements number of elements in this vector + /// \param[in] bw bits per element + /// \return the size in bytes of the bitpacked data + static int64_t GetBitPackedSize(int32_t num_elements, uint8_t bw) { Review Comment: The hand-rolled helper is gone rather than relocated — both call sites use `std::bit_width` directly now, so there's nothing left to host. -- 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]
