Tail Call Optimization

[Christian Humer]

Hi Cristian,

I did have a closer look at your code and I spotted several problems that
prevented your code to be optimized properly. I prepared a pull request
that should fix those problems.

https://github.com/cesquivias/mumbler/pull/6

Be aware of invalidations if you enable -G:+TraceTruffleCompilation. If
there are some you should review them for problems.

The inline failed message is valid as you are not using a tail call for the
inner lamda in countdown.
 ((lambda (x) (countdown 100) (- x 100))

Here are my benchmark results for the countdown benchmark:

Before my changes:
('computation-time 204)

After my changes:
('computation-time 0)

Have fun!

- Christian Humer


On Thu Jan 15 2015 at 02:07:04 Cristian Esquivias <
cristian.esquivias at gmail.com> wrote:

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