thinking about proper implementation of tail calls

[Alexander Turner]

Hi,

Other than overcoming the limits of the size of the
dispatch trampoline method, it is not clear to me what benefits for method
splitting tail calls gives one. The challenges of method splitting are
working out an appropriate size to which to split for maximum performance,
processing nested and overlapping jumps, managing the stack and making the
logic that does all of these things scale better than n**2. Non of these
get any easier with tail calls.

If one has a programming language like Magik, in which jump logic is mainly
expressed as closure like structures rather than jump instructions and so
nested jumps do no happen, then tail calls make a lot of sense for
splitting. However, the moment you get a structure like:

1  if_icmpeq 3
2 if_icmpeq 4
3 if_icmpeq 2
4 ...

Above we have interlocked jumps and unpicking that is quite a challenge.
There comes a point at which using a tail call would require more than one
tail closure to be passed and then those called conditionally - or at least
I believe that to be the case.

One the other hand - I do see tail calls as very important in another area.
As immutable structures become more and more important for free threading
in multi-threaded systems, tail calls become more important to overcome the
current problems with recursion. I have already found that the limited tail
call optimization available in the MS C++ compiler has helped in some
structures, but sadly it does not work with lambdas yet.

A concrete example is in Magik. We use immutable trie structures to handle
the global name space. By far the cleanest way to implement such a thing is
via recursion. Whilst I wrote our implementation to be tail recursive, it
is not, in Java, compiled that way. This makes the implementation much more
expensive than the code would suggest.

So, my vote goes to considering tail calls as an important feature moving
forward for free threading models. I am not so convinced on method
splitting though.

Kind regards - AJ

PS - if you are wondering why I know about method splitting but am not able
to say how it was done in the project I worked on:
http://www.freepatentsonline.com/y2012/0151457.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/mlvm-dev/attachments/20120831/413569ea/attachment-0001.html