read


read
or learn more

Why Clojure doesn’t need invokedynamic, but it might be nice

Oct 14, 2011

this is the third entry in an n-part series explaining the compilation techniques of Clojure.1

There was an interesting discussion about invokedynamic on the Clojure mailing list focused on the need for and potential benefits of invokedynamic. Granted this topic is often quite technical, so I suppose that it’s understandable that confusion and disagreement would arise. However, the general tone of the thread and the ensuing Internet discussion was that Clojure didn’t need invokedynamic. This is technically true, but there is a distinct difference between need and benefit. This post will hopefully clarify the current state of affairs regarding just how invokedynamic can benefit, and also hurt, Clojure on the JVM.

Why Clojure might not need invokedynamic

Tal Liron provided a very nice summary of the reasons that invokedynamic might be unnecessary for Clojure. I highly suggest you read his assessment as I will only summarize some high points here and in the next section, offering corrections where his thesis differs from the realities of the invokedynamic story for Clojure.

Java Interop

Let’s take a look at the first potential use of invokedynamic for Clojure, interop calls. As you may know, Clojure allows one to call Java class methods directly as below:

(defn at [s] (.charAt s 1))
(at "abc" 1)
;=> \b

However, the call above is problematic in that the compiler cannot resolve the class of the charAt method so an expensive route through reflection must take place at runtime. Unfortunately for us, though some common paths through reflection are indeed optimized by the JVM HotSpot, we wouldn’t want to hang our hat on that fact. Would it be possible therefore to use invokedynamic instead of the reflective call? Probably. However, it’s worth noting that through compile-time type inferencing, most interop calls are emitted in the most efficient ways possible. In fact, most of the interop calls in Clojure are compiled in the same way that Java itself is compiled. For those times as above when the Clojure compiler in unable to infer the correct target type, then Clojure provides type hinting to help the compiler along:

(defn at [^String s] (.charAt s 1))

Like many Lisps, Clojure is built around the principle that one should write the code correctly first and then only add adornments later when speed is needed. That is not to say that there is no place for a scenario whereby invokedynamic is used instead of reflection in the non-inferred case, but the presence of type hinting makes that scenario less than urgent and definitely not compelling enough to consider it a worthwhile venture on its own. I would imagine that time would be better spent implementing more comprehensive type inferencing. This is a clear win that would benefit many codebases quickly, with none of the downsides listed in the last section of this post.

Multimethods

Clojure has a multimethod function type that provides runtime dynamic dispatch of a named function to a set of unique implementations based on the result of a separate dispatch function. A simple example is below:

(defmulti say-count count)
(defmethod say-count 0 [_] "Zero")
(defmethod say-count 1 [_] "One")
(defmethod say-count :default [_] "A Bunch")

(say-count [1 2 3])
;=> A Bunch

As you might see, the multimethod say-count is defined to dispatch based on the result of the interceding function count. When count returns 0 the specific method associated with that value is invoked. For every call to a multimethod2 its dispatch method is called. This is a potential bottleneck, but what you give up in speed you gain in flexibility. But does it need to be this way? Can invokedynamic help alliviate this tradeoff? The answer as it turns out is similar to interop’s answer. How invokedynamic can help multimethods escapes me, although they do have a PIC-like doo-dad (technical term) under the hood — so the jury is still out here.

How invokedynamic can help Clojure

a nice source of core knowledge on this section is this treatment of dynamic invocation on the JVM by John Rose

Before any discussion about how invokedynamic can help begins, it’s critical to understand what it provides. In a nutshell, invokedynamic provides the raw material for building efficient polymorphic inline caches that are subject to finer grained HotSpot optimizations. At the moment Clojure and JRuby (and others for sure) build those PICs from “something else” (technical term). However, as I will discuss regarding Vars next, invokedynamic’s benefits are not limited to the case where one might find a PIC.

Much of the following is covered by the eminent Paul Stadig in the original thread, but I’ll provide an overview below.

def

At the core of Clojure’s dynamic heart is the Var. At it’s most boiled (i.e. before taking into account dynamic or thread-local bindings), a Var is a single point of mutability that holds a value or function. Clojure as a Lisp is predicated on the ability to change a function definition at any time. In production this explicit function redefinition is not used very much, but at the REPL, Clojure’s interactive console, this capability is used to great effect in incrementally building a solution and in-place sanity checking (i.e. REPL-based testing).

To provide this level of flexibility Clojure establishes a level of indirection.3 Specifically, all function lookups through a Var occur, at the lowest level, through an atomic volatile.4 This happens every time that a function bound using the def/defn special forms is called. This indirection is not amenable to HotSpot optimizations.

This is a great place for invokedynamic, especially during production scenarios where the root value of Vars remain stable. That is, invokedynamic would eliminate the volatile lookup on every call and likely lead to HotSpot inlining. From another perspective, the JVM provides a way to change out class implementations on the fly via something called safepoints. This implementation swapping is analogous, if not a mirror of, the swapping of Var root bindings. Safepoints are intuitively viewed as stable execution points where interrupts can be utilized to save JVM state, thus allowing magic (technical term) to happen safely and atomically. At the moment, invokedynamic is the only path to safepoints for the JVM language implementor. It would be awesome (technical term) to have a direct path to safepoints, but I digress.

protocols

Clojure’s protocols are polymorphic on the type of the first argument. The protocol functions are call-site cached (with no per-call lookup cost if the target class remains stable). In other words, the implementation of Clojure’s protocols are built on polymorphic inline caches. This is a clear win in using invokedynamic. This fact was, IMO, the biggest omission from the apparent motivation behind the Clojure mailing list thread.5

How invokedynamic can hurt Clojure

In all of the invokedynamic discussions that I have read there is little to no attention paid to the potential downsides. This is symptomatic of programming discussions in general that seem to always focus on the gain of some technology, and rarely, if ever on the costs. As expected, the discussions around invokedynamic tend toward a benefit-benefit analysis, but there are some serious questions that work to bring pause to its adoption in Clojure.

Issue #0 – Splitting the compiler

The Clojure developers work very hard to ensure that the compilation target operates on any Java5, Java6, and Java7 compatible JVM. However, to utilize invokedynamic would call for one of the following two scenarios:

  1. Break compatibility with Java5 and Java6 and target Java7 only
    • The adoption curve for Java7 is shaped like a gigantic question mark at the moment
  2. Split the compiler codebase into two branches targeting the invokedynamic and non-invokedynamic cases

Option #1 is probably out of the question, but like anything there may be overwhelming advantages to doing so that I’m just not seeing (although I doubt it). JRuby could possibly take this approach since in general Ruby devs are pretty adventurous with versioning,6 but I suspect that they will take option #2 instead. Option #2 is the practical choice, but it’s still not one to take lightly. Any compiler is complex and to maintain and enhance one is a tremendous effort. The effort to maintain two disparate branches is not linear in its complexity, but more likely geometric.7

Issue #1 – Speed

Charles Nutter, my personal invokedynamic guru, recently ran some speed tests for constant lookup in JRuby using various mixtures. For some measurement of speediness, the results were as follows:

So it definitely seems that the future looks bright. However, clearly the current implementation falls very short of the speed ideal set by JRuby and Clojure’s current “manual” PIC implementations. Will this enormous speed gap persist? If so, then for how long? What are the downsides of the faster development HotSpot? These are all legitimate questions that have no definitive answers. Granted if the dev HotSpot gets rolled in and lives up to its potential, then this issue probably goes away. However, the future might look bright, but a problem with the future is that it comes when it’s ready and never before, no matter how much we want it to or might need it. A bright future is not motivating enough to split the compiler into separate codebases.

Issue #2 – What is the cost?

As discussed there is a (potential) speed and maintenance cost to using invokedynamic in its current manifestation. However, there is potentially also a size cost as well. That is, in Mr. Nutter’s aforementioned post it is unclear what supporting code is required to support the observed speed improvements. When asked, Mr. Nutter seemed to dance around the issue. I am not trying to imply any impropriety in any way. Instead, the likely reason is that for JRuby the speed gain is the motivating factor for including invokedynamic and a tradeoff in code size is deemed acceptable. It could also mean that the size is not problematic, but from the perspective of Clojure adoption, it would factor into a final decision. Aside from crass code size considerations, there are also unknown complexities that might arise from the invokedynamic interface itself, but I must be honest that the subtleties surrounding them tend to fly over my head.8

Issue #3 – Java does not consume invokedynamic

In the original thread on the Clojure group, Tal Liron aptly states:

one of the challenges of using invokedynamic is that the Java language does not support it

The final, and in my opinion the most insidious, factor is that at the moment Java itself is in no way a consumer of invokedynamic. That is not to say that there are no potential benefits to be gained, only that the primary audience for the feature are external languages. Without pulling out the tin-foil hat, it is fair to posit that if given limited resources, the choice to improve Java or improve invokedynamic Oracle will almost always spell doom for the latter. As it stands, invokedynamic (like anything else I suppose) is subject to marketing pressures in addition to technical details. Therefore, Oracle’s approach is likely to follow a standard cost-benefit analysis; just as other marketing strategies. This is in no way meant to take away from the Herculean effort spent by those internal to Sun/Oracle in the design and development of invokedynamic. However, if it appears that the inclusion and maintenance of invokedynamic is a net loss from a management perspective, then what does that mean for languages like JRuby and Clojure? No one knows of course, but it’s a valid question and a valid concern.

Issue #4 – Time

Time spent on invokedynamic for the Clojure/core team is time not spent on something else (e.g. fork-join). However, in **no way* should that dissuade some brilliant Clojure community member from taking on invokedynamic in the ways mentioned (and those not mentioned) above. Clojure will become stronger based not solely on the efforts of Clojure/core (nor should it), but on the effort of the community at large. Do you have great ideas for invokedynamic? We would love to see them.

Finis

For those of you still awake, I wish that I could send you a cookie. You deserve it. For any new and exciting technology it’s natural for a level of excitement to follow. However, this post is meant to provide a perspective that mixes the good with the bad, or more appropriately the benefit with the cost. I hope that this post provides the canonical perspective on invokedynamic from a Clojure perspective. If you see something that doesn’t seems kosher then please comment below.

thanks to Rich Hickey for reading a draft of this post

:F


  1. OK, so I changed the spirit of the “series”… sue me. 

  2. Actually there is more to it than this as there are also dynamic hierarchies that are (potentially) traversed on each multimethod calls. 

  3. The root-level indirection through a volatile is not the same as dynamic binding. The latter is another level of indirection for Vars marked as ^:dynamic

  4. However, some Var root values not marked as ^:dynamic can be directly linked, but this occurs at the caller’s site and is not a property of Var’s themselves. 

  5. Paul Stadig did mention this, and in fact his comments in the thread are most inline with this post. It’s worth going back and focusing in on Paul’s commentary — I can’t stress this enough. 

  6. I kid. 

  7. Option #2 is clearly O(MG) multiplied by some constant Z in its complexity. 

  8. I’ve spent some recent months leveling-up on the Clojure compiler, but the added curveball of invokedynamic has my head spinning. 

11 Comments, Comment or Ping

  1. Ok, there’s some good points here and a few misguided/misinformed positions. I’ll try to cover everything.

    First, I need to point out a key detail of invokedynamic that may have escaped notice: any case where you must bounce through a generic piece of code to do dispatch — regardless of how fast that bounce may be — prevents a whole slew of optimizations from happening. This might affect Java dispatch, if there’s any argument-twiddling logic shared between call sites. It would definitely affect multimethods, which are using a hand-implemented PIC. Any case where there’s intervening code between the call site and the target would benefit from invokedynamic, since invokedynamic could be used to plumb that logic and let it inline straight through. This is, indeed, the primary benefit of using invokedynamic: arbitrarily complex dispatch logic folds away allowing the dispatch to optimize as if it were direct.

    Your point about inference in Java dispatch is a fair one…if Clojure is able to infer all cases, then there’s no need to use invokedynamic at all. But unless Clojure is able to infer all cases, then you’ve got this little performance time bomb just waiting to happen. Tweak some code path and obscure the inference, and kablam, you’re back on a slow reflective impl. Invokedynamic would provide a measure of consistency; the only unforeseen perf impact would be when the dispatch turns out to actually be polymorphic, in which case even a direct call wouldn’t do much better.

    For multimethods, the benefit should be clear: the MM selection logic would be mostly implemented using method handles and “leaf” logic, allowing hotspot to inline it everywhere it is used. That means for small-morphic MM call sites, all targets could potentially inline too. That’s impossible without invokedynamic unless you generate every MM path immediately around the eventual call.

    Now, on to defs and Var lookup. Depending on the cost of Var lookup, using a SwitchPoint-based invalidation plus invokedynamic could be a big win. In Java 7u2, SwitchPoint-based invalidation is essentially free until invalidated, and as you point out that’s a rare case. There would essentially be no cost in indirecting through a var until that var changes…and then it would settle back into no cost until it changes again. Frequently-changing vars could gracefully degrade to a PIC.

    It’s also dangerous to understate the impact code size has on JVM optimization. The usual recommendation on the JVM is to move code into many small methods, possibly using call-through logic as in multimethods to reuse the same logic in many places. As I’ve mentioned, that defeats many optimizations, so the next approach is often to hand-inline logic everywhere it’s used, to let the JVM have a more optimizable view of the system. But now we’re stepping on our own feet…by adding more bytecode, we’re almost certainly impacting the JVM’s optimization and inlining budgets.

    OpenJDK (and probably the other VMs too) has various limits on how far it will go to optimize code. A large number of these limits are based on the bytecoded size of the target methods. Methods that get too big won’t inline, and sometimes won’t compile. Methods that inline a lot of code might not get inlined into other methods. Methods that inline one path and eat up too much budget might push out more important calls later on. The only way around this is to reduce bytecode size, which is where invokedynamic comes in.

    As of OpenJDK 7u2, MethodHandle logic is not included when calculating inlining budgets. In other words, if you push all the Java dispatch logic or multimethod dispatch logic or var lookup into mostly MethodHandles, you’re getting that logic for free. That has had a tremendous impact on JRuby performance; I had previous versions of our compiler that did indeed infer static target methods from the interpreter, but they were often slower than call site caching solely because the code was considerably larger. With invokedynamic, a call is a call is a call, and the intervening plumbing is not counted against you.

    Now, what about negative impacts to Clojure itself…

    0 is a red herring. JRuby supports Java 5, 6, and 7 with only a few hundred lines of changes in the compiler. Basically, the compiler has abstract interfaces for doing things like constant lookup, literal loading, and dispatch that we simply reimplement to use invokedynamic (extending the old non-indy logic for non-indified paths). In order to compile our uses of invokedynamic, we use Rémi Forax’s JSR-292 backport, which includes a “mock” jar with all the invokedynamic APIs stubbed out. In our release, we just leave that library out, reflectively load the invokedynamic-based compiler impls, and we’re off to the races.

    1 would be fair if the Oracle Java 7u2 early-access drops did not already include the optimizations that gave JRuby those awesome numbers. The biggest of those optimizations was making SwitchPoint free, but also important are the inlining discounting and MutableCallSite improvements. The perf you see for JRuby there can apply to any indirected behavior in Clojure, with the same perf benefits as of 7u2.

    For #2, to address the apparent vagueness in my blog post…the big perf gain was largely from using SwitchPoint to invalidate constants rather than pinging a global serial number. Again, indirection folds away if you can shove it into MethodHandles. And it’s pretty easy to do it.

    3 is just plain FUD. Oracle has committed to making invokedynamic work well for Java too. The current thinking is that “lambda”, the support for closures in Java 7, will use invokedynamic under the covers to implement “function-like” constructs. Oracle has also committed to Nashorn, a fully invokedynamic-based JavaScript implementation, which has many of the same challenges as languages like Ruby or Python. I talked with Adam Messinger at Oracle, who explained to me that Oracle chose JavaScript in part because it’s so far away from Java…as I put it (and he agreed) it’s going to “keep Oracle honest” about optimizing for non-Java languages. Invokedynamic is driving the future of the JVM, and Oracle knows it all too well.

    As for #4…well, all good things take a little effort :) I think the effort required is far lower than you suspect, though.

  2. Re issue #3, my understanding is that some of the lambda support for JDK 8 are directly built on top of invokedynamic. So while Java may not use it atm I don’t think that will remain so very long.

    Maybe tangential, but still important… Oracle seemed to say in some JavaOne talks that they have a commitment to JavaScript (Rhino) as the primary scripting hook into Java and there seem to be multiple people working on invokedynamic-based JavaScript implementations (see recent mlvm mailing list discussions). While this is not Java, it seems to have support and be rising in priority by my reading of the tea leaves.

    I think invokedynamic will (eventually) be important for Clojure but it doesn’t seem worth pursuing this instant, other than as a pointer to the future. Eventually, I believe your issues will be reduced, the benefits will rise, and the install base will change such that the balance tips in the opposite direction. I’d guess that time frame is 1-2 years out.

  3. Kevin

    our fairly large clojure code base at work, when loaded (which compiles it and any non-aot’ed deps) ends up compiling around 40% of java methods calls (hostexprs in the compiler) reflectively.

  4. @Charlie

    I need more time to digest what you’ve posted, but I do want to address one point:

    is just plain FUD.

    It is not my intention to spread FUD. Instead, it seems that you have some inside information that I myself do not have. I suppose the difference between my own misgivings regarding invokedynamic and Java and true FUD is that I hope that I’m wrong. Reading your (and Alex’s) comments work to alleviate doubts. I would not say however that they are baseless doubts.

  5. I meant FUD in the nicest way (or perhaps the most literal way) possible. You fear that Oracle won’t support invokedynamic long term. That uncertainty leads you to deemphasize invokedynamic support in Clojure. Because there’s doubt in your mind, Clojure may end up missing an important opportunity. And the truth is that you simply don’t know, so you express your FUD instead of just keeping you rmouth shut. :)

    I did not mean to say you’re spreading FUD, but you’re expressing your own FUD. Education is the remedy, so hopefully I’ve helped somewhat.

  6. David

    I’m 95% sure you mean to say that Paul Stadig is eminent.

  7. I’d love to see invokedynamic make multimethods faster (on par with protocol dispatch) and let us have back dynamic vars without the performance penalty. Those seem like edges where we’ve ceded a bit of power in exchange for performance but man it would be nice to have both dynamism and performance.

  8. javajoe

    Charles,

    Please be more specific about where exactly invoke dynamic will be used in lambda. Last time I looked it was for very little – I believe what was said was that mh is still not has fast as inner classes (http://www.wiki.jvmlangsummit.com/images/1/1e/2011_Goetz_Lambda.pdf). Oracle would love to make us all believe what huge dividends invoke dynamic is giving us java programmers. I dont think they want people to know that all this investment is doing squat for their 90% use case …. yes of java programmers!

  9. ct

    Since invokedynamic will offer in a year or two x00% performance increases for multimethods, protcols and vars, I predict clojure will get forked if clojure/core wont support its use.

    People are now using clojure to build big distributed systems and if means > 10% less spent on aws or rackspace cpu cycles, then it will be a no brainer.

    If Oracle were to release such a touted feature as invokedynamic into the wild and somehow attempt to pull it back from its stated aim of supporting the JVM as a language platform, its entire stewardship of Java would be called into question. Doesn’t seem likely.

  10. ct:

    I and Clojure/core have always supported its use.

    See this:

    http://groups.google.com/group/clojure-dev/msg/1887cb34fb9ce0e5

    What we haven’t done is spend our own time on it to any great extent yet.

    This is because:

    Things are pretty good as it currently stands.

    Few people could actually leverage any such work in production, at this time.

    Note how the latter is still true, while that message is 2 years old!

    Now, should someone come on the clojure-dev list and say:

    “I have the time, interest and expertise to work on invokedynamic support for Clojure and would like to contribute it, how can I get started?”

    they’d be welcomed gladly. That hasn’t happened yet.

    Why someone would fork instead is baffling. Thanks for the prediction though.

  11. Julia

    Actually, Java is really an excellent programming language, and abstracts enough technical details to let you focus on the basic logic of the idea you want to animate. And here, I would like to recommend you a website which can barcode in Java applications. You can enjoy the pleasure of generating barcodes. It is really interesting! http://www.onbarcode.com/tutorial/java-barcode-generation.html

Reply to “Why Clojure doesn’t need invokedynamic, but it might be nice”