Tail Call Optimization

[Cristian Esquivias]

It looks like the inlining failed because of recursion.

[truffle] inline failed        [(define n ReadArgumentNode at 52525845),
IfNode at 3b94d659] |ASTSize      41/   41 |frequency     99.4917
|score          2.4266 |index=  0, force=N, callSites=221   |reason
recursion

I last pulled/built yesterday so the vm should be up to date.

On Wed, Jan 14, 2015 at 3:55 PM, Christian Humer <christian.humer at gmail.com>
wrote:

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