[jira] [Updated] (SPARK-59696) Skip the redundant second modulo in integral MathUtils.pmod for positive divisors

["Dongjoon Hyun (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/SPARK-59696?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Dongjoon Hyun updated SPARK-59696:
----------------------------------
    Affects Version/s: 4.4.0
                           (was: 4.1.0)

> 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.4.0
>            Reporter: David Mollitor
>            Assignee: David Mollitor
>            Priority: Minor
>              Labels: pull-request-available
>             Fix For: 4.4.0
>
>
> 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: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org