Array.fill, etc, could be optimized for constant functions

[retronym]

Array.fill accepts a by-name parameter for the element. For the (common) case that a constant expression is used, this will incur a performance penalty (calling the virtual Function0.apply method within the loop that fills the array.

There is an extra cost of calling ScalaRuntime.Array_update inside the loop, too.

For best performance, the user needs to revert to the Java API:

class Fill {
  def slow(n: Int, x: Int) = Array.fill[Int](n)(x)
  def fast(n: Int, x: Int) = {
    val a = new Array[Int](n)
    java.util.Arrays.fill(a, x)
    a
  }
}

(TODO: Benchmark the difference here. The benchmark should use a variety of array types to show the worst case for the megamorphic call inside the Array.fill while loop.)

Can we make the compiler and/or library do this automatically?

The most direct fix would be to teach the optimizer or some other part of the compiler about this specific case, and add a rewrite. Perhaps some of it falls out of well targetted inlining. But once we solve fill, we would need to turn attention to tabulate, and maybe map, etc.

What if we let the library author introspect the provided lambda to check if it is constant, and dispatch to a more efficient branch.

Sketching out the library support:

  /** Marker trait added by the compiler to anonymous functions that return a constant expression */
  trait ConstantFunction

  /**
    * Reveals the lambda that implements the by-name parameter
    * 
    * ```
    * scala> val f = new scala.runtime.AbstractFunction0[Int] with ConstantFunction { def apply = 42 }
    * f: scala.runtime.AbstractFunction0[Int] with ConstantFunction = ...
    * 
    * scala> def foo[A](a: => A) = lambdaOf(a)
    * foo: [A](a: => A)() => A
    * 
    * scala> foo(f()) eq f
    * res3: Boolean = true
    * ```
    * */
  final def lambdaOf[A](a: => A): () => A = () => a

  /** fill generic array  */
  final def array_fill(xs: AnyRef, value: Any): Unit = {
    xs match {
      case x: Array[AnyRef]  => java.util.Arrays.fill(x, value.asInstanceOf[AnyRef])
      case x: Array[Int]     => java.util.Arrays.fill(x, value.asInstanceOf[Int])
      case x: Array[Double]  => java.util.Arrays.fill(x, value.asInstanceOf[Double])
      case x: Array[Long]    => java.util.Arrays.fill(x, value.asInstanceOf[Long])
      case x: Array[Float]   => java.util.Arrays.fill(x, value.asInstanceOf[Float])
      case x: Array[Char]    => java.util.Arrays.fill(x, value.asInstanceOf[Char])
      case x: Array[Byte]    => java.util.Arrays.fill(x, value.asInstanceOf[Byte])
      case x: Array[Short]   => java.util.Arrays.fill(x, value.asInstanceOf[Short])
      case x: Array[Boolean] => java.util.Arrays.fill(x, value.asInstanceOf[Boolean])
      case x: Array[Unit]    => java.util.Arrays.fill(x.asInstanceOf[Array[Object]], ())
      case null => throw new NullPointerException
    }
  }

Which we could exploit as:

  def fill[T: ClassTag](n: Int)(elem: => T): Array[T] = {
    lambdaOf(elem) match {
      case _: ConstantFunction =>
        val e = elem
        val a = empty[T]
        array_fill(a, e)
        a
      case _ =>
        val b = newBuilder[T]
        b.sizeHint(n)
        var i = 0
        while (i < n) {
          b += elem
          i += 1
        }
        b.result()
    }
  }

Related:

• I once prototyped use of reused classes for constant functions to avoid anonymous class bloat.
• I think Paul tried out similar ideas

[retronym]

/cc @meskells @szeiger @Ichoran

[sjrd]

FWIW, the Scala.js optimizer, which is mostly based on inlining and closure elimination, is able to optimize those.

For fill:

// this is `slow`
$c_Lhelloworld_Fill.prototype.slow__I__I__AI = (function(n, x) {
  var elems$2 = null;
  elems$2 = [];
  var i = 0;
  while ((i < n)) {
    elems$2.push(x);
    i = ((1 + i) | 0)
  };
  return $makeNativeArrayWrapper($d_I.getArrayOf(), elems$2)
});

// this is j.u.Arrays.fill
$c_ju_Arrays$.prototype.fill__AI__I__V = (function(a, value) {
  var toIndex = a.u.length;
  var i = 0;
  while ((i !== toIndex)) {
    a.set(i, value);
    i = ((1 + i) | 0)
  }
});

Also for tabulate, with 2 dimensions:

class Tab {
  def slow(n1: Int, n2: Int) = Array.tabulate(n1, n2)((i, j) => i + j)
  
  def fast(n1: Int, n2: Int) = {
    val a = new Array[Array[Int]](n1)
    var i = 0
    while (i != n1) {
      val b = new Array[Int](n2)
      var j = 0
      while (j != n2) {
        b(j) = i + j
        j += 1
      }
      a(i) = b
      i += 1
    }
    a
  }
}

becomes

// slow
$c_Lhelloworld_Tab.prototype.slow__I__I__AAI = (function(n1, n2) {
  var elems$2 = null;
  elems$2 = [];
  var i = 0;
  while ((i < n1)) {
    var arg1 = i;
    var elems$2$1 = null;
    elems$2$1 = [];
    var i$1 = 0;
    while ((i$1 < n2)) {
      var arg1$1 = i$1;
      var elem = ((arg1 + arg1$1) | 0);
      elems$2$1.push(elem);
      i$1 = ((1 + i$1) | 0)
    };
    var elem$1 = $makeNativeArrayWrapper($d_I.getArrayOf(), elems$2$1);
    elems$2.push(elem$1);
    i = ((1 + i) | 0)
  };
  return $makeNativeArrayWrapper($d_I.getArrayOf().getArrayOf(), elems$2)
});

// fast
$c_Lhelloworld_Tab.prototype.fast__I__I__AAI = (function(n1, n2) {
  var a = $newArrayObject($d_I.getArrayOf().getArrayOf(), [n1]);
  var i = 0;
  while ((i !== n1)) {
    var b = $newArrayObject($d_I.getArrayOf(), [n2]);
    var j = 0;
    while ((j !== n2)) {
      b.set(j, ((i + j) | 0));
      j = ((1 + j) | 0)
    };
    a.set(i, b);
    i = ((1 + i) | 0)
  };
  return a
});

[mkeskells]

for the final def array_fill(xs: AnyRef, value: Any): Unit
is not correct or fully optimal

val a = empty[T]
array_fill(a, e)

doesnt really work. Its not empty, we need an array with size

as scala Array.fill generates a new Array filled

java Arrays.fill fills in an existing array ( and I think is internally optimised via intrinsics and the JVM macro support - effectively it turns into a memcpy )

we need to emit the bytecode for allocation of the array and fill with no gaps between ( so that the JVM will not fill with default value during allocation

This should mean that the fill should be the same cost as a plain allocation!