Optimizing Method Lookup in Truffle

Stefan Marr java at stefan-marr.de
Mon Sep 9 07:31:47 PDT 2013 

Hi:

On 09 Sep 2013, at 16:05, Chris Seaton <chris at chrisseaton.com> wrote:

> Ah, I see what you mean. To get around this you will probably have to look at cloning your implementation of ifTrue for each call site. Then each call site calls a different copy of the implementation of ifTrue, which can independently specialise. I haven't done this myself, but I know it's an anticipated use-case of Truffle, and is probably mentioned in the papers.

Yes, that sounds about right.
I was thinking in the same direction, but I am wondering whether there are already 'proven' approaches.

Methods taking blocks aren't exactly uncommon, and I anticipate a greater need for such node inlining specializations.
So, I would like to avoid hardcoding special cases for the boolean #ifTrue: and #ifFalse: because the library contains more of these cases, #whileTrue: being just another example.

Browsing through the Truffle API, if found the InlinableCallSite and InlinedCallSite interfaces. That sounds interesting, but gripping through the graal repository doesn't yield any uses.

Would the idea be to implement these interfaces for instance in the Method node class to enable such inlining/specialization?

Thanks
Stefan




> 
> Chris
> 
> 
> 
> 
> On 9 September 2013 13:20, Stefan Marr <java at stefan-marr.de> wrote:
> Hi Chris:
> 
> On 09 Sep 2013, at 13:57, Chris Seaton <chris at chrisseaton.com> wrote:
> 
> > I guess ifTrue is polymorphic because it's seeing both the True and False classes (that's how smalltalk works isn't it)? If that's the case you could have a variant of cached-message that is cached-message-iftrue that expects to get a Java boolean value and can actually use Java's if. It's like polymorphic-message but is more clever in that it looks at the boolean value rather than thinking about what class it is.
> 
> I have to look into it further, but my intuition tells me that the body of #ifTrue: is the problem.
> The debug output talks about True>>#ifTrue: being invalidated.
> So, I guess, Graal/Truffle try to take this expression:  `^block value` and inline it.
> `block` is here a lambda passed as a parameter. Typical code would look like this:
> 
>   (someVar > 5) ifTrue: [do something].
>   (i < 10)      ifTrue: [do something else].
> 
> If Graal/Truffle constantly try to inline different blocks that would lead to such ongoing recompilations, I guess.
> 
> With the polymorpic inline cache, I guess, I am kind of close to the cached-message-iftrue you propose. That behavior also only started to pop up with the inline caches. So, I guess the problem is rather the block than the polymorphic #ifTrue send itself.
> 
> Best regards
> Stefan
> 
> 
> >
> > Chris
> >
> >
> > On 9 September 2013 12:36, Stefan Marr <java at stefan-marr.de> wrote:
> > Hi Chris:
> >
> > Thanks, I fixed a couple of issues with nodes missing SourceSection info as well, and added the toString.
> > That's a very useful hint. Didn't make that connection before. Guess I should not have used a name as generic as 'Method' to understand what the debug output meant.
> >
> > Now I see what is going on, and one of the offenders is the True>>ifTrue: method node. The method itself is defined as `ifTrue:  block = ( ^block value )`.
> > Another one is Block>>#whileTrue:. Both are most likely megamorphic nodes, and are probably not stabilizing as it would be desirable.
> > How do you handle such cases in other languages?
> >
> > Thanks
> > Stefan
> >
> > On 09 Sep 2013, at 12:57, Chris Seaton <chris at chrisseaton.com> wrote:
> >
> > > Sorry, then you also need to override toString in method.
> > >
> > > Eg https://github.com/smarr/TruffleSOM/pull/1
> > >
> > >
> > > On 9 September 2013 11:30, Chris Seaton <chris at chrisseaton.com> wrote:
> > > It doesn't look like you assignSourceSection to your RootNode (Method class) anywhere. I think Truffle uses that source section to give a name to methods when in the trace outputs, so if you do that you may get the info you want.
> > >
> > > Chris
> > >
> > >
> > > On 8 September 2013 23:20, Stefan Marr <java at stefan-marr.de> wrote:
> > > Hi Thomas:
> > >
> > > On 10 Aug 2013, at 12:53, Thomas Wuerthinger <thomas.wuerthinger at oracle.com> wrote:
> > >
> > > > Stefan,
> > > >
> > > > One of the first steps towards speeding up the implementation is to cache information in the nodes that are useful for subsequent execution. The first candidate for this would be caching the receiverClass and the looked up Invokable instance in the MessageNode class. For this, you need two types of guards:
> > >
> > > Thanks for the hints. I finally got around to implement specialize MessageNodes that do inline caching [1].
> > > I experimented with a simple monomophic cache and a polymorphic one.
> > >
> > > However, I have encountered a few difficulties along the way, and it is not yet working perfectly.
> > >
> > > The first thing I tried was to represent the check for whether the receiver's class is the cached one as an Assumption.
> > > Unfortunately, I ran into complains from the Graal stack that certain code paths were compiled which should not have been.
> > > So, I changed it to something that seems to be close to the advice you gave to Mark:
> > >
> > > if (currentRcvrClass == rcvrClass) { // cache hit
> > >   return invokable.invoke(frame.pack(), rcvr, args);
> > > } else { // not a monomorpic send site
> > >   CompilerDirectives.transferToInterpreter();
> > >   PolymorpicMessageNode poly = new PolymorpicMessageNode(receiver,
> > >     arguments, selector, universe, rcvrClass, invokable, currentRcvrClass);
> > >   this.replace(poly, "It is not a monomorpic send.");
> > >   return doFullSend(frame, rcvr, args, currentRcvrClass);
> > > }
> > >
> > > A check of whether the invokable hasn't changed isn't included yet, because I got trouble again with invalidation of methods.
> > >
> > > First, I had issues with @Child/@Children annotations missing on the tree node fields, and adoptChild not being used consistently, but I figured that out.
> > > Would be great if Truffle could warn about such issues. I guess, a field in a Node subclass that is of the type of a Node is most likely to be a @Child, and it should most likely be assigned with the return value of adoptChild(.) instead of being assigned directly with the parameter. Since I got that wrong, some replace operations did not succeed completely, and I had uninitialized nodes executing more than once, which was unexpected.
> > >
> > > After fixing such issues, I now have a working version, but the Queens and Bounce benchmarks run very slowly because some method gets constantly recompiled.
> > > The output produced by the following command line is not exactly enlightening.
> > >
> > > ./mx.sh --vm server vm -XX:+TraceDeoptimization -G:+TraceTruffleCompilationDetails -Xbootclasspath/a:../som/build/classes som.vm.Universe -cp ../som/Smalltalk ../som/Examples/Benchmarks/Queens.som
> > >
> > > Is there a way to obtain the name of the Method with a given id? Or correlate it with what could be the most likely cause?
> > > While you have been debugging these issues earlier for me, it would be great if you could give me some hints on how to debug them myself.
> > > What's the approach you would take to figure out the reasons for these invalidations?
> > >
> > > Thanks a lot
> > > Stefan
> > >
> > >
> > > [1] https://github.com/smarr/TruffleSOM/commit/a1769ac439b2219006a3b888fe7c672b0f65eadf
> > >
> > >
> > > --
> > > Stefan Marr
> > > Software Languages Lab
> > > Vrije Universiteit Brussel
> > > Pleinlaan 2 / B-1050 Brussels / Belgium
> > > http://soft.vub.ac.be/~smarr
> > > Phone: +32 2 629 2974
> > > Fax:   +32 2 629 3525
> > >
> > >
> > >
> >
> > --
> > Stefan Marr
> > Software Languages Lab
> > Vrije Universiteit Brussel
> > Pleinlaan 2 / B-1050 Brussels / Belgium
> > http://soft.vub.ac.be/~smarr
> > Phone: +32 2 629 2974
> > Fax:   +32 2 629 3525
> >
> >
> 
> --
> Stefan Marr
> Software Languages Lab
> Vrije Universiteit Brussel
> Pleinlaan 2 / B-1050 Brussels / Belgium
> http://soft.vub.ac.be/~smarr
> Phone: +32 2 629 2974
> Fax:   +32 2 629 3525
> 
> 

-- 
Stefan Marr
Software Languages Lab
Vrije Universiteit Brussel
Pleinlaan 2 / B-1050 Brussels / Belgium
http://soft.vub.ac.be/~smarr
Phone: +32 2 629 2974
Fax:   +32 2 629 3525

More information about the graal-dev mailing list