optimizing collection creation

[scabug]

Quoting from https://groups.google.com/d/topic/scala-internals/5oRYBYBUqMY/discussion

When you create a collection, a lot of unnecessary work is done.  

Quoting from https://groups.google.com/d/msg/scala-internals/5oRYBYBUqMY/aq93-oBpaukJ

I think there's a middle ground between what we have now and macro/builtin compiler support. This reminds me an idea I had (and Miguel also mentioned to me) of early inlining. The current state of affairs is that code with foreach call like List(1,2,3) foreach println we first expand lambda to a class, we typecheck everything and generate lots of trees, then icode and only then we realize (if we are lucky) that we can inline foreach implementation, inline apply of a closure and throw away the whole class we generate for the closure. That's a huge amount of wasted work.

Quoting from The Scala Compiler Corner, about "early inlining"

• 2012-07-03: GC-savvy Closure conversion,
  http://lamp.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/2012Q3/2012-07-01-GC-savvy-Closure-conversion.pdf
• 2011-11-22: Just trying to generate faster code faster under -optimise
  http://lamp.epfl.ch/~magarcia/ScalaNET/slides/2011-11-22-BetterInlining.pdf

Many of these performance problems can go away with MethodHandles and invokedynamic. Therefore this bug should be broken up into pre-JDK7 and JDK7 versions.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-6247?orig=1
Reporter: @magarciaEPFL
See #6611

[scabug]

@magarciaEPFL said:
Quoting from https://groups.google.com/d/topic/scala-internals/5oRYBYBUqMY/discussion

The cases of particular interest to me are List and Array.

• List(1, 2, 3) leads to approximately this:
  {noformat} val arr = new ArrayInt
  arr(0) = 1
  arr(1) = 2
  arr(2) = 3
  val wrapped = new WrappedArray(arr)
  List.apply(wrapped)
  val cbf = implicitly[CanBuildFrom[...]]
  val builder = cbf() // new ListBuffer[Int]
  builder ++= wrapped
  builder.result

When it could be done like this:

new ::(1, new ::(2, new ::(3, Nil)))

- Array(1, 2, 3) leads to approximately this:

val arr = new ArrayInt
arr(0) = 1
arr(1) = 2
arr(2) = 3
// Hey, stop right there! Scala, stop! Oh no...
val wrapped = new WrappedArray(arr)
Array.apply(wrapped)
val arr2 = new ArrayInt
var i = 0
// throw in a closure and a boxing trip through Seq#foreach
for (x <- wrapped.iterator) { arr2(i) = x; i += 1 }
arr2
{noformat}

[scabug]

@retronym said:
Primitive array creation using Array.apply has now been hand-optimized in Cleanup, as was already done for reference arrays: scala/scala@8265175e

[neontorrent]

Array is currently optimized by compiler. Should we remove the code in Array.scala (e.g. change it to throw exception like the other method) so it doesn't confuse people who read it?

List is still not optimized. Considering it is one of the most frequently used collection in Scala, optimization for construction should be prioritized IMO.

[NthPortal]

2.12.12

scala> class Test {
     |   def string: List[String] = List("foo", "bar")
     |   def int:    List[Int]    = List(1, 2)
     | }
defined class Test

scala> :javap -c -filter Test
[...]
  public scala.collection.immutable.List<java.lang.String> string();
    Code:
       0: new           #18                 // class scala/collection/immutable/$colon$colon
       3: dup
       4: ldc           #20                 // String foo
       6: new           #18                 // class scala/collection/immutable/$colon$colon
       9: dup
      10: ldc           #22                 // String bar
      12: getstatic     #28                 // Field scala/collection/immutable/Nil$.MODULE$:Lscala/collection/immutable/Nil$;
      15: invokespecial #32                 // Method scala/collection/immutable/$colon$colon."<init>":(Ljava/lang/Object;Lscala/collection/immutable/List;)V
      18: invokespecial #32                 // Method scala/collection/immutable/$colon$colon."<init>":(Ljava/lang/Object;Lscala/collection/immutable/List;)V
      21: areturn

  public scala.collection.immutable.List<java.lang.Object> int();
    Code:
       0: getstatic     #41                 // Field scala/collection/immutable/List$.MODULE$:Lscala/collection/immutable/List$;
       3: getstatic     #46                 // Field scala/Predef$.MODULE$:Lscala/Predef$;
       6: iconst_2
       7: newarray       int
       9: dup
      10: iconst_0
      11: iconst_1
      12: iastore
      13: dup
      14: iconst_1
      15: iconst_2
      16: iastore
      17: invokevirtual #50                 // Method scala/Predef$.wrapIntArray:([I)Lscala/collection/mutable/WrappedArray;
      20: invokevirtual #54                 // Method scala/collection/immutable/List$.apply:(Lscala/collection/Seq;)Lscala/collection/immutable/List;
      23: areturn
[...]

2.13.3

scala> class Test {
     |   def string: List[String] = List("foo", "bar")
     |   def int:    List[Int]    = List(1, 2)
     | }
class Test

scala> :javap -c -filter Test
[...]
  public scala.collection.immutable.List<java.lang.String> string();
    Code:
       0: new           #18                 // class scala/collection/immutable/$colon$colon
       3: dup
       4: ldc           #20                 // String foo
       6: new           #18                 // class scala/collection/immutable/$colon$colon
       9: dup
      10: ldc           #22                 // String bar
      12: getstatic     #28                 // Field scala/collection/immutable/Nil$.MODULE$:Lscala/collection/immutable/Nil$;
      15: invokespecial #32                 // Method scala/collection/immutable/$colon$colon."<init>":(Ljava/lang/Object;Lscala/collection/immutable/List;)V
      18: invokespecial #32                 // Method scala/collection/immutable/$colon$colon."<init>":(Ljava/lang/Object;Lscala/collection/immutable/List;)V
      21: checkcast     #34                 // class scala/collection/immutable/List
      24: areturn

  public scala.collection.immutable.List<java.lang.Object> int();
    Code:
       0: getstatic     #43                 // Field scala/collection/immutable/List$.MODULE$:Lscala/collection/immutable/List$;
       3: getstatic     #48                 // Field scala/runtime/ScalaRunTime$.MODULE$:Lscala/runtime/ScalaRunTime$;
       6: iconst_2
       7: newarray       int
       9: dup
      10: iconst_0
      11: iconst_1
      12: iastore
      13: dup
      14: iconst_1
      15: iconst_2
      16: iastore
      17: invokevirtual #52                 // Method scala/runtime/ScalaRunTime$.wrapIntArray:([I)Lscala/collection/immutable/ArraySeq;
      20: invokevirtual #56                 // Method scala/collection/immutable/List$.apply:(Lscala/collection/immutable/Seq;)Ljava/lang/Object;
      23: checkcast     #34                 // class scala/collection/immutable/List
      26: areturn
[...]

List is optimised, though not for Int (and presumably not for other primitives either). it's unclear to me why it's optimised (seemingly) only for reference types.

[som-snytt]

To someone boxing primitives, it's just one more box.

Little boxes made of ticky-tacky...
In the clearing stands a boxer... 🎶

[neontorrent]

2.13.3

scala> class Test {
     |   def string: List[String] = List("foo", "bar")
     |   def int:    List[Int]    = List(1, 2)
     | }
class Test

scala> :javap -c -filter Test
[...]
  public scala.collection.immutable.List<java.lang.String> string();
    Code:
       0: new           #18                 // class scala/collection/immutable/$colon$colon
       3: dup
       4: ldc           #20                 // String foo
       6: new           #18                 // class scala/collection/immutable/$colon$colon
       9: dup
      10: ldc           #22                 // String bar
      12: getstatic     #28                 // Field scala/collection/immutable/Nil$.MODULE$:Lscala/collection/immutable/Nil$;
      15: invokespecial #32                 // Method scala/collection/immutable/$colon$colon."<init>":(Ljava/lang/Object;Lscala/collection/immutable/List;)V
      18: invokespecial #32                 // Method scala/collection/immutable/$colon$colon."<init>":(Ljava/lang/Object;Lscala/collection/immutable/List;)V
      21: checkcast     #34                 // class scala/collection/immutable/List
      24: areturn

  public scala.collection.immutable.List<java.lang.Object> int();
    Code:
       0: getstatic     #43                 // Field scala/collection/immutable/List$.MODULE$:Lscala/collection/immutable/List$;
       3: getstatic     #48                 // Field scala/runtime/ScalaRunTime$.MODULE$:Lscala/runtime/ScalaRunTime$;
       6: iconst_2
       7: newarray       int
       9: dup
      10: iconst_0
      11: iconst_1
      12: iastore
      13: dup
      14: iconst_1
      15: iconst_2
      16: iastore
      17: invokevirtual #52                 // Method scala/runtime/ScalaRunTime$.wrapIntArray:([I)Lscala/collection/immutable/ArraySeq;
      20: invokevirtual #56                 // Method scala/collection/immutable/List$.apply:(Lscala/collection/immutable/Seq;)Ljava/lang/Object;
      23: checkcast     #34                 // class scala/collection/immutable/List
      26: areturn
[...]

List is optimised, though not for Int (and presumably not for other primitives either). it's unclear to me why it's optimised (seemingly) only for reference types.

Looks like varargs not optimized for primitives. Good to know it is optimized for reference type though

[neontorrent]

Found another use case that is not optimized for List:

When List is aliased:

scala> val CC = List
val CC: scala.collection.immutable.List.type = scala.collection.immutable.List$@944b91b

scala> def f = CC("first")
def f: List[String]

scala> :javap #f
WARNING: An illegal reflective access operation has occurred
WARNING: Illegal reflective access by scala.tools.nsc.interpreter.shell.JavapTask (file:/D:/opt/scala/scala-2.13.2/lib/scala-compiler.jar) to method com.sun.tools.javap.JavapFileManager.create(javax.tools.DiagnosticListener,java.io.PrintWriter)
WARNING: Please consider reporting this to the maintainers of scala.tools.nsc.interpreter.shell.JavapTask
WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations
WARNING: All illegal access operations will be denied in a future release
  public scala.collection.immutable.List<java.lang.String> f();
    descriptor: ()Lscala/collection/immutable/List;
    flags: (0x0001) ACC_PUBLIC
    Code:
      stack=6, locals=1, args_size=1
         0: aload_0
         1: invokevirtual #23                 // Method $line5$$read$$iw$$$outer:()L$line5/$read;
         4: invokevirtual #27                 // Method $line5/$read.$line4$read:()L$line4/$read;
         7: invokevirtual #30                 // Method $line4/$read.$iw:()L$line4/$read$$iw;
        10: invokevirtual #34                 // Method $line4/$read$$iw.CC:()Lscala/collection/immutable/List$;
        13: getstatic     #40                 // Field scala/runtime/ScalaRunTime$.MODULE$:Lscala/runtime/ScalaRunTime$;
        16: iconst_1
        17: anewarray     #42                 // class java/lang/String
        20: dup
        21: iconst_0
        22: ldc           #44                 // String first
        24: aastore
        25: checkcast     #46                 // class "[Ljava/lang/Object;"
        28: invokevirtual #50                 // Method scala/runtime/ScalaRunTime$.wrapRefArray:([Ljava/lang/Object;)Lscala/collection/immutable/ArraySeq;
        31: invokevirtual #56                 // Method scala/collection/immutable/List$.apply:(Lscala/collection/immutable/Seq;)Ljava/lang/Object;
        34: checkcast     #58                 // class scala/collection/immutable/List
        37: areturn
      LineNumberTable:
        line 1: 0
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0      38     0  this   L$line5/$read$$iw;
    Signature: #19                          // ()Lscala/collection/immutable/List<Ljava/lang/String;>;

It works fine for Array though:

scala> val CC = Array
val CC: Array.type = scala.Array$@5c881c93

scala> def f = CC("first")
def f: Array[String]

scala> :javap #f
  public java.lang.String[] f();
    descriptor: ()[Ljava/lang/String;
    flags: (0x0001) ACC_PUBLIC
    Code:
      stack=4, locals=1, args_size=1
         0: iconst_1
         1: anewarray     #16                 // class java/lang/String
         4: dup
         5: iconst_0
         6: ldc           #18                 // String first
         8: aastore
         9: checkcast     #20                 // class "[Ljava/lang/Object;"
        12: checkcast     #22                 // class "[Ljava/lang/String;"
        15: areturn
      LineNumberTable:
        line 1: 0
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0      16     0  this   L$line7/$read$$iw;