Hacker News Reader

Profile-guided optimization is considered pretty effective: https://en.wikipedia.org/wiki/Profile-guided_optimization

One example of an optimization that cannot be performed AOT is anything that can be done in response to "noticing" that every time you get a List, you actually have an ArrayList. AOT can't make the assumption, but a JIT can start doing things like specializing/inlining code the implementation in question.

Let's consider the context here. HFT for advanced programmers. A sufficiently smart programmer working on the hot path of some HFT trading program in an AOT language can change the parameter type to ArrayList.

You can't if the method is in the standard library, or really any third-party code you don't control.

That's one of the biggest advantages of profile-guided optimization that works at the bytecode/IR level. It can recognize that generic libraries are only ever called with a single concrete type, and then specialize them to that type, and then inline the data representations of the concrete data types you actually pass, and then inline all the accessors that access that data.

To do that AOT you need to rewrite the library, which usually defeats the purpose of having libraries in the first place.

> need to rewrite the library

Or as one other possible instance of the design space you use the approach of cpp templates or any of Zig's comptime features -- when linking against a library you explicitly instantiate code corresponding to the things you know at compile time, apply optimizations, and throw away anything that's unused. Recognizing that generic libraries are only called with a single concrete type is child's play in those contexts.

> Recognizing that generic libraries are only called with a single concrete type is child's play in those contexts.

It's pretty trivial to prove this wrong. Return a different concrete type based on a config value that is loaded at startup. AOT can't save you here. We can keep moving goalposts but it shouldn't stretch the imagination that a program's runtime characteristics can't be exhaustively predicted at compiletime.

This is sort of like claiming that branch prediction isn't useful because can't you just throw away what's unused? No, obviously not, so if the branch exists, runtime analysis can find out which one is more likely to be called over time (and generics are just a branch at the type level).

The person I was responding to said that AOT was a non-starter because the tech I mentioned doesn't exist, and that itself was in the context of a domain where you often wouldn't want the perf hit of even having a poor program binary layout and thus probably wouldn't want such things to be config options anyway.

In any event, I was just saying that AOT can definitely cross library boundaries, not anything near as strong as what you seem to be arguing against (it seems you believe I'm asserting something like AOT being superior to JIT in all cases).

Sure. There's nothing Java can do that can't be done by hand.

The question is, how much effort are you going to put into the profiling to determine that that's an optimization worth making? The larger the program, the more difficult such optimizations are to find -- the example given here was a trivial one.

You could do all of this by writing machine code, or constructing a programmable logic array for it. But would you actually get more trading done that way, or would be get more profit turning your programmers onto other tasks rather than one that can be handled by a machine?

> Sure. There's nothing Java can do that can't be done by hand.

in practice there is. For example, the JVM can inline virtual calls to code that was loaded at runtime (even if that’s third party code for which you don’t have the source code).

To do that by hand, you more or less would have to write something like the JVM yourself.

Sure, it's possible to do it by hand, but it's not possible for the AOT to do it for you, and this then violates the parent's "all things considered equal" claim.

There are certainly going to be tradeoffs that runtime analysis can make that AOT cannot make, even if the example I wrote is possible to fix at compiletime.

> How is that possible? Assuming all things are equal AOT should always be better.

The primary thing here is that the hotter the code path the more optimized your code will be using a JIT (albeit compiled with a compiler which is slower) which is impossible with AOT (since we have a static binary compiled with -O2 or -O3 and that's it) also Java can take away the virtual dispatch if it finds a single implementation of interface or single concrete class of an abstract class which is not possible with c++ (where-in we'll always go thru the vtable which almost always resolves to a cache miss). So c++ gives you the control to choose if you want to pay the cost and if you want to pay the cost you always pay for it, but in java the runtime can be smart about it.

Essentially it boils down to runtime vs compile time optimizations - runtime definitely has a richer set of profiles & patterns to make a decision and hence can be faster by quite a bit.

> Java can take away the virtual dispatch if it finds a single implementation of interface or single concrete class of an abstract class which is not possible with c++ (where-in we'll always go thru the vtable which almost always resolves to a cache miss)

C++ LTO makes devirtualization practical to the point that your browser is benefitting from it right now: https://news.ycombinator.com/item?id=17504370

> Java can take away the virtual dispatch if it finds a single implementation of interface or single concrete class of an abstract class

It can even do that if there are multiple implementations, by adding checks to detect when it is necessary to recompile the code with looser assumptions, or by keeping around multiple versions of the compiled code.

It needs the ability to recompile code as assumptions are violated anyways, as “there’s only one implementation of this interface” can change when new JARs are loaded.

Mostly due to profiling, the JIT gets informed on actual program execution.

I wouldn't word it as vastly superior, because if you have a JIT you're probably doing some kind of tradeoff (most of the times, memory usage?), but the JIT can optimize based on the runtime profile, where an AOT't program cannot.

I know you're getting bombarded with a dozen answers but I don't think anyone's also mentioned speculative optimization/deoptimization. Jit can and often does assume things that can't be proven like a specific call site can be inlined through a virtual call because in practice it's always the same hard type. It can back out the optimization later if that proves to be untrue. Or if a function is always called with the same variable because it was read from a config: it can assume that it won't change.

> how could JIT be faster?

1. AOT compilers have less information about the program than JITs (they only see the program as code; JITs see the code and the current execution profile)

2. AOT compilers can only make optimisations that they can prove don't change semantics, while JITs can be more aggressive, making optimisations that are speculative, deoptimising if wrong.

A JIT can see the actual values that occur in hot loops, among other things, which aren't accessible at compile time but are at runtime. There is simply more information available to a JIT.

A JIT compiler can elide a virtual method to a simple static call based on how many implementing classes are loaded at runtime, or can remove conditional branches from code (e.g. think of a setting whose boolean value is checked in a hot loop (for example something graphics related) - a JIT compiler will remove the conditional based on the setting used).

Fun fact, the linux kernel actually has something similar with self-modifying code, that will remove a conditional at runtime.

The JIT compiler has live runtime data on how the program is actually used and it optimizes around this instead of what the source code says. For instance, the JIT compiler can see that a function has never been passed a null object and optimize out null checks and other branches that are never taken at runtime. An AOT compiler doesn't have this information unless its provided PGO data at compile time.

Nitpicking here.

> JIT compiler can see that a function has never been passed a null object

It cannot. It can only see that function has never been passed a null object so far.

And the cost of such optimization might be that edge cases are way slower than anticipated. But what if those edge cases are actually the only thing that provide value for your business?

Imagine you're building a monitoring system that alerts very rarely, but reaction time is really critical for you. Do you really want to JIT compiler to optimize the alerting branch out because it hasn't seen any alerts yet?

My bet is that JIT compiler rarely does those optimizations by default, because it cannot know which branches in your code contain business value. I don't need my code to be twice as fast on average but twice as slow on critical branches.

Now, what would be great if profiler would make suggestions about how to modify your code for performance based on usage. But those should be approved and commented by humans, because humans know whether those are valuable optimizations or a fad.

> so far

This is truly a nit pick.

> Imagine you're building a monitoring system that alerts very rarely, but reaction time is really critical for you. Do you really want to JIT compiler to optimize the alerting branch out because it hasn't seen any alerts yet?

Yes I do, because once the constraints are invalidated the the runtime system will instruct the JIT to recompile the code with the now uncommon branch [0].

[0] https://shipilev.net/jvm/anatomy-quarks/29-uncommon-traps/

>> JIT compiler can see that a function has never been passed a null object

>>... so far.

>This is truly a nit pick.

It's not even a nitpick, it's just wrong - your original statement is true: you said "has never been". The "so far" reply you received mistakenly implies you said "will never be" (given that HotSpot will deoptimise+reoptimise if its assumptions are invalidated)

That said, the remainder of their point I think is reasonable in the extremely specific (I think to the point of being unrealistic, given this seems like a hand-optimised assembly level of perf importance they have alluded to) scenario they mentioned - the JIT optimiser can't know that the user wants to optimise an extremely rare branch for performance to the point where the overwhelmingly common case should be degraded.

Another useful jumping off point to explore for HotSpot's performance techniques is [1]

1: https://wiki.openjdk.org/display/HotSpot/PerformanceTechniqu...

Can you show me how exactly does the optimization/deoptimization of unused branch look like? You need detect that you got into an unused branch and that requires... a branch!

In order to be able to optimize presumably dead branches you need a primitive that:

1. Can detect entering "dead" branches

2. Is faster than branch.

I'm not saying JIT optimizations are not possible, JIT compiler can totally choose to inline function call based on frequency or loop length. It can make "better" time/space complexity decisions (though "better" is still going to be controversial).

But optimizing branches because they were not called in runtime seems like common a myth. Like previous commenter who confused startup optimization with code optimization.

1) You catch the SEGV signal you get when failing to read the address, then it is complicated, but it is similar to the mechanism used to reach safe points (also does not use jumps).

2) If there are no nulls, it is faster not to do a branch.

https://shipilev.net/jvm/anatomy-quarks/25-implicit-null-che...

> Java specification says that NullPointerException would be thrown when we access the null object fields. Does this mean the JVM has to always employ runtime checks for nullity?

Once again, we're talking about how JIT can be faster than AOT, not how to reduce JIT overhead. Those are two different types of optimization. You will never be faster than AOT just by reducing JIT overhead. Both links that were provided talk about JIT overhead alone.

This one talks about internal JVM optimizations. Not about optimizations JIT is capable of doing for your code.

What exactly are we even comparing when talking about NullPointerException? To my knowledge, most AOT-compiled languages don't even have NPE (not in Java sense at least). It's apples to oranges comparison.

If we have the code "if (x != null) { x.foo = 42; }", then it can rewritten as x.foo = 42 (with some extra magic in the runtime). If x is not null it will be faster if the cost of a branch is higher than zero. If x is null, the (slow) trick with SEGV can be used.

The trick of catching the SEGV can also be used by an AOT compiler (https://llvm.org/docs/FaultMaps.html), but the AOT compiler would need profiling data to do this optimization that is more expensive to do if the variable x happens to be null often. Even if you have profile data for your application, and that profile data will correspond to your application profile of this particular run (on average), you can not handle the case when x != null for five hours and then is set to null for five hours. If you use an AOT compiler you would have exponential blow-up of code generations for combinations of variables that can be null (if you would try to compile all combinations), and you would basically reinvent a JIT compiler --- badly.

Theoretically, a JIT can do anything an AOT can do, but the reverse is not true.

The article is talking about optimizations the JIT is capable of doing for your code. It is well written, and although it is talking about code throwing a NullPointerException, I think you can see that the same optimization can be done for my example at the top (that is applicable to c++ as well). So my comparison is not apples to oranges.

But your observation that most compiled languages do not have NullPointerExceptions is interesting. It could very much be because that it is too expensive with an AOT, have you thought about that?

Also, in an AOT-way you couldn’t really play the same SEGFAULT trick multiple times without some expensive tracking of where did it come from, where to return to, etc, at which point you are doing borderline JIT compiler with precached method bodies.

Well I guess the point is that with JIT you can do a lot of tricks based on the fact that a function always gets passed a null (or anything relatively constant) in practice even if that wouldn't be statically probable.

If that assumption gets violated a JIT can deopt and adjust later. In AOT you can only make the assumptions based on what the code can statically tell you.

Feels like we're going in circles. I guess that's what you get for nitpicking :)

JIT can indeed do a lot of tricks to reduce JIT overhead. But you can't present that as a benefit of JIT over AOT: AOT doesn't have JIT overhead at all.

JIT can definitely trade space for time. I bet that JIT will inline/memoize certain calls based on call frequency.

The only thing I'm arguing against is that low call frequency (like zero branch executions) somehow provides room for optimization compared to AOT. The only optimizations you can do in this case are optimizations for JIT overhead itself.

Anything beyond that is simply not possible: you can't eliminate a branch and detect the fact that you were supposed to enter eliminated branch at the same time: the simplest mechanism that allows you to do that is branching!

One trick that OpenJDK uses is optimization of null checks. Since in Java memory has to be initialized, null pointers will have the value 0. If a given function using a null check gets called many times, and all these times it was called with a non-null object the JVM can compile the branch totally away. If the function is finally called with ‘null’ the compiled code will try to load the memory at address zero, causing the TLB to trigger and the OS to send a segfault. This can be handled safely by the JVM which will interpret it in accordance with the above and will deoptimize the code (with all possible side effects reverted) and either run it in interpreted mode or an optimized mode that does contain the null check “properly”.

How will the runtime system know to invalidate and recompile the code, if the alert check isn't being done on every call?

At some level, the check for the alert has to be done on every call. If it isn't being done, the one time there should be an alert it will be missed. If it is being done, where is it being done if not in the optimised JITted code, and how is that code even more optimised than the JITted version would be? Why not just put that optimisation in the JITted code?

The terms you'll want to read up on are JIT speculation and deoptimisation. There's a whole range of things that can be done like trapping the null derefrence instead of an explicit check, once hot code is inlined the check could be lifted out several call frames outside of loops. Then you can ignore the check later.

All sortsa stuff can happen.

We're talking about optimizations that JIT can do compared to AOT.

The link you shared talks about skipping compilation for certain branches to speed up the JIT compilation. Such optimization makes startup faster, but it doesn't make code execution faster. AOT compiled languages don't have slow startup problem in the first place.

It's like saying paper books are worse than e-ink readers because you cannot charge paper books.

Eliding a branch makes not only compilation faster, but the resulting code as well. That’s how for example some logging statements become zero-cost when the debug level is set lower than their corresponding one. JIT compiled languages don’t care too deeply about startup, they shine with longer runtimes.

Are you sure you're not confusing zero-cost with almost zero-cost? Even zerolog talks about negligible costs after most aggressive optimizations, not zero: https://github.com/obsidiandynamics/zerolog

If you're just using constants in your code to set logging level, AOT compilation can do exactly the same optimizations.

AOT would require recompilation and deployment. JIT can do it for the same code with final params.

When the log level is not final, branch prediction Will ensure JIT code is faster.

JIT compilers do exactly that. Not only do they have more information, they are also allowed to -- and very frequently do -- perform speculative optimisations. If proven wrong, they incur "deoptimisations" and then recompile with more information.

I don't believe this is right. The optimization as described does not preserve the correct program behavior unless you have a guard to do the null check anyway to fallback to the slow path

edit: just read kaba0 answer below and in fact it's possible via tlb miss, really cool

Something not generally mentioned is that Java can inline what would be virtual methods in C++, it can also remove them as behaviour changes or code is unloaded.