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!
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.
> 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.
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.
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.
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.
> That is how JavaScript "Array" objects work. Array indexes are coerced to a strings, as they are for all objects.
Well, according to the spec. All modern VMs make optimisations for small integers, which is allowed as long as the behaviour is in accordance to the spec.
Of course, but the language spec severely limit what optimizations can be done.
For example, V8 will happily give you a proper array if certain criteria is met, but it must always be ready for you trying to index it with a string, which means that it must attempt to parse the string as a numeric value. This means deoptimization checks, or in the worst case, a non-optimized array.
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.
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
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.
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 which is somewhat relevant.
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.
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
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.
I think Julia is a great example.
It also uses a "world-age" for function redefinitions, like another commenter suggested, to put the burden on redefinitions rather than than using runtime deoptimizations.
Before implementing the world age, they still didn't deoptimize. This meant that if "bar" called "foo", you call "bar" (causing it to compile), and redefine "foo", and then call "bar" again, it would still use the old foo method. That workaround (redefining "bar") was inconvenient, but unlike with deoptimizing, there was a workaround.
One comment on Julia though. It isn't like other JIT languages.
It's a lazy statically compiled language with a REPL. It uses LLVM (like Clang) to compile functions the first time they're called for a given set of input types (every function is like a C++ template by default).
This makes it easy to get C-level speed, because all it is is a different front end (with extensive type inference infrastructure/default "auto" for all types) to the same back end.
This is in constrast to an interpreted language, where code only gets compiled when hot (but then with the potential of profile-guided compilation, which could sometimes let them run even faster).
Is Julia really a Python competitor, I mean, for the same sort of niches? I had the impression that it was more specialized than that. (Bearing in mind of course that once you're Turing Complete and have a C binding you can technically do anything. Not that either of those two is necessary, but they are sufficient.) But as my phrasing implies, it was just an impression, and two people have mentioned it now.
Common Lisp, well, I suppose I'll leave that up to the reader. Personally, I observe that in a context where dynamic languages are being discussed in a positive manner, Common Lisp is a dynamic language, but when static languages are being discussed in a positive manner, suddenly Common Lisp is a static language. (In fact, that pattern may hold in general; for any given programming individual language characteristic being positively discussed, Common Lisp will have it, no matter how contradictory the whole set may be.) Under the hood, it must resemble one or the other more strongly, but after years of consuming advocacy, heck if I know which.
Honestly, the managed environment that is a lisp runtime gets to put a lot of the power into the developer. Just look into the dissassemble abilities of most lisps. Combined with many of the type hints you can give them, it really just changes the dynamic of when things happen. Such that, it really doesn't resemble one more than the other. Just depends what you want.
Because Common Lisp is powerful enough to get it both ways.
When old timers discuss Common Lisp, usually it goes around the development experience of yore that Allegro and LispWorks still offer, but most FOSS variants fail short of.
As for Julia, yes their main niche is scientific computing. Being able to write everything 100% in Julia, instead of switching to C, C++ or Fortran.
Common Lisp at the language level is similar to Python or Ruby as it has strong dynamic typing. One difference is that CL has optional type declarations which (in contrast to Python's take on the same thing) are really specified as declaring types but what the implementation should do with that information is completely implementation-defined with using it to implement C-style weak static typing being completely legitimate and for some time even popular.
Common Lisp systems have supported two ways to develop software:
a) fast incremental development of Lisp code. For that one got Lisp interpreters (executing the code on the s-expression level) and quick incremental compilers. Code then tends to be more on the dynamic side with full debug information.
b) delivery of optimized applications for deployment. We got optimizing native-code AOT compilers (using type hints and type inference), block compilers (optimizing larger batches of code), whole-program Lisp-to-C compilers and application delivery tools with tree shakers. Code then tends to be more on the static side with little or not debug/development information.
Between a) and b) there is a continuum of different approaches - often in the same program in different code sections - where compilers may support different code generation strategies.
Thus one can develop using an interpreter or fast incremental compiler, and then deliver with an optimizing compiler.
Common Lisp (CL) as a language is highly dynamic. However the typical implementation is incrementally AOT compiled (when you define a function, it is compiled, but you can redefine functions with few limitations).
CL as a language is essentially untyped[1], but does provide some provision for type hints in the standard. Some implementations extend this to the point where they can generate code as efficient as a typed language. Most implementations can also use these to detect some fraction of type errors when compiling.
Some features in lisp were designed with less flexibility to allow for improved performance while others with flexibility at the expense of performance.
I can't imagine how anyone could ever consider CL to be a static language without horribly misunderstanding the term, the language, or both.
1: You can declare types of variables, but the specification clearly intends this to be for optimization purposes: "
Type declarations present in the compilation environment must accurately describe the corresponding values at run time;..." the fact that some implementations use these type hints for more does not IMO change the nature of the language.
> consider CL to be a static language without horribly misunderstanding the term
If you look at the file compilation spec in the standard, the compiler is allowed to inline functions and it can assume that a function in the same file can't be redefined later. -> no late binding for the calls in the file. A function declared by the developers to be inlined, makes them also no longer use late-binding for calls.
Specific implementations may also remove the compiler (see Allegro CL, LispWorks and some others), parts of an interpreter and other stuff of a typical Lisp runtime from a delivered applications. Generally function calls then might no longer use late-binding.
The CL standard might mention some dynamic facilities, but actual implementations might remove parts of that from a delivered application, too.
Example for more static facilities were the block compilation mode of Lucid CL, IIRC CMU CL also had a block compilation mode, some compilers do their own inlining (Allegro CL), mocl/clicc (and some others) do 'static' compilation of whole-programs for a large CL subset to C applications, LispWorks has an extensive delivery system which removes various unused Lisp facilities from an application ( http://www.lispworks.com/documentation/lw71/DV/html/delivery... ) and which can drastically reduce dynamic features.
The standard is not 'dynamic' - it leaves a lot up to the implementations.
The CL standard is describing more 'static' options than usual for Lisp. Lexical binding is more static than Dynamic Binding. Macros are more static than Fexprs. A file compiler is more static than an interpreter.
Common Lisp was already designed with support for higher-performance implementations on stock hardware.
Python is not a 'language' - but for most people it is the combination of a language and its implementation. In this Python one of the main (THE main?) ways to get better performance is to write the code in C.
Not so Common Lisp - it is a language and a bunch of more or less conforming implementations. There the first and most important way to get better performance always has been to use an optimizing to-C or a to-Machine-Code compiler, code hints and compiler switches (SPEED, SAFETY, DEBUG, ...).
For example the developers of a large CAD system written mostly in Lisp (iCAD, PTC, ...) did not compete with Python at that time, but with C++ based CAD systems. Having a dynamic CLOS implementation is then often a burden: how many objects can be created per second? How many generic function calls are possible per second?
For example LispWorks allows the slot-value function to call a generic function slot-value-using-class. This is slow. Thus by default it is shut off.
Clozure CL has I/O functions over streams. By default streams are not CLOS objects / functions. One can get them as CLOS objects, but one has to do that.
There are many other examples where the implementation provides a dynamic version and a more static version.
The typical example in Common Lisp, the language itself: structures and CLOS classes.
Structures are efficiently compiled with inline access, no slot information, no updates on structure changes, efficient access into the slot (-> no multiple inheritance with changing slot otder).
CLOS classes OTOH are the opposite. More dyanamic, especially in an implementation with the Meta-object Protocol supported.
Whenever you decide to use structures in your program, then you choose 'static & fast'. When you choose CLOS classes then you choose: runtime dynamism and generally slower.
The standard itself does not talk about a specific implementation - the implementations in use and the needs of the developer for their application delivery determines then how 'static' the implementation can be or needs to be.
I know at least in LuaJIT you can use FFI to declare structs beforehand and gain a bunch of performance. But that's not a JIT-provided step. That's just something you have to do by hand.
> 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
I think "unknown type at compile time" and "JIT-able constructs" are opposites. You'd end up with a tracing JIT that compiles the same set of code in different, specialized ways based on runtime determination of the the input types as though the lang was static. Which is basically what we have today. You can have optionally typed languages, but you still have to write your runtime and compiler to the lowest common denominator, so you probably want to go more strict if you care about your (runtime or compile-time) compiler and runtime performance (as the Dart devs learned IIRC).
I would assume "JIT-ability" is proportional to the immutable input and output knowledge of the code to be compiled.
> I think "unknown type at compile time" and "JIT-able constructs" are opposites.
Not opposites exactly. Types enforce a phase separation between compile time and runtime, but there's no reason you can't have a compilation phase at runtime too. This leads to staged programming, like MetaOCaml.
Well, to phrase it simply, in my mind a dynamic type is not a very JIT-able construct. I suppose it comes down to what people consider "very JIT-able", but I don't consider the same code possibly JIT'ing in separate ways in the same execution as very JIT-able.
It depends what you mean by "dynamic type". Since we're talking about some hypothetical dynamic language which is JIT-friendly, "dynamic type" could mean a "staged type" of some kind.
It's kind of like how some static languages use code generation, say, based on a database schema, which is then compiled, except this would happen at runtime. It would have to let you programmatically guide this process dynamically, but the result is very close in performance to a statically compiled language.
I mean it in the most traditional sense of the term, a type that nothing can be assumed about it until runtime (especially since GGP mentioned Ruby or Python, type hints notwithstanding). The more you can determine before execution, of course the more you can help your JIT/compiler and it becomes less dynamic. Code generation, macros, type providers, etc do not affect the language's type-dynamicness IMO.
MoarVM has had a JIT since 2014.
(MoarVM was announced in January 2014, got a type specializer in March of that year and got the beginnings of a JIT in August of that year)
What it just got recently is a pluggable specializer that allows more interesting optimizations to be written in a higher level language (NQP). Since this is closer to Perl 6 than the VM it has more information with which to decide how to optimize code.
(Note that it also means you can do the same with any other language that runs on MoarVM, even if it is very different from Perl 6)
> 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.
This sounds a lot like Object.freeze[0] in JS, at least for prototypes. I can't remember any of the major engines doing this, but it could be an interesting direction to explore.
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
Someone did a study of their Python servers, and found that after an initial phase, almost no dynamic facilities were used at all!
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
I like that. Smalltalk kind of did this, but much less. Objects were just arrays of object references, but certain object references were adorned smallint values. People also wrote hash-like accessor implementations for objects. "Shape changes" to objects of a certain class would require a stop the world re-allocation of all such objects, however.
It seems like an horribly expensive shenanigan to me.
F# can do all the work that you described at compile time using type providers with no runtime cost and no need for a call to pledge()...
What will happen if someone forgets to call pledge?
Or, even worse, if someone calls pledge and then he does some other dynamic operation?
Or if he calls pledge at the right time but one thread has been rescheduled and when it is executed again it will continue to issue dynamic instructions?
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.
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.
You say all this as if JS's jit engines (V8, chakra, spidermokey, etc) did not destroy "better designed" languages when it comes to speed and efficiency. The only dynamic language that does not pale beyond what is achieved with V8 is LuaJIT.
How many "better designed" dynamic languages are there even out there? Julia is one such language and is substantially faster than V8, at least for idiomatic code.
The problem is that most dynamic languages (like JS) are never designed with speed and efficiency in mind. JS just happens to be the fastest of that bunch (other than Lua) because browser makers have invested substantial effort into making it fast - far more than anyone has put into other dynamic languages.
I hate JS with a passion (I worked with it professionally for years, and wrote crypto and compression algorithms, as well as an entire web browser sandbox), but my refuge is in static languages.
I no longer see dynamic languages useful for more than bash-like scripting where correctness is uninteresting. :/
I don't understand interest in dynamic languages. I have worked with them extensively, but I find them to be handicapped without benefit.
However, JS specifically was not designed at all to begin with, but just thrown together, and core concepts have stayed since this first iteration. These core concepts are its primary handicap.
But yes, in general the same lack of static guarantees that makes dynamic languages slow also makes code in dynamic languages hard to maintain. I think a lot of programmers tinker with code in dynamic languages and end up liking them as a result, but don't realize the difficulty of working in such a language in a much more complex codebase.
I'm curious what your claim is. The evidence here is primarily that engineering effort can provide massive benefits to runtime speed. This is not that controversial, I believe. It can feel disappointing, but there is no reason for it to. The people working on those engines are putting a ton of solid effort into it. They deserve the recognition they have gotten.
This in no way argues against some other languages being better designed for performance. Indeed, many other languages are better designed for performance. The designers should get recognition for the contributions they have made, as well.
Again, though, it can sound like disappointment that we can't get both teams working together. I contend that is short sighted. Yes, we can imagine a world where they worked together to make even better things. However, don't let that imagined world stop any communication on the front lines that we have today. (That make sense?)
The performance of JS is purely down to absolute compiler genius, which would have given better results and been better applied to a language that was not designed on the back of a napkin. JS does everything in its power to make life hard for the compiler.
Outside JS, most compiler work goes into static languages (which I strongly prefer), but once WebAssembly DOM support comes through, better languages will run on V8, stripping JS of everything it has.
> JS does everything in its power to make life hard for the compiler.
This is a bit hyperbole. It could be worse, it could be python. Yes pypy does not have the investment of v8, but there is more to it than that. Yes js sucks but the language was relatively simple enough to get speedups that would not be possible in jitted python because frankly python is a steaming hodge lodge pile of shit when you take the system as whole (imnsho)
You don't need in place memory operations with ridiculous performance in most(tm) applications.
On the contrary there are many applications where security is far more important than speed and something that basically embodies remote code execution (browser) is one of those.
The fact that JS has made this implementation choice while at the same time being mutable is the true peril, not the specific implementation per se.
Ah yes, I had forgotten about Typed Arrays, which is a terrible name for what is in fact a buffer view. The entire arraybuffer/typedarray system was a later (≥IE10 if I am not mistaken?) hack added to make up for the fact that Array and Number are super inefficient for data processing.
But regardless of them being a bandaid, you are correct that it is an exception. ArrayBuffer and all its views count 10 types in total, so were they the only exception? If so, I believe my point still stands.
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.
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.
> 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...
> 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.
It is common, but I do not think it is at all necessary. It always looks nasty whenever I see it in dynamic languages, and I never feel a need to do so in static languages. Whenever functionality is swapable, you'd instead have a function pointer that you call from a permanent method.
> 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.
I'd very much question this. Properly optimized JIT output should be orders of magnitude faster than interpreted bytecode for even the best interpreter, and if enough is JIT'ed, the interpreter is no longer in play. Contradicting data would be interesting, although I do not generally concern myself with dynamic languages anymore unless I have to.
Many language implementations divide their JIT into a "baseline JIT" and a "full JIT". A fast interpreter can do the job of the baseline JIT, with faster startup speed and less latency.
Having a good baseline (either a JIT or just a good interpreter) also means that you don't need to rely as much on the full JIT. This is important because it is actually hard to spend 100% of the time in the JIT -- poison pills abound.
> Properly optimized JIT output should be orders of magnitude faster than interpreted bytecode
Say we had code like,
a + b
Statically compiled code might look like
load a from stack to register
load b from stack to register
add a and b
A VM would look like
load opcode from state to register
compute opcode address # nullop or two loads and index
jump to opcode block
load a from state to register
load b from state to register
add a and b
All of that is easily pipelined, especially by the very latest processors which speculate through indirect jumps (which is why we have Spectre, etc). The above is idealized but well reflects, I think, how modern register-based software VMs work.
But when you have a JIT for a dynamically typed language, the entry and exit points of both interpreted sequences and JIT'd sequences require many more instructions to manage bookkeeping, exploding the cost. JIT'ing only works if you can compile blocks of code large enough that the benefits exceed the bookkeeping costs. But that's a tall order for dynamically typed languages where runtime mutations can invalidate JIT'd blocks at many points in a sequence, such as with prototype-based languages.
Getting "[p]roperly optimized JIT output" is the crux of the problem. It takes significant instrumentation and indirection to create and maintain "[p]roperly optimized JIT output". You can't compare the optimized machine code sequences to the analogous interpreted sequences, independent of the surrounding machinery.
Much of the performance benefit of statically compiled code isn't in execution, per se, but in the data structures. A language like Lua is constantly indexing hash tables[1] for even simple record objects, whereas in C you're usually doing direct memory references. But transforming hash table lookups in a dynamic language into direct memory references a la statically compiled C structs is extremely hard if not impossible. Engines like V8 manage to do it much of the time in the context of loading prototype methods, but for ad hoc runtime data structures I don't think it can optimize that at all.
But if your code is primarily operating on, e.g., JSON trees, it wouldn't matter one way or another. If your statically compiled code isn't benefiting from direct memory addressing of data (as is the case with many types of applications) then statically compiled, JIT'd, and interpreted code can have similar runtime profiles, and in many cases you can't even be sure which will be faster in real-world systems.
[1] Lua has opcodes for this so the cost is fixed and small relative to raw C code doing the lookup. And strings in Lua are interned so lookup is usually as simple as a mask and direct index into an array.
load opcode from state to register
compute opcode address # nullop or two loads and index
jump to opcode block
load a from state to register
load b from state to register
add a and b
This example means that a simple addition requires several loads, a jump, and due to the nature of such a VM, also a store that you did not mention so that the next opcode can use the result.
The JIT'ed version might end up as simple as:
ADD ECX, EDX
Why? The JIT version will take care of making the input simple platform integers, and can ensure that the values are kept in registers between all computations within the function. for fully JIT'd methods, args and return values can be passed as registers, never needing a load, and if a parameter is a small constant, it can be inlined into the instruction (e.g. ADD EAX, 3). Function calls can also be inlined, and depending on things, the arguments may be passed as registers to non-inlined JIT'd functions as well.
While the (extremely simplified!) VM example you gave can surely be pipelined well, it still has extremely suboptimal performance compared to a single "add" instruction (long jumping around is not free!), and wastes resources that could have been used to run the rest of the code. Instruction cache, micro-op cache and instruction decoder time are all very limited and valuable resources that would be wasted by such a VM.
Furthermore, in a real-world scenario, the VM version will be much worse, with potentially overloadable add operators and the likes, effectively making "add a + b" into a madness that potentially involves looking up inheritance chains to find an implementation of an "add" method.
The assumption that the JIT will need to have checks as a significant portion of the runtime for something like this would normally be false, unless the function indeed only implements "a+b". For a method-based JIT (i.e. jitting methods rather than arbitrary loops), any necessary checks will be at the beginning of the method as a one-time cost. These checks are usually quite basic, such as checking that an input is a primitive number (meaning no overloaded functionality or otherwise unexpected behavior), which is a simple compare. Assuming you do some longer math, the check becomes a very insignificant portion of the execution time.
I agree that data structures is a big part of performance (less wasted memory access), and that dynamic languages can't get quite as good as static languages in this regard, but V8 certainly does quite well in this regard. In JIT'd methods, it will even throw away JS types entirely and just operate in proper primitives if it can (V8's hidden classes are also quite robust, as long as you stick somewhat to the initial layout created by the method initially returning the object, such as a prototype constructor). However, I think it is incorrect to consider the better performance to not also be due to much better use of instructions and registers. With what I do for work, a single branch in the wrong place can lead to a 15% drop in performance, so I certainly do not think that CPU time should be tossed around.
I agree that things like navigating a large tree structure is mostly memory bound, but even then, a VM will show some amount of performance degradation over natively compiled code.
Array languages like APL/K/J can be tremendously fast for an interpreter, since each bytecode works on entire arrays at a time. Not quite as fast as say, C or C++ compiled with a modern compiler, but I think they can match other static languages. And of course, when you're branching on or processing single values rather than whole arrays/matrixes, you lose the speed benefit.
I'm not sure fork is a good example. Languages that rely on threads or coroutines (like Java or Go) don't even support the traditional fork semantics. This is a global operation that plays havok with language-level invariants.
How about a language that loses the ability to redefine structures and methods after a certain point?
I've been thinking of making a scripting language where you can freely redefine things until you return the main function to the script's caller. At that point main gets compiled / JITed / otherwise locked and any redefinitions done by calling it are errors.
Or even just a manual bake() call, with an expensive unbake() to use during development (or maybe even deployed if it's that reconfigurable). But I do agree that a tool like this should affect the global environment and not try to be fine grained. Leave any fine-grained decisions up to the VM itself.
Most languages lack one of these phases. C/C++ and the C preprocessor are completely different languages, you can't execute C code during preprocessing. That's annoying and the reason for the introduction of constexpr in C++11. Other languages are too dynamic to be handled by a static compiler, but might benefit if you could transition to optimized machine code at runtime. Except for Lisp, I don't think there are many other languages where such a thing is possible.
This seems nice but it is hard. Imagine the following scenario in a JavaScript where one has lisp like singly linked lists:
function map(f, list) {
if (list==null)
return null;
return cons(f(head(list)), map(f, tail(list)));
}
Now as there is a call to map, a JIT compiled version will put in a redefinition check and if the check passes then it can call an optimised map which eg knows it has two arguments and f is a function. If the check fails then a slow path which does a full call is followed.
In your scenario there is no redefinition check and instead when one tries to redefine map, any optimised calls must be downgraded to the slow path.
But now imagine calling map with a function that redefines map after say the third recursive call. Then the redefinition downgrading magic needs to somehow modify one version of map halfway through a call so that when f returns it will call the new map, but the calls further up the stack frame don’t need to be modified as they won’t call map again.
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.
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.
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.
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.
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)
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. :/
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.
> 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.
I wish 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.
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.
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.
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!
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).
I'm impressed that people didn't mention 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.
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.)
119 comments
[ 42.9 ms ] story [ 3068 ms ] threadNote to language designers: Reduce your language's poison pills. For those which can't be avoided, make them easy to profile!
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.
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.
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.
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-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.
Well, according to the spec. All modern VMs make optimisations for small integers, which is allowed as long as the behaviour is in accordance to the spec.
For example, V8 will happily give you a proper array if certain criteria is met, but it must always be ready for you trying to index it with a string, which means that it must attempt to parse the string as a numeric value. This means deoptimization checks, or in the worst case, a non-optimized array.
AOT master race
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.
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.
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
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.
The Ruby community went in different direction here [2] with RTL MJIT.
[1] https://github.com/eclipse/omr [2] https://medium.com/square-corner-blog/rubys-new-jit-91a5c864...
One comment on Julia though. It isn't like other JIT languages. It's a lazy statically compiled language with a REPL. It uses LLVM (like Clang) to compile functions the first time they're called for a given set of input types (every function is like a C++ template by default). This makes it easy to get C-level speed, because all it is is a different front end (with extensive type inference infrastructure/default "auto" for all types) to the same back end.
This is in constrast to an interpreted language, where code only gets compiled when hot (but then with the potential of profile-guided compilation, which could sometimes let them run even faster).
Common Lisp, well, I suppose I'll leave that up to the reader. Personally, I observe that in a context where dynamic languages are being discussed in a positive manner, Common Lisp is a dynamic language, but when static languages are being discussed in a positive manner, suddenly Common Lisp is a static language. (In fact, that pattern may hold in general; for any given programming individual language characteristic being positively discussed, Common Lisp will have it, no matter how contradictory the whole set may be.) Under the hood, it must resemble one or the other more strongly, but after years of consuming advocacy, heck if I know which.
Can't speak to the other two.
When old timers discuss Common Lisp, usually it goes around the development experience of yore that Allegro and LispWorks still offer, but most FOSS variants fail short of.
As for Julia, yes their main niche is scientific computing. Being able to write everything 100% in Julia, instead of switching to C, C++ or Fortran.
The adoption rate seems to be "slow and steady".
a) fast incremental development of Lisp code. For that one got Lisp interpreters (executing the code on the s-expression level) and quick incremental compilers. Code then tends to be more on the dynamic side with full debug information.
b) delivery of optimized applications for deployment. We got optimizing native-code AOT compilers (using type hints and type inference), block compilers (optimizing larger batches of code), whole-program Lisp-to-C compilers and application delivery tools with tree shakers. Code then tends to be more on the static side with little or not debug/development information.
Between a) and b) there is a continuum of different approaches - often in the same program in different code sections - where compilers may support different code generation strategies.
Thus one can develop using an interpreter or fast incremental compiler, and then deliver with an optimizing compiler.
CL as a language is essentially untyped[1], but does provide some provision for type hints in the standard. Some implementations extend this to the point where they can generate code as efficient as a typed language. Most implementations can also use these to detect some fraction of type errors when compiling.
Some features in lisp were designed with less flexibility to allow for improved performance while others with flexibility at the expense of performance.
I can't imagine how anyone could ever consider CL to be a static language without horribly misunderstanding the term, the language, or both.
1: You can declare types of variables, but the specification clearly intends this to be for optimization purposes: " Type declarations present in the compilation environment must accurately describe the corresponding values at run time;..." the fact that some implementations use these type hints for more does not IMO change the nature of the language.
If you look at the file compilation spec in the standard, the compiler is allowed to inline functions and it can assume that a function in the same file can't be redefined later. -> no late binding for the calls in the file. A function declared by the developers to be inlined, makes them also no longer use late-binding for calls.
Specific implementations may also remove the compiler (see Allegro CL, LispWorks and some others), parts of an interpreter and other stuff of a typical Lisp runtime from a delivered applications. Generally function calls then might no longer use late-binding.
The CL standard might mention some dynamic facilities, but actual implementations might remove parts of that from a delivered application, too.
Example for more static facilities were the block compilation mode of Lucid CL, IIRC CMU CL also had a block compilation mode, some compilers do their own inlining (Allegro CL), mocl/clicc (and some others) do 'static' compilation of whole-programs for a large CL subset to C applications, LispWorks has an extensive delivery system which removes various unused Lisp facilities from an application ( http://www.lispworks.com/documentation/lw71/DV/html/delivery... ) and which can drastically reduce dynamic features.
Common Lisp as a standard is highly dynamic. Common Lisp as actually implemented and used is sometimes much less dynamic.
Does the existence of Cython mean that Python is a static language? Most python programmers will never use it so I would argue not.
The CL standard is describing more 'static' options than usual for Lisp. Lexical binding is more static than Dynamic Binding. Macros are more static than Fexprs. A file compiler is more static than an interpreter.
Common Lisp was already designed with support for higher-performance implementations on stock hardware.
Python is not a 'language' - but for most people it is the combination of a language and its implementation. In this Python one of the main (THE main?) ways to get better performance is to write the code in C.
Not so Common Lisp - it is a language and a bunch of more or less conforming implementations. There the first and most important way to get better performance always has been to use an optimizing to-C or a to-Machine-Code compiler, code hints and compiler switches (SPEED, SAFETY, DEBUG, ...).
For example the developers of a large CAD system written mostly in Lisp (iCAD, PTC, ...) did not compete with Python at that time, but with C++ based CAD systems. Having a dynamic CLOS implementation is then often a burden: how many objects can be created per second? How many generic function calls are possible per second?
For example LispWorks allows the slot-value function to call a generic function slot-value-using-class. This is slow. Thus by default it is shut off.
Clozure CL has I/O functions over streams. By default streams are not CLOS objects / functions. One can get them as CLOS objects, but one has to do that.
There are many other examples where the implementation provides a dynamic version and a more static version.
The typical example in Common Lisp, the language itself: structures and CLOS classes.
Structures are efficiently compiled with inline access, no slot information, no updates on structure changes, efficient access into the slot (-> no multiple inheritance with changing slot otder).
CLOS classes OTOH are the opposite. More dyanamic, especially in an implementation with the Meta-object Protocol supported.
Whenever you decide to use structures in your program, then you choose 'static & fast'. When you choose CLOS classes then you choose: runtime dynamism and generally slower.
The standard itself does not talk about a specific implementation - the implementations in use and the needs of the developer for their application delivery determines then how 'static' the implementation can be or needs to be.
I think "unknown type at compile time" and "JIT-able constructs" are opposites. You'd end up with a tracing JIT that compiles the same set of code in different, specialized ways based on runtime determination of the the input types as though the lang was static. Which is basically what we have today. You can have optionally typed languages, but you still have to write your runtime and compiler to the lowest common denominator, so you probably want to go more strict if you care about your (runtime or compile-time) compiler and runtime performance (as the Dart devs learned IIRC).
I would assume "JIT-ability" is proportional to the immutable input and output knowledge of the code to be compiled.
Not opposites exactly. Types enforce a phase separation between compile time and runtime, but there's no reason you can't have a compilation phase at runtime too. This leads to staged programming, like MetaOCaml.
It's kind of like how some static languages use code generation, say, based on a database schema, which is then compiled, except this would happen at runtime. It would have to let you programmatically guide this process dynamically, but the result is very close in performance to a statically compiled language.
What it just got recently is a pluggable specializer that allows more interesting optimizations to be written in a higher level language (NQP). Since this is closer to Perl 6 than the VM it has more information with which to decide how to optimize code. (Note that it also means you can do the same with any other language that runs on MoarVM, even if it is very different from Perl 6)
This sounds a lot like Object.freeze[0] in JS, at least for prototypes. I can't remember any of the major engines doing this, but it could be an interesting direction to explore.
[0]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
Someone did a study of their Python servers, and found that after an initial phase, almost no dynamic facilities were used at all!
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
I like that. Smalltalk kind of did this, but much less. Objects were just arrays of object references, but certain object references were adorned smallint values. People also wrote hash-like accessor implementations for objects. "Shape changes" to objects of a certain class would require a stop the world re-allocation of all such objects, however.
If you're designing a new language, don't make everything (even arrays!) a hashmap.
So I would say "Yes[1]" ^^
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.
The problem is that most dynamic languages (like JS) are never designed with speed and efficiency in mind. JS just happens to be the fastest of that bunch (other than Lua) because browser makers have invested substantial effort into making it fast - far more than anyone has put into other dynamic languages.
I love Lua personally, but it has its own traps too. Never could get into Python too much, the indentation syntax is killing me :P
I no longer see dynamic languages useful for more than bash-like scripting where correctness is uninteresting. :/
However, JS specifically was not designed at all to begin with, but just thrown together, and core concepts have stayed since this first iteration. These core concepts are its primary handicap.
But yes, in general the same lack of static guarantees that makes dynamic languages slow also makes code in dynamic languages hard to maintain. I think a lot of programmers tinker with code in dynamic languages and end up liking them as a result, but don't realize the difficulty of working in such a language in a much more complex codebase.
This in no way argues against some other languages being better designed for performance. Indeed, many other languages are better designed for performance. The designers should get recognition for the contributions they have made, as well.
Again, though, it can sound like disappointment that we can't get both teams working together. I contend that is short sighted. Yes, we can imagine a world where they worked together to make even better things. However, don't let that imagined world stop any communication on the front lines that we have today. (That make sense?)
Outside JS, most compiler work goes into static languages (which I strongly prefer), but once WebAssembly DOM support comes through, better languages will run on V8, stripping JS of everything it has.
This is a bit hyperbole. It could be worse, it could be python. Yes pypy does not have the investment of v8, but there is more to it than that. Yes js sucks but the language was relatively simple enough to get speedups that would not be possible in jitted python because frankly python is a steaming hodge lodge pile of shit when you take the system as whole (imnsho)
You don't need in place memory operations with ridiculous performance in most(tm) applications. On the contrary there are many applications where security is far more important than speed and something that basically embodies remote code execution (browser) is one of those.
The fact that JS has made this implementation choice while at the same time being mutable is the true peril, not the specific implementation per se.
I can see at least 10 types which are not hash maps. Including all the flavors of Typed Arrays.
For example, try this:
and you get:But regardless of them being a bandaid, you are correct that it is an exception. ArrayBuffer and all its views count 10 types in total, so were they the only exception? If so, I believe my point still stands.
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.
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.
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...
It is common, but I do not think it is at all necessary. It always looks nasty whenever I see it in dynamic languages, and I never feel a need to do so in static languages. Whenever functionality is swapable, you'd instead have a function pointer that you call from a permanent method.
> 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.
I'd very much question this. Properly optimized JIT output should be orders of magnitude faster than interpreted bytecode for even the best interpreter, and if enough is JIT'ed, the interpreter is no longer in play. Contradicting data would be interesting, although I do not generally concern myself with dynamic languages anymore unless I have to.
Having a good baseline (either a JIT or just a good interpreter) also means that you don't need to rely as much on the full JIT. This is important because it is actually hard to spend 100% of the time in the JIT -- poison pills abound.
Say we had code like,
Statically compiled code might look like A VM would look like All of that is easily pipelined, especially by the very latest processors which speculate through indirect jumps (which is why we have Spectre, etc). The above is idealized but well reflects, I think, how modern register-based software VMs work.But when you have a JIT for a dynamically typed language, the entry and exit points of both interpreted sequences and JIT'd sequences require many more instructions to manage bookkeeping, exploding the cost. JIT'ing only works if you can compile blocks of code large enough that the benefits exceed the bookkeeping costs. But that's a tall order for dynamically typed languages where runtime mutations can invalidate JIT'd blocks at many points in a sequence, such as with prototype-based languages.
Getting "[p]roperly optimized JIT output" is the crux of the problem. It takes significant instrumentation and indirection to create and maintain "[p]roperly optimized JIT output". You can't compare the optimized machine code sequences to the analogous interpreted sequences, independent of the surrounding machinery.
Much of the performance benefit of statically compiled code isn't in execution, per se, but in the data structures. A language like Lua is constantly indexing hash tables[1] for even simple record objects, whereas in C you're usually doing direct memory references. But transforming hash table lookups in a dynamic language into direct memory references a la statically compiled C structs is extremely hard if not impossible. Engines like V8 manage to do it much of the time in the context of loading prototype methods, but for ad hoc runtime data structures I don't think it can optimize that at all.
But if your code is primarily operating on, e.g., JSON trees, it wouldn't matter one way or another. If your statically compiled code isn't benefiting from direct memory addressing of data (as is the case with many types of applications) then statically compiled, JIT'd, and interpreted code can have similar runtime profiles, and in many cases you can't even be sure which will be faster in real-world systems.
[1] Lua has opcodes for this so the cost is fixed and small relative to raw C code doing the lookup. And strings in Lua are interned so lookup is usually as simple as a mask and direct index into an array.
The JIT'ed version might end up as simple as:
Why? The JIT version will take care of making the input simple platform integers, and can ensure that the values are kept in registers between all computations within the function. for fully JIT'd methods, args and return values can be passed as registers, never needing a load, and if a parameter is a small constant, it can be inlined into the instruction (e.g. ADD EAX, 3). Function calls can also be inlined, and depending on things, the arguments may be passed as registers to non-inlined JIT'd functions as well.While the (extremely simplified!) VM example you gave can surely be pipelined well, it still has extremely suboptimal performance compared to a single "add" instruction (long jumping around is not free!), and wastes resources that could have been used to run the rest of the code. Instruction cache, micro-op cache and instruction decoder time are all very limited and valuable resources that would be wasted by such a VM.
Furthermore, in a real-world scenario, the VM version will be much worse, with potentially overloadable add operators and the likes, effectively making "add a + b" into a madness that potentially involves looking up inheritance chains to find an implementation of an "add" method.
The assumption that the JIT will need to have checks as a significant portion of the runtime for something like this would normally be false, unless the function indeed only implements "a+b". For a method-based JIT (i.e. jitting methods rather than arbitrary loops), any necessary checks will be at the beginning of the method as a one-time cost. These checks are usually quite basic, such as checking that an input is a primitive number (meaning no overloaded functionality or otherwise unexpected behavior), which is a simple compare. Assuming you do some longer math, the check becomes a very insignificant portion of the execution time.
I agree that data structures is a big part of performance (less wasted memory access), and that dynamic languages can't get quite as good as static languages in this regard, but V8 certainly does quite well in this regard. In JIT'd methods, it will even throw away JS types entirely and just operate in proper primitives if it can (V8's hidden classes are also quite robust, as long as you stick somewhat to the initial layout created by the method initially returning the object, such as a prototype constructor). However, I think it is incorrect to consider the better performance to not also be due to much better use of instructions and registers. With what I do for work, a single branch in the wrong place can lead to a 15% drop in performance, so I certainly do not think that CPU time should be tossed around.
I agree that things like navigating a large tree structure is mostly memory bound, but even then, a VM will show some amount of performance degradation over natively compiled code.
I've been thinking of making a scripting language where you can freely redefine things until you return the main function to the script's caller. At that point main gets compiled / JITed / otherwise locked and any redefinitions done by calling it are errors.
Sounds awesome! We could call the phases before that point "compile time" and "preprocessor time", and the phase after that point "run time".
/sarc
In your scenario there is no redefinition check and instead when one tries to redefine map, any optimised calls must be downgraded to the slow path.
But now imagine calling map with a function that redefines map after say the third recursive call. Then the redefinition downgrading magic needs to somehow modify one version of map halfway through a call so that when f returns it will call the new map, but the calls further up the stack frame don’t need to be modified as they won’t call map again.
> you stop the world at safepoints
But that's how deoptimisation checks work.
Nothing wrong with having ultra-dynamic languages, but you will inevitably trade speed for quirky code in cases like that.
This is an easy decision.
https://github.com/eclipse/omr
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.
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.
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. :/
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.
http://terralang.org/api.html#embedding-new-languages-inside...
This is a new area for me so apologies if I'm just misunderstanding the mechanics here!
JIT-ness is a concept related to the implementation, not to the language.
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).
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.
This can be your muse, channel it into something!
On the first page of the documentation for libjit is this:
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:
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.)