No one cares as much now days, we’ve moved our overrated opinion battlegrounds to other portions of what we do.
Which is not exclusively an argument for runtime JIT— it can also be an argument for instrumenting your runtime environment, and feeding that profiling data back to the compiler to help it make smarter decisions the next time. But that's definitely a more involved process than just baking it into the same JavaScript interpreter used by everyone— likely well worth it in the case of things like game engines, though.
Once you've managed to debug the codegen anyway (see: The Long and Arduous Story of Noalias).
Naively, I would have assumed that branch information would be most valuable, in terms of being able to guide execution toward the hot path and maximize locality for the memory accesses occurring on the common branches. And that info is not something that would be assisted by more expressive types, I don't think.
In finance the performance critical code path is often the one run least often. That is you have a if(unlikely_condition) {run_time_sensitive_trade();}. In this case you need to tell the compiler to ensure the CPU will have a pipeline stall because of a branch misprediction most of the time to ensure the time that counts the pipeline doesn't stall.
The above is a rare corner case for sure, but it is one of those weird exceptions you always need to keep in mind when trying to make any blanket rule.
http://eel.is/c++draft/dcl.attr.likelihood
Prior to this it was also possible, but required compiler-specific macros like GCC's __builtin_expect, which is used all over the kernel:
If you want to cause a pipeline stall, there's usually serializing instructions like cpuid/eieio.
Regardless, you can at least lay out code in a way that heavily favors one branch over the other, and potentially optimize for one branch (I.e. give one branch very expensive prelude/exit to make another branch very cheap). The last thing I’ve seen compilers greatly struggle with though…
But what likely/unlikely mechanism can do is that it can serve as a hint to the compiler which the compiler can then use to generate more optimal code layout. For example, if we provide the compiler with likely/unlikely hints in our code, compiler will try to use that hint to stitch together the more probable code paths first. In theory this approach should result with better utilization of CPU instruction cache and thus it may lead to better performance.
Assuming either source of data is the single source of truth for all optimizations is a fallacy.
Use the right tool for the right job. Use all the tools if you can.
Static + LTO w/ PGO is pretty much the practical ideal. JITs don't offer much until you start adding dynamically loaded code where LTO just isn't possible anymore.
So What language/runtime out there ships unoptimized bytecode, an optimized precompiled static + LTO w/ PGO, and can re-optimize with runtime gathered information via a JIT?
Heck, what language/runtime is even designed around being performance-focused with a JIT to deliver even more performance in the first place? Pretty much ever JIT'd language makes trade-offs that sacrifice up-front performance and later hopes the JIT can claw some of it back. maybe this is kinda WASM-ish territory, although it then sacrifices up-front performance for security and hopes the JIT can claw it back.
As others have pointed out, HP's Dynamo managed to use runtime re-optimization to improve performance of many binaries without cooperation from the original compiler. Runtime optimization doesn't strictly require any of the information lost in optimized binary builds.
Last I checked, the Android Runtime would AoT-compile Dalvik bytecode at install time, and in the background re-optimize the binary based on profiling information. Though, I don't think it performs hot code replacement.
I'm not sure the latest with Oracle's Java AoT. Last I checked, Oracle's JVM wasn't able to inline or re-optimize AoT-compiled code through JIT'd code.
Some optimizations, such as loop unrolling make JIT'ing harder. However, strength reduction, loop-invariant code hoisting, etc. make the JIT's life easier. Back around 2005-2006, my employer was getting good mileage out of a Java bytecode optimizer. If your AoT and JIT are cooperating, the AoT can stuff any helpful metadata (type information, aliasing analysis, serialized control flow graph, etc.) into an auxiliary section of the binary.
I'd like to eventually write a C compiler that essentially compiles to old-school threaded code: arrays of pointers to basic blocks (strait-line code with a single entry point and one or more exit points). Function entry would just pass the array of basic blocks to a trampoline function that calls the first basic block. Each basic block would return and index into the function's array of basic blocks for the trampoline to call next. Function return would be signaled by a basic block returning -1 to the trampoline loop. A static single assignment representation of each extended basic block would be stashed in an auxiliary ELF section. On a regular system without the runtime optimizer, the only startup overhead would be due to bloated binary size. A wild guess at the performance overhead without the runtime optimizer would be in the 5% to 15% range. However, on a system with the ELF dynamic loader replaced with a runtime-optimizer, the runtime would set up a perf signal handler that would keep counters for identifying hotspots to trace. If the tracing conditions were met, the perf signal handler would walk back up the call stack to find the last occurrence of the address of the trampoline, and replace it with a version of the trampoline that in addition, stores the address of the next extended basic block to run. Once a trace loops back on itself or meets some other TBD criteria, the runtime would stitch together the SSA representations of the constituent extended basic blocks, and generate a new optimized basic block that's the inline of the components of the trace, and finally place the address of the new extended basic block in the correct place in the array of extended basic blocks, thus performing runtime code replacement. Anyway, that's my grand vision. I've taken the introductiory Stanford compilers course, and am slowly working my way forward, but I have a job and a young kid, so I'm not holding my breath.
Most PGO for AOT scenarios suffers from tooling experience and not using data sets similar to production workflows.
Isn't low-latency trading only a subset of finance?
This is where the profile guided optimisation comes in – for statically compiled languages, with a caveat being not always straightforward to come up with a set of inputs that will trigger an execution of all possible code paths. One solution is to provide the coverage specifically for the performance critical code paths and let the rest just be.
Aren't JITs already self-instrumenting? What would you instrument that the JIT is not already keeping track of?
For object graphs in Java you can waste exorbitant amounts of memory by having a lot of “children” members that are sized for a default of 10 entries but the normal case is 0-2. I once had to deoptimize code where someone tried to do this by hand and the number they picked was 6 (just over half of the default). So when the average jumped to 7, then the data structure ended up being 20% larger than the default behavior instead of 30% smaller as intended.
For a server workflow, having data structured tuned to larger pools of objects with more complex comparison operations can also be valuable, but I don’t want that kitchen sink stuff on mobile or in an embedded app.
I still think this is viable, but only if you are clever about gathering data. For instance the incremental increase in runtime for telemetry data is quite high on the happy path. But corner cases are already expensive, so telemetry adds only a few percent there instead of double digits.
The nonstarter for this ended up being that most collections APIs violate Liskov, so you almost need to write your own language to pick a decomposition that doesn’t. Variance semantics help a ton but they don’t quite fix LSP.
Most other languages only have mutable collections, and name collection types after their implementation details instead of what the user actually wants from them.
As for mobile, this isn't far off from the whole set of hand written Assembly interpreter, JIT with PGO data caching, AOT compilation on idle with the PGO collected data, sharing PGO metadata with other devices via the PlayStore, that Android happens to do since version 7, and refined later.
Probably the optimal system is an hybrid iterative JIT/AOT compiler (which incidentally was the original objective of LLVM).
That said, a sufficiently advanced CPU could also make those optimisations on "static" code. That was one of the things Transmeta had been aiming towards, I think.
Modern compilers have a thing called PGO (Profile Guided Optimization) that lets you take a compiled application, run it and generate an execution profile for it, and then compile the application again using information from the profiling step. The reason why this works is that lots of optimization involves time-space tradeoffs that only make sense to do if the code is frequently called. JIT only runs on frequently-called code, so it has the advantage of runtime profiling information, while ahead-of-time (AOT) compilers have to make educated guesses about what loops are the most hot. PGO closes that gap.
Theoretically, a JIT could produce binary code hyper-tailored to a particular user's habits and their computer's specific hardware. However, I'm not sure if that has that much of a benefit versus PGO AOT.
In theory JIT can be a lot more efficient, optimizing for not only the exact instruction set, and do per CPU architecture optimizations, such as instruction length, pipeline depth, cache sizes, etc.
In reality I doubt most compiler or JIT development teams have the resources to write and test all those potential optimizations, especially as new CPUs are coming out all the time, and each set of optimizations is another set of tests that has to be maintained.
The thing that makes this mostly theoretical is that the underlying assumption is only true when you neglect that an AOT has zero run-time cost while a JIT compiler has to execute the code it's optimizing and the code to decide if it's worth optimizing and generate new code.
So JIT compiler optimizations are a bit different than AOT optimizations since they have to both generate faster/smaller code and the execute code that performs the optimization. The problem is that most optimizations beyond peephole are quite expensive.
There's another thing that AOT compilers don't need to deal with, which is being wrong.Production JITs have to implement dynamic de-optimization in the case that an optimization was built on a bad assumption.
That's why JITs are only faster in theory (today), since there are performance pitfalls in the JIT itself.
They still want to swap in that JIT'd result ASAP since after all by the time it's been flagged for compilation it's already too late & is a hot hot hot function.
Concretely, I think you'd want hardware that supported reservoir sampling of where CPU cycles are spent, sampling of which branches are mispredicted, and which code locations are causing cache misses. You'd also want lightweight hardware recording of execution traces.
The Javascript V8 engine, and the JVM both are popular and supported enough that I expect the teams working on them take advantage of every trick they can for specific CPUs, they have a lot of resources for this. (at least the major x86 and ARM chips - maybe they don't for MIPS or some uncommon variant of ARM...). Of courses there are other JIT engines, some uncommon ones don't have many resources and won't do this.
Not to the extent clang and gcc do, no. V8 does, e.g. use AVX instructions and some others if they are indicated to be available by CPUID. TurboFan does global scheduling in moving out of the sea of nodes, but that is not machine-specific. There was an experimental local instruction scheduler for TurboFan but it never really helped big cores, while measurements showed it would have helped smaller cores. It didn't actually calculate latencies; it just used a greedy heuristic. I am not sure if it was ever turned on. TurboFan doesn't do software pipelining or unroll/jam, though it does loop peeling, which isn't CPU-specific.
They are not very good at it, and can't be. You can look inside them and see the models are pretty simple; the best you can do is optimize for the first step (decoder) of the CPU and avoid instructions called out in the optimization manual as being especially slow. But on an OoO CPU there's not much else you can do ahead of time, since branches and memory accesses are unpredictable and much slower than in-CPU resource stalls.
For example AOT compilation often has to account for the possibility that the target machine might not have certain instructions - like SSE/AVX vector ops, and emit both SSE and non-SSE versions of a codepath with, say, a branch to pick the appropriate one dynamically.
Whereas a JIT knows what hardware it's running on - it doesn't have to worry about any other CPUs.
1. The usual caveats about benchmarking what you care about apply, of course. The mix of webish things I worked on and scientists I supported followed this pattern, YMMV.
The classical reason to use FMV is for SIMD optimizations, fwiw
An easy example is code compiled for 386 running on a 586. The A->A compiler can use CPU features that weren't available to the 386. As with PGO you have branch prediction information that's not available to the static compiler. You can statically compile the dynamically linked dependencies, allowing inlining that wasn't previously available.
On the other hand you have to do all of that. That takes warmup time just like a JIT.
I think the road to enlightenment is letting go of phrasing like "is superior". There are lots of upsides and downsides to pretty much every technique.
Also, optimizers usually target “most common denominator” so native binaries rarely use full power of current instruction set.
Jumping from that peculiar finding to praising runtime JIT feels like a longshot. To me it’s more of an argument towards distributing software in intermediate form (like Apple Bitcode) and compiling on install, tailoring for the current processor.
This turns out to be quite difficult, especially if you're using bitcode as a compiler IL. You have to know what the right "intermediate" level is; if assumptions change too much under you then it's still too specific. And it means you can't use things like inline assembly.
That's why bitcode is dead now.
By the way, I don't know why this thread is about how JITs can optimize programs when this article is about how Rosetta is not a JIT and intentionally chose a design that can't optimize programs.
> That's why bitcode is dead now.
Isn't this what Android does today? Applications are distributed in bytecode form and then optimized for the specific processor at install time.
In that case it's much less expressive, so developers simply can't do the unsafe/specialized code in the first place. Which means they can't write in C or assembly.
Bitcode was a specific Apple feature that used LLVM's compiler IL and might have promised extra portability, but it didn't really work out and was removed this year. ("LLVM" stands for "low level virtual machine" which is funny because it isn't low level and isn't a virtual machine.)
WebAssembly seems alive and well. I'm not sure how similar it is to java bitcode but its the same core idea.
That said, WASM through v8 is ~3x slower than the same code compiled natively. (Some of this might be due to the lack of SIMD in wasm).
Since 1961 plenty of systems have used bytecodes as executable formats, the most sucessfull still in use, IBM and Unisys mainframes and microcomputers.
Note that on gcc (I think) and clang (I'm sure), -Oz is a strict superset of -O2 (the "fast+safe" optimizations, compared to -O3 that can be a bit too aggressive, given C's minefield of Undefined Behavior that compilers can exploit).
I'd guess that, with cache fit considerations, -Oz can even be faster than -O2.
Or distribute it in source form and make compilation part of the install process. Aka, the Gentoo model.
Right now it's fairly common in software development to have a debug build and a release build with potentially different optimisation levels. So that's two builds to manage - if we could build with lower optimisation and still effectively run at higher levels then that's a whole load of build/test simplification.
Moreover, debugging optimised binaries is fiddly due to information that's discarded. Having the original, unoptimised, version available at all times would give back the fidelity when required (e.g. debugging problems in the field).
Java effectively lives in this world already as it can use high optimisation and then fall back to interpreted mode when debugging is needed. I wish we could have this for C/C++ and other native languages.
Everything before listen() is probably run once. Except not ever program calls listen().
I think it's a hypothetical. The Mill Computing lectures talk about a variant of this, which is sort of equivalent to an install-time specializer for intermediate code which might work, but that has many problems (for one thing, it breaks upgrades and is very, very problematic for VMs being run on different underlying hosts).
So if you ran the input back through the output multiple times then that means you could eventually get the runtime down to 0.
And then there’s processor family versus this exact model.
I know most of the time I get frustrated by everyday software, its doing something unnecessary in a long loop, and possibly forgetting to check for Windows messages too.
That already exists with c/c++...unity builds aka single translation unit builds. Compiling and linking a ton of object files takes an inordinate amount of time, often the majority of the build time
What made it interesting here was that as a sanity check they made an A->A mode where they took in one architecture and spit out machine code for the same architecture. The output was faster than the input. Meaning that even native code has some room for improvement with JIT technology.
I have been wishing for years that we were in a better place with regard to compilers and NP complete problems where the compilers had a fast mode for code-build-test cycles and a very slow incremental mode for official builds. I recall someone telling me the only thing they liked about the Rational IDE (C and C++?) was that it cached precompiled headers, one of the Amdahl’s Law areas for compilers. If you changed a header, you paid the recompilation cost and everyone else got a copy. I love whenever the person that cares about something gets to pay the consequence instead of externalizing it on others.
And having some CI machines or CPUs that just sit around chewing on Hard Problems all day for that last 10% seems to be to be a really good use case in a world that’s seeing 16 core consumer hardware. Also caching hints from previous runs is a good thing.