This is an automated email from the ASF dual-hosted git repository.
dongjoon-hyun pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/master by this push:
new ff17f551c384 [SPARK-59696][SQL] Skip the redundant second modulo in
integral MathUtils.pmod for positive divisors
ff17f551c384 is described below
commit ff17f551c3847752bbd8e427b863aeaf4a1ec8ce
Author: david-mollitor-db <[email protected]>
AuthorDate: Wed Oct 7 08:52:12 2026 -0700
[SPARK-59696][SQL] Skip the redundant second modulo in integral
MathUtils.pmod for positive divisors
### What changes were proposed in this pull request?
For integral `MathUtils.pmod(a, n)` with `n > 0`, skip the redundant second
modulo in the released `r = a % n; if (r < 0) (r + n) % n else r`. For `n > 0`
the result is `Math.floorMod(a, n)`: a negative remainder only needs `n` added.
This PR computes it with a branchless sign fix-up:
```scala
def pmod(a: Int, n: Int): Int = {
val r = a % n
if (n > 0) r + (n & (r >> 31)) else if (r >= 0) r else (r + n) % n
}
// Long: the same with `r >> 63`.
```
`n < 0` keeps the original `(r + n) % n`. `Byte`/`Short` delegate to `Int`.
`Float`/`Double` are unchanged.
### Why are the changes needed?
`pmod` with a positive divisor is the common case (e.g. `HashPartitioning`
passes `numPartitions` for every row), and the second `% n` is a no-op there.
The fix-up is written out because `Math.floorMod` adjusts with a
data-dependent conditional, which C2 often keeps as a branch that mispredicts
on random-sign dividends. JMH 1.37, x86_64, 16,384 `pmod(int, int)` calls per
op over random-sign dividends, 3 forks x 10 iterations; us/op:
| divisor | JDK | released | `Math.floorMod` | this PR |
|---|---|---|---|---|
| JIT constant `200` | 17 | 20.5 | 31.9 (bimodal) | 14.9 |
| | 25 | 31.9 | 43.4 | 4.5 (*) |
| per-row `200` | 17 | 65.9 | 81.7 | 26.1 |
| | 25 | 70.7 | 40.6 | 26.2 |
| loop-invariant `200` | 17 | 89.0 | 42.2 | 26.1 |
| | 25 | 65.7 | 25.7 | 25.4 |
(*) Likely the benchmark loop vectorizing, which does not apply to per-row
evaluation such as `HashPartitioning`. JDK 21 and ARM were not measured.
Harness (JMH and exhaustive equivalence check):
https://gist.github.com/david-mollitor-db/1cc2fe01b478062efda9ec191efd0f51
### Does this PR introduce _any_ user-facing change?
No. Results are identical for every input.
### How was this patch tested?
New cases in `ArithmeticExpressionSuite` "pmod":
- `pmod(-7, 3)` via `testNumericDataTypes`, which exercises the integral `n
> 0` fast path (`Byte`/`Short` via `Int`, and `Long`);
- `pmod(-6, 3) == 0` (`Int`, `Long`): a zero remainder with a negative
dividend;
- a `Long` case whose remainder is below `-2^62`, so a wrong shift count or
narrowing to `Int` changes the result;
- `pmod(-1e-20, 1.0) == 0.0` (and the `Float` analogue), which needs the
float/double `% n`;
- negative-divisor cases, and two assertions characterizing the
pre-existing `Int`/`Long` `n < 0` wrap-around (SPARK-59934).
The integral bodies were also checked for exact equality with the released
ones: all `byte` and `short` pairs, all 2^32 `int` dividends for 26 divisors
(including `Int.MinValue` and `-1073741825`), and `long` edge values plus 4e8
random pairs.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Opus 4.8
This pull request and its description were written by Isaac.
Closes #58906 from david-mollitor-db/pmod-drop-redundant-modulo.
Authored-by: david-mollitor-db <[email protected]>
Signed-off-by: Dongjoon Hyun <[email protected]>
---
.../apache/spark/sql/catalyst/util/MathUtils.scala | 29 ++++++++++++----------
.../sql/catalyst/expressions/arithmetic.scala | 8 +++---
.../expressions/ArithmeticExpressionSuite.scala | 22 +++++++++++++++-
3 files changed, 41 insertions(+), 18 deletions(-)
diff --git
a/sql/api/src/main/scala/org/apache/spark/sql/catalyst/util/MathUtils.scala
b/sql/api/src/main/scala/org/apache/spark/sql/catalyst/util/MathUtils.scala
index e318a60ce99a..b829bcd57b40 100644
--- a/sql/api/src/main/scala/org/apache/spark/sql/catalyst/util/MathUtils.scala
+++ b/sql/api/src/main/scala/org/apache/spark/sql/catalyst/util/MathUtils.scala
@@ -89,29 +89,32 @@ object MathUtils {
def floorMod(a: Long, b: Long): Long = withOverflow(Math.floorMod(a, b))
- // Positive modulo (`pmod`): the remainder `a % n` adjusted to share the
sign of `n`.
- // Unlike `floorMod`, this matches the `pmod` SQL function /
`HashPartitioning` semantics.
- // Shared by `Pmod`'s eval and codegen paths so the two never diverge.
+ // Positive modulo (`pmod`): for `n > 0` the result lies in `[0, n)` (for
the float/double
+ // overloads, when both inputs are finite); for integral `n < 0` it takes
the sign of the
+ // dividend `a` (unlike `floorMod`, which takes the sign of `n`). Matches
the `pmod` SQL
+ // function and `HashPartitioning`, and is shared by `Pmod`'s eval and
codegen so the two never
+ // diverge.
+ //
+ // Integral `n > 0` computes `Math.floorMod(a, n)` with a branchless sign
fix-up instead of
+ // calling it, because `Math.floorMod` adjusts with a data-dependent
conditional (SPARK-59696).
+ // The `n < 0` path can silently wrap for `Int`/`Long` when `r + n`
overflows (large-magnitude
+ // negative `n`), e.g. `pmod(-1, Int.MinValue)` returns `Int.MaxValue`;
tracked by SPARK-59934.
+ // `Byte`/`Short` delegate to `Int` (too narrow for `r + n` to overflow);
the float/double
+ // overloads keep `% n` because `r + n` can round up to exactly `n`.
def pmod(a: Int, n: Int): Int = {
val r = a % n
- if (r < 0) (r + n) % n else r
+ if (n > 0) r + (n & (r >> 31)) else if (r >= 0) r else (r + n) % n
}
def pmod(a: Long, n: Long): Long = {
val r = a % n
- if (r < 0) (r + n) % n else r
+ if (n > 0) r + (n & (r >> 63)) else if (r >= 0) r else (r + n) % n
}
- def pmod(a: Byte, n: Byte): Byte = {
- val r = a % n
- if (r < 0) ((r + n) % n).toByte else r.toByte
- }
+ def pmod(a: Byte, n: Byte): Byte = pmod(a.toInt, n.toInt).toByte
- def pmod(a: Short, n: Short): Short = {
- val r = a % n
- if (r < 0) ((r + n) % n).toShort else r.toShort
- }
+ def pmod(a: Short, n: Short): Short = pmod(a.toInt, n.toInt).toShort
def pmod(a: Float, n: Float): Float = {
val r = a % n
diff --git
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/arithmetic.scala
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/arithmetic.scala
index d0d7507e3250..233879fe425c 100644
---
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/arithmetic.scala
+++
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/arithmetic.scala
@@ -1239,10 +1239,10 @@ case class Pmod(
|${ev.isNull} = ${ev.value} == null;
|""".stripMargin
- // The positive-modulo arithmetic is the same fixed algorithm for every
primitive numeric
- // type, so delegate to the shared MathUtils.pmod helper (also used by
the eval path) instead
- // of emitting the remainder/adjust block inline. byte/short are widened
to int by `%`, and
- // the matching MathUtils.pmod overload narrows the result back.
+ // The positive-modulo arithmetic has the same semantics for every
primitive numeric type,
+ // so delegate to the shared MathUtils.pmod helper (also used by the
eval path) instead of
+ // emitting the remainder/adjust block inline. The byte/short overloads
compute in int and
+ // narrow the result back.
case _ =>
s"${ev.value} = $mathUtils.pmod(${eval1.value}, ${eval2.value});"
}
diff --git
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/ArithmeticExpressionSuite.scala
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/ArithmeticExpressionSuite.scala
index f8cdf825bc4c..13847fee8f44 100644
---
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/ArithmeticExpressionSuite.scala
+++
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/ArithmeticExpressionSuite.scala
@@ -565,6 +565,8 @@ class ArithmeticExpressionSuite extends SparkFunSuite with
ExpressionEvalHelper
val left = Literal(convert(7))
val right = Literal(convert(3))
checkEvaluation(Pmod(left, right), convert(1))
+ // Exercises the integral `n > 0` fast path (`Byte`/`Short` via `Int`,
and `Long`).
+ checkEvaluation(Pmod(Literal(convert(-7)), Literal(convert(3))),
convert(2))
checkEvaluation(Pmod(Literal.create(null, left.dataType), right), null)
checkEvaluation(Pmod(left, Literal.create(null, right.dataType)), null)
withSQLConf(SQLConf.ANSI_ENABLED.key -> "false") {
@@ -574,14 +576,32 @@ class ArithmeticExpressionSuite extends SparkFunSuite
with ExpressionEvalHelper
checkExceptionInExpression[ArithmeticException](
Pmod(left, Literal(convert(0))), "Remainder by zero")
}
+ // Negative divisor (n < 0): `pmod` is only guaranteed non-negative for
a positive divisor.
+ // These cases have negative dividends, so the expected values are <= 0
(released behavior).
+ // They guard the r < 0, n < 0 path where `r + n` still needs `% n` --
dropping it goes out
+ // of range (pmod(-3, -5) would be -8).
+ checkEvaluation(Pmod(Literal(convert(-3)), Literal(convert(-5))),
convert(-3))
+ checkEvaluation(Pmod(Literal(convert(-7)), Literal(convert(-3))),
convert(-1))
}
- checkEvaluation(Pmod(Literal(-7), Literal(3)), 2)
checkEvaluation(Pmod(Literal(7.2D), Literal(4.1D)), 3.1000000000000005)
+ checkEvaluation(Pmod(Literal(-1e-20D), Literal(1.0D)), 0.0D)
+ checkEvaluation(Pmod(Literal(-1e-10f), Literal(1.0f)), 0.0f)
checkEvaluation(Pmod(Literal(Decimal(0.7)), Literal(Decimal(0.2))),
Decimal(0.1))
checkEvaluation(Pmod(Literal(2L), Literal(Long.MaxValue)), 2L)
+ checkEvaluation(Pmod(Literal(-6), Literal(3)), 0)
+ checkEvaluation(Pmod(Literal(-6L), Literal(3L)), 0L)
+ // The remainder is below -2^62, so a wrong shift count or narrowing to
Int changes it.
+ checkEvaluation(
+ Pmod(Literal(Long.MinValue / 2 - 1), Literal(Long.MaxValue)),
4611686018427387902L)
checkEvaluation(Pmod(positiveShort, negativeShort), positiveShort.toShort)
checkEvaluation(Pmod(positiveInt, negativeInt), positiveInt)
checkEvaluation(Pmod(positiveLong, negativeLong), positiveLong)
+ // Pre-existing Int/Long wrap-around, pinned so the released results stay
exact: the retained
+ // `(r + n) % n` overflows for n < -2^30 / n < -2^62. Without overflow `(r
+ n) % n == r`, so
+ // these are the only inputs that tell the two apart. These assertions
characterize the current
+ // released behavior; fixing the wrap-around is tracked by SPARK-59934.
+ checkEvaluation(Pmod(Literal(-1), Literal(Int.MinValue)), Int.MaxValue)
+ checkEvaluation(Pmod(Literal(-1L), Literal(Long.MinValue)), Long.MaxValue)
Seq("true", "false").foreach { failOnError =>
withSQLConf(SQLConf.ANSI_ENABLED.key -> failOnError) {
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
