xiaoxuandev commented on code in PR #3397: URL: https://github.com/apache/parquet-java/pull/3397#discussion_r4289000466
########## parquet-column/src/main/java/org/apache/parquet/column/values/alp/AlpCodec.java: ########## @@ -0,0 +1,394 @@ +/* + * 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. + */ +package org.apache.parquet.column.values.alp; + +import static org.apache.parquet.column.values.alp.AlpConstants.DOUBLE_MAX_EXPONENT; +import static org.apache.parquet.column.values.alp.AlpConstants.FLOAT_MAX_EXPONENT; + +import org.apache.parquet.bytes.BytesUtils; + +/** + * Core ALP (Adaptive Lossless floating-Point) encoding and decoding logic. + * + * <p>ALP works by converting floating-point values to integers using decimal scaling, + * then applying Frame of Reference encoding and bit-packing. + * Values that cannot be losslessly converted are stored as exceptions. + * + * <p>Encoding formula: encoded = fastRound(value * POW10[e] * POW10_NEGATIVE[f]) + * <p>Decoding formula: value = encoded * POW10[f] * POW10_NEGATIVE[e] + * + * <p>The order of operations is critical for IEEE 754 correctness. Both formulas must + * be evaluated as single expressions — storing the intermediate multiplication result + * in a variable before the second multiply changes IEEE 754 rounding and produces extra + * exceptions. Likewise, scaling uses multiply-by-reciprocal (via POW10_NEGATIVE) rather than + * division: this reproduces the exact IEEE 754 rounding of the ALP reference algorithm, so the + * encoded integers — and therefore which values become exceptions and the resulting bytes — are + * identical across implementations. It is about cross-implementation determinism, not any one + * language. + * + * <p>Exception conditions: + * <ul> + * <li>NaN values</li> + * <li>Infinity values</li> + * <li>Negative zero (-0.0)</li> + * <li>Out of integer range</li> + * <li>Round-trip failure (decode(encode(v)) != v)</li> + * </ul> + */ +final class AlpCodec { + + // Magic numbers for the fast-rounding trick (see ALP paper, Section 3.2) + static final float MAGIC_FLOAT = 12_582_912.0f; // 2^22 + 2^23 + static final double MAGIC_DOUBLE = 6_755_399_441_055_744.0; // 2^51 + 2^52 + + // POWERS_OF_TEN: positive powers used for scaling up during encode/decode. + // Encode: fastRound(value * POW10[e] * POW10_NEGATIVE[f]) + // Decode: encoded * POW10[f] * POW10_NEGATIVE[e] + static final float[] FLOAT_POW10 = {1e0f, 1e1f, 1e2f, 1e3f, 1e4f, 1e5f, 1e6f, 1e7f, 1e8f, 1e9f, 1e10f}; + + static final double[] DOUBLE_POW10 = { + 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18 + }; + + // NEGATIVE_POWERS_OF_TEN: reciprocals used for scaling down (multiply-by-reciprocal). + // Multiplying by a precomputed reciprocal instead of dividing keeps the rounding bit-for-bit + // identical to the ALP reference implementation, so encoded values interop across implementations. + static final float[] FLOAT_POW10_NEGATIVE = { + 1e0f, 1e-1f, 1e-2f, 1e-3f, 1e-4f, 1e-5f, 1e-6f, 1e-7f, 1e-8f, 1e-9f, 1e-10f + }; + + static final double[] DOUBLE_POW10_NEGATIVE = { + 1e0, 1e-1, 1e-2, 1e-3, 1e-4, 1e-5, 1e-6, 1e-7, 1e-8, 1e-9, 1e-10, 1e-11, 1e-12, 1e-13, 1e-14, 1e-15, 1e-16, + 1e-17, 1e-18 + }; + + static final int FLOAT_NEGATIVE_ZERO_BITS = 0x80000000; + static final long DOUBLE_NEGATIVE_ZERO_BITS = 0x8000000000000000L; + + private static final double ENCODING_UPPER_LIMIT = 9223372036854774784.0; + private static final double ENCODING_LOWER_LIMIT = -9223372036854774784.0; + private static final float FLOAT_ENCODING_UPPER_LIMIT = 2147483520.0f; + private static final float FLOAT_ENCODING_LOWER_LIMIT = -2147483520.0f; + + private AlpCodec() { + // Utility class + } + + /** NaN, Inf, and -0.0 can never be encoded regardless of exponent/factor. */ + static boolean isIntrinsicFloatException(float value) { + if (Float.isNaN(value)) { + return true; + } + if (Float.isInfinite(value)) { + return true; + } + return Float.floatToRawIntBits(value) == FLOAT_NEGATIVE_ZERO_BITS; + } + + /** + * Encodes {@code value} and reports whether it is an exception, doing the scaling and rounding + * once and leaving the outcome in {@code out}. + * + * <p>Callers that need both the flag and the encoded value should use this rather than + * {@link #isFloatException} followed by {@link #encodeFloat}: the exception check has to encode + * the value to test the round trip, so the pair encodes twice. The scaled intermediate is reused + * here too, so the two multiplies are also only done once. The expression and its order match + * {@link #encodeFloat} exactly, which matters for cross-implementation bit compatibility. + */ + static void tryEncodeFloat(float value, int exponent, int factor, EncodeResult out) { + if (isIntrinsicFloatException(value)) { + out.isException = true; + return; + } + // Check before rounding: overflow or non-finite after scaling + float scaled = value * FLOAT_POW10[exponent] * FLOAT_POW10_NEGATIVE[factor]; + if (!Float.isFinite(scaled) || scaled > FLOAT_ENCODING_UPPER_LIMIT || scaled < FLOAT_ENCODING_LOWER_LIMIT) { + out.isException = true; + return; + } + int encoded = fastRoundFloat(scaled); + float decoded = decodeFloat(encoded, exponent, factor); + if (Float.floatToRawIntBits(value) != Float.floatToRawIntBits(decoded)) { + out.isException = true; + return; + } + out.encoded = encoded; + out.isException = false; + } + + /** + * Full exception check for a given (exponent, factor): intrinsic cases plus round-trip failure. + * Prefer {@link #tryEncodeFloat} when the encoded value is wanted as well. + */ + static boolean isFloatException(float value, int exponent, int factor) { + EncodeResult result = new EncodeResult(); + tryEncodeFloat(value, exponent, factor, result); + return result.isException; + } + + /** Round float to nearest integer using magic-number trick with sign branching. */ + static int fastRoundFloat(float value) { + if (value >= 0) { + return (int) ((value + MAGIC_FLOAT) - MAGIC_FLOAT); + } else { + return (int) ((value - MAGIC_FLOAT) + MAGIC_FLOAT); + } + } + + static int encodeFloat(float value, int exponent, int factor) { + return fastRoundFloat(value * FLOAT_POW10[exponent] * FLOAT_POW10_NEGATIVE[factor]); + } + + static float decodeFloat(int encoded, int exponent, int factor) { + return encoded * FLOAT_POW10[factor] * FLOAT_POW10_NEGATIVE[exponent]; + } + + /** NaN, Inf, and -0.0 can never be encoded regardless of exponent/factor. */ + static boolean isIntrinsicDoubleException(double value) { + if (Double.isNaN(value)) { + return true; + } + if (Double.isInfinite(value)) { + return true; + } + return Double.doubleToRawLongBits(value) == DOUBLE_NEGATIVE_ZERO_BITS; + } + + /** + * Encodes {@code value} and reports whether it is an exception, doing the scaling and rounding + * once and leaving the outcome in {@code out}. See {@link #tryEncodeFloat} for why this exists. + */ + static void tryEncodeDouble(double value, int exponent, int factor, EncodeResult out) { + if (isIntrinsicDoubleException(value)) { + out.isException = true; + return; + } + // Check before rounding: overflow or non-finite after scaling + double scaled = value * DOUBLE_POW10[exponent] * DOUBLE_POW10_NEGATIVE[factor]; + if (!Double.isFinite(scaled) || scaled > ENCODING_UPPER_LIMIT || scaled < ENCODING_LOWER_LIMIT) { + out.isException = true; + return; + } + long encoded = fastRoundDouble(scaled); + double decoded = decodeDouble(encoded, exponent, factor); + if (Double.doubleToRawLongBits(value) != Double.doubleToRawLongBits(decoded)) { + out.isException = true; + return; + } + out.encoded = encoded; + out.isException = false; + } + + /** + * Full exception check for a given (exponent, factor): intrinsic cases plus round-trip failure. + * Prefer {@link #tryEncodeDouble} when the encoded value is wanted as well. + */ + static boolean isDoubleException(double value, int exponent, int factor) { + EncodeResult result = new EncodeResult(); + tryEncodeDouble(value, exponent, factor, result); + return result.isException; + } + + /** Round double to nearest integer using magic-number trick with sign branching. */ + static long fastRoundDouble(double value) { + if (value >= 0) { + return (long) ((value + MAGIC_DOUBLE) - MAGIC_DOUBLE); + } else { + return (long) ((value - MAGIC_DOUBLE) + MAGIC_DOUBLE); + } + } + + static long encodeDouble(double value, int exponent, int factor) { + return fastRoundDouble(value * DOUBLE_POW10[exponent] * DOUBLE_POW10_NEGATIVE[factor]); + } + + static double decodeDouble(long encoded, int exponent, int factor) { + return encoded * DOUBLE_POW10[factor] * DOUBLE_POW10_NEGATIVE[exponent]; + } + + /** + * Outcome of a single {@link #tryEncodeFloat} or {@link #tryEncodeDouble} call. Mutable and + * meant to be reused by the caller so the per-value hot path allocates nothing; an Optional or a + * freshly allocated result here would box on every value. Not thread safe, so each writer keeps + * its own. + */ + static final class EncodeResult { + /** The encoded value, meaningful only when {@link #isException} is false. */ + long encoded; + + boolean isException; + } + + public static class EncodingParams { + final int exponent; + final int factor; + final int numExceptions; + + EncodingParams(int exponent, int factor, int numExceptions) { + this.exponent = exponent; + this.factor = factor; + this.numExceptions = numExceptions; + } + } + + // Index positions within an (exponent, factor) pair array. + private static final int E = 0; + private static final int F = 1; + + // All valid (exponent, factor) pairs for the full search, precomputed in nested-loop order + // (e ascending, then f ascending) so the tie-break and early-exit behave exactly like an inline + // double loop. Reused across every vector to avoid per-call allocation. + private static final int[][] ALL_VALID_FLOAT_PAIRS = buildAllPairs(FLOAT_MAX_EXPONENT); + private static final int[][] ALL_VALID_DOUBLE_PAIRS = buildAllPairs(DOUBLE_MAX_EXPONENT); + + private static int[][] buildAllPairs(int maxExponent) { + int count = (maxExponent + 1) * (maxExponent + 2) / 2; + int[][] pairs = new int[count][]; + int idx = 0; + for (int e = 0; e <= maxExponent; e++) { + for (int f = 0; f <= e; f++) { + pairs[idx++] = new int[] {e, f}; + } + } + return pairs; + } + + /** Try all (exponent, factor) combos and pick the one with the smallest estimated compressed size. */ + static EncodingParams findBestFloatParams(float[] values, int offset, int length) { + return pickBestFloat(values, offset, length, ALL_VALID_FLOAT_PAIRS); + } + + /** Same as findBestFloatParams but only tries the cached preset combos. */ + static EncodingParams findBestFloatParamsWithPresets(float[] values, int offset, int length, int[][] presets) { + return pickBestFloat(values, offset, length, presets); + } + + /** + * Scores each (exponent, factor) pair by estimated compressed size and returns the best. + * + * <p>Estimated size (in bits) = {@code length * bitWidth + exceptions * (Float.SIZE + Short.SIZE)}, + * where bitWidth is the number of bits needed to represent the signed range (max - min) of + * non-exception encoded values after frame-of-reference subtraction, matching the writer's FOR + * packing. This produces better compression ratios than minimizing exception count alone. Ties in + * size are broken toward the higher exponent, then the higher factor. The first pair (in {@code + * pairs} order) that encodes every value into a single FOR value with zero exceptions wins + * outright. When no pair yields any non-exception values, {@code pairs[0]} is returned. + */ + private static EncodingParams pickBestFloat(float[] values, int offset, int length, int[][] pairs) { + int bestExponent = pairs[0][E]; + int bestFactor = pairs[0][F]; + int bestExceptions = length; + long bestEstimatedSize = Long.MAX_VALUE; + + // One reusable result for the whole search: every value below is encoded exactly once. + EncodeResult result = new EncodeResult(); + for (int[] pair : pairs) { + int e = pair[E]; + int f = pair[F]; + int exceptions = 0; + int minEncoded = Integer.MAX_VALUE; + int maxEncoded = Integer.MIN_VALUE; + for (int i = 0; i < length; i++) { + tryEncodeFloat(values[offset + i], e, f, result); + if (result.isException) { + exceptions++; + } else { + int encoded = (int) result.encoded; + if (encoded < minEncoded) minEncoded = encoded; + if (encoded > maxEncoded) maxEncoded = encoded; + } + } + int nonExceptions = length - exceptions; + if (nonExceptions == 0) continue; + // Signed subtraction gives the true FOR span; getWidthFromMaxLong yields the correct + // unsigned bit width, and an overflowing large range is penalized with 64 bits. This matches + // the writer's FOR packing. + long delta = (nonExceptions < 2) ? 0 : ((long) maxEncoded - (long) minEncoded); + int bitsPerValue = BytesUtils.getWidthFromMaxLong(delta); + long estimatedSize = (long) length * bitsPerValue + (long) exceptions * (Float.SIZE + Short.SIZE); + if (estimatedSize < bestEstimatedSize + || (estimatedSize == bestEstimatedSize + && (e > bestExponent || (e == bestExponent && f > bestFactor)))) { + bestEstimatedSize = estimatedSize; + bestExponent = e; + bestFactor = f; + bestExceptions = exceptions; + if (bestExceptions == 0 && bitsPerValue == 0) { + return new EncodingParams(bestExponent, bestFactor, 0); + } + } + } + return new EncodingParams(bestExponent, bestFactor, bestExceptions); + } + + /** Try all (exponent, factor) combos and pick the one with the smallest estimated compressed size. */ + static EncodingParams findBestDoubleParams(double[] values, int offset, int length) { + return pickBestDouble(values, offset, length, ALL_VALID_DOUBLE_PAIRS); + } + + /** Same as findBestDoubleParams but only tries the cached preset combos. */ + static EncodingParams findBestDoubleParamsWithPresets(double[] values, int offset, int length, int[][] presets) { + return pickBestDouble(values, offset, length, presets); + } + + /** Double counterpart to {@link #pickBestFloat}; see it for the scoring and tie-break rules. */ + private static EncodingParams pickBestDouble(double[] values, int offset, int length, int[][] pairs) { + int bestExponent = pairs[0][E]; + int bestFactor = pairs[0][F]; + int bestExceptions = length; + long bestEstimatedSize = Long.MAX_VALUE; + + // One reusable result for the whole search: every value below is encoded exactly once. + EncodeResult result = new EncodeResult(); + for (int[] pair : pairs) { + int e = pair[E]; + int f = pair[F]; + int exceptions = 0; + long minEncoded = Long.MAX_VALUE; + long maxEncoded = Long.MIN_VALUE; + for (int i = 0; i < length; i++) { + tryEncodeDouble(values[offset + i], e, f, result); Review Comment: Not blocking, and fine as a follow-up given how much this PR has already been through. I was curious what the parameter search costs, so I timed `DoubleAlpValuesWriter` on its own (1M doubles, same data shape as the benchmark, 20480-value pages): about 70 ns/value vs ~7 ns/value for `PlainValuesWriter`. Most of that looks like this loop, since each candidate pair encodes the full vector. The spec's Parameter Selection section describes sampling as an option (256 values/vector) and the reference implementation uses 32; trying a strided sample here brought it to roughly 24 ns and 8 ns, with byte-identical output on the decimal data, and the result still decodes bit-exactly through the reader. One thing I noticed while trying it: on random doubles the sampled version produced ~27% larger output, because a sample with a single encodable value scores bitWidth 0 while the full vector then needs ~60 bits. So if you go this way, the mostly-exceptions case probably wants special handling. Sharing in case it's useful. -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
