JVM 7 support (invokedynamic)

[Tal Liron]

Hey folks,

I just want to reassure y'all that I am working on this. It took a while to create a test environment: one of the challenges of using invokedynamic is that the Java language does not support it; so the best way to test right now is with ASM 4.0, which is still not officially released. Documentation on the opcode is also somewhat scattered, and mostly out of date, since JSR-292 has changed quite a bit until the final release. The JRuby folk are definitely at the cutting edge of this right (well, after all, JRuby's John Rose is the key mover and architect behind the JSR), and I'm trying to learn from their implementation. Right now I'm working on a code tree outside the main Clojure source, and once that seems to work, I will try to merge it into a branch.

So, it's not *quite* as easy as I hoped, but I still think it will be much easier to use invokedynamic in Clojure than in JRuby.

I'll keep the mailing list updated on my (slow) progress, and will definitely make the code public once it becomes ... presentable.

[Ken Wesson]

Just out of curiosity, what will this actually enable? Optimizations?
What can we expect might perform faster -- calling closures?
Functional function-calls such as map, reduce, etc.? Multimethods,
protocols, and things like that?

--
Protege: What is this seething mass of parentheses?!
Master: Your father's Lisp REPL. This is the language of a true
hacker. Not as clumsy or random as C++; a language for a more
civilized age.

[Paulo Pinto]

invokedynamic reduces drastically the lookup times you require in
dynamic languages. The JVM and JIT understand what you are trying
to do and can optimize the invocation.

Currently all dynamic languages targeting the JVM generate code
that cannot be easily optimized by the JVM before invokedynamic
was available.

--
Paulo

On Aug 25, 9:59 am, Ken Wesson <kwess...@gmail.com> wrote:

[Laurent PETIT]

This does not really answer Ken's question, does it ?

2011/8/25 Paulo Pinto <paulo....@gmail.com>

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[Meikel Brandmeyer (kotarak)]

Hi,

Disclaimer: I have no clue whatsoever about the low-level JVM stuff.

I remember Rich saying in one of his talks/interviews, that invokedynamic is not very interesting for Clojure and that Clojure won't really benefit from it. I'm far from understanding these things. So details on what's improved would be very interesting, I guess.

Sincerely
Meikel

[Aaron Bedra]

That's correct. That is why Clojure/core hasn't prioritized this work.

Cheers,

Aaron Bedra
--
Clojure/core
http://clojure.com

[Phil Hagelberg]

On Thu, Aug 25, 2011 at 5:18 AM, Paulo Pinto <paulo....@gmail.com> wrote:
> invokedynamic reduces drastically the lookup times you require in
> dynamic languages. The JVM and JIT understand what you are trying
> to do and can optimize the invocation.

It's important to note that this only applies to method calls, not
function invocations.

> Currently all dynamic languages targeting the JVM generate code
> that cannot be easily optimized by the JVM before invokedynamic
> was available.

That's not really true; it's easy in Clojure to optimize with type
hints. Since Ruby isn't designed to run on the JVM, it doesn't have
any syntax for type hints to avoid reflective calls. I believe method
calls that use invokedynamic are much faster than reflective
(non-hinted) method calls, but still a bit slower than type-hinted
calls. So if you are in a tight loop you'll need to type hint anyway.

I suspect we'd get a lot more bang-for-the-buck out of type inference
than invokedynamic since that may allow us to get the benefits of type
hints without the grunt work of scattering declarations everywhere.

-Phil

[Nick Zbinden]

@Aaron: Could you go into why this is the case? What does jruby do
that it needs it so much and clojure does not.

@Tal Liron: You seem to differ in your opinion with Aaron (pretty sure
you would not be investing your time otherwise). What exactlly are you
attempting to speed up and how does invokedynamic help?

[Paul Stadig]

Hmm... If you didn't have to worry about Java <7 compatibility, for one thing with invokedynamic you could remove a lot of code from Clojure. No more IFn or AFn. You simply have a method handle.

Second, I think it would allow the JVM to have a better view into optimization, and would allow the JVM to optimize something speculatively and allow for Clojure tell the JVM when to deoptimize with a SwitchPoints and MutableCallSites.

I don't think Phil's comparison is actually a fair one. If you're going to use type hints or type inference, then you're basically moving more towards static typing, which of course will be faster.

If you're going to do dynamic dispatch without compile time types to aid the compiler, then invokedynamic is most certainly going to be faster than reflection, and make for much simpler code.

I think invokedynamic would be great for Clojure. Of course there are other concerns like the fact that it is only for Java 7, so maybe it won't be the best place to put resources at the moment. But that's no reason that Tal can't work on it.


Paul

[Phil Hagelberg]

On Thu, Aug 25, 2011 at 2:35 PM, Paul Stadig <pa...@stadig.name> wrote:
> I think invokedynamic would be great for Clojure. Of course there are other
> concerns like the fact that it is only for Java 7, so maybe it won't be the
> best place to put resources at the moment. But that's no reason that Tal
> can't work on it.

For the record, I didn't mean to discourage anyone from working on it,
only to explain why it hasn't been implemented yet.

-Phil

[Alessio Stalla]

I'm neither of them, nor I am a Clojure hacker, but still I think I
can contribute something to the discussion.

invokedynamic is basically a hook in the JVM's linking system; it
allows language implementers to resolve method calls respecting the
semantics of their language, but letting the JVM know about it so it
can optimize those method calls.
invokedynamic is not just that - it has advanced features like the
ability to invalidate call sites (thus forcing the JVM to redo the
linking) or to emit guarded calls, in order to specialize "fast
paths" (e.g. primitive arithmetic) while providing a slow fallback
path (e.g. generic arithmetic).

It mostly benefits dynamic object-oriented languages - Ruby, Python,
Smalltalk etc. - because all their method calls can get promoted to
"native" JVM method calls instead of being implemented in user code.
In dynamic functional languages like Lisp dialects, method resolution
is not a problem - there's a single method, apply (simplifying things
a bit). invokedynamic can help with *class* resolution instead: now in
Clojure or Common Lisp every function call which is not inlined must
pass through the symbol (or Var in Clojure) - e.g.
functionNameSymbol.getFunction().apply(...). This is hard to optimize
because the actual class implementing the function is not known to the
JVM. With indy that pattern can become simply: invokedynamic
"functionName" args - and the Lisp system can resolve the function
only once (at least until it is redefined). I.e. the JVM will
translate that instruction to: invoke
TheClassImplementingTheFunction.apply(theFunctionInstance, ...args).
This should make function calls more optimized.

Advanced uses of invokedynamic - while complex - can implement things
like runtime type-based optimizations as well; but I don't know if
that's worth the effort for Lisps.

And perhaps there are other or alternative uses of invokedynamic that
I haven't considered, please share your ideas!

Peace,
Alessio

[Paul Stadig]

Right invokedynamic doesn't just "mostly benefit object-oriented languages." A MethodHandle can be used for anything that the JVM can do from a static method call, to an instance method call, to a constructor, to a field access.

And in fact the bootstrap method that links an invokedynamic call site does not have to dispatch on the type of the first argument in an object oriented way, it can actually do completely generic dispatch akin to Clojure's multimethods.

You can take a MethodHandle and curry the method by supplying some of the arguments, and this nice little packaged MethodHandle is given to the JVM with complete transparency for it to do it's stuff.

You can create collector and spreader methods to do things like RestFn does where it takes rest args. You could probably even do destructuring of arguments in a chain of MethodHandles that the JVM then could understand and optimize.

Maybe not all that potential is fully delivered with the current release of Java 7, but I think the transparency that invokedynamic allows should make it much easier for the JVM to do better optimizations.


Paul

[Kenny Stone]

A significant speed improvement without resorting to type hints would be a pretty huge win from a programmer's standpoint.  

Kenny

[Tal Liron]

So, after setting up a JVM 7 environment to play with Clojure, and enthusiastically rummaging through the codebase, I have good news and bad news. :)

(To quickly answer someone's question here -- I do know that it's a low priority for the Clojure project, but thought the potential benefit could be worth *my* personal time. A few people suggested that invokedynamic would not be that useful for Clojure, but I'm a skeptic and wanted to see for myself. I think other questions posed here are answered in the long report below...)

The bad news is that I don't think Clojure can benefit from JVM 7's invokedynamic. The good news is that it is unnecessary, because Clojure's compiler is already efficient, and entirely bypasses all the pesky problems other dynamic JVM languages have, for which invokedynamic was introduced. (I work a lot with Rhino, JRuby, Jython, Groovy and Quercus (a JVM PHP engine), and can anecdotally say that Clojure and Quercus are "fastest" of their breed for the kind of web development work I do.)

The thing is that Clojure's compiler is itself very Clojure-like, in that it treats functions as a first-class data type, just like maps, sequences, vars, etc. In the runtime, all of these data types share common interfaces, such as ISeq, IVar and -- you guessed it -- IFn. This situation is very unlike many non-Lisp languages, in which functions are often methods bound to classes, modules, interfaces, etc., all that heavy internal structure that Lisps implement in Lisp. So, when Clojure calls a function, it either already has the instance in its entirety (a lambda) or it finds it by dereferencing a binding. Since all functions are instances that implement IFn, the implementation can then call invokeinterface, which is very efficient.

[See clojure.lang.Compiler#InvokeExpr.emitArgsAndCall]

Clojure can get away with this especially easily because the only variant for function signatures in Clojure is arity. So, all we need is a simple switch to call the IFn method with the correct arity. (Interestingly, this means that Clojure has a fixed set of such signatures, and thus a fixed upper limit to arity: 20, in case you were wondering.)

In a language like Ruby, methods are not so free floating, and have much more complex invocation styles as well as flexible signatures. (Clojure has only one style: function calls are simple forms.) So, in order to use invokeinterface, JRuby implementors would have had to create special classes *per* method *per* invocation style if they wanted to be efficient. But this is impossible, because so many classes would exhaust the perm-gen. For those languages, invokedynamic is a terrific solution, because it lets them dynamically link the implementation to the caller via a flexible "bootstrapping" mechanism, allowing them to do entirely without the extra class definition. Since all Clojure functions share essentially the same class as well as interface, none of these challenges exist.

Another aspect is the immutability of these IFn instances: you can't refactor them at runtime, all you can do is change the bindings to refer to new functions. So, Clojure achieves runtime dynamics by letting you simply rebind new functions to existing Vars, Refs, Atoms, etc., and the same invocation route continues as usual. In a language like Ruby, the bootstrapping mechanism of invokedynamic lets implementors change the base linkage to reflect a new signature for the method. Again, a terrific JVM 7 feature that Clojure simply does not need.

Another issue I examined was how Clojure calls non-Clojure JVM code, thinking that perhaps there invokedynamic would be useful. But, Clojure again has a straightforward approach that poses no problems. Here, Clojure very directly calls non-Clojure code using invokestatic, invokevirtual or invokeinterface as appropriate. A Clojure form with the "." or ".." notations translates quite directly to a JVM method call. In fact, there's no significant difference between how Clojure compiles such code and how a Java compiler (such as javac) would compile such code. Clojure, too, explicitly handles boxing and unboxing of primitive types and other conveniences. Where Clojure slightly differs is in how it picks the correct method to call (it does method reflection, but only once during the compilation phase), and its coercion of types to match the called method -- after all, its type system is dynamic.

[See clojure.lang.Compiler#InstanceMethodExpr, StaticMethodExpr, etc.]

Again, this is different from an implementation like JRuby, in which the design decision was that non-Ruby code would live in Ruby "as if" it were Ruby code, supporting that Ruby invocation styles. This makes such calls compile like calls to other Ruby functions, and thus represents the same challenges mentioned above.

One thought about this: Actually, this is a place where Clojure *could* be more like JRuby, and allow for tighter integration with non-Clojure code. For example, I think it would convenient if, say, a non-static Java method on a Java class could be extracted from its context and be treated as a simple form by Clojure, in which case it would carry a class instance with it. This is called a "delegate" in the Java world. A similar effect is easily achieved in Clojure by using, well, closures (created by bind, let, etc.), but such a "delegate" would let the Java method live outside of closures, and behave like a regular Clojure fn. For example, it can be returned from a closure or be bound to a Var. Depending on how this feature is implemented, it might make sense to use invokedynamic for it, thought I'm guessing that it, again, that would prove unnecessary.

Another note re: JRuby, is that it also has a very nice implementation of constants that makes use of invokedynamic, which ends up being somewhat similar to the problem of switching functions dynamically, but also uses a "SwitchPoint" mechanism to allow for very efficient concurrent mutability of constants. Indeed, JRuby makes use of every part of JSR-292! Clojure doesn't need consts, of course, because everything is immutable.

In summary, Clojure's dynamics are already handled as well as could be on the JVM, at least as far as I can see.

And so my direct contribution to Clojure in this case is not a code patch, but a research report. :) It's kinda like how the Large Hadron Collider might end up disproving the existence of the Higgs boson. (Yes, I just compared myself to the LHC! And also compared invokedynamic to the "God Particle"! Everything is awesome!)

If anyone thinks I missed something, please let me know. I've stared at this problem so much that I may have ended up cross-eyed.

+++

A related issue --

Though Clojure may not be able to benefit from invokedynamic, I think it would be nice if it had support for working with it. For example, a set of macros that would be able to create MethodHandles from Clojure functions, and a way to create "bootstrap" functions in Clojure (the latter would need to be supported in the Clojure runtime). This could be useful if someone would want to write an implementation of a dynamic language in Clojure, or if Clojure is to be embedded in another of the dynamic languages. Since Clojure *is* a dynamic language (albeit one that does not need invokedynamic) it would be a friendly gesture for it to play nicely with other dynamic languages on JVM 7, which will probably make heavy use of invokedynamic.

It might be a good idea to put this on a roadmap somewhere for that day in the far future where Clojure fully supports JVM 7 features.

[Tal Liron]

Since Ruby isn't designed to run on the JVM, it doesn't have
any syntax for type hints to avoid reflective calls. I believe method
calls that use invokedynamic are much faster than reflective
(non-hinted) method calls, but still a bit slower than type-hinted
calls. So if you are in a tight loop you'll need to type hint anyway.

I just want to point out that Lisp wasn't designed for the JVM, either, and the JVM presents a few particular challenges for it, too, for example when it comes to special kinds of recursion.

invokedynamic actually isn't faster than reflection per se, if you are able to store the reflection method points in a structure to use for later. Actually, if you play with invokedynamic (it's not easy) on the current iteration of the officially released Oracle JDK, you will find that invokedynamic is a bit slower than calling reflected methods! I understand that this was fixed in trunk, and the next release of JDK 7 will have invokedynamic be faster.

 

[Tal Liron]

A significant speed improvement without resorting to type hints would be a pretty huge win from a programmer's standpoint.  

True, but this is not a problem that invokedynamic can solve. :) It would require, perhaps, better automation in the decision of how to coerce types when calling Java methods. But, I'm not really sure this can be improved upon without hints: moving from a dynamic ally-typed language to a statically-typed language means you would always have to fill in that gap somehow.

-Tal

[Tal Liron]

Hmm... If you didn't have to worry about Java <7 compatibility, for one thing with invokedynamic you could remove a lot of code from Clojure. No more IFn or AFn. You simply have a method handle.

Actually, Clojure's solution is almost identical to a method handle. An instance of AFn is not much different from an instance of MethodHandle, from the JVM's standpoint. The problem MethodHandle solves for languages like JRuby is that they need *different classes* for each method handling, whereas Clojure gets away with instances. Where using MethodHandle becomes important is when you want to participate in the invokedynamic bootstrapping, which expects MethodHandle instances. If Clojure ever needs to do this, it would be a simple one-to-one translation from AFn. 

 

Second, I think it would allow the JVM to have a better view into optimization, and would allow the JVM to optimize something speculatively and allow for Clojure tell the JVM when to deoptimize with a SwitchPoints and MutableCallSites.

Except that there's no functional mutability in Clojure! I tried hard, but I could not come up with a case in which this could be used. What are you thinking of, specifically? 

 

I don't think Phil's comparison is actually a fair one. If you're going to use type hints or type inference, then you're basically moving more towards static typing, which of course will be faster.

See my comments on the issue in my longer report: Clojure does use standard JVM invocations with static typing. In fact, it has no choice. :) It's also pretty smart about coercing types to the what the JVM method expects, and of course there is hinting to help it out.

[Sam Aaron]

Hey Tai,

this is a brilliant report - thanks very much. Even though you haven't done anything but back up the assertions from Clojure/core, I find your report much more reassuring (from a personal perspective) than just blindly believing something.

I think the Clojure community would benefit from further such reports/discussions. Although they might not always directly improve Clojure the language, they clearly help inform and educate Clojure the community - which can only be a good thing.

We shouldn't just be satisfied with knowing which direction we're headed - we should be trying our best to collectively help each other understand why we're headed in that direction. This report has definitely given me more understanding of why.

Thanks once again,

Sam

---
http://sam.aaron.name

[Paul Stadig]

On Thu, Aug 25, 2011 at 5:41 PM, Tal Liron <tal....@gmail.com> wrote:

So, after setting up a JVM 7 environment to play with Clojure, and enthusiastically rummaging through the codebase, I have good news and bad news. :)

So, when Clojure calls a function, it either already has the instance in its entirety (a lambda) or it finds it by dereferencing a binding. Since all functions are instances that implement IFn, the implementation can then call invokeinterface, which is very efficient.

[See clojure.lang.Compiler#InvokeExpr.emitArgsAndCall]

What I said in another post was that with invokedynamic (assuming you could just go whole hog into Java 7) you don't need the IFn interface. You just need a MethodHandle. So yes, I agree that given all the existing Clojure code, and the desire to stay compatible with Java 5 or 6 or whatever, invokedynamic isn't very compelling. If you were going to do a green field project, and didn't mind the Java 7 requirement, invokedynamic is very compelling, because you can basically push a bunch of code down into the JVM. This mean much less work, and it means you get to benefit from any improvements and optimizations that get built into the JVM. Even for Clojure having an optional Java 7 target may still be interesting in that it allows you to hook into all the work that will be done on invokedynamic to support the whole dynamic language ecosystem on the JVM.
 

Clojure can get away with this especially easily because the only variant for function signatures in Clojure is arity. So, all we need is a simple switch to call the IFn method with the correct arity. (Interestingly, this means that Clojure has a fixed set of such signatures, and thus a fixed upper limit to arity: 20, in case you were wondering.)

In a language like Ruby, methods are not so free floating, and have much more complex invocation styles as well as flexible signatures. (Clojure has only one style: function calls are simple forms.) So, in order to use invokeinterface, JRuby implementors would have had to create special classes *per* method *per* invocation style if they wanted to be efficient. But this is impossible, because so many classes would exhaust the perm-gen. For those languages, invokedynamic is a terrific solution, because it lets them dynamically link the implementation to the caller via a flexible "bootstrapping" mechanism, allowing them to do entirely without the extra class definition. Since all Clojure functions share essentially the same class as well as interface, none of these challenges exist.

It's very possible that I'm missing something, but I'm not quite sure what you're getting at here. In JRuby, for instance, the method overloading is the same as in Clojure, it is based on arity. The slowdown is in dispatch where you have to check a singleton class, your class, your ancestors, then method_missing, etc. Once you've looked this all up you cache it to speed it up later. Then you want to invalidate the cache when the world changes.

Clojure has similar needs. For instance, Clojure has protocol dispatch and multimethod dispatch as well as Var based dispatch. The multimethod dispatch does a look up in the derivation hierarchy. All of this stuff can change at runtime, just like in Ruby you can add methods to a class, change methods on a class, etc. I don't see how Clojure's dispatch needs are much different than what other dynamic languages are doing.
 

Another aspect is the immutability of these IFn instances: you can't refactor them at runtime, all you can do is change the bindings to refer to new functions. So, Clojure achieves runtime dynamics by letting you simply rebind new functions to existing Vars, Refs, Atoms, etc., and the same invocation route continues as usual. In a language like Ruby, the bootstrapping mechanism of invokedynamic lets implementors change the base linkage to reflect a new signature for the method. Again, a terrific JVM 7 feature that Clojure simply does not need.

The "signature" of a JRuby method is not much different than a Clojure method. It is an arity overloaded method with generic arguments. They do similar things to lots of other dynamic languages (including Clojure) like generating a class with a bunch of different versions of the same method with different numbers of generic arguments (http://jruby.org/git?p=jruby.git;a=blob;f=src/org/jruby/internal/runtime/methods/DynamicMethod.java;h=b65854c057c8a1acec57d6dad95158f08c960dcc;hb=HEAD#l203). invokedynamic isn't about method signatures it's about dynamic dispatch, which is what Clojure does.
 

Another issue I examined was how Clojure calls non-Clojure JVM code, thinking that perhaps there invokedynamic would be useful. But, Clojure again has a straightforward approach that poses no problems. Here, Clojure very directly calls non-Clojure code using invokestatic, invokevirtual or invokeinterface as appropriate. A Clojure form with the "." or ".." notations translates quite directly to a JVM method call. In fact, there's no significant difference between how Clojure compiles such code and how a Java compiler (such as javac) would compile such code. Clojure, too, explicitly handles boxing and unboxing of primitive types and other conveniences. Where Clojure slightly differs is in how it picks the correct method to call (it does method reflection, but only once during the compilation phase), and its coercion of types to match the called method -- after all, its type system is dynamic.

[See clojure.lang.Compiler#InstanceMethodExpr, StaticMethodExpr, etc.]

This just isn't true. If you don't provide any type hints, then the constructor for InstanceMethodExpr sets method = null and warns you that you're doing reflection (if you have the warn-on-reflection var set) https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1364 then in the emit function, when method == null it compiles the invocation to a call to call to Reflector.invokeInstanceMethod (https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1456 and https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Reflector.java#L25) which does reflection at runtime everytime you invoke the method...*everytime*. With invokedynamic you can do the lookup in a bootstrap method for the invokedynamic call site, you get a MethodHandle to the method you found, and you cache it in a CallSite. Then the next time you come through you just use the MethodHandle in the CallSite. That's a huge performance boost. With invokedynamic you can do the same thing for static field access. Clojure cannot optimize static field access like this.

Also the Clojure Reflector class does a lot of mojo to try to find the right method, and do boxing of arguments to match them up with the method you want to invoke (https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Reflector.java#L467 and https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Reflector.java#L427). If you call MethodHandle.invoke (versus MethodHandle.invokeExact) it does that for you automatically, and presumably in the lower layers of the JVM that Clojure cannot access, *and* the JVM knows more about what is going on for optimization purposes.

Clojure also does other things with arguments to functions, like collecting and spreading rest args. These can be done with a chain of MethodHandles which pushes the work down into the JVM.
 

[snip]

Another note re: JRuby, is that it also has a very nice implementation of constants that makes use of invokedynamic, which ends up being somewhat similar to the problem of switching functions dynamically, but also uses a "SwitchPoint" mechanism to allow for very efficient concurrent mutability of constants. Indeed, JRuby makes use of every part of JSR-292! Clojure doesn't need consts, of course, because everything is immutable.

Not everything in Clojure is immutable. The most basic element of Clojure's dispatch (the Var) is mutable, and Clojure could benefit in the same way as JRuby with SwitchPoints. Rich did work in 1.3 to basically keep track of when the world of Vars changes, and when it does all of the cached Var values get invalidated, and the next time a Var is used its value is re-fetched. This is basically a SwitchPoint mechanism, and Sun nee Oracle has already done the work for you, and other dynamic languages will be using it, and everyone will benefit from improvements and optimizations except Clojure, because we don't use invokedynamic.
 

In summary, Clojure's dynamics are already handled as well as could be on the JVM, at least as far as I can see.

For version 5 of the JVM, I agree, and if your goal is to maintain compatibility with version 5 of the JVM, sure. However, there is lots of invokedynamic goodness that Clojure could benefit from. Java 7 could be an optional target that would tap into invokedynamic. You then get into the debate about whether its going to be worth the effort, when what we have already is about as good as you can do on Java 5.

I'm not necessarily disagreeing with anyone who says it doesn't make sense for Clojure to support invokedynamic given the current situation and desire to maintain Java 5 compatibility. However, I do take issue with people saying that Clojure cannot benefit from invokedynamic in principle.


Paul

[Paul Stadig]

On Thu, Aug 25, 2011 at 6:05 PM, Tal Liron <tal....@gmail.com> wrote:

Hmm... If you didn't have to worry about Java <7 compatibility, for one thing with invokedynamic you could remove a lot of code from Clojure. No more IFn or AFn. You simply have a method handle.

Actually, Clojure's solution is almost identical to a method handle. An instance of AFn is not much different from an instance of MethodHandle, from the JVM's standpoint. The problem MethodHandle solves for languages like JRuby is that they need *different classes* for each method handling, whereas Clojure gets away with instances. Where using MethodHandle becomes important is when you want to participate in the invokedynamic bootstrapping, which expects MethodHandle instances. If Clojure ever needs to do this, it would be a simple one-to-one translation from AFn. 

I may be missing something, but I don't see how JRuby needs different classes. If you look at the JRuby code at the most basic level a method on a class is an instance of org.jruby.internal.runtime.methods.* or something else and those classes don't have so much to do with dispatch styles as optimizations. See, JRuby is able to achieve performance that is pretty darn close to Java, while still doing dynamic dispatch (without type hints). Clojure can not even get close to Java performance without type hints. All those different Method classes and all the complex stuff that JRuby does to make *dynamic* dispatch fast now gets pushed down into the JVM, and if Clojure taps into it, we could also get performance for dynamic dispatch that is much closer to Java.

One could say, "If you want performance use type hints," and that's a valid opinion, but again it's a different thing. Using type hints you are switching to static dispatch. If you want much better performance for *dynamic* dispatch, if you want much better performance without having to do type hints, then invokedynamic is here to help.

Also, there's actually a huge difference between IFn and MethodHandle. When you invoke an IFn you have to cast your arguments into Objects, which for primitives means you have to box them. When you invoke a MethodHandle, this does not happen. You push your primitive arguments onto the stack, then when the invokedynamic instruction is executed the arguments are boxed only if necessary. Same thing with casting objects. You push the raw arguments onto the stack, and at runtime you can do casts, if necessary. IFn is a static, compile-time interface, and when using it you must force your arguments into it's compile-time signature. MethodHandles are not compile-time.

Second, I think it would allow the JVM to have a better view into optimization, and would allow the JVM to optimize something speculatively and allow for Clojure tell the JVM when to deoptimize with a SwitchPoints and MutableCallSites.

Except that there's no functional mutability in Clojure! I tried hard, but I could not come up with a case in which this could be used. What are you thinking of, specifically? 

A function value is immutable in Clojure, but Vars are not. Protocols are not. Multimethods are not. Those are the cases I'm thinking of where you could use SwitchPoints to tell the JVM, "hey, I know you optimized this MethodHandle by inlining all the code, but now the Var has changed (sorry)."


Paul

[Aaron Bedra]

Thank you very much for the write up. I am going to paste this along
with some additional details on the wiki under Java 7 support.

Aaron

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient
> with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

--

[Kevin Ilchmann Jørgensen]

This means I can read the rest of the logs
http://clojure-log.n01se.net/date/2008-09-03.html
and it stills hold up ? i.e we want tagged numbers ?

/Kevin

[David Nolen]

On Thu, Aug 25, 2011 at 9:05 AM, Kevin Ilchmann Jørgensen <kij...@gmail.com> wrote:

This means I can read the rest of the logs
http://clojure-log.n01se.net/date/2008-09-03.html
and it stills hold up ?   i.e we want tagged numbers ?

/Kevin

1.3 went a different route. Fast path for 64bit arithmetic.

David 

[Charles Nutter]

This is the best summary of how Clojure *could* benefit from invokedynamic.

Clojure doesn't dispatch as dynamically as JRuby, but there is a dynamic component...specifically, you have to go get the fn. That repeated "get" would disappear with invokedynamic,

In fact, anywhere you're going after something that's immutable but requires a memory access, you could potentially use invokedynamic to eliminate repeat memory accesses. I assume that would help in many places.

Also, as Paul notes below, there's no need for multiple-arity interfaces to get full-speed perf if you use invokedynamic; JRuby's invokedynamic-based dispatch ends up going directly from call site to target code body, with no intervening interface at all.

Listen to Paul. He's right.

- Charlie

[Tal Liron]

Paul, I'm going to combine two posts of yours in to one, if I may, and answer some of your points.

(Aaron, can we add some of this to the wiki, too? I'm including at least one correction)

-- For version 5 of the JVM, I agree, and if your goal is to maintain compatibility with version 5 of the JVM, sure. However, there is lots of invokedynamic goodness that Clojure could benefit from.

I can think of a few ways in which it would be possible to distribute a clojure.jar that supports JVM 7 features while still falling back to JVM 5 compatibility. So, I don't think this was ever a barrier. But you obviously unconvinced by my report! Thank you for challenging me on this, As I said, I'm by no means 100% sure I exhausted the issue. I would encourage you to try out your ideas.

-- If you don't provide any type hints, then the constructor for InstanceMethodExpr sets method = null and warns you that you're doing reflection (if you have the warn-on-reflection var set) https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1364 then in the emit function, when method == null it compiles the invocation to a call to call to Reflector.invokeInstanceMethod (https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1456 and https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Reflector.java#L25) which does reflection at runtime everytime you invoke the method...*everytime*. With invokedynamic you can do the lookup in a bootstrap method for the invokedynamic call site, you get a MethodHandle to the method you found, and you cache it in a CallSite. Then the next time you come through you just use the MethodHandle in the CallSite. That's a huge performance boost. With invokedynamic you can do the same thing for static field access. Clojure cannot optimize static field access like this.

You are right! This is perhaps the only place where invokedynamic can be useful for Clojure. *However*, to me this is not a big deal, because the workaround of allowing for type hinting solves the problem just as well, and perhaps even more efficiently from the compiler's point of view. All it does is require some extra annotations by the programmer. The fact that Clojure emits a warning seems good enough for me, personally.

-- I may be missing something, but I don't see how JRuby needs different classes.

I recommend this old writeup by Charles Nutter for a good explanation of why JRuby *could* have used classes to solve the optimization problem (JSR-292 changed a lot since 2008, but the principles remain pretty much the same):

http://blog.headius.com/2008/09/first-taste-of-invokedynamic.html

I would add one emphasis to his explanation --

He point outs, very rightly, that the JVM has no real static typing at the low level, *except* when it comes to linking methods. But there is in fact another serious limitation of the JVM that comes into play here, which might seem very obvious to him but not so much to Clojure folk: the smallest container unit of code for the JVM is a class. There is no such thing as a free-floating procedure that you can just invoke whenever. (Changing this would be a revolution in the JVM, because so much depends on the ClassLoader mechanism, from security to modularity in OSGi.) This means that any time you want to reuse code you need to create a class. (I forget which verson if the JVM it was -- 5? -- that it become possible for the garbage collector to unload classes. This was a great feature for dynamic languages like Rhino, which generated a lot of classes during runtime to solve different problems in dynamics.)

The class problem even worse for dynamic languages, because classes cannot be changed runtime, so if you hoped that you could just create one huge class and keep adding static methods to as your "free-floating" code, this again. This is a problem not only for JRuby, but also for implementing delegates in the Java, a long-request feature. Java thus needs to do ridiculous things like this, which in C# (for example) would be done so much more elegantly:

new Thread(new Runnable() { public void run() { ThisIsMyFakeDelegate(); }).start();

What we did above was create a new (anonymous) class as well as an instance! Clojure does essentially the same thing per fn, extending AFn instead of implementing Runnable.

* Correction: In my original report, I said that Clojure creates only instances of AFn, not classes. I was misstating the situation: it's exactly one class and one instance per fn. Clojure extends AFn and simply overrides the correct method according to arity. (Perhaps I should emphasize that all method arguments are also of type Object, since no type checking is done explicitly or even known at compile time. So, no further method signatures are necessary other than one per number of Object arguments.) There is no problem with proliferation of classes here, because Clojure does not normally create many new functions at runtime. (I would only see this happening if you somehow embedded the REPL into Clojure and evaled code that created functions. But, unless you bind them somewhere, the classes would be garbage collected. If you are binding them, you should reconsider your solution, as something like that would probably cause any Lisp to choke...)

-- Clojure has similar needs. For instance, Clojure has protocol dispatch and multimethod dispatch as well as Var based dispatch. The multimethod dispatch does a look up in the derivation hierarchy. All of this stuff can change at runtime, just like in Ruby you can add methods to a class, change methods on a class, etc. I don't see how Clojure's dispatch needs are much different than what other dynamic languages are doing.

So, perhaps I'm not understanding how you are using the term "change at runtime" to describe both JRuby regular dispatch and Clojure's multimethod. Actually, this is a good place to again explain why Clojure is so different, and why I didn't even consider (perhaps prematurely?) multimethod as a place where invokedynamic could help:

Ruby lets you change classes and modules at runtime, because from Ruby's perspective a class (or module) is simply a dictionary of methods. So, in such cases it's perfect that the CallSite can be invalidated, and force the JVM to call your bootstrapping method again every time you change the dict. So, "dynamic" in this sense means that the class/module dict is mutable, and invokedynamic allows for an elegant optimization. In Clojure, the "class/module" construct does not exist, and functions are bound to Vars/Refs/Atoms, if they are bound at all, which must always be dereferenced anyway.

(On further thought, I'm wondering now if we can do something with invokedynamic here after all. We may be handle such bound functions through invokedynamic linkage instead via dereferencing, effectively moving the binding to a deeper level. This may involve very different implementations per Var/Ref/Atom respectively. I'm going to look into this some more -- we have to be sure not to break Clojure's semantics and limit its flexibility here.)

Clojure's multimethod is "dynamic" in an entirely different way: the correct function is selected at runtime *according to the arguments* of the function. JVM-level linkage to the selected method would make no sense, because you'd be calling your bootstrapping method every single call!

You can argue that Clojure multimethods are inherently inefficient, and perhaps they are.

One solution I could see is we allow to expand Clojure's deftypes into something more like classes/modules in other languages, in that deftypes could encapsulate functions as well as fields. But, this would turn Clojure into essentially object-oriented language, and I sincerely doubt Rich would allow for that to happen. :)

Hope this helps clarify things! I don't think I've answered every single one of your points, but this discussion is already probably too long for more readers. Again, I encourage you to try to implement your ideas. The more eyes are on this problem, the better.

-Tal

[Tal Liron]

Another correction:

I stated that Clojure's maximum arity is 20. That's not exactly true: for arity's beyond 20, IFn has a special invocation that accepts the arguments as an array. But this means that the compiler has to account for this, and arrange the arguments as a single array argument instead of multiple arguments. So, it just means that for arity's beyond 20, Clojure switches to a slightly less efficient invocation.

(Also, sorry for my weird grammar on that last post. Sometimes when I type, words that are in my head do not end up in the final message. :/ Fill in the gaps!)

[Tal Liron]

Progress!

I am staring right now at my JVM 7 build of Clojure that uses invokedynamic for Vars that contain functions. It essentially works, well enough for experimentation. A few of my simple apps seem to work fine with it.

There are still a lot of problems: the Clojure test suite fails, and my re-linking fallback mechanism (based on SwitchPoint) does not differentiate between root bindings of Var and their "box" thread-binding, so in theory any rebinding will cause all linkages on that Var to reset. Not very optimal.

I've really done very little optimizing at all at this point: invokedynamic is just replacing the usual invokeinterface. So, I was surprised that when fooling around with some benchmarks, one of them showed about 30% performance improvement on one of my Clojure-built web servers. Tantalizing! But, until the test suite succeeds, I can't be sure that this isn't a side effect of something not so great that's going on.

I'm hoping to have something the rest of you can play with soon, but thought you would want to hear a progress report. What would be the most convenient way to share this? A dump to github of the whole tree? A patch?

I've used the Clojure 1.2.1 codebase, because I didn't want to work on a moving target, and also think it might be easier for the community to help test this with existing applications. (As I said earlier, I also have a few ideas on how to make sure we can have this mechanism gracefully downgrade to JVM <7.)

Many thanks to Paul Stadig and Charlie Nutter for prodding me to realize that the one point where invokedynamic can help is to bridge the gap between dereferencing the Var and then calling invokeinterface on it. My mistake when looking at this the first time around was assuming that the dereferencing and subsequent invokeinterface were fast operations, and that it would make little difference to replace them with invokedynamic. But, speed is not the issue here: it's that this gap represents a black hole for HotSpot, around which it can't optimize well. Because this mechanism represents the primary junction for all of Clojure, optimization here could enable some nifty optimization across the board. I think it's a good way to imagine invokedynamic's benefits: it's a bridge over troubled water for HotSpot.

Paul also points out areas where MethodHandles can replace the rather sticky reflection work that Clojure does now to massage calls to non-Clojure libraries. That's not entirely related to the invokedynamic stuff I'm working on, so I think I'll leave it to somebody else to take a stab at that...

-Tal

[Paul Stadig]

On Sat, Aug 27, 2011 at 8:31 PM, Tal Liron <tal....@gmail.com> wrote:

I can think of a few ways in which it would be possible to distribute a clojure.jar that supports JVM 7 features while still falling back to JVM 5 compatibility. So, I don't think this was ever a barrier. But you obviously unconvinced by my report! Thank you for challenging me on this, As I said, I'm by no means 100% sure I exhausted the issue. I would encourage you to try out your ideas.

I agree. I wasn't saying that it was impossible to target both Java 5 and take advantage of Java 7 features. I had mentioned that targeting Java 7 could be specified as an option when AOT compiling, or it could automatically be detected when compiling at runtime. However, I think that people (perhaps rightly so) make the argument that the amount of effort weighed against compatibility concerns and resource allocation and the percentage of Clojure code that would benefit, doesn't make it worth doing. That's different than saying that there would be no benefit to Clojure.

-- If you don't provide any type hints, then the constructor for InstanceMethodExpr sets method = null and warns you that you're doing reflection...[snip]

You are right! This is perhaps the only place where invokedynamic can be useful for Clojure. *However*, to me this is not a big deal, because the workaround of allowing for type hinting solves the problem just as well, and perhaps even more efficiently from the compiler's point of view. All it does is require some extra annotations by the programmer. The fact that Clojure emits a warning seems good enough for me, personally.

This seems to be a standard response from people, and I don't really understand it. You are comparing apples to oranges. Don't get me wrong. Type hints are a critical tool for improving the performance of critical sections, and would probably be necessary even if Clojure's dynamic dispatch was faster than it is, but it seems like a win to just automatically make dispatch faster without type hints, and I guess it boils down to mostly non-technical factors (see above). Plus the biggest boost would be to code that interoperates with Java, which is arguably rarer than pure Clojure code (though I think that invokedynamic could even speed up Var dispatch, protocol dispatch, and multimethod dispatch (see below)).

-- I may be missing something, but I don't see how JRuby needs different classes.

But there is in fact another serious limitation of the JVM that comes into play here, which might seem very obvious to [Charles Nutter] but not so much to Clojure folk: the smallest container unit of code for the JVM is a class. There is no such thing as a free-floating procedure that you can just invoke whenever. ...

...This is a problem not only for JRuby, but also for implementing delegates in the Java, a long-request feature. Java thus needs to do ridiculous things like this, which in C# (for example) would be done so much more elegantly:

new Thread(new Runnable() { public void run() { ThisIsMyFakeDelegate(); }).start();

What we did above was create a new (anonymous) class as well as an instance! Clojure does essentially the same thing per fn, extending AFn instead of implementing Runnable.

* Correction: In my original report, I said that Clojure creates only instances of AFn, not classes. I was misstating the situation: it's exactly one class and one instance per fn. Clojure extends AFn and simply overrides the correct method according to arity. ...

I'm still not seeing an problems that are different than Clojure. JRuby must create a class for every method of every class in order to make the methods hot-swappable at runtime. Clojure does the same thing for its IFns and for the same reason. Both JRuby and Clojure would have to do this even if invokedynamic didn't exist, because it is a problem more with classes and class loading, than with invocation. I don't necessarily want to get distracted by this...

-- Clojure has similar needs. For instance, Clojure has protocol dispatch and multimethod dispatch as well as Var based dispatch. The multimethod dispatch does a look up in the derivation hierarchy. All of this stuff can change at runtime, just like in Ruby you can add methods to a class, change methods on a class, etc. I don't see how Clojure's dispatch needs are much different than what other dynamic languages are doing.

So, perhaps I'm not understanding how you are using the term "change at runtime" to describe both JRuby regular dispatch and Clojure's multimethod. ...

Correct me if I'm wrong, but multimethod dispatch calls a dispatch function that returns a value. This value can then be used to inspect the global derivation hierarchy. Then the result is used to find the right defmethod to call, by basically looking up in a dictionary of methods. The global derivation hierarchy can be changed at runtime which can cause different dispatch values to be returned for the same arguments at different times. Also, new defmethods can be added at runtime, which can change the dictionary of methods. Protocol dispatch is similar, but doesn't go through the global derivation hierarchy.

I believe there's already some form of caching implemented for multimethods and protocols. That caching code could be replaced by bootstrap methods and CallSites, which isn't really that exciting. However, I do believe that the JVM can better optimize a MethodHandle in a CallSite than it can an IFn that is fetched from a method dictionary at runtime. Perhaps that's just speculation on my part. However, I've been hearing good things about invokedynamic.

Plus, I believe with a CallSite the cache is more immediate than with a dictionary lookup. With a dictionary lookup, you do the lookup every time through the code path, but, as Charlie mentioned in another post, with a MethodHandle you go straight from a reference to the implementation code without having to do the lookup and without going through an interface. This seems to be not only a performance boost, but provides more specific information to the JVM, which would seem to improve optimizations.

Anyway, the biggest boost would seem to be calling Java methods from Clojure without type hints.

Clojure's multimethod is "dynamic" in an entirely different way: the correct function is selected at runtime *according to the arguments* of the function. JVM-level linkage to the selected method would make no sense, because you'd be calling your bootstrapping method every single call!

Yeah, I've thought about that. That may be true. However, Clojure does use caching for multimethod and protocol dispatch, and to whatever extent that caching is successful it can be pushed down into the JVM. And again, to me the advantage would be that the JVM has a MethodHandle directly to a method, which would improve optimization potential, and also once they are bootstrapped MethodHandles don't have check and recheck access levels and types of arguments. MethodHandles are designed to remove the extra layers of things you normally have to deal with when implementing dynamic languages on the JVM.

[Paul Stadig]

On Sun, Aug 28, 2011 at 10:25 AM, Tal Liron <tal....@gmail.com> wrote:

Progress!

I am staring right now at my JVM 7 build of Clojure that uses invokedynamic for Vars that contain functions. It essentially works, well enough for experimentation. A few of my simple apps seem to work fine with it.

There are still a lot of problems: the Clojure test suite fails, and my re-linking fallback mechanism (based on SwitchPoint) does not differentiate between root bindings of Var and their "box" thread-binding, so in theory any rebinding will cause all linkages on that Var to reset. Not very optimal.

I've really done very little optimizing at all at this point: invokedynamic is just replacing the usual invokeinterface. So, I was surprised that when fooling around with some benchmarks, one of them showed about 30% performance improvement on one of my Clojure-built web servers. Tantalizing! But, until the test suite succeeds, I can't be sure that this isn't a side effect of something not so great that's going on.

I'm hoping to have something the rest of you can play with soon, but thought you would want to hear a progress report. What would be the most convenient way to share this? A dump to github of the whole tree? A patch?

Hey that's good news! It would be simple enough for you to push a branch to your own fork of Clojure on github.
 

I've used the Clojure 1.2.1 codebase, because I didn't want to work on a moving target, and also think it might be easier for the community to help test this with existing applications. (As I said earlier, I also have a few ideas on how to make sure we can have this mechanism gracefully downgrade to JVM <7.)

Many thanks to Paul Stadig and Charlie Nutter for prodding me to realize that the one point where invokedynamic can help is to bridge the gap between dereferencing the Var and then calling invokeinterface on it. My mistake when looking at this the first time around was assuming that the dereferencing and subsequent invokeinterface were fast operations, and that it would make little difference to replace them with invokedynamic. But, speed is not the issue here: it's that this gap represents a black hole for HotSpot, around which it can't optimize well. Because this mechanism represents the primary junction for all of Clojure, optimization here could enable some nifty optimization across the board. I think it's a good way to imagine invokedynamic's benefits: it's a bridge over troubled water for HotSpot.

Paul also points out areas where MethodHandles can replace the rather sticky reflection work that Clojure does now to massage calls to non-Clojure libraries. That's not entirely related to the invokedynamic stuff I'm working on, so I think I'll leave it to somebody else to take a stab at that...

I wonder if it would be that difficult to replace the reflector code with an invokedynamic. There is a way to get from a java.lang.reflect.Method to a java.lang.invoke.MethodHandle (see java.lang.invoke.MethodHandles.Lookup.unreflect). You could probably just replace the code that emits a direct call to clojure.lang.Reflector to emit an invokedynamic instruction that calls a bootstrap method that wraps the Reflector code and just converts the Method into a MethodHandle for bootstrapping.

But things always seem easier until you actually get into them. :)

Paul

[Tal Liron]

Paul also points out areas where MethodHandles can replace the rather sticky reflection work that Clojure does now to massage calls to non-Clojure libraries. That's not entirely related to the invokedynamic stuff I'm working on, so I think I'll leave it to somebody else to take a stab at that...

I wonder if it would be that difficult to replace the reflector code with an invokedynamic. There is a way to get from a java.lang.reflect.Method to a java.lang.invoke.MethodHandle (see java.lang.invoke.MethodHandles.Lookup.unreflect). You could probably just replace the code that emits a direct call to clojure.lang.Reflector to emit an invokedynamic instruction that calls a bootstrap method that wraps the Reflector code and just converts the Method into a MethodHandle for bootstrapping.

I think you're overstating the problem: reflection is ugly, but it only happens here during compilation. From then on, the compiled code does what it needs to do with the types. At least, that's my reading of it: you told me before that I was dead wrong here, and maybe I am! If I'm right, then I don't see a "gap" here that invokedynamic can help bridge.
 

But things always seem easier until you actually get into them. :)

Tell me about it! Getting invokedynamic to work was much harder than I thought. It doesn't help that the Clojure codebase is a) very non-canonical Java, and b) utterly undocumented. Also, there's very little documentation about these new JVM features. They involve various tricks having to do with frame stack accounting and signatures, and when you don't get it right, you get terrible exceptions from ASM or the JVM. In both cases, all they can tell you is that "you're doing it wrong." Not for the faint of heart, nor for people who hate assembly...

-Tal

[Paul Stadig]

On Sun, Aug 28, 2011 at 10:58 AM, Tal Liron <tal....@gmail.com> wrote:

I wonder if it would be that difficult to replace the reflector code with an invokedynamic. There is a way to get from a java.lang.reflect.Method to a java.lang.invoke.MethodHandle (see java.lang.invoke.MethodHandles.Lookup.unreflect). You could probably just replace the code that emits a direct call to clojure.lang.Reflector to emit an invokedynamic instruction that calls a bootstrap method that wraps the Reflector code and just converts the Method into a MethodHandle for bootstrapping.

I think you're overstating the problem: reflection is ugly, but it only happens here during compilation. From then on, the compiled code does what it needs to do with the types. At least, that's my reading of it: you told me before that I was dead wrong here, and maybe I am! If I'm right, then I don't see a "gap" here that invokedynamic can help bridge.

If you look at the links in my previous e-mail (specifically this one https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1364). The reflection is done in the compiler only when there is a tag (i.e. a type hint). Otherwise the compiler just emits an invoke instruction to call the Reflector at runtime. That invoke could be replaced with an invokedynamic instruction.

If you are able to push a branch I may be able to find some time to hack on it.

Thanks for sticking with this though. The more I understand about invokedynamic the more interesting it becomes.


Paul

[Tal Liron]

If you look at the links in my previous e-mail (specifically this one https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1364). The reflection is done in the compiler only when there is a tag (i.e. a type hint). Otherwise the compiler just emits an invoke instruction to call the Reflector at runtime. That invoke could be replaced with an invokedynamic instruction.

Yes, that's exactly where one of us is mistaken. :) My understanding is that this constructor is only called once during the analysis mode. Then, one of the emit() methods is called, and from then on we are only executing the compiled code.

-Tal

 

[Alan Malloy]

On Aug 28, 12:41 pm, Tal Liron <tal.li...@gmail.com> wrote:
> > If you look at the links in my previous e-mail (specifically this one

> >https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/C...).

> > The reflection is done in the compiler only when there is a tag (i.e. a type
> > hint). Otherwise the compiler just emits an invoke instruction to call the
> > Reflector at runtime. That invoke could be replaced with an invokedynamic
> > instruction.
>
> Yes, that's exactly where one of us is mistaken. :) My understanding is that
> this constructor is only called once during the analysis mode. Then, one of
> the emit() methods is called, and from then on we are only executing the
> compiled code.

Well, the statement you just made is true, but nonetheless you are the
one who is mistaken. The emit() method is called, but if not enough
information was present at compile time to resolve to a real method
call (that is, if `method = null` was executed), then the emit() code
emits a call to clojure.lang.Reflector/invokeMatchingMethod, which
does runtime reflection. See
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1426
where the "fast path" code is only emitted if `method != null`, and
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1446
where the slow code is emitted instead.

Most of what I know about invokedynamic is from watching this thread,
but here seems to definitely be an area where you could avoid some
runtime reflection, which is quite slow.

You have to be careful, though, because the Method resolved the first
time may not be right the second time. Consider (. some-obj (size)).
If it is called on a j.u.Collection, we can do the reflection and
create a MethodHandle for faster dispatch later. but if someone later
passes in a j.u.Map (which is not a Collection), you have to reflect
again and come up with another MethodHandle. I assume there's some way
to do this, but it's harder than just shoving all runtime reflection
into MethodHandles.

[Tal Liron]

Well, the statement you just made is true, but nonetheless you are the
one who is mistaken. The emit() method is called, but if not enough
information was present at compile time to resolve to a real method
call (that is, if `method = null` was executed), then the emit() code
emits a call to clojure.lang.Reflector/invokeMatchingMethod, which
does runtime reflection. See
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1426
where the "fast path" code is only emitted if `method != null`, and
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1446
where the slow code is emitted instead.

See here:

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L1366

You will get a warning that the slow path will be used, so you will have a chance to add hinting to your code. In my opinion, it's a reasonable workaround.

Still... your comment makes me think that are especially dynamic use cases where you really don't want hinting, but you do want the correct method to be called (which is why this is a warning and not an error, I guess). But... wouldn't solving this in Lisp be easier?

I commented somewhere else that Lisp differs from other languages in that a lot of optimization is often the programmer's job. Memoization, smart recursion techniques, etc., can't be left to the underlying engine. Sometimes this is good! Programmer knows best. :)

-Tal

 

[Tal Liron]

Progress... is slow.

I encouraged other people to try, so the least I can do now is to point you at some of the serious challenges.

Right now I have what I think is a nice semi-generic mechanism for invokedynamic. It's called the "Linker": it handles finding the target method handle, bootstrapping, and what I call "restrapping", which is what happens when you guard it with an "ILinkable" (another new interface) and it fallbacks when a SwitchPoint is invalidated. There some various MethodHandle composing to make sure caller and target are both happy. I hope the "Linker" will make is easier to add invokedynamic in Clojure, and possibly in other projects.

My real challenge is not there, however, but with adapting Clojure to JVM 7 more generally. invokedynamic requires V1.7 classes, and for V1.7 the stack frame map that was optional in V1.6 is now a requirement. This is overall a very good idea for moving the JVM forward (these maps are a huge help for HotSpot), but I have no doubt that it will create serious pain for any project that generates JVM bytecode and until JVM 7 now could afford to be sloppier with stack frames. The V1.7 verifier will simply not let you load classes that don't have perfectly aligned maps.

ASM has very nice support for doing the stack frame arithmetic for you, but this is still being worked on in ASM 4 (trunk), and is not working in Clojure. I'm getting VerifyErrors specifically having to do with the mapping of try-catch blocks, and am working on debugging this via close look at CheckClassAdapter dumps. It's about as much fun as filling in tax forms. :/

(I've added support for two new defines, -Dclojure.jvm7=true and -Dclojure.invokedynamic=true, so each can be turned on separately. To be clear, my problems right now are in -Dclojure.jvm7=true and -Dclojure.invokedynamic=false.)

I've already patched one tiny part of ASM commons in order to add support for invokedynamic, and my work on debugging this may result in a more major patch to ASM. Assuming I do manage a fix. :/

So, what can I say? It's the cutting edge, baby. In for a penny, in for a pound.

-Tal

[Aaron Bedra]

The version of ASM that is bundled in Clojure is very old. This will
likely cause problems. You are correct in looking to ASM 4 since it has
started supported the JSR-292 stuff and other Java 7 changes. I am
planning on doing an extraction, update, and re-packaging of ASM in
Clojure as soon as Programming Clojure hits the printers. This most
likely won't get started until October though because of conferences.

Cheers,

Aaron Bedra
--
Clojure/core
http://clojure.com

[Tal Liron]

On 08/29/2011 06:01 PM, Aaron Bedra wrote:

The version of ASM that is bundled in Clojure is very old.  This will
likely cause problems.  You are correct in looking to ASM 4 since it has
started supported the JSR-292 stuff and other Java 7 changes.  I am
planning on doing an extraction, update, and re-packaging of ASM in
Clojure as soon as Programming Clojure hits the printers.  This most
likely won't get started until October though because of conferences.

I've already done that for my branch (that was a task in itself! needed a little monkeypatching to support Clojure's DynamicClassLoader), so you may want to leave it to me.

My code is in quite a messy state now and I'm embarrassed to make it public quite yet...

BTW, does somebody have an Eclipse Java code formatter configuration for Clojure's wacky coding style?

-Tal

[Laurent PETIT]

2011/8/30 Tal Liron <tal....@gmail.com>

You mean for the java parts of Clojure in java.lang ?
No, sorry, no.
 

[Paul Stadig]

I started on some work to use invokedynamic instructions (instead of reflection) for calling Java interop. I based my work on 1.3beta2, and my goal was just to see how much of a performance difference it could make (if any).

So far all I have done is update the bundled ASM and modify Clojure to emit Java7 class files, but I'm getting VerifyErrors (same as Tal). It's possible that this is a bug in the way that ASM automatically calculates stack maps, or perhaps it is the best that ASM can do, in which case the Clojure compiler would have to be modified to do bookkeeping around stack maps.

I even tried moving to ASM trunk to see if it made any difference, but it didn't.

Anyway, I pushed a couple of branches to my fork of Clojure:

https://github.com/pjstadig/clojure/tree/indy-3.3.2

and

https://github.com/pjstadig/clojure/tree/indy-trunk

Perhaps when ASM 4.0 is finalized it will be a different story.


Paul

--

[Tal Liron]

On 09/06/2011 08:42 AM, Paul Stadig wrote:

So far all I have done is update the bundled ASM and modify Clojure to emit Java7 class files, but I'm getting VerifyErrors (same as Tal). It's possible that this is a bug in the way that ASM automatically calculates stack maps, or perhaps it is the best that ASM can do, in which case the Clojure compiler would have to be modified to do bookkeeping around stack maps.

Cool! I'm making some progress with some folk on the ASM mailing list. We might crack this yet.

-Tal