improve performance of integer multiplication overflow check on Duration

- also rename divisor arguments to “divisor”
- and add a scalacheck for multiplication overflow detection

2 files changed, 106 insertions, 20 deletions

diff --git a/src/library/scala/concurrent/util/Duration.scala b/src/library/scala/concurrent/util/Duration.scala
index 4567bf8ee6..c980170f0d 100644
--- a/src/library/scala/concurrent/util/Duration.scala
+++ b/src/library/scala/concurrent/util/Duration.scala
@@ -275,13 +275,13 @@ object Duration {
       if (factor == 0d || factor.isNaN) Undefined
       else if (factor < 0d) -this
       else this
-    def /(factor: Double): Duration =
-      if (factor.isNaN || factor.isInfinite) Undefined
-      else if ((factor compare 0d) < 0) -this
+    def /(divisor: Double): Duration =
+      if (divisor.isNaN || divisor.isInfinite) Undefined
+      else if ((divisor compare 0d) < 0) -this
       else this
-    def /(other: Duration): Double = other match {
+    def /(divisor: Duration): Double = divisor match {
       case _: Infinite => Double.NaN
-      case x           => Double.PositiveInfinity * (if ((this > Zero) ^ (other >= Zero)) -1 else 1)
+      case x           => Double.PositiveInfinity * (if ((this > Zero) ^ (divisor >= Zero)) -1 else 1)
     }
 
     final def isFinite() = false
@@ -529,12 +529,12 @@ sealed abstract class Duration extends Serializable with Ordered[Duration] {
    *
    * $ovf
    */
-  def /(factor: Double): Duration
+  def /(divisor: Double): Duration
   /**
    * Return the quotient of this and that duration as floating-point number. The semantics are
    * determined by Double as if calculating the quotient of the nanosecond lengths of both factors.
    */
-  def /(other: Duration): Double
+  def /(divisor: Duration): Double
   /**
    * Negate this duration. The only two values which are mapped to themselves are [[Duration.Zero]] and [[Duration.Undefined]].
    */
@@ -561,7 +561,7 @@ sealed abstract class Duration extends Serializable with Ordered[Duration] {
    *
    * $ovf
    */
-  def div(factor: Double)    = this / factor
+  def div(divisor: Double)    = this / divisor
   /**
    * Return the quotient of this and that duration as floating-point number. The semantics are
    * determined by Double as if calculating the quotient of the nanosecond lengths of both factors.
@@ -691,17 +691,17 @@ final class FiniteDuration(val length: Long, val unit: TimeUnit) extends Duratio
     else if ((factor > 0) ^ (this < Zero)) Inf
     else MinusInf
 
-  def /(factor: Double) =
-    if (!factor.isInfinite) fromNanos(toNanos / factor)
-    else if (factor.isNaN) Undefined
+  def /(divisor: Double) =
+    if (!divisor.isInfinite) fromNanos(toNanos / divisor)
+    else if (divisor.isNaN) Undefined
     else Zero
 
   // if this is made a constant, then scalac will elide the conditional and always return +0.0, SI-6331
   private[this] def minusZero = -0d
-  def /(other: Duration): Double =
-    if (other.isFinite) toNanos.toDouble / other.toNanos
-    else if (other eq Undefined) Double.NaN
-    else if ((length < 0) ^ (other > Zero)) 0d
+  def /(divisor: Duration): Double =
+    if (divisor.isFinite) toNanos.toDouble / divisor.toNanos
+    else if (divisor eq Undefined) Double.NaN
+    else if ((length < 0) ^ (divisor > Zero)) 0d
     else minusZero
 
   // overloaded methods taking FiniteDurations, so that you can calculate while statically staying finite
@@ -719,16 +719,33 @@ final class FiniteDuration(val length: Long, val unit: TimeUnit) extends Duratio
    *
    * @throws ArithmeticException if the factor is 0
    */
-  def /(factor: Long) = fromNanos(toNanos / factor)
+  def /(divisor: Long) = fromNanos(toNanos / divisor)
 
   /**
    * Return the product of this duration and the given integer factor.
    *
    * @throws IllegalArgumentException if the result would overflow the range of FiniteDuration
    */
-  def *(factor: Long) = {
-    if (length > Long.MaxValue / factor) throw new IllegalArgumentException("multiplication overflow")
-    new FiniteDuration(length * factor, unit)
+  def *(factor: Long) = new FiniteDuration(safeMul(length, factor), unit)
+
+  /*
+   * This method avoids the use of Long division, which saves 95% of the time spent,
+   * by checking that there are enough leading zeros so that the result has a chance
+   * to fit into a Long again; the remaining edge cases are caught by using the sign
+   * of the product for overflow detection.
+   *
+   * This method is not general purpose because it disallows the (otherwise legal)
+   * case of Long.MinValue * 1, but that is okay for use in FiniteDuration, since
+   * Long.MinValue is not a legal `length` anyway.
+   */
+  private def safeMul(_a: Long, _b: Long): Long = {
+    val a = math.abs(_a)
+    val b = math.abs(_b)
+    import java.lang.Long.{ numberOfLeadingZeros => leading }
+    if (leading(a) + leading(b) < 64) throw new IllegalArgumentException("multiplication overflow")
+    val product = a * b
+    if (product < 0) throw new IllegalArgumentException("multiplication overflow")
+    if (a == _a ^ b == _b) -product else product
   }
 
   /**
@@ -736,7 +753,7 @@ final class FiniteDuration(val length: Long, val unit: TimeUnit) extends Duratio
    *
    * @throws ArithmeticException if the factor is 0
    */
-  def div(factor: Long) = this / factor
+ def div(divisor: Long) = this / divisor
 
   /**
    * Return the product of this duration and the given integer factor.
diff --git a/test/files/scalacheck/duration.scala b/test/files/scalacheck/duration.scala
new file mode 100644
index 0000000000..8037720f69
--- /dev/null
+++ b/test/files/scalacheck/duration.scala
@@ -0,0 +1,69 @@
+import org.scalacheck._
+import Prop._
+import Gen._
+import Arbitrary._
+import math._
+import concurrent.util.Duration.fromNanos
+
+object Test extends Properties("Division of Duration by Long") {
+
+  val weightedLong =
+    frequency(
+      1 -> choose(-128L, 127L),
+      1 -> (arbitrary[Byte] map (_.toLong << 8)),
+      1 -> (arbitrary[Byte] map (_.toLong << 16)),
+      1 -> (arbitrary[Byte] map (_.toLong << 24)),
+      1 -> (arbitrary[Byte] map (_.toLong << 32)),
+      1 -> (arbitrary[Byte] map (_.toLong << 40)),
+      1 -> (arbitrary[Byte] map (_.toLong << 48)),
+      1 -> (choose(-127L, 127L) map (_ << 56))
+    )
+
+  val genTwoSmall = for {
+    a <- weightedLong
+    b <- choose(-(Long.MaxValue / max(1, abs(a))), Long.MaxValue / max(1, abs(a)))
+  } yield (a, b)
+
+  val genTwoLarge = for {
+    a <- weightedLong
+    b <- arbitrary[Long] suchThat (b => (abs(b) > Long.MaxValue / max(1, abs(a))))
+  } yield (a, b)
+
+  val genClose = for {
+    a <- weightedLong
+    if a != 0
+    b <- choose(Long.MaxValue / a - 10, Long.MaxValue / a + 10)
+  } yield (a, b)
+
+  val genBorderline =
+    frequency(
+      1 -> (Long.MinValue, 0L),
+      1 -> (Long.MinValue, 1L),
+      1 -> (Long.MinValue, -1L),
+      1 -> (0L, Long.MinValue),
+      1 -> (1L, Long.MinValue),
+      1 -> (-1L, Long.MinValue),
+      90 -> genClose
+    )
+
+  def mul(a: Long, b: Long): Long = {
+    (fromNanos(a) * b).toNanos
+  }
+
+  property("without overflow") = forAll(genTwoSmall) { case (a, b) =>
+    a * b == mul(a, b)
+  }
+
+  property("with overflow") = forAll(genTwoLarge) { case (a, b) =>
+    try { mul(a, b); false } catch { case _: IllegalArgumentException => true }
+  }
+
+  property("on overflow edge cases") = forAll(genBorderline) { case (a, b) =>
+    val shouldFit =
+      a != Long.MinValue && // must fail due to illegal duration length
+      (b != Long.MinValue || a == 0) && // Long factor may only be MinValue if the duration is zero, otherwise the result will be illegal
+      (abs(b) <= Long.MaxValue / max(1, abs(a))) // check the rest against the “safe” division method
+    try { mul(a, b); shouldFit }
+    catch { case _: IllegalArgumentException => !shouldFit }
+  }
+}