Optimizing Method Lookup in Truffle

[Chris Seaton]

I haven't used InlinableCallSite or InlinedCallSite - you'll need someone
else to comment on that. But when I say inlining I mean doing it yourself,
at the level of nodes. So your ifTrue method has no local variables, so you
can actually have an @Child in your inlined-call-site node that refers
directly to a copy of the entire callee tree - so there is no Truffle call
site at all - it's just a bigger tree and Truffle doesn't know or care that
this sub-tree came from somewhere else.

You are right that you probably want to carefully think through a system
for managing this inlining, and not doing it adhoc for just a few methods.
Again, other people might be able to give you more experience there.

Chris


On 9 September 2013 15:31, Stefan Marr <java at stefan-marr.de> wrote:

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