A First Look at the JIT
blog.erlang.org
blog.erlang.org
With a dynamic language like Erlang (as with JS,Lua,etc) the main benefits won't come from better register allocation,DCE,etc that is the primary reason one would pick LLVM but rather just getting rid of the interpreter overhead (and later the oppurtunity to do some higher level type dependent optimizations that will have a higher impact than register allocation and instruction selection).
Type dependant stuff why LLVM is ill suited IMHO and why you only see LLVM being mentioned as the highest optimizataion level by for example JavaScriptCore(Safari) when the runtime hasn't deoptimized code and is pretty certain of the types that will be used.
Also they mentioned the complexity of maintaining interpreter/JITed jumps and I'm not surprised since i remember reading some paper about one of their earlier attempts and they were maintaining dual stacks with quite complex cross-boundary jumps.
Some might mention that V8 moved away from the always-JIT paradigm to save on memory and startup time but since Erlang is mostly used in servers i think they might see this as a good compromise.
The most powerful JIT compiler that I have worked with - Graal - generates code that often on the face of it seems puzzlingly inefficient in terms of registers allocated and instructions selected. Turns out maybe it's another thing that's not as important as all the text books say?
The important bit is removing object allocating, removing boxing, deep inlining, and specialisation... when you've done all that work the exact registers and instructions don't seem to really make a huge difference.
Linear Scan is an example I reach for when I talk about what parts of the compiler are really important, if that's what you mean.
http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf
> The linear scan algorithm is considerably faster than algorithms based on graph coloring, is simple to implement, and results in code that is almost as efficient as that obtained using more complex and time-consuming register allocators based on graph coloring.
Also things like escape analysis and inlining are often called 'the mothers of optimisation' because they fundamentally enable so many other optimisations. Not sure there's really a citation for it but I doubt anyone would dispute.
I wrote about the impact on optimising Ruby.
These findings: The important bit is removing object allocating, removing boxing, deep inlining, and specialisation... when you've done all that work the exact registers and instructions don't seem to really make a huge difference.
> Linear Scan is an example I reach for when I talk about what parts of the compiler are really important
Sure, but you just said that register allocation is not a relevant factor compared to other achievements when using Gral VM. Or did I get that wrong?
Right - didn't I cover those? I gave the example that Graal is extremely powerful with a huge amount of money and effort behind it, but doesn't really bother at all with serious register allocation or clever instruction selection as suggested you should in text books. It uses the most basic algorithm and doesn't see any need to do any more, even when they're still keen on tiny improvements to the output. It just doesn't seem to be worth it.
But it does put a lot of effort into object allocation, boxing, inlining, specialisation, etc. So those seem in practice to be worth it.
Well, as I understand this is an assumption, not the result of a dedicated study. I made similar observations when using LuaJIT as a SOM backend (see https://github.com/rochus-keller/Som), but it's not clear why the Gral based SOM implementations are that much faster.
I'm not sure what you're angling for?
Some kind of falsifiable proof about where it makes sense to put engineering effort and complexity? You're not going to find that sorry nobody's ever been able to seriously quantify those kind of things.
> I made similar observations
Well then why are we arguing about it if it's apparent to both of us?
You assume that The important bit is removing object allocating, removing boxing, deep inlining, and specialisation... when you've done all that work the exact registers and instructions don't seem to really make a huge difference.
But it would be very interesting to have something like a scientific study about why Gral is indeed faster than other approaches.
> Well then why are we arguing about it if it's apparent to both of us?
Because I would like to understand the true reason to be able to improve my implementation (if feasible).
EDIT: as you claim textbooks about compiler design are wrong or not up to date, so my desire to have someone change that seems understandable, isn't it?
Linear Scan produces a program with apparently less efficient register allocation. In practice, it does not matter for the wider performance of the code. Is this not evidence to support the assumption that sophisticated register allocation does not matter as much as we thought?
When you enable Graal's more sophisticated escape analysis algorithms you get real-world speed ups in workloads such as Twitter, worth hundreds of thousands of dollars in costs saved. Is this not evidence to support the assumption that sophisticated escape analysis algorithms do matter?
The first is a formal scientific study. The second is not but it's still a very large-scale empirical result measured by an expert. They aren't falsifiable but as I said I don't think that's a realistic expectation, and I think these are enough for it to be more than an assumption.
It's an indication but it doesn't sufficiently support the conclusion. There are so many other things to consider.
> Is this not evidence to support the assumption that sophisticated escape analysis algorithms do matter?
Would you as a scientist seriously accept this as a sufficient evidence for your claims?
But let's leave it at that for the moment. As far as I know there are ongoing research projects which could deliver more insights why specifically a Smalltalk VM runs faster on Gral than anywhere else.
It was a comment on a web page dude... I didn't claim it in a research paper for publication!
If we discourage others from more casually sharing our observations as you're doing we'll miss opportunities to find things to form hypotheses from in the first place! Casual discussion in the community is part of science, something to be encouraged, and you're sadly missing something by dismissing it like this.
Casually sharing observations is a good thing, and even better when there is some detail information available which makes it possible to understand the propositions sufficiently well and to assess how certain the conclusions are.
For example I'll see what seems to my less-experienced eyes some completely redundant 'mov' instructions shifting things around. I'll ask 'should we fix this' and the response is usually 'doesn't really matter it's basically free'.
Well that's partly why I'm still surprised, but I think for a lot of dynamic languages there's such a huge volume of code anyway... that these little 'mov's are pretty insignificant.
Removing them would have a down-side - extra compilation time.
Most instructions have 3-20 cycle latency. A lot of what CPU do on many programs is wait for an instruction to complete so they can use its result to chase some pointer - and in the mean time, find an instruction that doesn't depend on it to execute. So many "simple" moves and register renames are practically free, as they happen in these waiting-for-result slots.
HPC code is most definitely not like that - but it's only found in specialized parts of software (game rendering paths, maths stuff, some NumPy code, etc). But most code spends most of its time with the CPU waiting.
In languages like Java w/o value types & virtual methods everywhere, interprocedural analysis is very important. Even otherwise I believe interprocedural optimizations are more important than small register fiddling or cute integer arithmetic tricks. But when you reach a dead-end in optimized code, all these things matter.
Sure, it may not matter for Erlang / Elixir on server.
I'm not sure what the differences will be but start up time is still a very big deal for web servers.
For example I can start up a non-Dockerized Python / gunicorn app with 8,000 lines of code and 50+ package dependencies in about 400ms on a $5 a month DigitalOcean server without doing any type of optimizations.
For someone who just wants to deploy a project to 1 server that means there's only 400ms of down time when I restart my server.
If a runtime takes let's say 10 seconds to start up, that could be enough of a deterrent to not use it if you know you're going down the route of a single server deploy.
Erlang already gives you robust primitives to do things like blue-green deploys, and even graceful transfer of server state even across versioning changes. If downtime between releases is an something you care about, you should use those, and it's likely that your downtime can be in the microseconds range regardless of the vm startup latency.
Which blue-green deploy primitives are you referencing btw?
To do a simple blue green deploy you just have to use the builtin node system to make a cluster, and use :global to detect if there are any downversion nodes, if the current node is up version, it slays a downversion node and your external restart mechanism (either erlangs heart, systemd, kubernetes, or Amazon elb, or whatever brings back the node but with the newer code).
They did, but their always-JIT was a bit heavyweight. They generated full method-jit code on first invocation at first. This was a massive improvement over the existing state of the art, but it was also relatively early in the whole development of the "fast JS" ecosystem we live in now.
The _size_ of JS grew, and the size of functions grew, and the complexity of logic grew. The amount of cold and run-once code grew.
That issue was brought into focus by the growth of the webapp space and the size of the payloads.
In this case (erlang folks) - they're going about the whole thing in a very good way. Their "jit-everything" is actually "jit one instruction at a time", which is _amazingly_ perceptive of the challenges people in other JIT teams have faced (e.g. JS JIT teams). What they're doing is tightly scoped, easy to bootstrap and test with fallbacks to VM-calls into the VM for slowpaths or complicated stuff.
That's a solid base you can slowly layer with higher tiers later if it matters. They're keeping their abstraction layers strong by having a well-specified bytecode system, and hopefully they will strive to keep it relatively independent of the runtime, and avoid leakages of runtime semantics into instructions.
I was personally very impressed by their description of their approach and motivation behind each decision.
Had a brief look at asmjit; as it seems it only supports x86 and x86_64 and is not really an abstraction (i.e. a platform independent IR). I will try to find out why they didn't use e.g. LLVM or sljit.
EDIT: according to this article (https://www.erlang-solutions.com/blog/performance-testing-th...) the speed-up factor caused by the JIT is about 1.3 to 2.3 (as a comparison the speed-up between the PUC Lua 5.1 interpreter and LuaJIT 2.0 is about factor 15 in geometric mean over all benchmarks, see http://luajit.org/performance_x86.html).
Probably because it uses DynASM and I believe only those platforms are supported.
I had a look at https://github.com/asmjit/asmjit/tree/master/src/asmjit and didn't find any indication that DynASM is used. Anyway, DynASM and LuaJIT are available for many different architectures, not only x86 and x86_64.
https://github.com/erlang/otp/pull/2745#issuecomment-6914821...
“
LLVM is much slower at generating code when compared to asmjit. LLVM can do a lot more, but it's main purpose is not to be a JIT compiler.
With asmjit we get full control over all the register allocation and can do a lot of simplifications when generating code.
On the downside we don't get any of LLVMs built-in optimizations.
We also considered using dynasm, but found the tooling that comes with asmjit to be better.
“
EDIT: But it still gives no answer why they preferred asmjit in favour of other solutions than LLVM or DynASM (where the latter is just an assembler which helps to integrate with C code, not a platform abstraction like LLVM or others).
Even LuaJIT can be used as a backend for other languages than Lua, see e.g. https://github.com/rochus-keller/oberon/.
That's not exactly true from what I recall of speaking with Vikram and Chris. The idea was to build a compiler framework that could support profile-guided optimization (and other then-advanced JIT techniques) for idle-time or install-time optimization of C/C++ codes. Chris's original thesis doesn't even mention JIT compilers, except as comparison point for techniques, and instead focuses on things like link-time optimization. (Indeed, Chris offered LLVM to replace gcc's then-broken LTO infrastructure, but this was turned down.)
Having a platform independent IR in AsmJit is not planned. AsmJit is more about control and ISA completeness. IR could of course be implemented on top of AsmJit, but it seems nobody really needed that so far - users that need complex IR can use LLVM and users that want something really simple can use SLJIT. AsmJit is just in a different category and it has a lot of useful features considering its size.
You can look back all the way to a 1995 paper (1) (with people that then worked on early Java JIT's) that did a comparison of JIT vs AOT compilation for Self, while good AOT is kind of feasible in many ways there is always situations in languages not initially designed for AOT where a JIT won't be forced to go with conservative estimates that hampers performance.
So AOT compilation was not tested in that paper.
> This may seem silly, aren’t machine registers faster?
> Yes, but in practice not by much and it would make things more complicated.
My understanding is that the latency of an L1 cache load is 5 cycles on recent Intel processors.
In tight code that is a really substantial overhead. I get that register allocation is complicated, and I totally see the benefit of simplicity, but it's hard not to think that this will significantly limit performance.
Erlang is designed for massive, distributed, highly reliable network systems. Therefore, it is likely that a lot of Erlang code does a lot of waiting around for the network rather than needing every available CPU cycle.
This is the first time they're releasing a JIT. They'll deliver their performance gains, and if they want to and it seems feasible they can come back and do further work in the future.
But you have to put work in where it's valuable, and somehow I doubt RabbitMQ (for example) is going to care about this being missed this time around.
https://en.wikichip.org/wiki/intel/microarchitectures/skylak...
[1] http://blog.erlang.org/a-closer-look-at-the-interpreter/
Yeah, that is a jit. Perhaps not a very fancy one, the same way ARC is a very unfancy GC, but it is still a jit.
Yes... but it does that just-in-time, which is what JIT stands for.
> There's no advanced type specialization or lazy deoptimization.
I don't think those things are required for it to be a JIT are they? I'd say it's a static JIT, rather than a dynamic, profiling, and specialising JIT, but both are JITs.
> It might as well be an in-memory, lazy, AOT compiler.
Well yeah... that describes a JIT.