David Mollitor created SPARK-59696:
--------------------------------------
Summary: Remove redundant second modulo in integral MathUtils.pmod
Key: SPARK-59696
URL: https://issues.apache.org/jira/browse/SPARK-59696
Project: Spark
Issue Type: Improvement
Components: SQL
Affects Versions: 4.1.0
Reporter: David Mollitor
h3. Problem
The integral {{MathUtils.pmod}} overloads ({{Int}}, {{Long}}, {{Byte}},
{{Short}}) compute the positive remainder as:
{code:scala}
val r = a % n
if (r < 0) (r + n) % n else r
{code}
The trailing {{% n}} is redundant _only when the divisor {{n > 0}}_. Since {{a
% n}} has magnitude strictly less than |n|, for {{r < 0}} and {{n > 0}} the
shifted value {{r + n}} already lies in {{[0, n)}} and the second modulo is a
no-op. For {{n < 0}}, {{r + n}} can fall below {{n}} and still needs reducing,
so the {{% n}} must be kept there.
h3. Change
{{MathUtils.pmod}} backs the {{pmod}} SQL function and the per-row partition-id
expression of {{HashPartitioning}} ({{Pmod(Murmur3Hash(...), numPartitions)}}),
so it runs once per row on the map side of every hash-partitioned shuffle --
always with a positive divisor ({{numPartitions}}). Removing the redundant
modulo in that case takes an integer division off the hot path.
The {{Float}}/{{Double}} overloads are left unchanged on purpose:
floating-point rounding can round {{r + n}} up to exactly {{n}}, and the extra
{{% n}} folds that back to {{0}}, so there it is a real correctness guard
rather than a no-op.
h3. Benchmark
JMH microbenchmark of the three forms (16,384 {{pmod(int, int)}} calls per op,
JDK 17, JMH 1.37, 2 forks x 5 iterations, {{AverageTime}}):
||divisor n||OLD (r+n)%n||drop-all (rejected)||this change (guarded)||guarded
vs OLD||
|8 (n > 0)|81.05 us/op|25.26 us/op|25.28 us/op|approx 3.2x faster|
|200 (n > 0)|88.90 us/op|25.28 us/op|25.31 us/op|approx 3.5x faster|
|-200 (n < 0)|87.46 us/op|25.28 us/op (*)|87.10 us/op|unchanged (correct)|
For positive divisors the guarded form matches the unconditional drop (the {{if
(n > 0)}} test is free) and is about 3.2-3.5x faster than the original. For
negative divisors it correctly keeps the modulo, matching the original cost and
result. (*) the drop-all column at {{n < 0}} is fast only because it skips the
required modulo and returns the wrong, out-of-range value.
h3. Correctness
No user-facing change: the result is identical to released Spark for every
input, including negative divisors. {{pmod}} is only guaranteed non-negative
for a positive divisor; for a negative divisor it shares the sign of the
dividend ({{pmod(-3, -5) == -3}}), and that released behavior is preserved.
Verified by cross-checking the guarded form for exact equality with the
original against an exhaustive oracle: all {{byte}} and {{short}} {{(a, n)}}
pairs, and all 2^32 {{int}} dividends across positive and negative divisors,
with zero mismatches. New regression cases in {{ArithmeticExpressionSuite}}
cover the {{r < 0, n < 0}} path (e.g. {{pmod(-3, -5) == -3}}) that an
unconditional drop would break and that existing tests did not exercise.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
