dajiaohuang commented on code in PR #20059:
URL: https://github.com/apache/pinot/pull/20059#discussion_r4639540107
##########
pinot-common/src/main/java/org/apache/pinot/common/function/scalar/ArrayFunctions.java:
##########
@@ -642,21 +643,29 @@ private static int generatedArrayLength(long start, long
end, long inc) {
}
/// Length of the `float` sequence `start, start + inc, ...` bounded by
`end`, inclusive. The step count is computed
- /// in `float` arithmetic, as the single-stage engine always did.
+ /// in double precision; the rounding tolerance is based on the ULPs of the
original float inputs.
private static int generatedArrayLength(float start, float end, float inc) {
checkFloatingPointArguments(start, end, inc);
- // TODO: decimal steps such as 0.1 are not exact in binary, so this can
drop the end; see apache/pinot#19814
- return checkGeneratedArrayLength((long) ((end - start) / inc + 1) - 1);
+ // Use double precision for the step count and compare its error with ULPs
of the original float inputs.
+ double steps = (end - start) / inc;
+ return generatedFloatingArrayLength(steps, Math.ulp(start), Math.ulp(end),
Math.ulp(inc), inc);
}
/// Length of the `double` sequence `start, start + inc, ...` bounded by
`end`, inclusive.
private static int generatedArrayLength(double start, double end, double
inc) {
checkFloatingPointArguments(start, end, inc);
- // Adding 1 before truncating matches the length the single-stage engine
always computed. It absorbs part of the
- // rounding error of decimal steps, so 0.1 to 0.3 by 0.1 keeps its end.
- // TODO: it does not absorb all of it, so 0.1 to 0.7 by 0.1 still drops
its end; see apache/pinot#19814
- // A span too wide for a long saturates the cast at Long.MAX_VALUE, which
the length check below rejects.
- return checkGeneratedArrayLength((long) ((end - start) / inc + 1) - 1);
+ return generatedFloatingArrayLength((end - start) / inc, Math.ulp(start),
Math.ulp(end), Math.ulp(inc), inc);
+ }
+
+ /// Snaps a floating-point step count to an integer only when the distance
is within the rounding error of the input
+ /// bounds and increments. Otherwise, truncates toward the last step that
does not pass the end.
+ private static int generatedFloatingArrayLength(double steps, double
startUlp, double endUlp, double incUlp,
+ double inc) {
+ double nearestSteps = Math.rint(steps);
+ double roundingError = 2 * (startUlp + endUlp + Math.abs(nearestSteps) *
incUlp) / Math.abs(inc);
+ double fullSteps = Math.abs(steps - nearestSteps) <= roundingError ?
nearestSteps : Math.floor(steps);
Review Comment:
Fixed in fa8379795e.
The overshoot is gone because the step count is no longer decided by a
tolerance over the quotient. The tolerance was the bug: it grew with the
magnitude of the bounds, so once a bound was spaced far wider than the
increment it could reach or pass 0.5 of a step. For your repro the quotient is
7.7257 and the tolerance about 0.347, so `rint` snapped to 8 and appended
91322.48, three float ulps past the end at 91322.45.
Widening or tightening the tolerance cannot work, because a quotient that
close to a whole step is genuinely ambiguous. 5.9999 stands both for `0.1` to
`0.7` by `0.1`, which should keep its end, and for an end that really does fall
between steps. So the ambiguity is resolved instead. In order:
1. If the element the sequence would actually generate at `rint(steps)`
equals `end` in the element type, that is the count. This uses the property you
pointed at: the bounds can tell apart values the quotient cannot. It is also
what keeps `163443.44f` to `163909.03f` by `9.7f`, where the quotient is
47.9994 but element 48 is exactly the bound.
2. Otherwise, if the quotient is farther from a whole step than the rounding
error bound, its floor is the count with no further arithmetic.
3. Otherwise the count is the floor of the quotient of the decimal values
the arguments denote, which is what a decimal step means.
Your three repros, all now rejected:
- `generateFloatArray(91321.76f, 91322.45f, 0.09f)` -> 8 elements, last
91322.39f.
- `generateFloatArray(1000000f, 1000000.75f, 1f)` -> `[1000000]`.
- `generateDoubleArray(1e15, 1e15 + 1.5, 1d)` -> `[1e15, 1e15 + 1]`.
Regression cases for both types are added. Beyond the suite I fuzzed 1.5M
float and 1.1M double ranges with end generated as `start + n * inc`, checking
the last element never passes the end and the end is never dropped: no
violations in either type. I also fuzzed 800k decimal-step ranges per type
against the exact decimal count: no drift. Two things that remain and that I
would rather flag than hide. A step that is not representable at the magnitude
of the bounds, such as 0.0141 at 3.4e5 where one ulp is 0.0151, has no
well-defined count; the base, the head and this revision all differ there, and
the count now follows the generated elements. And a range whose only in-bounds
element repeats the one before it still ends on the earlier one, as the base
did.
##########
pinot-common/src/main/java/org/apache/pinot/common/function/scalar/ArrayFunctions.java:
##########
@@ -642,21 +643,29 @@ private static int generatedArrayLength(long start, long
end, long inc) {
}
/// Length of the `float` sequence `start, start + inc, ...` bounded by
`end`, inclusive. The step count is computed
- /// in `float` arithmetic, as the single-stage engine always did.
+ /// in double precision; the rounding tolerance is based on the ULPs of the
original float inputs.
private static int generatedArrayLength(float start, float end, float inc) {
checkFloatingPointArguments(start, end, inc);
- // TODO: decimal steps such as 0.1 are not exact in binary, so this can
drop the end; see apache/pinot#19814
- return checkGeneratedArrayLength((long) ((end - start) / inc + 1) - 1);
+ // Use double precision for the step count and compare its error with ULPs
of the original float inputs.
+ double steps = (end - start) / inc;
Review Comment:
Moot in fa8379795e, and thank you for catching it.
The float path now promotes an operand before the subtraction, so both the
subtraction and the division happen in double precision:
```java
double steps = ((double) end - start) / inc;
```
The Javadoc no longer claims anything about the arithmetic the old code
used, since the whole computation is restructured. It now describes what the
function guarantees instead. Your point that the mismatch was introduced by the
new documentation rather than by the old code was correct, and the fix removes
the mismatch rather than rewording around it.
##########
pinot-common/src/main/java/org/apache/pinot/common/function/scalar/ArrayFunctions.java:
##########
@@ -642,21 +643,29 @@ private static int generatedArrayLength(long start, long
end, long inc) {
}
/// Length of the `float` sequence `start, start + inc, ...` bounded by
`end`, inclusive. The step count is computed
- /// in `float` arithmetic, as the single-stage engine always did.
+ /// in double precision; the rounding tolerance is based on the ULPs of the
original float inputs.
private static int generatedArrayLength(float start, float end, float inc) {
checkFloatingPointArguments(start, end, inc);
- // TODO: decimal steps such as 0.1 are not exact in binary, so this can
drop the end; see apache/pinot#19814
- return checkGeneratedArrayLength((long) ((end - start) / inc + 1) - 1);
+ // Use double precision for the step count and compare its error with ULPs
of the original float inputs.
+ double steps = (end - start) / inc;
+ return generatedFloatingArrayLength(steps, Math.ulp(start), Math.ulp(end),
Math.ulp(inc), inc);
}
/// Length of the `double` sequence `start, start + inc, ...` bounded by
`end`, inclusive.
private static int generatedArrayLength(double start, double end, double
inc) {
checkFloatingPointArguments(start, end, inc);
- // Adding 1 before truncating matches the length the single-stage engine
always computed. It absorbs part of the
- // rounding error of decimal steps, so 0.1 to 0.3 by 0.1 keeps its end.
- // TODO: it does not absorb all of it, so 0.1 to 0.7 by 0.1 still drops
its end; see apache/pinot#19814
- // A span too wide for a long saturates the cast at Long.MAX_VALUE, which
the length check below rejects.
- return checkGeneratedArrayLength((long) ((end - start) / inc + 1) - 1);
+ return generatedFloatingArrayLength((end - start) / inc, Math.ulp(start),
Math.ulp(end), Math.ulp(inc), inc);
+ }
+
+ /// Snaps a floating-point step count to an integer only when the distance
is within the rounding error of the input
+ /// bounds and increments. Otherwise, truncates toward the last step that
does not pass the end.
+ private static int generatedFloatingArrayLength(double steps, double
startUlp, double endUlp, double incUlp,
+ double inc) {
+ double nearestSteps = Math.rint(steps);
+ double roundingError = 2 * (startUlp + endUlp + Math.abs(nearestSteps) *
incUlp) / Math.abs(inc);
+ double fullSteps = Math.abs(steps - nearestSteps) <= roundingError ?
nearestSteps : Math.floor(steps);
Review Comment:
Fixed in fa8379795e.
You were right that no tolerance over the quotient can settle this, for
exactly the reason you gave: the tolerance grows with the magnitude of the
bounds, so any value wide enough to keep the end of `0.1` to `0.7` by `0.1`
also turns a large genuine fractional step count into a whole one. Capping it
below 0.5 does not work either. At 5.9999 versus a cap of 0.4999 the decimal
case survives, but your `91321.76f` case has a tolerance of about 0.347 and a
distance of 0.274, so a cap between them only moves which ranges break.
So I took the first option you listed: check the element that will actually
be generated.
```java
if (Math.rint(steps) < MAX_GENERATED_ARRAY_LENGTH && start + (float)
Math.rint(steps) * inc == end) {
fullSteps = (long) Math.rint(steps);
}
```
The comparison is in the element type, so it uses exactly the values the
bounds can distinguish. If that does not settle it, and the quotient is farther
from a whole step than the rounding error bound, the floor is the count. Only
inside the remaining window is the count taken from the decimal values the
arguments denote.
`generateFloatArray(91321.76f, 91322.45f, 0.09f)` now returns 8 elements
ending 91322.39f, `generateFloatArray(1000000f, 1000000.75f, 1f)` returns
`[1000000]`, and `generateDoubleArray(1e15, 1e15 + 1.5, 1d)` returns `[1e15,
1e15 + 1]`.
One case worth noting from the fuzzing, because it is what makes the element
check necessary rather than just tidier: `generateFloatArray(163443.44f,
163909.03f, 9.7f)` has a quotient of 47.9994, which looks exactly like a
between-step end, but element 48 is 163909.03f, exactly the bound. Flooring
drops an end that is genuinely in the range. The element check keeps it, so the
49-element result there and the 8-element result above come from the same rule.
##########
pinot-common/src/main/java/org/apache/pinot/common/function/scalar/ArrayFunctions.java:
##########
@@ -642,21 +643,29 @@ private static int generatedArrayLength(long start, long
end, long inc) {
}
/// Length of the `float` sequence `start, start + inc, ...` bounded by
`end`, inclusive. The step count is computed
- /// in `float` arithmetic, as the single-stage engine always did.
+ /// in double precision; the rounding tolerance is based on the ULPs of the
original float inputs.
private static int generatedArrayLength(float start, float end, float inc) {
checkFloatingPointArguments(start, end, inc);
- // TODO: decimal steps such as 0.1 are not exact in binary, so this can
drop the end; see apache/pinot#19814
- return checkGeneratedArrayLength((long) ((end - start) / inc + 1) - 1);
+ // Use double precision for the step count and compare its error with ULPs
of the original float inputs.
+ double steps = (end - start) / inc;
Review Comment:
Fixed in fa8379795e, in the float path only, which is where the mismatch was.
```java
double steps = ((double) end - start) / inc;
```
So the subtraction and the division both happen in double precision, and
your `0f, 0.1f, 0.3f` example no longer differs between the documented and
actual arithmetic.
The rest of the computation changed with it, so the claim is no longer just
about this one expression. The Javadoc now states the guarantee (a decimal step
runs to its end, a value genuinely between steps is never included) and the
inline comments describe which of the three branches applies, instead of
asserting an arithmetic detail that could drift from the code again.
--
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]