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

Computing lub in WrappedArray.make takes 0.25s #6979

Closed
scabug opened this issue Jan 15, 2013 · 10 comments
Closed

Computing lub in WrappedArray.make takes 0.25s #6979

scabug opened this issue Jan 15, 2013 · 10 comments

Comments

@scabug
Copy link

scabug commented Jan 15, 2013

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.

@scabug
Copy link
Author

scabug commented Jan 15, 2013

@scabug
Copy link
Author

scabug commented Jan 16, 2013

@retronym said:
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: scala/scala#1908, but it is only a slight improvement.

@scabug
Copy link
Author

scabug commented Jan 23, 2013

@adriaanm said (edited on Jan 23, 2013 12:02:31 AM UTC):
to be considered for backporting for 2.10.1-rc1 (fixed in 2.11.0-M2)

@scabug
Copy link
Author

scabug commented Jan 23, 2013

@gkossakowski said:
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.

@scabug
Copy link
Author

scabug commented Jan 23, 2013

@adriaanm said:
Greg, could you have a look at the backport?

@scabug
Copy link
Author

scabug commented Jan 28, 2013

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

@scabug
Copy link
Author

scabug commented Apr 29, 2013

@dragos said:
The PR was merged, should we close this ticket?

@scabug
Copy link
Author

scabug commented Apr 29, 2013

@retronym said (edited on Apr 29, 2013 3:50:04 PM UTC):
That optimization just improves things marginally. But I'm out of ideas. LUBs are fundamentally open to these explosions.

@scabug
Copy link
Author

scabug commented May 20, 2013

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

@scabug
Copy link
Author

scabug commented Nov 21, 2013

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants