3 ms·

> Data layout optimizations are a really neglected part of compiler engineering. From what I understand this is mostly impossible in other popular languages be

> 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 ago
    It'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/
  - vardump 8y ago
    I think you missed the question was about optimizing data layouts. Any references about that?
  - fjeremic 8y ago
    The IBM J9 JVM was open sourced and now lives as the Eclipse OpenJ9 project [1]. We rely on interpreter profiling (block frequency, and value profiling) before the JIT gets it's hands on the method. Once the JIT has determined the cost/benefit is right for a JIT compile we will run through an extended basic block ordering optimization which will lay out the code by block frequency calculated from the taken vs. not taken profiling information on the branch bytecodes given to us by the interpreter. 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]. [1] https://github.com/eclipse/openj9 https://github.com/eclipse/openj9 [2] https://blog.openj9.org/category/jit/aot/ https://blog.openj9.org/category/jit/aot/
    - deleted 8y ago
      [deleted]
- fulafel 8y ago
  I think they do this on the JS side: http://www.jayconrod.com/posts/52/a-tour-of-v8-object-representation http://www.jayconrod.com/posts/52/a-tour-of-v8-object-repres... 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.
kllrnohj 8y ago
JIT'd languages don't help you here. You still need the data layout of a given class to be constant otherwise all field lookups can't just be a load at an offset. And you can't specialize this on a per-method basis, which is the level JITs tend to work out. You'd have to do this via whole-program optimization, which JITs by and large don't ever come close to doing. 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.
- fulafel 8y ago
  Yes, there are separate things that don't depend on each other: the language semantic support for compact layout, the the application profiling, and the hot-swapping of implementations. And none of these are really bound to JIT or AOT. 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.

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 ago
  It'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/
- vardump 8y ago
  I think you missed the question was about optimizing data layouts. Any references about that?
- fjeremic 8y ago
  The IBM J9 JVM was open sourced and now lives as the Eclipse OpenJ9 project [1]. We rely on interpreter profiling (block frequency, and value profiling) before the JIT gets it's hands on the method. Once the JIT has determined the cost/benefit is right for a JIT compile we will run through an extended basic block ordering optimization which will lay out the code by block frequency calculated from the taken vs. not taken profiling information on the branch bytecodes given to us by the interpreter. 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]. [1] https://github.com/eclipse/openj9 https://github.com/eclipse/openj9 [2] https://blog.openj9.org/category/jit/aot/ https://blog.openj9.org/category/jit/aot/
  - deleted 8y ago
    [deleted]
fulafel 8y ago
I think they do this on the JS side: http://www.jayconrod.com/posts/52/a-tour-of-v8-object-representation http://www.jayconrod.com/posts/52/a-tour-of-v8-object-repres... 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.

kllrnohj 8y ago

JIT'd languages don't help you here. You still need the data layout of a given class to be constant otherwise all field lookups can't just be a load at an offset. And you can't specialize this on a per-method basis, which is the level JITs tend to work out. You'd have to do this via whole-program optimization, which JITs by and large don't ever come close to doing. 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.

fulafel 8y ago
Yes, there are separate things that don't depend on each other: the language semantic support for compact layout, the the application profiling, and the hot-swapping of implementations. And none of these are really bound to JIT or AOT. 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.