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]

Reply via email to