Scala Programming Language
  1. Scala Programming Language
  2. SI-6979

Computing lub in WrappedArray.make takes 0.25s

    Details

      Description

      I found out that type-checking WrappedArray.make method (https://github.com/scala/scala/blob/master/src/library/scala/collection/mutable/WrappedArray.scala#L99) takes 0.25s and all that time is spent in calculating a single lub (probably coming from pattern match).

      I'm creating this ticket in case somebody wanted to have a closer look into that.

        Activity

        Hide
        Jason Zaugg added a comment -

        Yep, it's lubbing:

        (0)  = {scala.reflect.internal.Types$TypeRef$$anon$6@4974}"Null"
        (1)  = {scala.reflect.internal.Types$TypeRef$$anon$5@4976}"scala.collection.mutable.WrappedArray.ofRef[AnyRef]"
        (2)  = {scala.reflect.internal.Types$TypeRef$$anon$6@4978}"scala.collection.mutable.WrappedArray.ofInt"
        (3)  = {scala.reflect.internal.Types$TypeRef$$anon$6@4980}"scala.collection.mutable.WrappedArray.ofDouble"
        (4)  = {scala.reflect.internal.Types$TypeRef$$anon$6@4982}"scala.collection.mutable.WrappedArray.ofLong"
        (5)  = {scala.reflect.internal.Types$TypeRef$$anon$6@4984}"scala.collection.mutable.WrappedArray.ofFloat"
        (6)  = {scala.reflect.internal.Types$TypeRef$$anon$6@4986}"scala.collection.mutable.WrappedArray.ofChar"
        (7)  = {scala.reflect.internal.Types$TypeRef$$anon$6@4988}"scala.collection.mutable.WrappedArray.ofByte"
        (8)  = {scala.reflect.internal.Types$TypeRef$$anon$6@4990}"scala.collection.mutable.WrappedArray.ofShort"
        (9)  = {scala.reflect.internal.Types$TypeRef$$anon$6@4992}"scala.collection.mutable.WrappedArray.ofBoolean"
        (10)  = {scala.reflect.internal.Types$TypeRef$$anon$6@4994}"scala.collection.mutable.WrappedArray.ofUnit"
        

        It them throws the LUB away to call asInstanceOf

        import reflect.runtime.universe._, collection.mutable._, WrappedArray._
        
        scala> val ts = List(typeOf[ofInt], typeOf[ofLong], typeOf[ofShort], typeOf[WrappedArray[AnyRef]], typeOf[ofUnit], typeOf[ofDouble], typeOf[ofFloat], typeOf[ofBoolean], typeOf[Null])
        ts: List[reflect.runtime.universe.Type] = List(scala.collection.mutable.WrappedArray.ofInt, scala.collection.mutable.WrappedArray.ofLong, scala.collection.mutable.WrappedArray.ofShort, scala.collection.mutable.WrappedArray[scala.AnyRef], scala.collection.mutable.WrappedArray.ofUnit, scala.collection.mutable.WrappedArray.ofDouble, scala.collection.mutable.WrappedArray.ofFloat, scala.collection.mutable.WrappedArray.ofBoolean, Null)
        
        scala> lub(ts)
        res11: reflect.runtime.universe.Type = scala.collection.mutable.WrappedArray[_ >: Int with Long with Short with Unit with Double with Float with Boolean]
        

        For that particular method we can of course avoid the lub altogether by annotating the type of the match as `Any`. But I guess that's not why you raised this ticket.

        I believe that this optimization is safe: https://github.com/scala/scala/pull/1908, but it is only a slight improvement.

        Show
        Jason Zaugg added a comment - Yep, it's lubbing: (0) = {scala.reflect.internal.Types$TypeRef$$anon$6@4974}"Null" (1) = {scala.reflect.internal.Types$TypeRef$$anon$5@4976}"scala.collection.mutable.WrappedArray.ofRef[AnyRef]" (2) = {scala.reflect.internal.Types$TypeRef$$anon$6@4978}"scala.collection.mutable.WrappedArray.ofInt" (3) = {scala.reflect.internal.Types$TypeRef$$anon$6@4980}"scala.collection.mutable.WrappedArray.ofDouble" (4) = {scala.reflect.internal.Types$TypeRef$$anon$6@4982}"scala.collection.mutable.WrappedArray.ofLong" (5) = {scala.reflect.internal.Types$TypeRef$$anon$6@4984}"scala.collection.mutable.WrappedArray.ofFloat" (6) = {scala.reflect.internal.Types$TypeRef$$anon$6@4986}"scala.collection.mutable.WrappedArray.ofChar" (7) = {scala.reflect.internal.Types$TypeRef$$anon$6@4988}"scala.collection.mutable.WrappedArray.ofByte" (8) = {scala.reflect.internal.Types$TypeRef$$anon$6@4990}"scala.collection.mutable.WrappedArray.ofShort" (9) = {scala.reflect.internal.Types$TypeRef$$anon$6@4992}"scala.collection.mutable.WrappedArray.ofBoolean" (10) = {scala.reflect.internal.Types$TypeRef$$anon$6@4994}"scala.collection.mutable.WrappedArray.ofUnit" It them throws the LUB away to call asInstanceOf import reflect.runtime.universe._, collection.mutable._, WrappedArray._ scala> val ts = List(typeOf[ofInt], typeOf[ofLong], typeOf[ofShort], typeOf[WrappedArray[AnyRef]], typeOf[ofUnit], typeOf[ofDouble], typeOf[ofFloat], typeOf[ofBoolean], typeOf[Null]) ts: List[reflect.runtime.universe.Type] = List(scala.collection.mutable.WrappedArray.ofInt, scala.collection.mutable.WrappedArray.ofLong, scala.collection.mutable.WrappedArray.ofShort, scala.collection.mutable.WrappedArray[scala.AnyRef], scala.collection.mutable.WrappedArray.ofUnit, scala.collection.mutable.WrappedArray.ofDouble, scala.collection.mutable.WrappedArray.ofFloat, scala.collection.mutable.WrappedArray.ofBoolean, Null) scala> lub(ts) res11: reflect.runtime.universe.Type = scala.collection.mutable.WrappedArray[_ >: Int with Long with Short with Unit with Double with Float with Boolean] For that particular method we can of course avoid the lub altogether by annotating the type of the match as `Any`. But I guess that's not why you raised this ticket. I believe that this optimization is safe: https://github.com/scala/scala/pull/1908 , but it is only a slight improvement.
        Hide
        Adriaan Moors added a comment - - edited

        to be considered for backporting for 2.10.1-rc1 (fixed in 2.11.0-M2)

        Show
        Adriaan Moors added a comment - - edited to be considered for backporting for 2.10.1-rc1 (fixed in 2.11.0-M2)
        Hide
        Grzegorz Kossakowski added a comment -

        Jason,

        Do you mean we can annotate the return type of the match?

        And yes, I meant investigating if there's a bug in lub computation somewhere which makes it explore more of a search space than it's needed. My main point here is that the code looks totally unreasonable to any Scala user and it triggers really bad behavior in type checker. The ticket is meant to investigate if we can do something about it.

        Probably the first step would be to create tool that allows detecting those problems, especially in IDE. Iulian said he would like to look into integrating my experiments with AspectJ-based profiling into Eclipse. I added him to watching list of this issue.

        Show
        Grzegorz Kossakowski added a comment - Jason, Do you mean we can annotate the return type of the match? And yes, I meant investigating if there's a bug in lub computation somewhere which makes it explore more of a search space than it's needed. My main point here is that the code looks totally unreasonable to any Scala user and it triggers really bad behavior in type checker. The ticket is meant to investigate if we can do something about it. Probably the first step would be to create tool that allows detecting those problems, especially in IDE. Iulian said he would like to look into integrating my experiments with AspectJ-based profiling into Eclipse. I added him to watching list of this issue.
        Hide
        Adriaan Moors added a comment -

        Greg, could you have a look at the backport?

        Show
        Adriaan Moors added a comment - Greg, could you have a look at the backport?
        Hide
        Adriaan Moors added a comment -

        i think it should be enough to push down the cast on the outside into each case

        Show
        Adriaan Moors added a comment - i think it should be enough to push down the cast on the outside into each case
        Hide
        Iulian Dragos added a comment -

        The PR was merged, should we close this ticket?

        Show
        Iulian Dragos added a comment - The PR was merged, should we close this ticket?
        Hide
        Jason Zaugg added a comment - - edited

        That optimization just improves things marginally. But I'm out of ideas. LUBs are fundamentally open to these explosions.

        Show
        Jason Zaugg added a comment - - edited That optimization just improves things marginally. But I'm out of ideas. LUBs are fundamentally open to these explosions.
        Hide
        James Iry added a comment -

        2.10.2 is about to be cut. Kicking down the road and un-assigning to foster work stealing.

        Show
        James Iry added a comment - 2.10.2 is about to be cut. Kicking down the road and un-assigning to foster work stealing.
        Hide
        Jason Zaugg added a comment -

        Closing as out of scope as there are no concrete actions in this ticket. LUBs are fundamentally prone this problem.

        Show
        Jason Zaugg added a comment - Closing as out of scope as there are no concrete actions in this ticket. LUBs are fundamentally prone this problem.

          People

          • Assignee:
            Jason Zaugg
            Reporter:
            Grzegorz Kossakowski
          • Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development