Optimizer benchmark: array optimizations

[retronym]

trafficstars

array.exists(_ == 10) should perform like a while loop.

[lrytz]

Array(1,2,3).map(_ * 2) is actually more interesting, as it also passes a ClassTag that could be optimized away if we really get to that while loop. See also Sébastien's talk: https://plus.google.com/events/cr8iuprn2a3f0pv5na5p35319jc

[lrytz]

Array.foreach is slowly getting better, but still boxing every value for primitive arrays. The implementation of ArrayOps.ofInt is inherited from IndexedSeqOptimized. The method is inlined and the closure eliminated. However, foreach invokes this.apply(index) to get array elements, and that method is the generic def apply(idx: Int): A from SeqLike, so it returns a boxed value.

class C {
  def consume(x: Int) = ()
  def t1(a: Array[Int]): Unit = a foreach consume
}

gives (cfr-decompiler)

    public void t1(int[] a) {
        ArrayOps.ofInt foreach_this = new ArrayOps.ofInt(Predef..MODULE$._intArrayOps(a));
        int foreach_len = foreach_this.length();
        for (int foreach_i = 0; foreach_i < foreach_len; ++foreach_i) {
            int n = BoxesRunTime.unboxToInt((Object)foreach_this.apply(foreach_i));
            this.C$$$anonfun$1(n);
        }
    }

To improve we need to stack-allocate ofInt and then inline foreach_this.apply, then the box can be eliminated.

[lrytz]

Array.exists is not optimized currently. ArrayOps.ofInt inherits the implementation from IndexedSeqOptimized

def exists(p: A => Boolean): Boolean = prefixLengthImpl(p, expectTrue = false) != length

The method prefixLengthImpl is private, so exists cannot be inlined into a different class. This can be fixed by a more optimistic heuristic that continues inlining also the prefixLengthImpl method, which we have to do anyway to eliminate the closure. That would allow eliminating the closure, then we have the same situation as with foreach above (primitive boxing).

[lrytz]

Mostly fixed by https://github.com/scala/scala/pull/7133. There are some operations that can be further improved, for example partition (Need to avoid using a generic array builder to avoid boxing. Needs more special cases / intrinsic knowledge. See InlinerTest.cleanArrayPartition).

Other operations that are known to be non-optimal: filter, reverse, groupBy.

Operations that need to be checked / benchmarked: flatMap, flatten, collect, appended, prepended, contains, patch, toArray, copyToArray, startsWith, endsWith, updated. See also comment in InlinerTest (below cleanArrayPartition).