This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
The following commit(s) were added to refs/heads/master by this push:
new 5fcb66a1 Update remainderUnsigned and divideUnsigned
5fcb66a1 is described below
commit 5fcb66a1e4928b6d7299aacb5cca91f36134cfc2
Author: Alex Herbert <aherb...@apache.org>
AuthorDate: Sun Mar 3 14:52:26 2024 +0000
Update remainderUnsigned and divideUnsigned
Re-implement the methods from Hackers Delight 2.0.
Delegate to JDK method for integers.
Add notes that the JDK long method is fast from JDK 17 and an intrinsic
from JDK 19.
---
.../commons/numbers/core/ArithmeticUtils.java | 133 ++++++++++++---------
.../commons/numbers/core/ArithmeticUtilsTest.java | 18 +--
.../examples/jmh/core/ArithmeticPerformance.java | 37 ++++--
src/changes/changes.xml | 5 +-
4 files changed, 113 insertions(+), 80 deletions(-)
diff --git
a/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java
b/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java
index d34d7e2b..8ed56e0f 100644
---
a/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java
+++
b/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java
@@ -470,56 +470,70 @@ public final class ArithmeticUtils {
* Returns the unsigned remainder from dividing the first argument
* by the second where each argument and the result is interpreted
* as an unsigned value.
- * <p>This method does not use the {@code long} datatype.</p>
+ *
+ * <p>Implementation note
+ *
+ * <p>In v1.0 this method did not use the {@code long} datatype.
+ * Modern 64-bit processors make use of the {@code long} datatype
+ * faster than an algorithm using the {@code int} datatype. This method
+ * now delegates to {@link Integer#remainderUnsigned(int, int)}
+ * which uses {@code long} arithmetic; or from JDK 19 an intrinsic method.
*
* @param dividend the value to be divided
* @param divisor the value doing the dividing
* @return the unsigned remainder of the first argument divided by
* the second argument.
+ * @see Integer#remainderUnsigned(int, int)
*/
public static int remainderUnsigned(int dividend, int divisor) {
- if (divisor >= 0) {
- if (dividend >= 0) {
- return dividend % divisor;
- }
- // The implementation is a Java port of algorithm described in the
book
- // "Hacker's Delight" (section "Unsigned short division from
signed division").
- final int q = ((dividend >>> 1) / divisor) << 1;
- dividend -= q * divisor;
- if (dividend < 0 || dividend >= divisor) {
- dividend -= divisor;
- }
- return dividend;
- }
- return dividend >= 0 || dividend < divisor ? dividend : dividend -
divisor;
+ return Integer.remainderUnsigned(dividend, divisor);
}
/**
* Returns the unsigned remainder from dividing the first argument
* by the second where each argument and the result is interpreted
* as an unsigned value.
- * <p>This method does not use the {@code BigInteger} datatype.</p>
+ *
+ * <p>Implementation note
+ *
+ * <p>This method does not use the {@code BigInteger} datatype.
+ * The JDK implementation of {@link Long#remainderUnsigned(long, long)}
+ * uses {@code BigInteger} prior to JDK 17 and this method is 15-25x
faster.
+ * From JDK 17 onwards the JDK implementation is as fast; or from JDK 19
+ * even faster due to use of an intrinsic method.
*
* @param dividend the value to be divided
* @param divisor the value doing the dividing
* @return the unsigned remainder of the first argument divided by
* the second argument.
+ * @see Long#remainderUnsigned(long, long)
*/
public static long remainderUnsigned(long dividend, long divisor) {
- if (divisor >= 0L) {
- if (dividend >= 0L) {
- return dividend % divisor;
- }
- // The implementation is a Java port of algorithm described in the
book
- // "Hacker's Delight" (section "Unsigned short division from
signed division").
- final long q = ((dividend >>> 1) / divisor) << 1;
- dividend -= q * divisor;
- if (dividend < 0L || dividend >= divisor) {
- dividend -= divisor;
- }
- return dividend;
+ // Adapts the divideUnsigned method to compute the remainder.
+ if (divisor < 0) {
+ // Using unsigned compare:
+ // if dividend < divisor: return dividend
+ // else: return dividend - divisor
+
+ // Subtracting divisor using masking is more complex in this case
+ // and we use a condition
+ return dividend >= 0 || dividend < divisor ? dividend : dividend -
divisor;
+
}
- return dividend >= 0L || dividend < divisor ? dividend : dividend -
divisor;
+ // From Hacker's Delight 2.0, section 9.3
+ final long q = ((dividend >>> 1) / divisor) << 1;
+ final long r = dividend - q * divisor;
+ // unsigned r: 0 <= r < 2 * divisor
+ // if (r < divisor): r
+ // else: r - divisor
+
+ // The compare of unsigned r can be done using:
+ // return (r + Long.MIN_VALUE) < (divisor | Long.MIN_VALUE) ? r : r -
divisor
+
+ // Here we subtract divisor if (r - divisor) is positive, else the
result is r.
+ // This can be done by flipping the sign bit and
+ // creating a mask as -1 or 0 by signed shift.
+ return r - (divisor & (~(r - divisor) >> 63));
}
/**
@@ -531,28 +545,23 @@ public final class ArithmeticUtils {
* bit-wise identical if the two operands are regarded as both
* being signed or both being unsigned. Therefore separate {@code
* addUnsigned}, etc. methods are not provided.</p>
- * <p>This method does not use the {@code long} datatype.</p>
+ *
+ * <p>Implementation note
+ *
+ * <p>In v1.0 this method did not use the {@code long} datatype.
+ * Modern 64-bit processors make use of the {@code long} datatype
+ * faster than an algorithm using the {@code int} datatype. This method
+ * now delegates to {@link Integer#divideUnsigned(int, int)}
+ * which uses {@code long} arithmetic; or from JDK 19 an intrinsic method.
*
* @param dividend the value to be divided
* @param divisor the value doing the dividing
* @return the unsigned quotient of the first argument divided by
* the second argument
+ * @see Integer#divideUnsigned(int, int)
*/
public static int divideUnsigned(int dividend, int divisor) {
- if (divisor >= 0) {
- if (dividend >= 0) {
- return dividend / divisor;
- }
- // The implementation is a Java port of algorithm described in the
book
- // "Hacker's Delight" (section "Unsigned short division from
signed division").
- int q = ((dividend >>> 1) / divisor) << 1;
- dividend -= q * divisor;
- if (dividend < 0L || dividend >= divisor) {
- q++;
- }
- return q;
- }
- return dividend >= 0 || dividend < divisor ? 0 : 1;
+ return Integer.divideUnsigned(dividend, divisor);
}
/**
@@ -564,28 +573,36 @@ public final class ArithmeticUtils {
* bit-wise identical if the two operands are regarded as both
* being signed or both being unsigned. Therefore separate {@code
* addUnsigned}, etc. methods are not provided.</p>
- * <p>This method does not use the {@code BigInteger} datatype.</p>
+ *
+ * <p>Implementation note
+ *
+ * <p>This method does not use the {@code BigInteger} datatype.
+ * The JDK implementation of {@link Long#divideUnsigned(long, long)}
+ * uses {@code BigInteger} prior to JDK 17 and this method is 15-25x
faster.
+ * From JDK 17 onwards the JDK implementation is as fast; or from JDK 19
+ * even faster due to use of an intrinsic method.
*
* @param dividend the value to be divided
* @param divisor the value doing the dividing
* @return the unsigned quotient of the first argument divided by
* the second argument.
+ * @see Long#divideUnsigned(long, long)
*/
public static long divideUnsigned(long dividend, long divisor) {
- if (divisor >= 0L) {
- if (dividend >= 0L) {
- return dividend / divisor;
- }
- // The implementation is a Java port of algorithm described in the
book
- // "Hacker's Delight" (section "Unsigned short division from
signed division").
- long q = ((dividend >>> 1) / divisor) << 1;
- dividend -= q * divisor;
- if (dividend < 0L || dividend >= divisor) {
- q++;
- }
- return q;
+ // The implementation is a Java port of algorithm described in the book
+ // "Hacker's Delight 2.0" (section 9.3 "Unsigned short division from
signed division").
+ // Adapts 6-line predicate expressions program with (u >=) an unsigned
compare
+ // using the provided branchless variants.
+ if (divisor < 0) {
+ // line 1 branchless:
+ // q <- (dividend (u >=) divisor)
+ return (dividend & ~(dividend - divisor)) >>> 63;
}
- return dividend >= 0L || dividend < divisor ? 0L : 1L;
+ final long q = ((dividend >>> 1) / divisor) << 1;
+ final long r = dividend - q * divisor;
+ // line 5 branchless:
+ // q <- q + (r (u >=) divisor)
+ return q + ((r | ~(r - divisor)) >>> 63);
}
/**
diff --git
a/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/ArithmeticUtilsTest.java
b/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/ArithmeticUtilsTest.java
index 0b4aa797..3a3687b0 100644
---
a/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/ArithmeticUtilsTest.java
+++
b/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/ArithmeticUtilsTest.java
@@ -19,7 +19,7 @@ package org.apache.commons.numbers.core;
import java.util.Arrays;
import java.math.BigInteger;
import java.util.Collections;
-
+import java.util.concurrent.ThreadLocalRandom;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
@@ -492,12 +492,11 @@ class ArithmeticUtilsTest {
for (int j = 0; j < 20; j++) {
ints[i++] = j;
}
- for (int j = i - 1; j >= 0; j--) {
+ for (int j = i; --j >= 0;) {
ints[i++] = ints[j] > 0 ? -ints[j] : Integer.MIN_VALUE;
}
- java.util.Random r = new java.util.Random(System.nanoTime());
for (; i < ints.length;) {
- ints[i++] = r.nextInt();
+ ints[i++] = ThreadLocalRandom.current().nextInt();
}
return ints;
}
@@ -529,12 +528,11 @@ class ArithmeticUtilsTest {
for (int j = 0; j < 20; j++) {
longs[i++] = j;
}
- for (int j = i - 1; j >= 0; j--) {
+ for (int j = i; --j >= 0;) {
longs[i++] = longs[j] > 0L ? -longs[j] : Long.MIN_VALUE;
}
- java.util.Random r = new java.util.Random(System.nanoTime());
for (; i < longs.length;) {
- longs[i++] = r.nextLong();
+ longs[i++] = ThreadLocalRandom.current().nextLong();
}
return longs;
}
@@ -581,7 +579,8 @@ class ArithmeticUtilsTest {
() -> ArithmeticUtils.remainderUnsigned(dividend,
divisor)
);
} else {
-
Assertions.assertEquals(remainderUnsignedExpected(dividend, divisor),
ArithmeticUtils.remainderUnsigned(dividend, divisor));
+
Assertions.assertEquals(remainderUnsignedExpected(dividend, divisor),
ArithmeticUtils.remainderUnsigned(dividend, divisor),
+ () -> dividend + " % " + divisor);
}
}
}
@@ -605,7 +604,8 @@ class ArithmeticUtilsTest {
// Success.
}
} else {
-
Assertions.assertEquals(remainderUnsignedExpected(dividend, divisor),
ArithmeticUtils.remainderUnsigned(dividend, divisor));
+
Assertions.assertEquals(remainderUnsignedExpected(dividend, divisor),
ArithmeticUtils.remainderUnsigned(dividend, divisor),
+ () -> dividend + " % " + divisor);
}
}
}
diff --git
a/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/core/ArithmeticPerformance.java
b/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/core/ArithmeticPerformance.java
index d8c98382..ddd09751 100644
---
a/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/core/ArithmeticPerformance.java
+++
b/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/core/ArithmeticPerformance.java
@@ -20,6 +20,7 @@ package org.apache.commons.numbers.examples.jmh.core;
import java.util.concurrent.TimeUnit;
import java.util.function.IntBinaryOperator;
import java.util.function.LongBinaryOperator;
+import org.apache.commons.numbers.core.ArithmeticUtils;
import org.apache.commons.rng.simple.RandomSource;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
@@ -49,9 +50,13 @@ import org.openjdk.jmh.annotations.Warmup;
@Fork(value = 1, jvmArgs = {"-server", "-Xms512M", "-Xmx512M"})
public class ArithmeticPerformance {
/** Method to compute the divide using unsigned arithmetic. */
- private static final String DIVIDE_UNSIGNED = "divideUnsigned";
+ private static final String DIVIDE_UNSIGNED_1_0 = "divideUnsigned_1.0";
/** Method to compute the remainder using unsigned arithmetic. */
- private static final String REMAINDER_UNSIGNED = "remainderUnsigned";
+ private static final String REMAINDER_UNSIGNED_1_0 =
"remainderUnsigned_1.0";
+ /** Method to compute the divide using unsigned arithmetic. */
+ private static final String DIVIDE_UNSIGNED_1_1 = "divideUnsigned_1.1";
+ /** Method to compute the remainder using unsigned arithmetic. */
+ private static final String REMAINDER_UNSIGNED_1_1 =
"remainderUnsigned_1.1";
/**
* Source of {@code long} array data.
@@ -117,8 +122,8 @@ public class ArithmeticPerformance {
@State(Scope.Benchmark)
public static class LongFunctionSource {
/** Name of the source. */
- @Param({"Long.divideUnsigned", DIVIDE_UNSIGNED,
- "Long.remainderUnsigned", REMAINDER_UNSIGNED})
+ @Param({"Long.divideUnsigned", DIVIDE_UNSIGNED_1_0,
DIVIDE_UNSIGNED_1_1,
+ "Long.remainderUnsigned", REMAINDER_UNSIGNED_1_0,
REMAINDER_UNSIGNED_1_1})
private String name;
/** The action. */
@@ -138,12 +143,16 @@ public class ArithmeticPerformance {
public void setup() {
if ("Long.divideUnsigned".equals(name)) {
function = Long::divideUnsigned;
- } else if (DIVIDE_UNSIGNED.equals(name)) {
+ } else if (DIVIDE_UNSIGNED_1_0.equals(name)) {
function = ArithmeticPerformance::divideUnsigned;
+ } else if (DIVIDE_UNSIGNED_1_1.equals(name)) {
+ function = ArithmeticUtils::divideUnsigned;
} else if ("Long.remainderUnsigned".equals(name)) {
function = Long::remainderUnsigned;
- } else if (REMAINDER_UNSIGNED.equals(name)) {
+ } else if (REMAINDER_UNSIGNED_1_0.equals(name)) {
function = ArithmeticPerformance::remainderUnsigned;
+ } else if (REMAINDER_UNSIGNED_1_1.equals(name)) {
+ function = ArithmeticUtils::remainderUnsigned;
} else {
throw new IllegalStateException("Unknown long function: " +
name);
}
@@ -156,8 +165,8 @@ public class ArithmeticPerformance {
@State(Scope.Benchmark)
public static class IntFunctionSource {
/** Name of the source. */
- @Param({"Integer.divideUnsigned", DIVIDE_UNSIGNED,
- "Integer.remainderUnsigned", REMAINDER_UNSIGNED})
+ @Param({"Integer.divideUnsigned", DIVIDE_UNSIGNED_1_0,
DIVIDE_UNSIGNED_1_1,
+ "Integer.remainderUnsigned", REMAINDER_UNSIGNED_1_0,
REMAINDER_UNSIGNED_1_1})
private String name;
/** The action. */
@@ -177,12 +186,16 @@ public class ArithmeticPerformance {
public void setup() {
if ("Integer.divideUnsigned".equals(name)) {
function = Integer::divideUnsigned;
- } else if (DIVIDE_UNSIGNED.equals(name)) {
+ } else if (DIVIDE_UNSIGNED_1_0.equals(name)) {
function = ArithmeticPerformance::divideUnsigned;
+ } else if (DIVIDE_UNSIGNED_1_1.equals(name)) {
+ function = ArithmeticUtils::divideUnsigned;
} else if ("Integer.remainderUnsigned".equals(name)) {
function = Integer::remainderUnsigned;
- } else if (REMAINDER_UNSIGNED.equals(name)) {
+ } else if (REMAINDER_UNSIGNED_1_0.equals(name)) {
function = ArithmeticPerformance::remainderUnsigned;
+ } else if (REMAINDER_UNSIGNED_1_1.equals(name)) {
+ function = ArithmeticUtils::remainderUnsigned;
} else {
throw new IllegalStateException("Unknown int function: " +
name);
}
@@ -195,7 +208,7 @@ public class ArithmeticPerformance {
* as an unsigned value.
* <p>This method does not use the {@code long} datatype.</p>
*
- * <p>This is a copy of the original method in {@code
o.a.c.numbers.core.ArithmeticUtils}.
+ * <p>This is a copy of the original method in {@code
o.a.c.numbers.core.ArithmeticUtils} v1.0.
*
* @param dividend the value to be divided
* @param divisor the value doing the dividing
@@ -225,7 +238,7 @@ public class ArithmeticPerformance {
* as an unsigned value.
* <p>This method does not use the {@code BigInteger} datatype.</p>
*
- * <p>This is a copy of the original method in {@code
o.a.c.numbers.core.ArithmeticUtils}.
+ * <p>This is a copy of the original method in {@code
o.a.c.numbers.core.ArithmeticUtils} v1.0.
*
* @param dividend the value to be divided
* @param divisor the value doing the dividing
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index d9b796b2..1ff6e3da 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -56,7 +56,10 @@ If the output is not quite correct, check for invisible
trailing spaces!
<release version="1.2" date="TBD" description="
New features, updates and bug fixes.
">
- <action dev="aherbert" type="add" due-to="Harald Kirsch"
issue="NUMBERS-205">
+ <action dev="aherbert" type="update" due-to="Sebb, Alex Herbert">
+ "ArithmeticUtils": Improve performance of remainderUnsigned and
divideUnsigned.
+ </action>
+ <action dev="aherbert" type="add" due-to="Harald Kirsch"
issue="NUMBERS-205">
"Addition/Multiplication": Introduces isZero to Addition and isOne to
Multiplication
interfaces. Override the default implementation in implementing
classes to avoid
expensive equals(Object) operations.
