JVM Anatomy Quarks: Compressed References
shipilev.net
shipilev.net
Compressed references is one of the most basic optimizations that is routinely done by hand when programmers do performance work. Others include storing data in a columnar form (aka AoS->SoA transformation), altering array layout to be cache-friendly (tiling / swizzling), moving rarely accessed members out of line, and field shrinking based on dynamic range analysis.
The history of "compressed references", afaict, is reactive on the JVM: people were shocked at memory usage increases when moving from 32-bit to 64-bit machines. So it came about semi-accidentally and is not really indicative of systematic work on data layout optimizations in the JVM...
There is also a term of art in CS that refers to economical use of memory: https://en.wikipedia.org/wiki/Succinct_data_structure and a second one that is for shrinking data structures based on content entropy: https://en.wikipedia.org/wiki/Compressed_data_structure - this literature is dealing with more advanced encoding tricks that are rather far from what a compiler could realistically do on its own, and often make big tradeoffs such as making the structure read-only.
From what I understand this is mostly impossible in other popular languages because the compiler just puts fields of your structs in the order you wrote it in. (You wanted this, right? Here ya go!) JIT'd languages don't have this problem because they can rewrite the layouts however they want and based on real time profiling. AoT languages either have to run first and compile with the profiling information to have hope of doing this, or else the author has to break out perf and VTune and do it manually. Both are difficult and time consuming, which is why it doesn't happen much in practice.
A minor example of this is Protobuf, where the IDL translates to the same field layout in C++. Could the fields be packed into a more cache friendly layout? Sure, but only on a case-by-case, application-by-application basis. It doesn't work in general, even though proto authors don't care about the precise layout.
Any examples of this?
> AoT languages either have to run first and compile with the profiling information to have hope of doing this...
What prevents one from JITting AoT compiled binaries?
Yes, Java and .NET.
Some JVM implementations, e.g. IBM J9, can save profile information between runs and use it for speeding up code generation, based on the complete history of the executable.
Google also started doing this when they rebooted ART into a mix of interpreter written in Assembly/JIT/AOT runtime. Starting with Android P they are even uploading profile information back to the store, so that similar devices can reach optimized AOT compiled code faster.
.NET Framework allows some control to save PGO data, and variants like that WinRT/UWP cloud compiler take it further.
> What prevents one from JITting AoT compiled binaries?
It relatively complex, versus just starting from bytecodes.
Hence why mainframes always took the approach of either JITing at installation time, or using microcoded CPUs.
Like on Burroughs, Xerox PARC and IBM cases.
If that could make it into the developer's IDE somehow, it'd be awesome. As in, the runtime detects which fields suffer from cache misses, tries a different layout, gathers data; and it all comes as fields being painted shades of blue/red in the IDE. It is one thing to have an optimized JPA object layout, but it is another to only have flat relevant data in the first place. Sort of like a database pushdown optimization through the developer, if you will.
The persistence portion you mention between runs is our AOT capability in which we are able to cache JIT method compilations on disk and load them between different JVM invocations to greatly speed up startup performance. There is a recent series of blog posts on the AOT technology in OpenJ9 in [2].
For example, an array can be specialized to hold just one datatype, or just a couple of fields, based on how it seems to be used, and then de-optimized later if the assumption is broken.
Also, the problem you describe (abi stability) is orthogonal to whether or not it's JIT or AOT. Nothing says an AOT language needs to have a defined data layout (see: Rust), and nothing says a JIT'd language doesn't have that same constraint (see .NET CLR, which defines struct layout as sequential by default for interop with unmanaged code).
It's easier to do data layout optimization in AoT'd languages as a result. Much, much easier. And, in fact, some JIT'd languages have been converted to AOT specifically to do this, such as Unity's HPC#.
EDIT: Also you need value types for these layout optimizations to make any sense at all - which Java doesn't even have.
I agree that whole-program optimization is really what you want here. There are similarities to GC since that also swaps out data from under the program. There are lots of interesting dynamic whole-program optimization things you could imagine a JIT doing, based on emergent program behaviour patterns that might vary from run to run of the program.
Trading off direct field access may be done as one strategy, it's just a couple of conditional cheap ALU instructions after all. Another way would be to compile alternate versions of the hot code path in question.
Of course those are still compile-time decisions, so compressed pointers are out since they only work if you restrict yourself to ~32GB, depending on alignments.
Beyond that rust has always done field reordering to minimize wastage from alignment gaps.
Other optimizations are still being planned.
Depends on which JVM one is talking about and what JIT is being used.
The JVM never literally 'stack allocates'. It scalar replaces objects, so object header words, klass pointers, unused fields disappear, and remaining fields become just dataflow edges so may be folded, or may end up in registers or on the stack. Additionally, objects which are 'stack allocated' do not need to be aligned as on the heap, and do not use GC head-room. All of this does mean a real reduction in memory consumption, but it's likely extremely small in practice.
Could you expand a bit on this? Can't find any ressource about it, words are overloaded.
As a concrete example, a tree node reference could be a 16-bit index into a backing table of real tree nodes, similar to how indexed vertex data is represented in graphics code.
¹ You could do it in an AOT language too, but it's easier to think about our common JIT languages as the example case.
In your example, you mean the indices are shrunk if you know the size of the table? I knew about specialization and deopt, but never suspected the principle could be applied to vertex indices in the GPU.
We're in an awkward time right now, where many servers have more than 32GB of RAM, but not that much more. Once it becomes routine for servers to have 1TB of memory, this will no longer be much of an issue.
Am I correct in assuming that this is made possible because Hotspot can re-JIT? So the GC/Allocator just warns the JITter, "hey, all of your Oops [flags] code is no longer valid," resulting in a re-JIT of everything? Or a prologue in every method that checks the Oops flags (and triggers a re-JIT)?
What does that bit of legalese mean?