> JITs are pretty much a necessity for languages with dynamic dispatch, which are nearly impossible to optimize ahead-of-time,
Depends what you consider "nearly impossible". A lot of compilers for dynamic languages are just awful for no particularly good reason so it's often hard to assess what is slow because it is hard and what is slow because the implementation disregards the last 30 years of experience with compiling dynamic languages.
E.g. I'm working on an ahead-of-time Ruby compiler. While it will need a JIT component for cases where people call eval, and while Ruby is particularly nasty to compile for a variety of reasons, the method dispatch is easy to reduce to one indirection via a vtable (you just need to propagate method overrides down the class hierarchy and update the vtables, but updates to the methods is much rarer than cals so it's ok for it to be more expensive), equivalent to C++ virtual member functions (though C++ compilers have better hope of being able to optimize away the virtual call).
Despite the pathological cases possible because of the singly rooted object hierarchy, for most typical applications the wasted space in vtables (for method slots for methods that are unimplemented in a specific branch of the class hiearchy) is easily compensated for by e.g. needing less bookkeeping for methods that are known statically at compile time (which is the vast majority for most applications).
If you're willing to compile a fallback path and suitable guards, you can sometimes optimize away many indirections entirely and even inline code ahead of time even for languages like Ruby (incidentally for example of that you can look at the work Chris Seaton has done on a JRuby Truffle/Graal backend - while that does these optimizations at runtime, many of them are applicable ahead of time too, though the JIT can get the advantage of not having to generate code for fallback cases unless they're actually needed at runtime)
Note that I agree with you that JIT's have many advantages. At the same time, while I love the flexibility of dynamic languages, I prefer the smallest number of moving wheels possible in production environment. Spent too long doing devops.. Makes me lament the lack of attention to AOT/"as static as possible" compilers for dynamic languages.
"E.g. I'm working on an ahead-of-time Ruby compiler.... easy..."
If you haven't already... it's 2015. You might want to go look at the sun-bleached bones of all your predecessors who confidently proclaimed that all the dynamic scripting languages were slow for no good reason and a JIT could totally just JIT all the slowness away.
If it's a journey you wish to take, by all means, be my guest, but, please, be sure you know what you're getting into.
(The aforementioned sun-bleached bones are the bulk of the reason why I no longer believe in the old adage that "languages don't have performance characteristics, only implementations do", at least in the full sense intended. Languages may not have performance characteristics but the evidence rather strongly suggests they can put upper bounds on performance.)
You might want to go look at the sun-bleached bones of all your predecessors
who confidently proclaimed that all the dynamic scripting languages were slow
for no good reason and a JIT could totally just JIT all the slowness away.
I ask this with the best of intentions: where can I learn more about this?
(FWIW, I'm curious specifically about the ways in which Common Lisp (or Lisps in general) does or does not avoid the performance pitfalls of - say - Ruby or Python. But I'm definitely interested in the general topic as well...)
Study PyPy, particularly w.r.t. to the definition of RPython and why it had to have the restrictions it had.
There's a lot of issues that Python/Ruby/Perl/JS have at runtime that Lisp takes care of at compile time, where everything is technically a massive set of method resolutions. Lisp may allow macros to do the same thing, but careful construction will do more of the resolution at compile time.
If you are coming from the perspective of a Ruby programmer, there are lots of papers on optimising Ruby in the Bibliography http://rubybib.org.
But what you want to do is take a look at a few of the VM papers there, and then look at their references and see what people have tried previously. The related work sections often talk about previous limitations.
Lisps in general are much more static than a language like Ruby, so it wouldn't be very instructive to compare against them. The trickiest Ruby features are things like Proc#binding and Kernel#set_trace_func, as these require you to modify running code and data structures which may have already been very aggressively modified.
I don't think (but am not an expert) that most Lisps have features like those. Lisps have code as data of course, which sounds like a nightmare to compile, but it's really not - the code trees are immutable (I believe) when generated, so just compile them whenever you see a new tree root and cache.
With just the vtables, Kernel#set_trace_func is reasonably easy - you can do it just by introducing thunks that proxy to the real method after calling the trace function. Wasteful, though, but easy to patch in/out.
The moment you inline, I think it's still possible to do reasonably ok using ptrace as long as sufficient debug info is kept to identify call sites. In both cases I think that for my project, if I ever get to looking at set_trace_func, I'll probably require a compiler option to enable debug info, as it's not exactly frequently used. Alternatively use the approach we've discussed and fall back to a "slow path".
Binding is basically a closure that captures all local variables and arguments of its context, so it's not that tricky in most cases as long as you can identify it and alias / copy variables into a separate environment. This is already how I handle block references to surrounding variables - by hoisting the creation of the environment for the closure up to the start of the relevant scope and aliasing all mentioned variables.
eval() of course complicates this massively, but then eval() complicates everything massively - and doubly so for ahead-of-time compilation.
Features like generic dispatch in Common Lisp result in similar amounts of dynamism; methods and classes can be defined and redefined at any time so a lot of work goes into making that fast; see for example http://metamodular.com/generic-dispatch.pdf
> Lisps in general are much more static than a language like Ruby
What?
You mean running code directly off of data structures like in Lisp interpreters, using late binding, dynamic CLOS dispatch with method combinations, a full blown meta-object protocol, etc. is more static than Ruby?
I specifically addressed this. You may need to re-compile if you see a new code data structure instance, but when you've compiled the fact it came from a data structure isn't interesting. All JIT compilers have code as data - they have an IR.
> late binding
This is no more troublesome than it is in Ruby.
> dynamic CLOS dispatch with method combination
But these are optional features that you sometimes use. In Ruby all operations, method calls and most control structures use the strongest form of dynamic dispatch available in the language.
> full blown MOP
So does Ruby.
So I can't say Lisp is any more dynamic for the compiler than Ruby. A sibling of yours mentioned a trace extension but said people don't expect it to be fast so nobody is bothering. In the implementation of Ruby I work on, we've even made set_trace_func as fast as we can.
Well I'm not an expert in compiling Lisp and I guess you're not an expert in compiling Ruby, so we're probably not going to come to an agreement on this.
> A sibling of yours mentioned a trace extension but said people don't expect it to be fast so nobody is bothering.
That's a bit of a misrepresentation of what I said. I don't know about TRACE in particular (which is not an extension but a core part of the language), but the sbcl developers in particular have been very attentive to the performance of development tools like that. (And, probably, the commercial vendors, as well.)
He means, I think, that method dispatch (i.e. function resolution) in Lisps is less dynamic than in Ruby/JS, where you resolve the call target by searching for the method name in a map -- at least as an abstraction -- belonging to the target object at runtime (or Ruby's method_missing). I am not familiar with all Lisps, but their method polymorphism is usually much more structured.
Actually CLOS (Common Lisp Object System) is more dynamic than Ruby.
Every CLOS method is part of a generic function. Each generic function is a collection of methods. At runtime the applicable methods are collected, based on the runtime class graph of the arguments to dispatch over, and an effective method is assembled by a per generic function method combination.
Method selection is also depending on more than one argument (the target object), but on multiple arguments.
Various parts of that are implemented by a meta-object protocol in CLOS implementations, which make it possible to change the behavior of the object system at runtime in various ways.
Your contraction massively misrepresents what I wrote. Compiling Ruby is by no means easy. And optimizing it to similar speed as e.g. C is massively hard.
But optimizing the dynamic dispatch down to the cost of a vtable call is trivially easy.
"Your contraction massively misrepresents what I wrote."
Yeah, sort of, but it represents what I was trying to say accurately enough. You will find, as you go through your project, that nothing is "trivially easy" when it comes to JIT'ing Ruby, and, alas, "just compile it down to a vtable call" is likely to not be that easy either. Dynamic language JITs have a terrible recursive 90/10 problem. In fact I doubt that it actually will be that simple because if it were, PyPy would be a great deal faster than it is.
(From a JIT perspective, Ruby and Python are all but identical.)
The point I'm making is not that you shouldn't do this. The point is that A LOT of people have ALREADY done this, and it has proved to be a lot harder than any of them thought, and you really ought to take some time to go study PyPy or various PHP JIT projects before getting too excited about thinking that you are going to speed Ruby up as much as you think you are. Particularly have a look at RPython. If you are going to tackle this project, this notorious Zeno tarpit [1], I recommend everyone do it with eyes open. No, it isn't going to be as easy as "just do X", or it would already have been done.
> nothing is "trivially easy" when it comes to JIT'ing Ruby
First of all, I'm not JIT'ing Ruby. Secondly, a lot of things are "trivially easy" when it comes to compiling Ruby - even ahead of time. I know, because while there's lots of outstanding bits, I am compiling a reasonable subset, and I understand the remaining tradeoffs well enough to know where the pitfalls are - it's by no means my first compiler
> The point is that A LOT of people have ALREADY done this
A lot of people have done this, but despite decades of history of optimisation of dynamic languages, most of them appears to not have bothered with even a cursory look at the literature.
In terms of JIT, the Truffle backend for JRuby is a good example of the difference actually applying modern techniques makes.
When you call/jump through a vtable, you've already lost inlining opportunities. Indirect branches themselves aren't free either. This is an order of magnitude performance loss for simple functions. Additional order of magnitude worse, if the simple function behind vtable indirect jump/call was a vectorization opportunity.
Agreed, which is why I also pointed out that with suitable guards and fallback path you can often inline as well, as large proportions of callsites in dynamic code is monomorphic or can be transformed to monomorphic by relatively small numbers of guards and split paths that can often be hoisted quite far.
But a call/jump via vtable is already a massive improvement over most dynamic language implementations. It's not unusual still to find e.g. hash-table lookups and hierarchical searches up through the inheritance chain for no good reason.
Depends what you consider "nearly impossible". A lot of compilers for dynamic languages are just awful for no particularly good reason so it's often hard to assess what is slow because it is hard and what is slow because the implementation disregards the last 30 years of experience with compiling dynamic languages.
E.g. I'm working on an ahead-of-time Ruby compiler. While it will need a JIT component for cases where people call eval, and while Ruby is particularly nasty to compile for a variety of reasons, the method dispatch is easy to reduce to one indirection via a vtable (you just need to propagate method overrides down the class hierarchy and update the vtables, but updates to the methods is much rarer than cals so it's ok for it to be more expensive), equivalent to C++ virtual member functions (though C++ compilers have better hope of being able to optimize away the virtual call).
Despite the pathological cases possible because of the singly rooted object hierarchy, for most typical applications the wasted space in vtables (for method slots for methods that are unimplemented in a specific branch of the class hiearchy) is easily compensated for by e.g. needing less bookkeeping for methods that are known statically at compile time (which is the vast majority for most applications).
If you're willing to compile a fallback path and suitable guards, you can sometimes optimize away many indirections entirely and even inline code ahead of time even for languages like Ruby (incidentally for example of that you can look at the work Chris Seaton has done on a JRuby Truffle/Graal backend - while that does these optimizations at runtime, many of them are applicable ahead of time too, though the JIT can get the advantage of not having to generate code for fallback cases unless they're actually needed at runtime)
Note that I agree with you that JIT's have many advantages. At the same time, while I love the flexibility of dynamic languages, I prefer the smallest number of moving wheels possible in production environment. Spent too long doing devops.. Makes me lament the lack of attention to AOT/"as static as possible" compilers for dynamic languages.