14 ms·

What I Learned Making My Own JIT Language

291 points by developer-mike 8y ago

stcredzero 8y ago
Sure, there are things that can be "poison pills" for performance, even in JITs. For example, another reason why my fib benchmark beats V8 is that V8 has to continually check if the fib function was redefined as a deoptimization check. I don't allow that in Vaiven, so I can produce faster code. Dart was designed to have fewer of these poison pills, for instance. Note to language designers: Reduce your language's poison pills. For those which can't be avoided, make them easy to profile!
- TomMarius 8y ago
  Is there a list of common language poison pills? I'd like to learn more.
  - saagarjha 8y ago
    I'd assume anything that breaks expectations and speculative execution. Weak typing, dynamic function calls, etc.
  - jerf 8y ago
    Well, I can't do a full list, but: Memory non-locality. On modern systems, thrashing through RAM just kills you on performance. I don't know that you have to hand full control over to the programmer, but if you're randomly flinging values on the heap everywhere (a.k.a. "hash tables"), you're gonna hit a wall long before you get to "C performance". For JITs, any time the JIT has the ability to make an assumption, but then you break it. The obvious one is "this function always returns an int", which the JIT can nicely optimize, but if once you ever return a string, the JIT will have to do something to deoptimize that case again, possibly permanently. More subtly, things like "returning an object that always has these three keys that map to these three values of a certain type", which a JIT can optimize to a struct under the hood, until you change a type or add a field for a particular call. Just in general, any assumption the JIT can make for performance that you might break in a function. You should generally program your performance-sensitive JS as if it were statically typed, even if it isn't. Indirection for the user's convenience; one of the reasons CPython is sooo slooooow is that there's a ton of indirection going on. For the code x.y(), you can change x by directly overriding "y" on the specific x you are using, or it can be set at the class level, or it can be set by any of the superclasses, or the dot operator may be a function that does arbitrary things up to and including arbitrary mutation of whatever it gets its hands on, etc., plus even without overridding getattr there's this whole "property" thing, plus it could be a __slot__, and I'm pretty sure I'm missing at least one thing here, and CPython is hopping through all these hoops for every such lookup. The fact that "x.y()" translates to dozens or hundreds of C lines of code is what Python so convenient, but at the same time, what makes it so slow, too. I understand the value of being able to override things; I question the need of dynamic scripting languages to provide so many places to override things.
    - blattimwind 8y ago
      > I don't know that you have to hand full control over to the programmer, but if you're randomly flinging values on the heap everywhere (a.k.a. "hash tables"), you're gonna hit a wall long before you get to "C performance". Rule of Python: Everything is at least two pointers away. -- > and CPython is hopping through all these hoops for every such lookup. Actually CPython has a cache for that. This becomes apparent if you improperly replace methods in the class dictionary. I think the bane of Python specifically is a bit different. It's not so much that it's very dynamic, because JITs can clearly deal with that. It's that CPython exposes all kinds of interpreter state that's off-limits in other languages, which makes it way harder to JIT. In JavaScript there are at most a handful ways how you can mutate a prototype, but in CPython you don't have enough fingers to count them, even if you only consider Python and not the C API.
      - jerf 8y ago
        "Actually CPython has a cache for that." My apologies for my unclarity. In my head, "hopping through all these hoops" included using caching, but that is completely unclear. It is true that there is a lot of caching being done, because it would simply be unusable if there isn't. But it is also true that there is still a lot of work to do for "x.y()", even when all caches are used fully.
        blattimwind 8y ago
        Yes... and most of it is even part of stable APIs.
    - arghwhat 8y ago
      I'd like to add: Don't define your array as nothing but a hashmap with strings as array indexes, with two assignment hooks: One that on assignment updates that sets length = max(length, ToUint32(assigned key)), and one on "length" assignment that iterates over all keys in the hashmap, and for those that can be parsed as uint32's, delete those that have a numerical value larger than the value assigned to length. That is how JavaScript "Array" objects work. Array indexes are coerced to a strings, as they are for all objects. For the curious, here is full definition from ECMA-262 1st edition, which describe what browsers currently implement (https://www.ecma-international.org/publications/files/ECMA-ST-ARCH/ECMA-262,%201st%20edition,%20June%201997.pdf https://www.ecma-international.org/publications/files/ECMA-S..., page 65): Array objects give special treatment to a certain class of property names. A property name P (in the form of a string value) is an array index if and only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 232−1. Every Array object has a length property whose value is always an integer with positive sign and less than 232. It is always the case that the length property is numerically greater than the name of every property whose name is an array index; whenever a property of an Array object is created or changed, other properties are adjusted as necessary to maintain this invariant. Specifically, whenever a property is added whose name is an array index, the length property is changed, if necessary, to be one more than the numeric value of that array index; and whenever the length property is changed, every property whose name is an array index whose value is not smaller than the new length is automatically deleted. This constraint applies only to properties of the Array object itself and is unaffected by length or array index properties that may be inherited from its prototype.
  - kodablah 8y ago
    Anything that has to be interpreted or un-JIT'd for the most part. Runtime eval, runtime struct memory layout redefining, runtime type change, etc. Basically it's a trade off between pre-compiled immutable omniscience and developer friendliness. Targeting the former often increases perf due to the assumptions you can make, targeting the latter increases comfort and adoption and usability and simplicity.
  - gameswithgo 8y ago
    a JIT is one! time is wasted doing compiling while running, the compiler has strict time constraints so can't do as many optimizations, claims about theoretical benefits from runtime data collection and-recompilation for optimization are rarely reazlied in the actual world and profile guided optimizations can achieve similar things for AOT compiled programs. soooooooooooo AOT master race
    - TomMarius 8y ago
      What about WebAssembly? How would you provide the same guarantees and benefits without JITing or interpreting?
    - bjoli 8y ago
      As someone who has ported racket's for loops to guile scheme (or at least, re-implemented them without looking at the source of the original racket macros), a JIT has several benefits. There are some things that you just can't know at compile time, and hot paths/inline caches solve a lot of those things. for example (for/list ([a (in-range a b c)]) (+ a 100)). Since in-range has to check when to end the loop, it has to know whether the loop goes in negative or positive direction (ie: to check the loop using < or >). If the values of a b c isn't known at compile time, the comparator has to be checked for each loop. This can potentially be very expensive, especially in an inner loop. There are loads of optimizations that can be done much more efficiently/easily by a JIT. Store sinking, store/load forwarding, array bounds check elimination, value-range propagation and hyperblock scheduling to name a few. LuaJIT is still the fastest dynamic language out there, but the complexity of the codebase surely makes you wish that wasn't the case.
      - ufo 8y ago
        You can avoid the test by generating two loops (one that goes up and one that goes down). But that can lead to code bloat...
  - beagle3 8y ago
    Mike Pall of LuaJIT fame opined on that on the luajit mailing list a few years back. Can't find the discussion right now, but only https://news.ycombinator.com/item?id=8605225 https://news.ycombinator.com/item?id=8605225 which is somewhat relevant.
  - bjoli 8y ago
    Redefining things are generally a no-no, especially top level things. Knowing what things are and where they are makes things much easier to implement. For inline caches it is much better if you don't redefine things, which applies to JITs. I remember reading that Mike Pall said about pypy that most of the optimizations he did for luajit were possible for python, but just a lot more work. Using mutation is a really good way to make most scheme implementations run slowly, since mutation is generally avoided, and thus most flow analysis is spent on checking recursion. A while-loop using set! is generally a lot slower than a recursive named let loop. Flow analysis is simply easier without mutation, even though it might not look easier for the person reading the code.
  - ufo 8y ago
    The poison-pills are implementation dependent. At the end of the day it is just a matter of the JIT not optimizing a certain programming pattern. Sometimes it is just because the authors didn't get around to that yet. Sometimes there is a more fundamental reason why optimizing that pattern would be hard. I am most familiar with LuaJIT. It has wiki page with a list of things that force it to fall back to the interpreter http://wiki.luajit.org/NYI http://wiki.luajit.org/NYI
    - TomMarius 8y ago
      Sure. I was interested in known patterns that make optimization hard, because I'm toying with implementing a language myself. Thank you for your link!
- jerf 8y ago
  I would be intrigued to see a modern attempt at a dynamic language like Python or Ruby, but with attention paid from day one to ensure that only very JIT-able constructs were used, and with an eye towards the language helping the user stick to those and be aware of when they deviate, rather than designing a language, setting "runs fast" somewhere around the third or fourth priority, then trying to JIT it after 10-15 years of non-JIT development. Even LuaJIT, which is to my understand the closest anyone has come to this, still was retrofitting JIT onto an existing language. I'm not convinced we're going to see much more performance out of JS, for instance, which is about as fast as a dynamic language can go nowadays. But I wonder what the real limits of a "dynamic scripting" language would be from this perspective. Edit: Per my other comment about indirection being a performance poison pill, here's an example of an idea where a new scripting language might be able to get a lot of performance. Suppose you keep the ability to dynamically create classes and load code and so forth, so that (just as an example, not necessarily a good idea) you can write code that dynamically connects to a database and loads in tables as classes with automatically defined properties, etc. But instead of working the way the languages do now, instead of constantly walking through all the layers of indirection that can be used to implement all this at every call site and for every call, what if you could do something like the "pledge()" call that says "OK, this is it, I'm all set up, the dynamism is all done, you may now assume that all the type analysis you've done is now complete". Now the JIT can drop all of its paranoia code. It isn't completely obvious to me how to do this correctly (by implication, if you can "connect to a database" before this pledge()-like call is done, you have to have a pretty complete runtime available just for that), nor is it obvious to me how this would affect the type system, etc. Maybe it's not possible. But it's the type of thing I mean that would be interesting to have examined by someone, who might be able to concretely show why it's not possible, or, whoknows, make it work. And that's just one idea of how to design a dynamic language from the top for performance, basically off the cuff; who knows what a smart person who sat down and thought about this for a couple of weeks before even beginning to code could come up with. Another one is that it isn't obvious to me that scripting languages must be all based on hash tables that laboriously can be cast back to structs by the JIT; it seems to me that it would also be feasible to go the other way, and allow users to define things as structs, and if you want to offer hash-like access it would be easy to lay down hash-like access to the struct members (iteration, etc.), and either implicitly or explicitly also offer an "overflow" hash table if desired. This would give at least a bit of locality control. Something something arrays too for array control, and suddenly you're starting cook with gas.
- amelius 8y ago
  Isn't there some kind of static analysis possible for such cases?
  - saagarjha 8y ago
    If you could perform static analysis on these cases, why couldn’t the JIT just do so itself and not have any issues?
    - amelius 8y ago
      Well, I suppose a JIT has tighter time constraints.
  - arghwhat 8y ago
    JavaScript is too dynamic for such analysis. JavaScript at its core is not a very well designed language, and it's a bloody miracle that a JIT can make it usable. If you're designing a new language, don't make everything (even arrays!) a hashmap.
    - j-pb 8y ago
      [1]In clojure the array type is basically a hashmap to enable high perf/low memory immutability. So I would say "Yes[1]" ^^
      - arghwhat 8y ago
        I would certainly say "no" to having your basic array type be a hashmap as a hashmap is several orders of magnitude slower than an array for all operations on small arrays and for access for all sizes, although there is nothing wrong with also having hashmap and linked list collections if you need O(1) inserts. However, what I was referring to is much worse than that: JavaScript arrays are defined as a normal hashmap with string keys with hooks on assignment to parse the key as a uint32 and update the length property if the value is larger than the current one, and on length assignment iterate over all keys and delete those that successfully parse as a uint32 and has a numeric value larger than the one assigned to length.
- white-flame 8y ago
  I say screw deoptimization checks, and put the burden in the redefinition processing. When you redefine something, you stop the world at safepoints and update prior baked assumptions that are registered on the old definition. These redefinitions usually happen during development and initialization, not during performance-sensitive runtime. It would add more to the memory footprint, but that information is not accessed at all except during recompilation.
  - chrisseaton 8y ago
    > I say screw deoptimization checks > you stop the world at safepoints But that's how deoptimisation checks work.
  - arghwhat 8y ago
    Then you either need to have "redefinition" checks, or an actual, full stop the world, which is also a performance nightmare and also affects unrelated code. The proper solution is to not have unnecessary dynamics. There is no need for the ability to redefine methods on an object. If you have functions as first-class objects, you can just let users store functions and call them at the cost of indirection if they wish to have such dynamics.
    - wahern 8y ago
      > There is no need for the ability to redefine methods on an object In prototype-based languages like JavaScript and Lua redefining methods on an object is common at runtime, which makes them quite challenging to JIT. It may be most common early in execution, but there's no way to semantically define that boundary. Since Lua 5.2 (IIRC) certain metamethods are locked & loaded when you assign a metatable (a prototype definition) to an object. Thus, the __gc finalizer is only obeyed if it existed when the metatable was set on the object. (I don't think this was a performance improvement--more about tradeoffs in GC complexity--but it's an example of side-effect semantics that could be leveraged for JIT optimization.) But this isn't the case for OOP-like methods (which in Lua are normally defined indirectly through the __index metamethod field), as those are ad hoc and would be expected to change during runtime. A similar issue occurs in any dynamic language (JavaScript, Lua, Perl, etc) that uses generic dictionaries for assigning and loading functions. Ideally a JIT would know that invoking a function like "a.b.foo()" would always load the same function and could elide the dictionary lookup for "b" and "foo". But keeping track of whether the dictionary a or b was modified is costly. Theoretically you could, e.g., add callback hooks to dictionary entries that, when invoked, invalidate some JIT'd block; but such conditional checks and operations cause a huge amount of code bloat and slow down the fast path. Adding more logic in an attempt to minimize unnecessary work causes the same problems. The lesson from languages like Forth, K, and Lua is that the most important thing to optimize isn't JITing, but the software VM itself, including the bytecode and dispatch tables. (Mike Pall of LuaJIT fame makes this point.) The deep pipelines and huge caches (e.g. for branch speculation) in modern processors means that the abstraction of a bytecode and dispatch table can often be subsumed into the pipeline, resulting in a fixed but relatively small overheard as compared to native code. This is especially true for the bulk of the application code, where you may only see a [hand waving] 1.5x or 2x overhead in a language like Lua or especially LuaJIT. And you can do even better by moving specific hot spots into C code. Languages like Python and Ruby don't have nearly as lean a VM as Lua so the overhead is greater and more variable, but the idea is similar. If WebAssembly catches on, I think we'll begin to see some regressions in JavaScript JITs because the marginal cost and complexity won't be as worthwhile when people begin moving compute-heavy code into WebAssembly. Simplicity might even bring some performance improvements for code that was never susceptible to JITing because there'll be less baggage. [1] Largely a result of the lean and clean semantics. Which is not the same as power--Lua has fully lexical scoping with proper closures, and asymmetric stackful coroutines. Asymmetric, stackful coroutines are exceedingly powerful abstractions, but also rid Lua of the colored functions[2] problem that languages that adopt explicit async/await semantics have, which means function invocation semantics are unified making the implementation simpler and leaner and in turn making it more likely VM dispatch is cleanly pipelined in hardware. Less is more. Which is a similar lesson Linux taught the world--Windows never had fork() as it was considered too heavyweight and complex for the common case, and instead focused on multiple different interfaces, one for creating threads and one for invoking new programs. But Linux optimized the heck out of fork, so even creating a thread is faster on Linux than on Windows, and the semantic power of fork makes it easier to implement complex resource sharing schemes between processes than on Windows (i.e. rather having an extremely complex data structure and flags for telling the OS what resources to pass or share between processes, you just use other common APIs--e.g. dup(), etc--before exec()). [2] http://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/ http://journal.stuffwithstuff.com/2015/02/01/what-color-is-y...
- pjc50 8y ago
  Most of the poison pills are someone else's convenience features, sadly.
- Sawamara 8y ago
  Note to commenter: you can design a language to never change a function's signature, in which case that language loses the "dynamic" and "scripting" part (okay, maybe just the dynamic part). Nothing wrong with having ultra-dynamic languages, but you will inevitably trade speed for quirky code in cases like that.
  - burfog 8y ago
    So the restrictions needed for performance also eliminate many causes of unmaintainable messy code and runtime errors? This is an easy decision.
filereaper 8y ago
PSA: If there are folks writing their own JIT languages (and are highly encouraged to do so) please also checkout out the Eclipse OMR project. OMR is a bunch pluggable runtime components (GC, JIT etc...) intended to ease building of runtimes from scratch. https://github.com/eclipse/omr https://github.com/eclipse/omr
- tomcam 8y ago
  What an incredible resource. Thank you.
- PeCaN 8y ago
  OMR is amazing. It's essentially IBM's J9 virtual machine, with all the man-decades of effort that went into that. However, if you're writing your own JIT language and you've never written one before, you probably want to learn something and write your own GC, JIT, etc. It's really not that hard. Then once you get an idea of how everything works you can use OMR and make it fast.
  - qznc 8y ago
    How does it compare to PyPy?
    - PeCaN 8y ago
      Don't know yet. IBM has a CPython-based JIT using OMR but it hasn't been publicly released yet. Ruby OMR is a little more public and from what I can tell gets about a 30%-200% speedup. They basically just stapled OMR onto the regular Ruby interpreter, so there's nothing fancy going on yet and those numbers will definitely get higher.
    - ufo 8y ago
      Different technology. PyPy/RPython is a more "high level" approach built on top of metatracing while OMR is more low level and geared towards method-at-a-time JIT. (I might be wrong. I worked more with pypy but only know OMR superficially)
mncharity 8y ago
A while back, it looked like v8 deopt type guards, for at least monomorphic call sites, were consistently ending up off of the processor speculative execution mainline. They were "free"-ish. Then speculative execution attacks and mitigations hit. Does anyone know the current state of play? I've wanted fast multiple dispatch in js for many years. V8's handling of inlining budgets improved, and guards seemed off mainline, so I'd looked forward to trying again to get dispatch trees inlined away. Then Spectre hit. :/
- jcdavis 8y ago
  Not really familiar with v8 internals, aren't there ways to do deopts without relying on guards? The JVM deopts methods by hotpatching the start of them to be a jump to runtime handlers.
  - mncharity 8y ago
    > aren't there ways to do deopts without relying on guards Yes, in general. But I was basically hoping to craft a javascript multiple dispatch implementation that mostly landed on V8's existing dispatch fast path. A polymorphic inline cache for a call site, starts with a check(s) that the object is an expected type. And a bit of inlined code, may start with checks that the inlining assumptions (types of arguments, etc) are still valid. In the JITed assembly, it looks like a bunch of test and jump instructions that come before the real work. But the processor's branch prediction, ideally recognizes that the common case is a still-valid cache/inlining. So the processor's speculative execution, ideally proceeds immediately with the real work. The checks happen off to the side - they don't delay the real work. One way to do dynamic multiple dispatch is a dispatch tree of similar checks. As with regular dispatch, most multiple dispatch call sites are monomorphic. So if the dispatch checks gets inlined, you would have an extended version of the usual checks. And V8 changed how it allocates it's inlining budget, in a way that made arranging for inlining of dispatch seem more plausible than it once was. My hope was the dispatch checks would also happen off mainline. So multiple dispatch might be as fast as single dispatch. But then speculative execution implementation flaws were recognized as a security threat, and jits began intentionally disabling or constraining speculative execution. Which might be sufficient to invalidate the whole idea. Since those mitigations seem an ongoing work in progress, and in the past I've found it expensive to tool up for v8 jit code analysis, I thought I'd see if anyone already had a feel for where we're at/headed.
corysama 8y ago
I wish http://terralang.org http://terralang.org got more attention. It’s a great way to write a jitting library. Add in LuaPEG and it’s a great way to write a jitting language.
- iTokio 8y ago
  Doesn’t it rely on llvm internally? That means that the jit path is slow to start and that your have a huge dependency.
  - corysama 8y ago
    terra.dll is 53 megs. Terra is really oriented around high performance computing, so if you want a quick little script, it's a bad fit. For small apps, it can still be useful as an ahead-of-time compiler to either a stand-alone executable or a C-linkable library.
- ufo 8y ago
  I'm not sure I'd put Terra together with dynamic language JITs. It a low-level statically typed language that is closer to C than to Lua.
  - corysama 8y ago
    Terra itself is static, yes. But, the idea is to use Lua to parse your own language then compose Terra on the fly to execute your language. So, it's a roll-your-own-language foundation rather than a language-specialized JIT. http://terralang.org/api.html#embedding-new-languages-inside-lua http://terralang.org/api.html#embedding-new-languages-inside...
sigjuice 8y ago
Title should say 'JIT compiler'.
- jamestimmins 8y ago
  Is it not fair to say that this is the same thing? My impression was that in designing a compiler you're explicitly determining the rules for language, which is the same as designing the language itself? Or do you mean that technically the compiler, not the language, is JIT? This is a new area for me so apologies if I'm just misunderstanding the mechanics here!
  - ufo 8y ago
    In theory the programming language is independent from the implementation. You could write an alternate implementation if you wanted. JIT-ness is a concept related to the implementation, not to the language.
    - jamestimmins 8y ago
      Gotcha, that makes sense. So I'm guessing that java based python vs c based python is an example of theory vs implementation? Thanks for explaining!
      - ufo 8y ago
        Yup
    - developer-mike 8y ago
      The language is, however, designed to be JITted. Languages are not designed in isolation.
- developer-mike 8y ago
  This is true in the same sense that "a JIT" should really be "a JIT compiler." Used as "a JIT," the term is given new meaning (to refer to a compiler implicitly). And used as "JIT language," its giving the term a new meating (to refer to the fact that the language designed to be JITted).
s2g 8y ago
This is cool, I used to really like this sort of thing. At some point I transformed into a bitter sad man who can't stand reading articles like this because I feel like such a worthless piece of crap.
- sitkack 8y ago
  > bitter sad This can be your muse, channel it into something!
barrkel 8y ago
It is so pleasant to read an article with Intel asm syntax rather than AT&T, my eyes thank you.
timClicks 8y ago
wren is another language that fits lots of extra data within the "spare" bits within NaNs. http://wren.io/ http://wren.io/
- 52-6F-62 8y ago
  That seems like a great project
mingodad 8y ago
I'm impressed that people didn't mention https://www.gnu.org/software/libjit/ https://www.gnu.org/software/libjit/ it's a small well designed library with a very good interpreter. I wish more people put some effort on improving it and all of us could benefit form it without reinventing the whell again and again.
- b2gills 8y ago
  I'm very confident it would not be very good at optimizing Perl 6 code. On the first page of the documentation for libjit is this: “Only a very small proportion of the work is concerned with language specifics.” The thing is that Perl 6 tends to break more of the established rules than it follows. For example, most normal operators in Perl 6 are just subroutines with a special name: a + b == &infix:«+»(a,b) put &infix:«+».candidates.elems; # 26 There is currently 26 multi subs with the same name for handling the numeric infix addition operator. (27 if you count the proto sub) That is among the easiest of things to optimize in Perl 6. I would also like to know if it is a JIT that profiles and compiles the optimized code on another thread like MoarVM does. Is there a plugin system that allows high level code to influence what code gets JIT compiled like MoarVM recently received? I'm sure that for just about every other dynamic language libjit would be very suitable. It's just that I imagine it would quickly strain under the weight that is Perl 6. (Perl 6 brings in many varied features from many languages, and combines them in a way that it feel like they have always belonged together.)

Sure, there are things that can be "poison pills" for performance, even in JITs. For example, another reason why my fib benchmark beats V8 is that V8 has to continually check if the fib function was redefined as a deoptimization check. I don't allow that in Vaiven, so I can produce faster code. Dart was designed to have fewer of these poison pills, for instance. Note to language designers: Reduce your language's poison pills. For those which can't be avoided, make them easy to profile!

TomMarius 8y ago
Is there a list of common language poison pills? I'd like to learn more.
- saagarjha 8y ago
  I'd assume anything that breaks expectations and speculative execution. Weak typing, dynamic function calls, etc.
- jerf 8y ago
  Well, I can't do a full list, but: Memory non-locality. On modern systems, thrashing through RAM just kills you on performance. I don't know that you have to hand full control over to the programmer, but if you're randomly flinging values on the heap everywhere (a.k.a. "hash tables"), you're gonna hit a wall long before you get to "C performance". For JITs, any time the JIT has the ability to make an assumption, but then you break it. The obvious one is "this function always returns an int", which the JIT can nicely optimize, but if once you ever return a string, the JIT will have to do something to deoptimize that case again, possibly permanently. More subtly, things like "returning an object that always has these three keys that map to these three values of a certain type", which a JIT can optimize to a struct under the hood, until you change a type or add a field for a particular call. Just in general, any assumption the JIT can make for performance that you might break in a function. You should generally program your performance-sensitive JS as if it were statically typed, even if it isn't. Indirection for the user's convenience; one of the reasons CPython is sooo slooooow is that there's a ton of indirection going on. For the code x.y(), you can change x by directly overriding "y" on the specific x you are using, or it can be set at the class level, or it can be set by any of the superclasses, or the dot operator may be a function that does arbitrary things up to and including arbitrary mutation of whatever it gets its hands on, etc., plus even without overridding getattr there's this whole "property" thing, plus it could be a __slot__, and I'm pretty sure I'm missing at least one thing here, and CPython is hopping through all these hoops for every such lookup. The fact that "x.y()" translates to dozens or hundreds of C lines of code is what Python so convenient, but at the same time, what makes it so slow, too. I understand the value of being able to override things; I question the need of dynamic scripting languages to provide so many places to override things.
  - blattimwind 8y ago
    > I don't know that you have to hand full control over to the programmer, but if you're randomly flinging values on the heap everywhere (a.k.a. "hash tables"), you're gonna hit a wall long before you get to "C performance". Rule of Python: Everything is at least two pointers away. -- > and CPython is hopping through all these hoops for every such lookup. Actually CPython has a cache for that. This becomes apparent if you improperly replace methods in the class dictionary. I think the bane of Python specifically is a bit different. It's not so much that it's very dynamic, because JITs can clearly deal with that. It's that CPython exposes all kinds of interpreter state that's off-limits in other languages, which makes it way harder to JIT. In JavaScript there are at most a handful ways how you can mutate a prototype, but in CPython you don't have enough fingers to count them, even if you only consider Python and not the C API.
    - jerf 8y ago
      "Actually CPython has a cache for that." My apologies for my unclarity. In my head, "hopping through all these hoops" included using caching, but that is completely unclear. It is true that there is a lot of caching being done, because it would simply be unusable if there isn't. But it is also true that there is still a lot of work to do for "x.y()", even when all caches are used fully.
      - blattimwind 8y ago
        Yes... and most of it is even part of stable APIs.
  - arghwhat 8y ago
    I'd like to add: Don't define your array as nothing but a hashmap with strings as array indexes, with two assignment hooks: One that on assignment updates that sets length = max(length, ToUint32(assigned key)), and one on "length" assignment that iterates over all keys in the hashmap, and for those that can be parsed as uint32's, delete those that have a numerical value larger than the value assigned to length. That is how JavaScript "Array" objects work. Array indexes are coerced to a strings, as they are for all objects. For the curious, here is full definition from ECMA-262 1st edition, which describe what browsers currently implement (https://www.ecma-international.org/publications/files/ECMA-ST-ARCH/ECMA-262,%201st%20edition,%20June%201997.pdf https://www.ecma-international.org/publications/files/ECMA-S..., page 65): Array objects give special treatment to a certain class of property names. A property name P (in the form of a string value) is an array index if and only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 232−1. Every Array object has a length property whose value is always an integer with positive sign and less than 232. It is always the case that the length property is numerically greater than the name of every property whose name is an array index; whenever a property of an Array object is created or changed, other properties are adjusted as necessary to maintain this invariant. Specifically, whenever a property is added whose name is an array index, the length property is changed, if necessary, to be one more than the numeric value of that array index; and whenever the length property is changed, every property whose name is an array index whose value is not smaller than the new length is automatically deleted. This constraint applies only to properties of the Array object itself and is unaffected by length or array index properties that may be inherited from its prototype.
- kodablah 8y ago
  Anything that has to be interpreted or un-JIT'd for the most part. Runtime eval, runtime struct memory layout redefining, runtime type change, etc. Basically it's a trade off between pre-compiled immutable omniscience and developer friendliness. Targeting the former often increases perf due to the assumptions you can make, targeting the latter increases comfort and adoption and usability and simplicity.
- gameswithgo 8y ago
  a JIT is one! time is wasted doing compiling while running, the compiler has strict time constraints so can't do as many optimizations, claims about theoretical benefits from runtime data collection and-recompilation for optimization are rarely reazlied in the actual world and profile guided optimizations can achieve similar things for AOT compiled programs. soooooooooooo AOT master race
  - TomMarius 8y ago
    What about WebAssembly? How would you provide the same guarantees and benefits without JITing or interpreting?
  - bjoli 8y ago
    As someone who has ported racket's for loops to guile scheme (or at least, re-implemented them without looking at the source of the original racket macros), a JIT has several benefits. There are some things that you just can't know at compile time, and hot paths/inline caches solve a lot of those things. for example (for/list ([a (in-range a b c)]) (+ a 100)). Since in-range has to check when to end the loop, it has to know whether the loop goes in negative or positive direction (ie: to check the loop using < or >). If the values of a b c isn't known at compile time, the comparator has to be checked for each loop. This can potentially be very expensive, especially in an inner loop. There are loads of optimizations that can be done much more efficiently/easily by a JIT. Store sinking, store/load forwarding, array bounds check elimination, value-range propagation and hyperblock scheduling to name a few. LuaJIT is still the fastest dynamic language out there, but the complexity of the codebase surely makes you wish that wasn't the case.
    - ufo 8y ago
      You can avoid the test by generating two loops (one that goes up and one that goes down). But that can lead to code bloat...
- beagle3 8y ago
  Mike Pall of LuaJIT fame opined on that on the luajit mailing list a few years back. Can't find the discussion right now, but only https://news.ycombinator.com/item?id=8605225 https://news.ycombinator.com/item?id=8605225 which is somewhat relevant.
- bjoli 8y ago
  Redefining things are generally a no-no, especially top level things. Knowing what things are and where they are makes things much easier to implement. For inline caches it is much better if you don't redefine things, which applies to JITs. I remember reading that Mike Pall said about pypy that most of the optimizations he did for luajit were possible for python, but just a lot more work. Using mutation is a really good way to make most scheme implementations run slowly, since mutation is generally avoided, and thus most flow analysis is spent on checking recursion. A while-loop using set! is generally a lot slower than a recursive named let loop. Flow analysis is simply easier without mutation, even though it might not look easier for the person reading the code.
- ufo 8y ago
  The poison-pills are implementation dependent. At the end of the day it is just a matter of the JIT not optimizing a certain programming pattern. Sometimes it is just because the authors didn't get around to that yet. Sometimes there is a more fundamental reason why optimizing that pattern would be hard. I am most familiar with LuaJIT. It has wiki page with a list of things that force it to fall back to the interpreter http://wiki.luajit.org/NYI http://wiki.luajit.org/NYI
  - TomMarius 8y ago
    Sure. I was interested in known patterns that make optimization hard, because I'm toying with implementing a language myself. Thank you for your link!
jerf 8y ago
I would be intrigued to see a modern attempt at a dynamic language like Python or Ruby, but with attention paid from day one to ensure that only very JIT-able constructs were used, and with an eye towards the language helping the user stick to those and be aware of when they deviate, rather than designing a language, setting "runs fast" somewhere around the third or fourth priority, then trying to JIT it after 10-15 years of non-JIT development. Even LuaJIT, which is to my understand the closest anyone has come to this, still was retrofitting JIT onto an existing language. I'm not convinced we're going to see much more performance out of JS, for instance, which is about as fast as a dynamic language can go nowadays. But I wonder what the real limits of a "dynamic scripting" language would be from this perspective. Edit: Per my other comment about indirection being a performance poison pill, here's an example of an idea where a new scripting language might be able to get a lot of performance. Suppose you keep the ability to dynamically create classes and load code and so forth, so that (just as an example, not necessarily a good idea) you can write code that dynamically connects to a database and loads in tables as classes with automatically defined properties, etc. But instead of working the way the languages do now, instead of constantly walking through all the layers of indirection that can be used to implement all this at every call site and for every call, what if you could do something like the "pledge()" call that says "OK, this is it, I'm all set up, the dynamism is all done, you may now assume that all the type analysis you've done is now complete". Now the JIT can drop all of its paranoia code. It isn't completely obvious to me how to do this correctly (by implication, if you can "connect to a database" before this pledge()-like call is done, you have to have a pretty complete runtime available just for that), nor is it obvious to me how this would affect the type system, etc. Maybe it's not possible. But it's the type of thing I mean that would be interesting to have examined by someone, who might be able to concretely show why it's not possible, or, whoknows, make it work. And that's just one idea of how to design a dynamic language from the top for performance, basically off the cuff; who knows what a smart person who sat down and thought about this for a couple of weeks before even beginning to code could come up with. Another one is that it isn't obvious to me that scripting languages must be all based on hash tables that laboriously can be cast back to structs by the JIT; it seems to me that it would also be feasible to go the other way, and allow users to define things as structs, and if you want to offer hash-like access it would be easy to lay down hash-like access to the struct members (iteration, etc.), and either implicitly or explicitly also offer an "overflow" hash table if desired. This would give at least a bit of locality control. Something something arrays too for array control, and suddenly you're starting cook with gas.
amelius 8y ago
Isn't there some kind of static analysis possible for such cases?
- saagarjha 8y ago
  If you could perform static analysis on these cases, why couldn’t the JIT just do so itself and not have any issues?
  - amelius 8y ago
    Well, I suppose a JIT has tighter time constraints.
- arghwhat 8y ago
  JavaScript is too dynamic for such analysis. JavaScript at its core is not a very well designed language, and it's a bloody miracle that a JIT can make it usable. If you're designing a new language, don't make everything (even arrays!) a hashmap.
  - j-pb 8y ago
    [1]In clojure the array type is basically a hashmap to enable high perf/low memory immutability. So I would say "Yes[1]" ^^
    - arghwhat 8y ago
      I would certainly say "no" to having your basic array type be a hashmap as a hashmap is several orders of magnitude slower than an array for all operations on small arrays and for access for all sizes, although there is nothing wrong with also having hashmap and linked list collections if you need O(1) inserts. However, what I was referring to is much worse than that: JavaScript arrays are defined as a normal hashmap with string keys with hooks on assignment to parse the key as a uint32 and update the length property if the value is larger than the current one, and on length assignment iterate over all keys and delete those that successfully parse as a uint32 and has a numeric value larger than the one assigned to length.
white-flame 8y ago
I say screw deoptimization checks, and put the burden in the redefinition processing. When you redefine something, you stop the world at safepoints and update prior baked assumptions that are registered on the old definition. These redefinitions usually happen during development and initialization, not during performance-sensitive runtime. It would add more to the memory footprint, but that information is not accessed at all except during recompilation.
- chrisseaton 8y ago
  > I say screw deoptimization checks > you stop the world at safepoints But that's how deoptimisation checks work.
- arghwhat 8y ago
  Then you either need to have "redefinition" checks, or an actual, full stop the world, which is also a performance nightmare and also affects unrelated code. The proper solution is to not have unnecessary dynamics. There is no need for the ability to redefine methods on an object. If you have functions as first-class objects, you can just let users store functions and call them at the cost of indirection if they wish to have such dynamics.
  - wahern 8y ago
    > There is no need for the ability to redefine methods on an object In prototype-based languages like JavaScript and Lua redefining methods on an object is common at runtime, which makes them quite challenging to JIT. It may be most common early in execution, but there's no way to semantically define that boundary. Since Lua 5.2 (IIRC) certain metamethods are locked & loaded when you assign a metatable (a prototype definition) to an object. Thus, the __gc finalizer is only obeyed if it existed when the metatable was set on the object. (I don't think this was a performance improvement--more about tradeoffs in GC complexity--but it's an example of side-effect semantics that could be leveraged for JIT optimization.) But this isn't the case for OOP-like methods (which in Lua are normally defined indirectly through the __index metamethod field), as those are ad hoc and would be expected to change during runtime. A similar issue occurs in any dynamic language (JavaScript, Lua, Perl, etc) that uses generic dictionaries for assigning and loading functions. Ideally a JIT would know that invoking a function like "a.b.foo()" would always load the same function and could elide the dictionary lookup for "b" and "foo". But keeping track of whether the dictionary a or b was modified is costly. Theoretically you could, e.g., add callback hooks to dictionary entries that, when invoked, invalidate some JIT'd block; but such conditional checks and operations cause a huge amount of code bloat and slow down the fast path. Adding more logic in an attempt to minimize unnecessary work causes the same problems. The lesson from languages like Forth, K, and Lua is that the most important thing to optimize isn't JITing, but the software VM itself, including the bytecode and dispatch tables. (Mike Pall of LuaJIT fame makes this point.) The deep pipelines and huge caches (e.g. for branch speculation) in modern processors means that the abstraction of a bytecode and dispatch table can often be subsumed into the pipeline, resulting in a fixed but relatively small overheard as compared to native code. This is especially true for the bulk of the application code, where you may only see a [hand waving] 1.5x or 2x overhead in a language like Lua or especially LuaJIT. And you can do even better by moving specific hot spots into C code. Languages like Python and Ruby don't have nearly as lean a VM as Lua so the overhead is greater and more variable, but the idea is similar. If WebAssembly catches on, I think we'll begin to see some regressions in JavaScript JITs because the marginal cost and complexity won't be as worthwhile when people begin moving compute-heavy code into WebAssembly. Simplicity might even bring some performance improvements for code that was never susceptible to JITing because there'll be less baggage. [1] Largely a result of the lean and clean semantics. Which is not the same as power--Lua has fully lexical scoping with proper closures, and asymmetric stackful coroutines. Asymmetric, stackful coroutines are exceedingly powerful abstractions, but also rid Lua of the colored functions[2] problem that languages that adopt explicit async/await semantics have, which means function invocation semantics are unified making the implementation simpler and leaner and in turn making it more likely VM dispatch is cleanly pipelined in hardware. Less is more. Which is a similar lesson Linux taught the world--Windows never had fork() as it was considered too heavyweight and complex for the common case, and instead focused on multiple different interfaces, one for creating threads and one for invoking new programs. But Linux optimized the heck out of fork, so even creating a thread is faster on Linux than on Windows, and the semantic power of fork makes it easier to implement complex resource sharing schemes between processes than on Windows (i.e. rather having an extremely complex data structure and flags for telling the OS what resources to pass or share between processes, you just use other common APIs--e.g. dup(), etc--before exec()). [2] http://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/ http://journal.stuffwithstuff.com/2015/02/01/what-color-is-y...
pjc50 8y ago
Most of the poison pills are someone else's convenience features, sadly.
Sawamara 8y ago
Note to commenter: you can design a language to never change a function's signature, in which case that language loses the "dynamic" and "scripting" part (okay, maybe just the dynamic part). Nothing wrong with having ultra-dynamic languages, but you will inevitably trade speed for quirky code in cases like that.
- burfog 8y ago
  So the restrictions needed for performance also eliminate many causes of unmaintainable messy code and runtime errors? This is an easy decision.

filereaper 8y ago

PSA: If there are folks writing their own JIT languages (and are highly encouraged to do so) please also checkout out the Eclipse OMR project. OMR is a bunch pluggable runtime components (GC, JIT etc...) intended to ease building of runtimes from scratch. https://github.com/eclipse/omr https://github.com/eclipse/omr

tomcam 8y ago
What an incredible resource. Thank you.
PeCaN 8y ago
OMR is amazing. It's essentially IBM's J9 virtual machine, with all the man-decades of effort that went into that. However, if you're writing your own JIT language and you've never written one before, you probably want to learn something and write your own GC, JIT, etc. It's really not that hard. Then once you get an idea of how everything works you can use OMR and make it fast.
- qznc 8y ago
  How does it compare to PyPy?
  - PeCaN 8y ago
    Don't know yet. IBM has a CPython-based JIT using OMR but it hasn't been publicly released yet. Ruby OMR is a little more public and from what I can tell gets about a 30%-200% speedup. They basically just stapled OMR onto the regular Ruby interpreter, so there's nothing fancy going on yet and those numbers will definitely get higher.
  - ufo 8y ago
    Different technology. PyPy/RPython is a more "high level" approach built on top of metatracing while OMR is more low level and geared towards method-at-a-time JIT. (I might be wrong. I worked more with pypy but only know OMR superficially)

mncharity 8y ago

A while back, it looked like v8 deopt type guards, for at least monomorphic call sites, were consistently ending up off of the processor speculative execution mainline. They were "free"-ish. Then speculative execution attacks and mitigations hit. Does anyone know the current state of play? I've wanted fast multiple dispatch in js for many years. V8's handling of inlining budgets improved, and guards seemed off mainline, so I'd looked forward to trying again to get dispatch trees inlined away. Then Spectre hit. :/

jcdavis 8y ago
Not really familiar with v8 internals, aren't there ways to do deopts without relying on guards? The JVM deopts methods by hotpatching the start of them to be a jump to runtime handlers.
- mncharity 8y ago
  > aren't there ways to do deopts without relying on guards Yes, in general. But I was basically hoping to craft a javascript multiple dispatch implementation that mostly landed on V8's existing dispatch fast path. A polymorphic inline cache for a call site, starts with a check(s) that the object is an expected type. And a bit of inlined code, may start with checks that the inlining assumptions (types of arguments, etc) are still valid. In the JITed assembly, it looks like a bunch of test and jump instructions that come before the real work. But the processor's branch prediction, ideally recognizes that the common case is a still-valid cache/inlining. So the processor's speculative execution, ideally proceeds immediately with the real work. The checks happen off to the side - they don't delay the real work. One way to do dynamic multiple dispatch is a dispatch tree of similar checks. As with regular dispatch, most multiple dispatch call sites are monomorphic. So if the dispatch checks gets inlined, you would have an extended version of the usual checks. And V8 changed how it allocates it's inlining budget, in a way that made arranging for inlining of dispatch seem more plausible than it once was. My hope was the dispatch checks would also happen off mainline. So multiple dispatch might be as fast as single dispatch. But then speculative execution implementation flaws were recognized as a security threat, and jits began intentionally disabling or constraining speculative execution. Which might be sufficient to invalidate the whole idea. Since those mitigations seem an ongoing work in progress, and in the past I've found it expensive to tool up for v8 jit code analysis, I thought I'd see if anyone already had a feel for where we're at/headed.

corysama 8y ago

I wish http://terralang.org http://terralang.org got more attention. It’s a great way to write a jitting library. Add in LuaPEG and it’s a great way to write a jitting language.

iTokio 8y ago
Doesn’t it rely on llvm internally? That means that the jit path is slow to start and that your have a huge dependency.
- corysama 8y ago
  terra.dll is 53 megs. Terra is really oriented around high performance computing, so if you want a quick little script, it's a bad fit. For small apps, it can still be useful as an ahead-of-time compiler to either a stand-alone executable or a C-linkable library.
ufo 8y ago
I'm not sure I'd put Terra together with dynamic language JITs. It a low-level statically typed language that is closer to C than to Lua.
- corysama 8y ago
  Terra itself is static, yes. But, the idea is to use Lua to parse your own language then compose Terra on the fly to execute your language. So, it's a roll-your-own-language foundation rather than a language-specialized JIT. http://terralang.org/api.html#embedding-new-languages-inside-lua http://terralang.org/api.html#embedding-new-languages-inside...

sigjuice 8y ago

Title should say 'JIT compiler'.

jamestimmins 8y ago
Is it not fair to say that this is the same thing? My impression was that in designing a compiler you're explicitly determining the rules for language, which is the same as designing the language itself? Or do you mean that technically the compiler, not the language, is JIT? This is a new area for me so apologies if I'm just misunderstanding the mechanics here!
- ufo 8y ago
  In theory the programming language is independent from the implementation. You could write an alternate implementation if you wanted. JIT-ness is a concept related to the implementation, not to the language.
  - jamestimmins 8y ago
    Gotcha, that makes sense. So I'm guessing that java based python vs c based python is an example of theory vs implementation? Thanks for explaining!
    - ufo 8y ago
      Yup
  - developer-mike 8y ago
    The language is, however, designed to be JITted. Languages are not designed in isolation.
developer-mike 8y ago
This is true in the same sense that "a JIT" should really be "a JIT compiler." Used as "a JIT," the term is given new meaning (to refer to a compiler implicitly). And used as "JIT language," its giving the term a new meating (to refer to the fact that the language designed to be JITted).

s2g 8y ago

This is cool, I used to really like this sort of thing. At some point I transformed into a bitter sad man who can't stand reading articles like this because I feel like such a worthless piece of crap.

sitkack 8y ago
> bitter sad This can be your muse, channel it into something!

barrkel 8y ago

It is so pleasant to read an article with Intel asm syntax rather than AT&T, my eyes thank you.

timClicks 8y ago

wren is another language that fits lots of extra data within the "spare" bits within NaNs. http://wren.io/ http://wren.io/

52-6F-62 8y ago
That seems like a great project

mingodad 8y ago

I'm impressed that people didn't mention https://www.gnu.org/software/libjit/ https://www.gnu.org/software/libjit/ it's a small well designed library with a very good interpreter. I wish more people put some effort on improving it and all of us could benefit form it without reinventing the whell again and again.

b2gills 8y ago
I'm very confident it would not be very good at optimizing Perl 6 code. On the first page of the documentation for libjit is this: “Only a very small proportion of the work is concerned with language specifics.” The thing is that Perl 6 tends to break more of the established rules than it follows. For example, most normal operators in Perl 6 are just subroutines with a special name: a + b == &infix:«+»(a,b) put &infix:«+».candidates.elems; # 26 There is currently 26 multi subs with the same name for handling the numeric infix addition operator. (27 if you count the proto sub) That is among the easiest of things to optimize in Perl 6. I would also like to know if it is a JIT that profiles and compiles the optimized code on another thread like MoarVM does. Is there a plugin system that allows high level code to influence what code gets JIT compiled like MoarVM recently received? I'm sure that for just about every other dynamic language libjit would be very suitable. It's just that I imagine it would quickly strain under the weight that is Perl 6. (Perl 6 brings in many varied features from many languages, and combines them in a way that it feel like they have always belonged together.)