Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

optimizing collection creation #6247

Open
scabug opened this issue Aug 16, 2012 · 8 comments
Open

optimizing collection creation #6247

scabug opened this issue Aug 16, 2012 · 8 comments
Milestone

Comments

@scabug
Copy link

@scabug scabug commented Aug 16, 2012

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"

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
Copy link
Author

@scabug scabug commented Aug 16, 2012

@scabug
Copy link
Author

@scabug scabug commented Aug 16, 2012

@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
Copy link
Author

@scabug scabug commented Nov 5, 2012

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

@scabug scabug added this to the Backlog milestone Apr 7, 2017
@texasbruce
Copy link

@texasbruce texasbruce commented Oct 8, 2020

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
Copy link

@NthPortal NthPortal commented Oct 8, 2020

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
Copy link

@som-snytt som-snytt commented Oct 8, 2020

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

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

@texasbruce
Copy link

@texasbruce texasbruce commented Oct 8, 2020

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

@texasbruce
Copy link

@texasbruce texasbruce commented Oct 26, 2020

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;

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants