Tail calls again?

[Ben Evans]

Hi John and group.

Given the new timelines announced for milestone releases for 7, what are the chances of getting tail calls back on the table for that release?

If the answer is basically "no chance", then what are the roadblocks?

If it could be done, then what would be required and who could help with various stages?

(Apologies if this has been covered recently, pls feel free to point me at a thread - I am rather behind on mail).

Thanks,

Ben

[Kresten Krab Thorup]

FYI, I wrote a blob on how I encode tail recursion in Erjang:
http://bit.ly/6XIma1 .

This technique is applicable (and surprisingly quite fast) if a
language encoding (a) passes a "thread state" to all operations, and
(b) are encoded so that functions do not return primitive types.
Granted - those are severe restrictions, but they apply to Erjang.
Could apply to other languages encoded for the JVM as well.

On Dec 8, 1:58 pm, Ben Evans <benjamin.john.ev...@googlemail.com>
wrote:

[Jon Harrop]

AFAIK Arnold Schwaighofer completed the work a long time ago, implementing TCO
in OpenJDK, but the problem is that the JVM committee do not want to add TCO
to JVMs as standard. I assume the reason is simply benefit vs cost: they do
not believe enough people would use TCO to warrant the work it would require.

If you want JVM+TCO then you should already be able to use OpenJDK. Another
forthcoming option may be VMKit, which is a JVM and CLR built upon LLVM
(which provides TCO so it should be relatively easy to add if it has not been
done already). Or, of course, use or build a completely different VM already
provides TCO...

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

[Jon Harrop]

On Tuesday 08 December 2009 13:39:50 Kresten Krab Thorup wrote:
> FYI, I wrote a blob on how I encode tail recursion in Erjang:
> http://bit.ly/6XIma1 .
>
> This technique is applicable (and surprisingly quite fast) if a
> language encoding (a) passes a "thread state" to all operations, and
> (b) are encoded so that functions do not return primitive types.
> Granted - those are severe restrictions, but they apply to Erjang.
> Could apply to other languages encoded for the JVM as well.

Yes. There are complications with structs and TCO because structs can be stack
allocated in the current stack frame and TCO can delete that stack frame.

[John Cowan]

On Tue, Dec 8, 2009 at 9:53 AM, Jon Harrop <j...@ffconsultancy.com> wrote:

> If you want JVM+TCO then you should already be able to use OpenJDK. Another
> forthcoming option may be VMKit, which is a JVM and CLR built upon LLVM
> (which provides TCO so it should be relatively easy to add if it has not been
> done already). Or, of course, use or build a completely different VM already
> provides TCO...

LLVM provides it only on certain hardwares, and I believe it optimizes
only tail recursion, not general tail calls.

>
> --
> Dr Jon Harrop, Flying Frog Consultancy Ltd.
> http://www.ffconsultancy.com/?e
>

> --
>
> You received this message because you are subscribed to the Google Groups "JVM Languages" group.
> To post to this group, send email to jvm-la...@googlegroups.com.
> To unsubscribe from this group, send email to jvm-language...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/jvm-languages?hl=en.
>
>
>



--
GMail doesn't have rotating .sigs, but you can see mine at
http://www.ccil.org/~cowan/signatures

[Rich Dougherty]

On Wed, Dec 9, 2009 at 7:24 AM, John Cowan <johnw...@gmail.com> wrote:
> LLVM provides it only on certain hardwares, and I believe it optimizes
> only tail recursion, not general tail calls.

There are platform restrictions, but I believe it can work with any
tail call that uses the fastcc calling convention.

Cheers
Rich

--
Rich Dougherty
http://www.richdougherty.com/

[Jon Harrop]

On Tuesday 08 December 2009 18:24:30 John Cowan wrote:
> On Tue, Dec 8, 2009 at 9:53 AM, Jon Harrop <j...@ffconsultancy.com> wrote:
> > If you want JVM+TCO then you should already be able to use OpenJDK.
> > Another forthcoming option may be VMKit, which is a JVM and CLR built
> > upon LLVM (which provides TCO so it should be relatively easy to add if
> > it has not been done already). Or, of course, use or build a completely
> > different VM already provides TCO...
>
> LLVM provides it only on certain hardwares,

LLVM's TCO is fully functional on x86 and x64 but I'm not sure about DEC
Alpha, ARM, Blackfin, Cell, MIPS, CIL, MSP430, 16-bit PIC, PowerPC, Sparc and
XCore.

> and I believe it optimizes only tail recursion, not general tail calls.

No, that is definitely incorrect. TCO was very important to me when I was
trying to choose a foundation to build upon and I carefully tested several
options including the JVM, Mono and LLVM. LLVM was the only choice to offer
real TCO at the time. AFAIK, OpenJDK now offers full TCO (implemented by the
same guy) and Mono's implementation is still fundamentally broken.

[Ben Evans]

Hi Jon,

On Tue, Dec 8, 2009 at 5:53 PM, Jon Harrop <j...@ffconsultancy.com> wrote:

On Tuesday 08 December 2009 12:58:22 Ben Evans wrote:
> Hi John and group.
>
> Given the new timelines announced for milestone releases for 7, what are
> the chances of getting tail calls back on the table for that release?
>
> If the answer is basically "no chance", then what are the roadblocks?
>
> If it could be done, then what would be required and who could help with
> various stages?
>
> (Apologies if this has been covered recently, pls feel free to point me at
> a thread - I am rather behind on mail).

AFAIK Arnold Schwaighofer completed the work a long time ago, implementing TCO
in OpenJDK, but the problem is that the JVM committee do not want to add TCO
to JVMs as standard. I assume the reason is simply benefit vs cost: they do
not believe enough people would use TCO to warrant the work it would require.

 I put this question to the group at the Java 7 BOF at Devoxx and Alex Buckley gave an interesting answer - that people basically feel that the patchset is sound, but that what's missing is people prepared to run with it, test it out, report back, etc.

If that's the case, then what do people on this group think? Is there enough demand for it for people to commit time to it? It's a long time till Java 8, after all.

Charlie: Would you use it for JRuby if it was available?

Ben

[Attila Szegedi]

I think it would be really valuable to have it. Since JVM has now definitely moved away from the Java-as-the-only-language, availability of TCO would allow languages that semantically assume it to be ported to JVM.

Attila.

[Jon Harrop]

On Tuesday 08 December 2009 19:50:07 Ben Evans wrote:
> I put this question to the group at the Java 7 BOF at Devoxx and Alex
> Buckley gave an interesting answer - that people basically feel that the
> patchset is sound, but that what's missing is people prepared to run with
> it, test it out, report back, etc.
>
> If that's the case, then what do people on this group think? Is there
> enough demand for it for people to commit time to it? It's a long time till
> Java 8, after all.
>
> Charlie: Would you use it for JRuby if it was available?

I'm sure Scala and Clojure would leap on it and they probably already have
tens of thousands of users and hundreds of industrial users behind them.

[Jon Harrop]

On Tuesday 08 December 2009 20:19:53 Attila Szegedi wrote:
> I think it would be really valuable to have it. Since JVM has now
> definitely moved away from the Java-as-the-only-language, availability of
> TCO would allow languages that semantically assume it to be ported to JVM.

You can already port them by using the same workarounds that FPLs targetting C
have used (i.e. goto when possible and trampolines otherwise). They'll just
be slow and uninteroperable but lots of things are already slow because of
the lack of structs which cannot be worked around.

[Patrick Wright]

>  I put this question to the group at the Java 7 BOF at Devoxx and Alex
> Buckley gave an interesting answer - that people basically feel that the
> patchset is sound, but that what's missing is people prepared to run with
> it, test it out, report back, etc.
>
> If that's the case, then what do people on this group think? Is there enough
> demand for it for people to commit time to it? It's a long time till Java 8,
> after all.
>
> Charlie: Would you use it for JRuby if it was available?

If you post it, they will come, I think. If we can get someone or
several people to help set up a clean build of MLVM with the tail call
patches, then we can either distribute a binary or even a complete VM
(VMWare, Parallels) image people can play with. Once it's out there
lang authors will need to work out the bits to push the extra
instruction to mark tail calls, and we can get some feedback. Even
negative feedback coming from several languages would be welcome, I
think.

I think the main step is getting at least an x86 MLVM build posted
somewhere, then notifying the various lang authors that it's
available. Ideally there would be a build server but that's probably
too much to hope for.

Not that I'm saying I have the time, just wanted to helpfully point
out a way forward :)
Patrick

[Charles Oliver Nutter]

On Tue, Dec 8, 2009 at 1:50 PM, Ben Evans
<benjamin....@googlemail.com> wrote:
>  I put this question to the group at the Java 7 BOF at Devoxx and Alex
> Buckley gave an interesting answer - that people basically feel that the
> patchset is sound, but that what's missing is people prepared to run with
> it, test it out, report back, etc.
>
> If that's the case, then what do people on this group think? Is there enough
> demand for it for people to commit time to it? It's a long time till Java 8,
> after all.
>
> Charlie: Would you use it for JRuby if it was available?

A couple points:

* TCO isn't part of the Ruby language, so there would need to be some
discussion about whether us doing TCO would diverge from the language
specification itself. I'd love to see it though. And I'd love for the
JVM to have it so that when they eventually *do* add TCO, we wouldn't
have an impossible time implementing it.
* The functional guys would probably love to have TCO right now. But
it's a bitch to build OpenJDK+patches for many folks.
* John Rose posted recently about invokedynamic + tail calls; I have
not had a chance to read it yet.

I think it should get rolled in as a JVM feature even if Java doesn't
support it right now, because other languages coming down the pike
*will* want it. Honestly...we have a working patch. Why not?

And while we're at it, we should take up a collection to get fixnums
and value types added.

- Charlie

[Charles Oliver Nutter]

On Tue, Dec 8, 2009 at 2:50 PM, Patrick Wright <pdou...@gmail.com> wrote:
> I think the main step is getting at least an x86 MLVM build posted
> somewhere, then notifying the various lang authors that it's
> available. Ideally there would be a build server but that's probably
> too much to hope for.

JRuby has been on the forefront of testing out new JVM features from
the MLVM project, but even we haven't had a chance to play with tail
calls yet. It certainly requires resources.

Either way, though...I think they should be added so we have the
option to use them. It's a chicken/egg thing...languages don't support
TCO because the JVM doesn't. JVM doesn't support TCO because the
languages don't use it. Something's got to give, and since we have a
working patch...shove it in.

- Charlie

[Tom Davies]

On Dec 10, 6:48 am, Charles Oliver Nutter <head...@headius.com> wrote:
> since we have a
> working patch...shove it in.

Do we have an up to date working patch in the mlvm repo?

[Rémi Forax]

About the tail call patch:

Le 10/12/2009 05:37, Tom Davies a �crit :

I've just tested the patch named "eager", and it doesn't work out of the
box.
You can't apply it without modify it (at least the hotspot patch,
I haven't tested the langtools patch because I've my own backend)
It was written against a revision that is too old to be handled
by the mercurial patch mechanism.

Moreover, the series file doesn't show the changeset used to write
the patch, so you can't also go backward and apply the patch to
the old revision because you don't know it :(

R�mi

[Tom Davies]

On Dec 10, 6:35 pm, Rémi Forax <fo...@univ-mlv.fr> wrote:
> I've just tested the patch named "eager", and it doesn't work out of the
> box.

That's Arnold Schwaighofer's patch?

[Rémi Forax]

Le 10/12/2009 09:24, Tom Davies a �crit :

>
> On Dec 10, 6:35 pm, R�mi Forax<fo...@univ-mlv.fr> wrote:
>
>> I've just tested the patch named "eager", and it doesn't work out of the
>> box.
>>
> That's Arnold Schwaighofer's patch?
>

yes, in fact Arnold creates two patches,
see http://hg.openjdk.java.net/mlvm/mlvm/hotspot/file/74b2b52ed9cf/tailc.txt

R�mi

[Charles Oliver Nutter]

On Thu, Dec 10, 2009 at 1:35 AM, Rémi Forax <fo...@univ-mlv.fr> wrote:
> I've just tested the patch named "eager", and it doesn't work out of the
> box.
> You can't apply it without modify it (at least the hotspot patch,
> I haven't tested the langtools patch because I've my own backend)
> It was written against a revision that is too old to be handled
> by the mercurial patch mechanism.
>
> Moreover, the series file doesn't show the changeset used to write
> the patch, so you can't also go backward and apply the patch to
> the old revision because you don't know it :(

That may be true, but it was a working patch against *some* revision.
It should be possible to update it, if people show enough interest in
getting it to work.

- Charlie

[Per Bothner]

On 12/08/2009 05:39 AM, Kresten Krab Thorup wrote:
> FYI, I wrote a blob on how I encode tail recursion in Erjang:
> http://bit.ly/6XIma1 .

The "trampoline" mechanism you describe is basically what Kawa
does when in --full-tailcalls mode - the basic idea is of course
quite old.

(I suspect Erland's parameter-passing is faster, as Kawa could
do with some tuning here. I've concentrated on the performance
of the default --no-full-tailcalls mode.)

Kawa does support "state-machine semantics" where mutually recursive
functions are compiled to gotos, even when in the --no-full-tailcalls
mode. (This is fairly recent - it was implemented this Summer.)

Rather than a single function per class, Kawa compiles multiple
functions to a class, which reduces static footprint, at the cost of an
extra level of indirection (but only when calling an unknown function).

This link has a description of how Kawa implements functions, though it
is very sparse on how tail-call-elimination works:
http://www.gnu.org/software/kawa/internals/procedures.html
--
--Per Bothner
p...@bothner.com http://per.bothner.com/

[Kresten Krab Thorup]

Cool! Nice that you did so extensive writeup on your encoding.

Yes, it makes a big performance difference if do not have to allocate
a new CpsFrame to start a tail call.
I am guessing here, but I think the performance increase is not just
because of GC, but also because it gives better data cache locality.
In Erjang the CpsFrame structure you write about is inlined into the
EProc process object which is passed around in all calls.
Sometimes it would be great to be able to debug the code the JVM
generates. Sigh.

Kresten

[Charles Oliver Nutter]

On Mon, Dec 14, 2009 at 6:34 AM, Kresten Krab Thorup <kr...@trifork.com> wrote:
> Cool!  Nice that you did so extensive writeup on your encoding.
>
> Yes, it makes a big performance difference if do not have to allocate
> a new CpsFrame to start a tail call.
> I am guessing here, but I think the performance increase is not just
> because of GC, but also because it gives better data cache locality.
> In Erjang the CpsFrame structure you write about is inlined into the
> EProc process object which is passed around in all calls.
> Sometimes it would be great to be able to debug the code the JVM
> generates. Sigh.

Debug it or just read it? There are numerous options available to get
you assembly output, if that's what you want. I've read more of it
than I like to admit...

- Charlie

[Kresten Krab Thorup]

How do you get the emitted code? I did not know you can do that. Can
you get description of what is inlined and why also?

[Peter Veentjer]

I also have troubles figuring out how 'smart' the JIT is (or how smart
the CPU is).

So getting access to the generated assembler would be a big step
forward for me as well.

ps:
although I'm not working on a language, I'm working on a library
(http://multiverse.googlecode.com)
that could be seen as a language feature (software transactional memory).

[Ben Evans]

Hi Peter,

Try a combination like -XX:+UnlockDiagnosticVMOptions
-XX:+PrintNMethods -XX:+PrintSignatureHandlers -XX:+PrintAssembly

Or this link:

http://wikis.sun.com/display/HotSpotInternals/PrintAssembly

This should work on 6u18 and above.

Thanks,

Ben

[Peter Veentjer]

Hi Ben,

thanks for the information. I have just run an application with these
parameters (and played with some using the link you added). But I
don't get the actual assembler generated (or I can't recognise it); I
do get a lot of output however.

I would expect a lot of i386+ assembler statements (I have done some
assembler many many years ago).

This is a fragment:

OopMap{ebp=Oop [256]=Oop [40]=Oop [44]=Oop [48]=Oop [56]=Oop [96]=Oop
[124]=Oop [128]=Oop [180]=Oop [216]=Oop off=31380}
#442
OopMap{ebp=Oop [256]=Oop [40]=Oop [44]=Oop [48]=Oop [56]=Oop [96]=Oop
[124]=Oop [128]=Oop [180]=Oop [216]=Oop off=31396}
#443
OopMap{ebp=Oop [256]=Oop [40]=Oop [44]=Oop [48]=Oop [56]=Oop [96]=Oop
[124]=Oop [128]=Oop [180]=Oop [216]=Oop off=31412}
#444
OopMap{ebp=Oop [256]=Oop [40]=Oop [44]=Oop [48]=Oop [56]=Oop [96]=Oop
[124]=Oop [128]=Oop [180]=Oop [216]=Oop off=31428}
#445
OopMap{[256]=Oop [24]=Oop [40]=Oop [44]=Oop [48]=Oop [56]=Oop [96]=Oop
[124]=Oop [128]=Oop [180]=Oop [216]=Oop off=31444}
#446
OopMap{off=31460}
#447
OopMap{off=31476}
#448
OopMap{off=31492}
#449
OopMap{off=31508}
#450
OopMap{off=31524}
#451
OopMap{off=31540}
#452
OopMap{off=31556}
#453
OopMap{off=31572}
#454
OopMap{off=31588}
#455
OopMap{off=31604}
#456
OopMap{off=31620}
#457
OopMap{off=31636}
#458
OopMap{off=31652}
#459
OopMap{[256]=Oop [40]=Oop [44]=Oop [48]=Oop [96]=Oop [112]=Oop
[132]=Oop [156]=Oop [176]=Oop [180]=Oop [216]=Oop off=31668}
#460
OopMap{off=31684}
#461
OopMap{off=31700}
#462
OopMap{off=31716}
#463
OopMap{off=31732}
#464
OopMap{off=31748}
#465
OopMap{off=31764}
#466
OopMap{off=31780}
#467
OopMap{off=31796}
#468
OopMap{off=31812}
#469
OopMap{off=31828}
#470
OopMap{off=31844}
#471
OopMap{off=31868}
#472
OopMap{off=31892}
#473
OopMap{[256]=Oop [24]=Oop [40]=Oop [44]=Oop [48]=Oop [92]=Oop
[216]=Oop off=31908}
#474
OopMap{off=31932}
#475
OopMap{off=31948}
#476
OopMap{off=31964}
#477
OopMap{off=31980}
#478
OopMap{off=31996}
#479
OopMap{off=32012}
#480
OopMap{off=32028}
#481
OopMap{off=32044}
#482
OopMap{off=32060}
#483
OopMap{off=32076}
#484
OopMap{off=32096}
#485
OopMap{off=32116}
#486
OopMap{off=32132}
#487
OopMap{[52]=Oop [72]=Oop [108]=Oop [148]=Oop off=32148}
#488
OopMap{off=32164}
#489
OopMap{off=32180}
#490
OopMap{off=32196}
#491
OopMap{off=32212}
#492
OopMap{off=32228}
#493
OopMap{off=32244}
#494
OopMap{off=32260}
#495
OopMap{off=32276}
#496
OopMap{off=32292}
#497
OopMap{off=32308}
#498
OopMap{off=32324}
#499
OopMap{off=32340}
#500
OopMap{off=32356}
Compiled (c2) 82 nmethod (2)
org.multiverse.stms.AbstractTransaction::getStatus (30 bytes)
total in heap [0xb3ab7a88,0xb3ab7bf8] = 368
relocation [0xb3ab7b3c,0xb3ab7b54] = 24
main code [0xb3ab7b60,0xb3ab7bc0] = 96
stub code [0xb3ab7bc0,0xb3ab7bcf] = 15
constants [0xb3ab7bcf,0xb3ab7bd0] = 1
scopes data [0xb3ab7bd0,0xb3ab7bd4] = 4
scopes pcs [0xb3ab7bd4,0xb3ab7bec] = 24
dependencies [0xb3ab7bec,0xb3ab7bf0] = 4
oops [0xb3ab7bf0,0xb3ab7bf8] = 8
OopMapSet contains 0 OopMaps

Compiled (c2) 83 nmethod (2)
java.util.Formatter$FormatSpecifier::checkBadFlags (39 bytes)
total in heap [0xb3ac12c8,0xb3ac15d4] = 780
relocation [0xb3ac137c,0xb3ac13ac] = 48
main code [0xb3ac13c0,0xb3ac14c0] = 256
stub code [0xb3ac14c0,0xb3ac14d9] = 25
constants [0xb3ac14d9,0xb3ac14dc] = 3
scopes data [0xb3ac14dc,0xb3ac1540] = 100
scopes pcs [0xb3ac1540,0xb3ac1594] = 84
dependencies [0xb3ac1594,0xb3ac159c] = 8
handler table [0xb3ac159c,0xb3ac15b4] = 24
nul chk table [0xb3ac15b4,0xb3ac15c8] = 20

[Ben Evans]

Hi Peter,

Do you have the hsdis-base .so (disassembler plugin) from:

http://kenai.com/projects/base-hsdis/downloads

installed in your JVM? If so, can you check if you're getting a message about "Plugin disabled" when the JVM starts?

Thanks,

Ben

[Charles Oliver Nutter]

On Tue, Dec 15, 2009 at 10:13 AM, Ben Evans
<benjamin....@googlemail.com> wrote:
> Hi Peter,
>
> Try a combination like -XX:+UnlockDiagnosticVMOptions
> -XX:+PrintNMethods -XX:+PrintSignatureHandlers -XX:+PrintAssembly

You may actually get better information from +PrintOptoAssembly, which
has some annotated information about where the code is coming from.
It's only in (fast)debug builds though. I usually use
PrintOptoAssembly.

I believe John Rose was going to try to add more annotated data to the
PrintAssembly output (or otherwise make more annotated data available
some how) but I'm not sure if there's a flag or process for getting
that.

- Charlie