Tail Call Optimization

[Christian Humer]

Your code looks good at first sight. Can you verify that all your call
nodes get inlined properly with -G:+TraceTruffleInlining?
If so there should be no performance hit but a big improvement, as the
whole function should be transformed into a while loop instead of recursive
function calls.
That said, if Truffle does not see the exception thrown and catched in the
same compilation scope there is some price to pay for tail calls atm, yes.


On Wed Jan 14 2015 at 23:50:08 Cristian Esquivias <
cristian.esquivias at gmail.com> wrote:

> Thanks for the help Stefan & Christian. I switched over to passing
> CallTarget objects and following the SimpleLanguage example for an inline
> cache of direct dispatch node. No more opt failures.
>
>
> https://github.com/cesquivias/mumbler/commit/ba4986d33d983b17eaa19892e4a37fb3d42a212c
>
> Unfortunately, even though the direct dispatch node is called, performance
> has taken a big hit. The median time on my microbenchmark increased over
> 50% (360ms to 550ms). Is throwing a flow exception out of function frames
> not very fast?
>
> Microbenchmark:
> https://github.com/cesquivias/mumbler/commit/616fcdea94d50ec8a121ac4da2eb3eef9d5092be
>
> On Tue, Jan 13, 2015 at 4:31 PM, Christian Humer <
> christian.humer at gmail.com> wrote:
>
>> Hi Christian,
>>
>> You should not pass nodes around like values (like you do with the
>> DirectCallNode). Instead let the TailCallException carry a CallTarget.
>>
>> As Stefan pointed out, in the catch block of the TailCallException you
>> are going to need another inline cache similar to the one in
>> SLDirectDispatchNode. To try it out quickly you can also use an
>> IndirectCallNode instead, but don't expect perfect performance from this.
>>
>> - Christian Humer
>>
>>
>>
>> On Wed Jan 14 2015 at 00:18:13 Cristian Esquivias <
>> cristian.esquivias at gmail.com> wrote:
>>
>>> Hi Stefan,
>>>
>>> Thanks for taking a look. So I would create a linked list of dispatch
>>> nodes
>>> like in Simple Language?
>>>
>>> http://hg.openjdk.java.net/graal/graal/file/3a59e1411192/gra
>>> al/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/
>>> SLDirectDispatchNode.java
>>>
>>> Since the function object and the call target don't change, how should I
>>> test for equality between one dispatch node and another? That is, how do
>>> I
>>> know to use one dispatch node versus another?
>>>
>>> Thanks again,
>>> Cristian
>>>
>>> On Tue, Jan 13, 2015 at 3:06 PM, Stefan Marr <java at stefan-marr.de>
>>> wrote:
>>>
>>> > Hi Cristian:
>>> >
>>> > > On 13 Jan 2015, at 23:25, Cristian Esquivias <
>>> > cristian.esquivias at gmail.com> wrote:
>>> > >
>>> > > I'm trying to add tail call optimization to my test language and
>>> have a
>>> > > functional version (no stackoverflows).
>>> > >
>>> > >
>>> > https://github.com/cesquivias/mumbler/commit/3b61f7ccdad7429
>>> d2feac6068b0f57edce6a4151
>>> >
>>> > Looking at the diff/code, I think the issue is the call node that you
>>> pass
>>> > back in the exception.
>>> > At the point where you handle the exception, you’ll probably need to
>>> make
>>> > that node a constant as part of the AST, by using a dispatch node
>>> chain/an
>>> > inline cache.
>>> >
>>> > Best regards
>>> > Stefan
>>> >
>>> >
>>> > --
>>> > Stefan Marr
>>> > INRIA Lille - Nord Europe
>>> > http://stefan-marr.de/research/
>>> >
>>> >
>>> >
>>> >
>>>
>>
>