[
https://issues.apache.org/jira/browse/SPARK-59696?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
David Mollitor updated SPARK-59696:
-----------------------------------
Summary: Skip the redundant second modulo in integral MathUtils.pmod for
positive divisors (was: Remove redundant second modulo in integral
MathUtils.pmod)
> Skip the redundant second modulo in integral MathUtils.pmod for positive
> divisors
> ---------------------------------------------------------------------------------
>
> 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
> Priority: Minor
> Labels: pull-request-available
>
> 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]
