Looping construction using only MethodHandles

[Charles Oliver Nutter]

This actually came up early this past summer, when I tried to do the
same thing (after Ola Bini showed me the MutableCallSite invoker
trick. You can probably find the thread in July some time.

The bottom line was that even if the handles could get folded into
tail recursion, the call site ends up interfering with the
MethodHandle optimizer's visibility into the graph.

I was as disappointed as you are (or as you will be, once you've read
this). I wish I'd been more involved early in the JSR-292 process and
pushed for a looping construct. Unfortunately that train has sailed,
and I've found no way to do loops (or any sort of backward branching)
using the current set of method handle adapters :(

Here's the tease, for future work on invokedynamic: I believe that if
we had a way to do backward branches, method handles could become a
turing-complete, user-accessible IR for the JVM's JIT.

- Charlie

On Mon, Dec 5, 2011 at 1:06 PM, MLeo <mleodaalder at gmail.com> wrote:
> Hello all,
>
> Over the past few days I've been thinkering with a bit of code that folds
> over the values of some container using some MethodHandle and a 'zero'
> value.
>
> https://gist.github.com/1425706
>
> It's actually an implementation of a strategy to encode higher order
> functions (HOF) without introducing a plethoramorphic callsite (if I
> remember the term correctly). If you squint at it right sort of resembles
> inversion of control. Or it's more like turning a function inside out.
>
> And it mostly works, with suprising result.
> It's not entirely tail call optimized, it still eats stack, but not the same
> amount as an naive unequivalent Java static method that is hand optimized
> for the task (so no HOF).
>
> I'm using the x64 update 2 jdk on Windows Vista with -Xss10m. And the naive
> version bails after a depth of ~110000 and after some optimization it will
> get to ~310000 (after the first invocation!). The fold, on the other hand,
> only bails out after recursing for ~650000 times and gets there nearly
> immediately, the first run is ~10000 lower, but the remainder of invocations
> is consistent (or seems that way, rather, I think it's because not enough
> optimizations have kicked in yet).
>
> Execution time is another story, the POJM (Plain Old Java Method) takes
> ~5ms, while the fold takes ~30ms. Which, now I think some more about it, is
> more or less in line with the previous initial result, but still seems to be
> a bit slow to me.
> After some optimizations have kicked in (when the POJM reaches a depth of
> 310000) the execution times stay roughly the same. So it would appear the
> JVM inlined the POJM 2 or 3 times. Creating the stacktraces doesn't seem to
> impact performance, if I make them recurse 100000 times (so it doesn't
> overflow) then the execution time is roughly the same.
>
> Both ways are tested by invoking them through invokeWithArguments (I haven't
> yet managed to get ASM to produce a test class for me), and I let both try
> to sum an array (turned into an Iterator through
> Arrays.asList(...).iterator()) of a million elements, so both will cause a
> StackOverflowException. The test is to invoke a methods 1000 times (I got a
> bit tired of waiting for a million times) and that I do 6 times (so I take 6
> samples and average across them).
>
>
> Now my question, is there something I can do to make it completely tail call
> optimized? I've tried to 'rotate' the call graph/tree but that obviously
> wouldn't work (it's still a direct recursion, no matter if you do it
> directly or in the combiner of a foldArguments). It seems that it is almost
> completely TCO already, but I haven't found where it's leaking stack. It's
> definitely leaking less stack than a simple recursion.
> Or will we need a special looping combinator here? I initially tried to
> create a while combinator, however it seems that guardWithTest does not
> accept MethodHandles returning void (for the target and fallback).
>
> If this can be made to work (so fully TCO'd, and maybe some massaging from
> HotSpot engineers), then in theory it would allow for functional languages a
> way to monomorphize HOFs.
> For something like map (or fold) it will probably require a guard/PIC for
> the implementations of that method, and those methods need to be compiled in
> such a way so that they become bootstrap methods/factories (see the
> constructor of MethodHandleFoldBuilder.java in the gist) which can then get
> installed in the invocation of that fold.
>
> Thank you for your time,
> --Maarten Daalder
>
> PS.
>
> In case you haven't noticed, I'm not a statistics wizard, so the numbers
> mentioned should be taken only as an early indication and not of any
> statistical significance. YMWV.
>
> Btw, if you were to implement 'map' with this then it would (if I noticed it
> correctly) also reverse the list, or you're going to need to append each
> element to the list, which will probably be slow. This is something I'm
> going to try in the next few days or so.
>
> _______________________________________________
> mlvm-dev mailing list
> mlvm-dev at openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
>