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@openjdk.java.net http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
