Looping construction using only MethodHandles

[MLeo]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/mlvm-dev/attachments/20111205/f3cab31a/attachment.html