Missing generated AnyRef specialization for array access

[bbrehm]

Reproduction steps

Consider the following jmh benchmark (on scala 2.13.8 and hotspot openjdk-19, but I believe this applies to all versions except that graal is possibly better than C2 at loop hoisting the checks):

//effectively equivalent to scala standard library array iterator
class AnyIter[@specialized A](a: Array[A]) extends Iterator[A] {
  private[this] var idx = 0
  private[this] val len = a.length

  override def hasNext: Boolean = idx < len
  override def next(): A        = { val r = a(idx); idx += 1; r }
}

class AnyRefIter[A <: AnyRef](a: Array[A]) extends Iterator[A] {
  private[this] var idx = 0
  private[this] val len = a.length

  override def hasNext: Boolean = idx < len

  override def next(): A = {
    val r = a(idx); idx += 1; r
  }
}
@State(Scope.Benchmark)
@OperationsPerInvocation(1000)
class ArrayOps {
  val items = Range(1, 1000).iterator.map { idx => s"${idx}" }.toArray

  @Benchmark
  def scalaIter(bh: Blackhole): Unit = {
    val iter = items.iterator.filter { _ != "aaa" }
    bh.consume(iter)
    for (item <- iter) bh.consume(item)
  }

  @Benchmark
  def anyIter(bh: Blackhole): Unit = {
    val iter = new AnyIter(items).filter { _ != "aaa" }
    bh.consume(iter)
    for (item <- iter) bh.consume(item)
  }

  @Benchmark
  def anyRefIter(bh: Blackhole): Unit = {
    val iter = new AnyRefIter(items).filter { _ != "aaa" }
    bh.consume(iter)
    for (item <- iter) bh.consume(item)
  }
}

This gives with LinuxPerfNorm profiler enabled

Benchmark                                               Mode  Cnt    Score    Error  Units
joernBench.ArrayOps.anyIter                             avgt   21    5.307 ±  0.045  ns/op
joernBench.ArrayOps.anyIter:instructions:u              avgt    3  115.353 ± 10.216   #/op
joernBench.ArrayOps.anyRefIter                          avgt   21    4.689 ±  0.034  ns/op
joernBench.ArrayOps.anyRefIter:instructions:u           avgt    3  104.056 ± 25.334   #/op
joernBench.ArrayOps.scalaIter                           avgt   21    5.397 ±  0.119  ns/op
joernBench.ArrayOps.scalaIter:instructions:u            avgt    3  116.199 ± 21.201   #/op

(the confidence intervals reported by jmh are overly wide in many cases, because it assumes the quite conservative student t distribution. In other words, one needs to very carefully design test parameters with high iteration and fork counts in order to get good confidence intervals, and I did not do that here)

Problem

The problem is that specialization conflates AnyRef with Any. In many cases, there is not a relevant distinction in terms of performance whether we statically know that a type T is T <: AnyRef.

For accessing an Array[T] this makes a big difference, though: Accessing the array is aload if T <: AnyRef, and is a much slower scala.runtime.ScalaRunTime.array_apply(xs: AnyRef, idx: Int): Any.

Ideally, specialization would stop conflating Any and AnyRef.

If that is difficult for technical reasons, then we need to very prominently document this and warn people away from naive use of @specialized. Instead we need to point people to using custom specialization, as the standard library already does in some places like scala.collection.immutable.ArraySeq$ofRef.

Furthermore, we need to take our own bitter medicine and manually specialize performance critical parts. It is hard to imagine more critical code than iteration over arrays, so we definitely need a class scala.collection.ArrayOps$ArrayIteratorOfRef. But we need to look at all uses of @specialized and consider manually specializing the AnyRef case.

[SethTisue]

then we need to very prominently document this and warn people away from naive use of @specialized

I'm not sure where that would go...? In the Scaladoc for @specialized? And/or, one could imagine a feature guide to specialization living at https://docs.scala-lang.org/overviews/index.html , perhaps using the original SID as a guide.

[SethTisue]

If that is difficult for technical reasons

Nobody is working on Scala 2 specialization; there are many open bugs. Currently @specialized is a no-op in Scala 3, as the design is considered flawed. Threads about what a replacement might look like include https://contributors.scala-lang.org/t/status-of-specialization-in-scala-3/4628 and scala/scala3#17329

[som-snytt]

specialized means primitives. specialized(AnyRef) used to work in 2.9.2:

  <specialized> class AnyIter$mcT$sp extends AnyIter {
    <paramaccessor> <specialized> protected[this] val a$mcT$sp: Array[java.lang.Object] = _;
    override <specialized> def next(): java.lang.Object = AnyIter$mcT$sp.this.next$mcT$sp();
    override <specialized> def next$mcT$sp(): java.lang.Object = {
      val r: java.lang.Object = AnyIter$mcT$sp.this.a$mcT$sp.apply(AnyIter$mcT$sp.this.AnyIter$$idx);
      AnyIter$mcT$sp.this.AnyIter$$idx = AnyIter$mcT$sp.this.AnyIter$$idx.+(1);
      r
    };
    <specialized> def this(a$mcT$sp: Array[java.lang.Object]): AnyIter$mcT$sp = {
      AnyIter$mcT$sp.this.a$mcT$sp = a$mcT$sp;
      AnyIter$mcT$sp.super.this(a$mcT$sp);
      ()
    }
  };

Scaladoc is unclear.

https://github.com/scala/scala/blob/v2.13.13/src/library/scala/specialized.scala#L31

Oh, there is a test that suggests a workaround:

class Spek[@specialized(Int, AnyRef) A, @specialized(Unit) B](a: Array[A]) extends Test.It[A] {
  private[this] var idx = 0
  private[this] val len = a.length

  override def hasNext: Boolean = idx < len
  override def next(): A        = { val r = a(idx); idx += 1; r }

  //def bomb(): B = null.asInstanceOf[B]
}

where type It[A] = scala.collection.AbstractIterator[A] makes classes that are easier to work with;
and in which the second (unused) dummy specialized parameter forces Spek$mcLV$sp.class

  public A$sp next$mcL$sp();
    flags: ACC_PUBLIC
    Code:
      stack=3, locals=2, args_size=1
         0: aload_0
         1: getfield      #19;                // Field a$mcL$sp:[Ljava/lang/Object;
         4: aload_0
         5: getfield      #23;                // Field Spek$$idx:I
         8: aaload
         9: astore_1
        10: aload_0
        11: aload_0
        12: getfield      #23;                // Field Spek$$idx:I
        15: iconst_1
        16: iadd
        17: putfield      #23;                // Field Spek$$idx:I
        20: aload_1
        21: areturn

warn people away from naive use of @specialized

it could say "beware generalist use of specialized!"