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

@specialize vs. @inline: @specialize wins (unnecessarily) #5005

Closed
scabug opened this issue Sep 18, 2011 · 25 comments
Closed

@specialize vs. @inline: @specialize wins (unnecessarily) #5005

scabug opened this issue Sep 18, 2011 · 25 comments
Assignees
Labels
Milestone

Comments

@scabug
Copy link

@scabug scabug commented Sep 18, 2011

The following demonstrates a method which is inlined until its class is specialized, after which it isn't, because the specialized version of the (declared final) method is not final. As a debugging aid, the specialized one is inlined if the call site is in a constructor, just not if it's in the body of a regular method.

class C[U]() {
  @inline final def apply(x: U): U = x
}

class C2[@specialized(Boolean) U]() {
  @inline final def apply(x: U): U = x
}

class B {
  private val cNormal = new C[Boolean]()
  private val cSpec   = new C2[Boolean]()
  
  final def m1 = cNormal(true)
  final def m2 = cSpec(true)
  // ./a.scala:14: warning: Could not inline required method apply$mcZ$sp because it can be overridden.
  //   final def m2 = cSpec(true)
  //                       ^
  // one warning found

  // however, here it inlines
  cNormal(true)
  cSpec(true)
}
@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Sep 18, 2011

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Sep 19, 2011

@paulp said (edited on Sep 19, 2011 3:12:07 AM UTC):
And on top of this, attempting to compile the same file a second time (that is, with class files present) crashes. See #5006.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Oct 11, 2011

@paulp said:
Assigning to meeting because I think that a) one of the few classes I would specialize with no reservations is Option and b) we cannot even consider specializing Option unless this is fixed, because we would be gifted with hundreds of getOrElse closure objects which are presently eliminated.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Feb 14, 2012

@non said (edited on Feb 14, 2012 2:30:36 PM UTC):
Because of the way specialized classes (e.g. C2$mcZ$sp) subclass the parent (e.g. C2) C2's methods obviously can't be final (IIRC "final" is removed during "specialize"). But the compiler could remember which methods were marked final/@inline and mark the specialized subclass's methods appropriately.

By itself this wouldn't fix your issue with Option. But using AnyRef specialization we can ensure that all uses of C2 will be rerouted to a specialized subclass (whose methods would correctly be final). I think this would fix this bug with regards to Option, although it wouldn't fix it in general. To fix it in general (IMO) would require always using AnyRef specialization (which seems like an OK plan to me) or to do a bigger change to how specialization works (maybe too big).

Am I missing something? What do you think?

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Feb 15, 2012

@non said:
It turns out that actually, we don't even need to remove "final" from methods even when we're going to override them--I noticed this while working on this issue. Not sure if there are larger impliciations, but leaving final on the base class (and thus copying it to specialized subclasses) seems to actually preserve the original author's intention (not to let other classes subclass) better than what we're current doing (removing final), since leaving final alone doesn't seem to cause any problems with method overriding.

One weird thing I noticed is that even when all the apply methods are marked final (and correctly inlined in m2) they are not inlined in B's (although scalac doesn't complain about this). In fact, when I looked more closely I saw that they were never inlined in the first place (in 2.9.1, or master, or my branch).

I'm not sure whether Paul actually looked in B's bytecode and saw the apply calls being inlined, or if it was the absence of a warning which made him assuming it was happening. But I don't see any evidence that they were ever inlined in 2.9.1.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Feb 15, 2012

@non said:
I've submitted a pull request (a one line change) which resolves this particular issue, although there are related issues around inlining (e.g. that inlining in B's constructor isn't working) which are not resolved.

I will open a new issue for that particular problem.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Feb 15, 2012

@ijuma said:
"It turns out that actually, we don't even need to remove "final" from methods even when we're going to override them--I noticed this while working on this issue."

Have you checked that the verifier does not complain?

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Feb 15, 2012

@non said:
Hi Ismael,

So... apologies, this actually doesn't work. I must have been running the wrong code. I just double-checked and indeed the JVM notices this and complains. So I will need to refine the patch a bit.

Thanks.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Feb 15, 2012

@paulp said:
I was sufficiently skeptical that there wasn't much danger of my acting on the patch. If the jvm was cool with that and I hadn't heard about it by now, I'd need to hang out with a better class of people.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Feb 15, 2012

@non said:
Glad you were skeptical of my boneheadedness Paul!

I have a new patch which is less-completely-broken. It should fix the handling of final/@inline (i.e. letting classes like C2$mcZ$sp keep final on apply and apply$mcZ$sp) as well as removing @inline when removing final (to prevent annoying warnings).

Unfortunately, there are two other things that your example hits:

  1. The inferred type of your lazy vals and defs is "C2" which means that ultimately the call will be "C2.apply$mcZ$sp" which still cannot be final/@inline (because it's in C2 and not C2$mcZ$sp). I'm not sure how feasible it is to "re-type" methods/vals whose type is a specialized class.

  2. Even if you try doing new C2Bool(true), which does correctly call C2$mcZ$sp.apply$mcZ$sp(true), it doesn't get inlined. Not sure why.

Anyway, I think the patch should be ok, but didn't want you to think that I had "fixed" this whole issue. What do you see as the scope of #5005 anyway? It encompasses (at least) 3 separate bugs in specialization, IMO.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Feb 15, 2012

@VladUreche said:
In the example above no inlining will take place, even after adding inline and final flags to specialized members for two reasons:

  • as Erik pointed out, the inferred type for the accessor is C2[Boolean] (instead of C2$mcZ$sp) + accessor is not final and not inlined => intra-procedural TFA will infer C2[Boolean] for the stack slot
  • the inliner doesn't consider the constructor basic blocks as possible inlining targets (that's the actual reason there's no message for the cNormal(true) and cSpec(true))

A test case one could use here is:

class C2[@specialized(Boolean) U]() {
  @inline final def apply(x: U): U = x
}

class B {
  (new C2[Boolean]())(true)
}
@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Feb 16, 2012

@paulp said:
To background the original example a little, I wrote that after seeing the Option behavior. Unfortunately I sprinkled it with red herrings with the constructor business and the poor correspondence between the compiler warnings and the actual inlining. For the issue which motivated the ticket, the elimination of getOrElse closures from Option, there's no question the inlining was, and then wasn't, taking place. Thanks for figuring out the confounders.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 3, 2012

@magarciaEPFL said:
Related: I'm working on a revamped type-flow analysis to track exact types as resulting from new. With that, a (future) version of Inliner could determine additional target methods, even if not marked final. Here's that work in progress:

magarciaEPFL/scala@master...SinglePassTFA

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 5, 2012

@gkossakowski said:
Is this issue being worked on? I just hit this issue while trying to inline collection operations. I have another example where specialization doesn't work with inlining:

class SimpleCol[A](x: A) {
  @inline
  final def filter(p: A => Boolean): SimpleCol[A] = if (p(x)) this else null
  def isEmpty: Boolean = ???
}

class A(xs: SimpleCol[A], val a: Int) {
  @inline
  final def filter(p: A => Boolean): A =
    if (!xs.filter(p).isEmpty) this else
    if (p(this)) this
    else null

  def foo() = filter(x => x.a > 0)
}

I you compile it with -no-specialization then everything will get inlined into foo and closure will get eliminated. Otherwise the p(this) will remain (it's specialized apply) not inlined and the whole closure allocation is not eliminated.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 5, 2012

@VladUreche said:
Hi Greg, unfortunately it's not being worked on at the moment, as I've been spending 100% of my time with scaladoc, to get it (almost) bug-free by 2.10. It would be great if you took the time to fix it.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 5, 2012

@magarciaEPFL said:

For the snippet in [comment-58618 | https://issues.scala-lang.org/browse/SI-5005?focusedCommentId=58618&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-58618] , the following non-inlined callsite keeps the closure alive (ie instantiated)

  5: pred: List(13) succs: List(8, 7) flags: <closed>
    17	LOAD_LOCAL(field p1)
    17	THIS(Object)
    17	CALL_METHOD scala.Function1.apply$mcZL$sp (dynamic)
    17	CZJUMP (BOOL)NE ? 7 : 8

using -Ydebug -Ylog:inliner to get more detailed log output.

In turn, the following suggests no ICode is loaded for that closure method (although type-flow gets right the most specific type of the closure, A$$anonfun$foo$1 , and thus could load bytecode for it)

[log inliner] shouldLoadImplFor: anonymous class A$$anonfun$foo$1.method apply$mcZL$sp: false
[log inliner] Treating CALL_METHOD scala.Function1.apply$mcZL$sp (dynamic)
	receiver: anonymous class A$$anonfun$foo$1
	icodes.available: false
	concreteMethod.isEffectivelyFinal: false

The condition that fails for loading said ICode is sym.isEffectivelyFinal below:

    /** Should method 'sym' being called in 'receiver' be loaded from disk? */
    def shouldLoadImplFor(sym: Symbol, receiver: Symbol): Boolean = {
      def alwaysLoad    = (receiver.enclosingPackage == RuntimePackage) || (receiver == PredefModule.moduleClass)
      def loadCondition = sym.isEffectivelyFinal && isMonadicMethod(sym) && isHigherOrderMethod(sym)

      val res = hasInline(sym) || alwaysLoad || loadCondition
      debuglog("shouldLoadImplFor: " + receiver + "." + sym + ": " + res)
      res
    }

To recap, for inlining of an specialized apply method to happen, it's a necessary condition that shouldLoadImplFor succeeds for that method's symbol, and currently it doesn't because sym.isEffectivelyFinal is false.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 5, 2012

@magarciaEPFL said:
More background info, this time from javap. There's no override in A$$anonfun$foo$1 for apply$mcZL$sp:

public final class A$$anonfun$foo$1 extends scala.runtime.AbstractFunction1$mcZL$sp implements scala.Serializable{
    public static final long serialVersionUID;
    public static {};
    public final boolean apply(A);
    public final java.lang.Object apply(java.lang.Object);
    public final boolean apply(java.lang.Object);
    public A$$anonfun$foo$1(A);
}
@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 5, 2012

@magarciaEPFL said:
For argument's sake, let's say the decision had been made instead to load ICode for A$$anonfun$foo$1.apply$mcZL$sp. The following shows the implementation A$$anonfun$foo$1 inherits from scala.runtime.AbstractFunction1:

Compiled from "AbstractFunction1.scala"
public abstract class scala.runtime.AbstractFunction1 extends java.lang.Object implements scala.Function1{

 . . . 

public boolean apply$mcZL$sp(java.lang.Object);
  Code:
   0:	aload_0
   1:	aload_1
   2:	invokestatic	#164; //Method scala/Function1$class.apply$mcZL$sp:(Lscala/Function1;Ljava/lang/Object;)Z
   5:	ireturn

Given that it's just a forwarder, for the closure to be eliminated the target method in scala.Function1$class would also have to be inlined, ie:

Compiled from "Function1.scala"
public abstract class scala.Function1$class extends java.lang.Object{
public static scala.Function1 compose(scala.Function1, scala.Function1);

 . . . 

public static boolean apply$mcZL$sp(scala.Function1, java.lang.Object);
  Code:
   0:	aload_0
   1:	aload_1
   2:	invokeinterface	#39,  2; //InterfaceMethod scala/Function1.apply:(Ljava/lang/Object;)Ljava/lang/Object;
   7:	invokestatic	#43; //Method scala/runtime/BoxesRunTime.unboxToBoolean:(Ljava/lang/Object;)Z
   10:	ireturn

Alone the resulting code size (if inlining handles forwarding methods as any other) would make the heuristics stop inlining sometime before getting there.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 5, 2012

@magarciaEPFL said:
Thinking a bit more about this, given an invocation of shouldLoadImplFor with arguments:

  sym      == method apply$mcZL$sp
  receiver == anonymous class A$$anonfun$foo$1

as above, then sym.isEffectivelyFinal is doing the right thing when reporting false.

Rather, what shouldLoadImplFor does not check is:

  • a final receiver implies that non-overridden methods must be inherited from a superclass

The question then is whether ICode can be loaded for receiver and its superclasses (if not available). For inspiration one can look at:

    def lookupIMethod(meth: Symbol, receiver: Symbol): Option[IMethod] = {
      def tryParent(sym: Symbol) = icodes icode sym flatMap (_ lookupMethod meth)

      (receiver.info.baseClasses.iterator map tryParent find (_.isDefined)).flatten
    }

In the case at hand, an attempt is made to load ICode for concreteMethod.enclosingClass, which doesn't help.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 5, 2012

@gkossakowski said:
Miguel, thanks for digging into this more.

I spent the evening with Alex on the problem I mentioned in my comment and it turns out to be problem with specialization, specialized bridge generation and separate compilation. Basically, we do not preserve enough information between compiler runs (in pickler) and specialization gets very confused.

I'll create another ticket with our findings tomorrow.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 6, 2012

@axel22 said:
Here's the branch for that change (I've put annotation checking in the UnPickler too):
https://github.com/axel22/scala-github/tree/feature/spec-pickling

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 6, 2012

@gkossakowski said:
Check #6035 for details on why specialization gets confused and that leads to breaking inlining (due to missing specialized bridge).

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 7, 2012

@gkossakowski said:
I verified that if we fix both SI-6035 and SI-6043 then we get proper inlining in example I have given in the comment above (https://issues.scala-lang.org/browse/SI-5005?focusedCommentId=58618&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-58618).

Conclusions are the following:

  • inlining doesn't need any fixing
  • once we fix two bugs in specialization both specialization and inlining do work together
@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 14, 2012

@non said:
So I went back and revisited this bug based on the state of specialization in master.

My findings are:

  1. Vlad's test case from February 15th seems to be working in master (that is, there's no explicit call to apply)
  2. Most of Paul's examples are not inlining
  3. Greg's issue is linked to a different bug (#6043) which I think is a different issue than some of the others here.

So, I think it's worth closing this bug and opening a new bug (if necessary) for some of the issues specific to Paul's example (i.e. inferred type of accessors related to inlining) since right now the bug's state is a bit confused.

If we aren't going to close it, I'd like to get consensus on the test case for this bug (i.e. a source file and the desired output) since right now I'm not clear what it would take to consider it "fixed"

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Nov 21, 2013

@retronym said:
I'm following Erik's suggestion to close this ticket.

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

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.