<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div>On Aug 22, 2014, at 1:08 PM, Charles Oliver Nutter <<a href="mailto:headius@headius.com">headius@headius.com</a>> wrote:</div><div><br class="Apple-interchange-newline"><blockquote type="cite"><span style="font-family: Helvetica; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">Marcus coaxed me into making a post about our indy issues. Our indy</span><br style="font-family: Helvetica; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: Helvetica; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">issues mostly surround startup and warmup time, so I'm making this a</span><br style="font-family: Helvetica; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: Helvetica; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">general post about startup and warmup.</span><br style="font-family: Helvetica; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"></blockquote><br></div><div>This is a vigorous and interesting discussion. I will make some piecemeal replies to</div><div>specific points, but first, as a HotSpot team member, I'll comment on the startup</div><div>problem and then set out our position and vision for indy and dynamic languages.</div><div><br></div>Achilles had two heels, and so does Java: Startup and warmup. Many teams of many<br>people have worked on these issues for years, with hard-won progress. Compared<div>with C programs (say, "/bin/awk"), the JVM takes a long time to get going.</div><div><br></div><div>Fundamentally this comes from the decision to package programs as bytecodes</div><div>(JARs, etc.) rather than machine instructions plus mappable data (dylibs, etc.).</div><div>As everyone on this list knows and appreciates, Java bytecodes are a portable,</div><div>stable, and compact intermediate representation for both code and data structure.</div><div>You can do an amazing variety of great things with them, and there is no credible</div><div>proposal (IMO) to replace them wholesale with some other representation.</div><div><br></div><div>As an inherent property, bytecodes cannot be executed directly, requiring</div><div>additional machinery to execute: an interpreter, JIT compiler, and/or AOT engine.</div><div>Making this machinery look small is an ongoing challenge for us JVM implementors.</div><div>I say "ongoing" (not just "historic") because software complexity scales up with time.</div><div><br></div><div>Our basic move is organizing cold stuff differently from hot stuff.</div><div>The C2 JIT spends lots of effort on the hot paths in hot methods.</div><div>On the cold side, Java's class data sharing feature tries to organize large</div><div>amounts of start-up bytecode in a form that can be quickly loaded and discarded.</div><div>The most useful distinctions between hot and cold data and code usually</div><div>require some sort of online measurement, which is one reason Java is</div><div>competitive with C++, which generally lacks behavior-dependent optimizations.</div><div><br></div><div>Building on these basic considerations, an ideal Java implementation would</div><div>quickly get through the start-up process quickly by executing cold code and/or</div><div>loading pre-configured data structures, with the result that data which must be</div><div>configured by every JVM on startup, or by every invocation of a given application,</div><div>is quickly assembled. This would be done in some cases by loading a</div><div>pre-composed bitwise data image, or perhaps more efficiently by "decompressing"</div><div>an operationally encoded description of the initial data image by executing</div><div>some sort of code. In fact, that is what Java interpreters are pretty good at,</div><div>when augmented by a pre-composed "class data archive" that maps in</div><div>a pre-parsed version of classes from "rt.jar". (Sometimes this image is</div><div>found in a file called "classes.jsa".)</div><div><br></div><div>But if more of the initial state of a Java application could be demand-paged from</div><div>an image file (like the initial data of C programs) there might be less latency,</div><div>since there would certainly be fewer order constraints between the different</div><div>loading events (at the page and cache line level), allowing prefetch machinery</div><div>to hide latency. This is an important area of growth for Java.</div><div><br></div><div>Second, an ideal Java implementation would quickly discover the particular</div><div>on-line characteristics of the application under execution, and produce</div><div>tailor-made machine code for that execution, with the result that the</div><div>application's critical inner loops would execute at full performance,</div><div>almost immediately. This would be done in some cases by capturing</div><div>profile information from early phases of the application and applying them</div><div>to the creation of customized code. In fact, the profiling interpreter and</div><div>tiered C1 JIT are pretty good at gathering such information, and</div><div>feeding it to the C2 JIT.</div><div><br></div><div>What's missing? Probably a certain amount of prediction of behavior</div><div>based on previous runs of the application, combined with a way of</div><div>loading data and executing code that benefits from that prediction,</div><div>even before the application has gotten that far. To me that sounds</div><div>like a static compiler of some sort, though an open-world kind that</div><div>allows the compiler's model of the world to change during execution.</div><div><br></div><div>Maybe another missing bit is a slightly more static initialization model</div><div>for Java, under which the assembly of initial data can be predicted</div><div>off-line with greater accuracy. For starters, we should have array</div><div>initializers that are more distinct from random bytecode execution,</div><div>plus a little more discipline about the effects of <clinit> methods,</div><div>separating those effects into "yes we can statically model this"</div><div>vs. "do you really want to do this crazy thing?".</div><div><br></div><div>One wrong answer would be to do more JIT stuff, earlier and oftener.</div><div>But JIT optimizations are inherently throughput-oriented; they do</div><div>nothing do reduce start-up or spin-up overheads; they often worsen</div><div>those overheads. (Example: Iteration range splitting which makes</div><div>the middle of a loop run without array range checks, at the expense</div><div>of extra calculations at the beginning and end of the loop.)</div><div><br></div><div>So what we need is a new set of optimizations for application start-up,</div><div>akin to those developed for managing static data and relocations in</div><div>shared libraries.</div><div><br></div><div>One thing to note about Java's very dynamic startup semantics is that</div><div>it's not always bad. It is not always the right idea to load a statically</div><div>composed bit-image of data or code, if that image is large compared</div><div>with its true information content (e.g., a character range table).</div><div>If the data is going to be traversed sequentially, sometimes it is</div><div>better to expand it from a less complex representation.</div><div>Compressed file systems exploit this insight, when they win.</div><div><br></div><div>The encoding of Java lambdas uses invokedynamic to make</div><div>a decisively more compact encoding, relative to inner classes,</div><div>which can be expanded in local memory faster (in some cases)</div><div>than it can be loaded from cold bits in a JAR file. This is one</div><div>of the reasons Java 8 lambdas (expanded on the fly) beat inner</div><div>classes (precompiled into a JAR).</div><div><br></div><div>The lesson here is that if you are going to precompile, consider</div><div>precompiling something compact, and use a load-time translator</div><div>as needed. This insight has to be traded off against the complexity</div><div>of the translation process, and also against the low-level advantage</div><div>of a pre-fetch-capable load format (such as a brute image of an</div><div>array of bytes).</div><div><br></div><div>That brings us to invokedynamic. This is designed to be the swiss</div><div>army knife of bytecode instructions, able to do the job of ten others,</div><div>yet fitting in one compact carrying case. When indy works right,</div><div>a specialized call site is encoded in the natural number of tokens</div><div>(constant pool entries), expanded quickly by its bootstrap method</div><div>to a method handle, where the method handle has a simple and</div><div>natural structure, and is compiled almost as quickly (pending only</div><div>last touches of profile data) to optimal machine code.</div><div><br></div><div>As a test case, an indy call site is able to emulate any other concrete</div><div>JVM instruction that can be described as N pops and 0 or 1 pushes,</div><div>and in that case should quickly compile to the same machine code</div><div>as if that concrete instruction were given instead. (Why not throw</div><div>out the other instructions then? Well, they can be viewed as</div><div>shorthand for the equivalent indy instructions, if we wish. This</div><div>is suggestive of possible shapes for Bytecode 2.0, but who</div><div>knows when that will be.)</div><div><br></div><div>Conversely, when indy goes wrong, it is probably because there</div><div>are an unnatural number of bytecode constructs involved (bad</div><div>factoring) or the bootstrap method is doing something complicated</div><div>(perhaps a cache is needed somewhere) or the resulting method</div><div>handle is overly complex (too many "lambda forms" under the</div><div>covers) or the compiler is stumbling over something and failing</div><div>to inline and optimize (often shallow inlining or polluted profiles</div><div>or surprise box/unbox events).</div><div><br></div><div>Put another way, when indy goes wrong, it is because the relatively</div><div>simple programming model it offers is belied by internal simulation</div><div>overheads. Language programmers know about simulation overheads</div><div>and can manage them explicitly, but indy provides an attractive way</div><div>to refactor them, as long as it does not add too many more overheads.</div><div><br></div><div>Is it shocking that a JVM mechanism should have simulation overheads?</div><div>No, it is not. What is painful at this moment in time is that those overheads</div><div>have not been reduced as quickly as we hoped. There is a combination</div><div>of reasons for this, which are not technically interesting. It is still our</div><div>position that those overheads are not inherent to the design, but rather</div><div>implementation artifacts. For example, for the sake of JDK 8 lambdas,</div><div>we were able to remove enough overheads to make lambdas worthy</div><div>successors to inner classes.</div><div><br></div><div>There is a range of proposals to overcome more of those overheads</div><div>by tuning or replacing the implementation. They all boil down to</div><div>increased sharing of common structure early in the execution pipeline,</div><div>with inlining and customization later allowing fully optimized JIT code.</div><div>Fredrik's "rabbit out of the hat" technique radically simplifies the</div><div>common structures, by relying on very strong box/unbox and varargs</div><div>optimizations later in the pipeline. The current architecture avoids</div><div>reliance on those optimizations (which are hard to get 100% correct),</div><div>at the expense of more redundant copies of the IR and the bytecodes.</div><div><br></div><div>(The metaphor of "pipeline" is apt, although a code pipeline has a</div><div>different "fluid" running through each segment. You can characterize</div><div>a code pipeline by its phases: Loader, linker, interpreter, JIT.</div><div>Method handle IR adds more phases, including the lambda form</div><div>interpreter and bytecode renderer.)</div><div><br></div><div>The current architecture makes multiple copies of each general shape</div><div>of method handle, to distinguish different combinations of primitives vs.</div><div>references. Internally, these shapes are represented in an IR which</div><div>shows up as "lambda forms".</div><div><br></div><div>The current story is that the cost of making a method handle is way</div><div>too high: We generate bit of IR for any non-trivial method handle,</div><div>and those bits get composed and shoved down the code pipeline.</div><div>This leads to a large load of code, some of it useful and some not.</div><div>Also, the IR is retained in an executable form, causing heap bloat at scale.</div><div><br></div><div>These lambda forms are obnoxious in the heap and on the execution</div><div>stack not because they are representing small distinctions between code</div><div>shape, but rather because they are often generated one per method</div><div>handle. I intended this to be a temporary state, before 8 FCS, alas.</div><div>We will be able to improve this state, soon, but it has been a long wait.</div><div><br></div><div>One of the reasons it has been difficult to make the improvement is that,</div><div>paradoxically, the existing over-production of lambda forms has some</div><div>advantages, akin to the advantages of over-inlining. If your instruction</div><div>processing pipeline can handle a 10x overload of redundant instructions,</div><div>sometimes you win, because profiling and prediction tactics work better</div><div>on single-use instructions, as opposed to shared-use instructions.</div><div>This is true both at the bytecode and machine-code levels.</div><div><br></div><div>Our major challenge is to preserve existing performance peaks</div><div>while reducing the volume of IR and bytecodes going down the</div><div>pipeline. The challenge is tied to the choice of IR, but not in</div><div>such as radical way that we need an IR change. The real</div><div>challenge, as we see it, is twofold.</div><div><br></div><div>First, as method handles are built, recognize emergent similarities</div><div>of structure, and reuse similar bits of IR to build similar method</div><div>handles. Put negatively, don't build full custom IR for each</div><div>method handle. Put positively, build generic IR if you can get</div><div>away with it, or at least cache repeatedly built patterns, as possible.</div><div>You know you have won when people stop noticing IR dregs</div><div>in their heaps.</div><div><br></div><div>Second, as method handles are executed (and/or as their IR or</div><div>bytecodes are executed), collect profile data that will be useful</div><div>to the eventual full-custom object code at any or all of the relevant</div><div>invocation sites—or nowhere, if those sites don't exist.</div><div><br></div><div>These goals are in tension with each other, regardless of what</div><div>you call your IR. Exploring this tension has been a key component</div><div>of our recent engineering. In basic terms, profile information should</div><div>be attached as early as possible to the particular method handles</div><div>bound at an invokedynamic site, while each chunk IR should be</div><div>cagily shared among as many method handles as possible.</div><div><br></div><div>(The previous requirement is expressed in terms of indy call</div><div>sites, but it should extend to other kinds of method handle</div><div>call sites. An indy call site is, in effect, an invokeExact of a</div><div>compile-time constant method handle, but we also have</div><div>optimizations for non-constant method handle invocations,</div><div>both exact and inexact. Still, the focus is on indy.)</div><div><br></div><div>We can use the "pipeline" metaphor to observe that overly long</div><div>pipelines have drawbacks. If code must be dynamically translated</div><div>into several different states before full throughput, it is possible</div><div>that some intermediate state will introduce an irregularity that</div><div>later phases will not be able to normalize or optimize. This is</div><div>the case, for example, with the lambda form interpreter. This</div><div>exists (a) to work around some bootstrap issues, and (b) to allow</div><div>programs to warm a little before committing to bytecode.</div><div>(A third advantage is an executable documentation of semantics.)</div><div>It appears that neither benefit is strong enough to overcome the</div><div>disadvantage of having the JIT stumble over the lambda form</div><div>interpreter, so we are likely to remove that phase.</div><div><br></div><div>It does not follow, however, that the other pipeline phases for</div><div>lambda forms should also be removed. In fact, neither bytecodes</div><div>nor bundles of some lower-level IR are a replacement for lambda</div><div>forms, insofar as they fill a special niche, the need for an easily</div><div>created representation of a stand-alone, ad hoc JVM method.</div><div>We need a way to build small bits of behavior that can be</div><div>assembled, method-wise, into larger bits of behavior.</div><div>There may be better ways to build such things than lambda</div><div>forms, but any proposal to eliminate lambda forms needs to</div><div>provide an up-front design for a way to compose, analyze,</div><div>cache, and load ad hoc methods.</div><div><br></div><div>In the near future, we expect the overhead of a method handle to</div><div>be more like the overhead of a closure and less like the overhead</div><div>of an inner class. This means that you will win if you "compress"</div><div>your call sites using indy instead of open-coding them with many</div><div>bytecodes. The warm-up will process the compact form, leading</div><div>to less net data motion for loading, while the hot form of the code</div><div>will be indistinguishable from the open-coded version.</div><div><br></div><div>And we expect to get better at capturing the call-site specific types,</div><div>values, and branch behavior of the contents of an invokedynamic site.</div><div><br></div><div>Such work is intended to replicate the hot-path effects of open-coded</div><div>bytecodes, without their startup time bulk. It worked for JDK 8 lambdas.</div><div>We intend it to work for our other customers.</div><div><br></div><div>For example, one of our goals is that taking a generic method handle,</div><div>shrinking it with "asType", and then binding it to an indy site, will</div><div>end up having a customization effect similar to spinning customized</div><div>bytecodes for the internals of the generic method handle. This will</div><div>get us close to Fredrik's "rabbit" design, even if we don't handle</div><div>arity polymorphism any time soon. Note that value types are pushing</div><div>us in this direction also, since values effectively require the creation</div><div>of many more customizations, in a system that cannot interchange</div><div>boxed and unboxed representations. An early part of this work is</div><div>carefully defining more optimizer-friendly semantics for primitive</div><div>boxes, to be extended to value boxes.</div><div><br></div><div>Moving forward, we expect invokedynamic to continue to provide a</div><div>powerful way to reduce the complexity of bytecode shapes of advanced</div><div>languages (including Java), without compromising on performance.</div><div><br></div><div>I hope this helps. Please let me know if something is unclear or seems</div><div>wrong; these are certainly slippery topics.</div><div><br></div><div>Best wishes,</div><div>— John</div></body></html>