4 ms·
Data layout optimizations are a really neglected part of compiler engineering. Performance bottlenecks are now in caching and moving data in the memory hierarch
by fulafel 8y ago
Data layout optimizations are a really neglected part of compiler engineering. Performance bottlenecks are now in caching and moving data in the memory hierarchy, instead of ALU throughput. So compact data representation lets you fit more items in the same amount of cache and move more items in the same amoutn of banwidth.
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 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 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.
- denormalfloat 8y ago> Data layout optimizations are a really neglected part of compiler engineering. 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.
- vardump 8y ago> JIT'd languages don't have this problem because they can rewrite the layouts however they want and based on real time profiling. 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?
- pjmlp 8y ago> Any examples of this? 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.
- BenoitP 8y agoIt'd be great if IBM and Google could contribute that into OpenJDK. Would that collide with project Panama [1] currently under way? (Or maybe that's a goal of the project?). Also, wasn't that the goal of Azul's ObjectLayout [2]? 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. [1] http://openjdk.java.net/projects/panama/ http://openjdk.java.net/projects/panama/ [2] https://www.azul.com/presentation/objectlayout/ https://www.azul.com/presentation/objectlayout/
- 8y ago
- the8472 8y agoRust does quite some optimization on layouts[0], it can do so since its internal ABI, including struct layouts, is unspecified and thus they can change it while still having C ABI for interop. They're also keeping the options open for PGO-based layouts. 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. [0] https://github.com/rust-lang/rust/pull/45225 https://github.com/rust-lang/rust/pull/45225
- saagarjha 8y agoSwift does layout optimization as well, since it similarly has not pinned down module stability.
- fulafel 8y agoCan you point out some layout optimizations that are done? I could not make out much of your link sadly.
- the8472 8y agoLook at the "Size optimizations implemented so far" section. It's mostly about packing enum discriminators into unused bits and bytes. Beyond that rust has always done field reordering to minimize wastage from alignment gaps. Other optimizations are still being planned.
- vbezhenar 8y agoIt's problem of Java, because it uses heap objects for almost anything instead of using structs.
- pjmlp 8y agoIn Java a new doesn't always map to heap objects. Depends on which JVM one is talking about and what JIT is being used.
- vbezhenar 8y agoIf you're talking about stack allocation, memory usage will be the same. Stack allocation reduces GC pressure just a little bit, but if your software uses 25G RAM, it won't help. There's no JVM optimization that I'm aware of, to inline object inside another object.
- chrisseaton 8y ago> If you're talking about stack allocation, memory usage will be the same 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.
- chrisseaton 8y agoThe 'heap' in Java is an abstract concept. The JVM doesn't literally need to use heap objects for everything.
- BenoitP 8y ago> field shrinking based on dynamic range analysis Could you expand a bit on this? Can't find any ressource about it, words are overloaded.
- fulafel 8y agoRange analysis is a compiler term that means exploiting the known range of values that are placed in a field. In a JIT language¹ this can be done even when you can't absolutely prove the range, by trapping and deoptimizing the structure if it turns out that the compiler's range assumption failed. Similarly to how JS JITs do specialization and fall back to deopt. 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.
- BenoitP 8y agoMuch thanks. 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.