BT

Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ

Topics

Choose your language

InfoQ Homepage Presentations Project Valhalla: Bringing Performance to Java Developers

Project Valhalla: Bringing Performance to Java Developers

Bookmarks
21:33

Summary

Tobi Ajila explains the advances being made in Project Valhalla to improve Java's memory density by making it easy to create compact, cache efficient data structures.

Bio

Tobi Ajila is a Java Runtime developer for the OpenJ9 VM team in Ottawa, Canada. In the past he has worked on Interpreter optimizations, JVMTI enhancements, JSR 335 and more. Currently, his main focus is on Project Valhalla where he collaborates with other developers in the Valhalla expert group.

About the conference

QCon Plus is a virtual conference for senior software engineers and architects that covers the trends, best practices, and solutions leveraged by the world's most innovative software organizations.

Transcript

Ajila: My name is Tobi. I'm going to talk about how Project Valhalla is bringing performance to Java developers. I'm a developer on the OpenJ9 VM team, based in Ottawa, Canada. In the past, I've worked on projects like JSR-335 modularity. Currently, I am part of the Valhalla Experts Group, where I work with other developers and collaborate on Project Valhalla.

Outline

The goal of today's presentation is to answer four questions. What is Project Valhalla? What is the problem that it's trying to solve? Then I'll introduce inline types and show how it solves these problems. Then I'll talk about the future of Project Valhalla and where it's going.

What Project Valhalla Is

What is Project Valhalla? Project Valhalla is a collaborative effort. It's done in OpenJDK. To summarize it, I'll borrow a quote from Brian Goetz. The goal of Project Valhalla is to bring more flexible flattened data types to the JVM languages, to bring the programming model back in line with the performance characteristics of modern hardware. There are two main points here. The first is that there is currently a shortcoming in the JVM that doesn't allow the JVM to make the most of modern hardware. The next major point is that in order to solve this problem, we need to find a way to express flattened data types to the JVM. That's basically the goal of Project Valhalla. This will be realized by a series of steps, the main ones being inline types, and specialized generics.

What Problem Is Project Valhalla Solving?

Currently, the Java type system doesn't quite fit well with the performance characteristics of modern hardware. In the past couple decades, CPUs have been able to process more instructions per cycle forever. However, memory latencies haven't improved as much. Memory latency tends to be the biggest bottleneck for Java application performance. Here are some latency numbers from a core i7, from a 5th Gen Xeon. All of these numbers represent the optimistic case, obviously, these are the best case scenarios for the memory types. At the top, we have registers. It's typically a single cycle. When you go down to a one, or two or three, the amount of time it takes to do the memory load takes longer. When you go to RAM, there is a bit of a jump, and there's an even bigger jump when you go to SSD. Basically, this table shows that it pays to have condensed data, where temporal and spatial locality are aligned. This basically means that you want to have the data that you'll access together to be stored in memory together. As soon as you have to move up to a higher tier or a higher cache, then you pay the latency cost.

What's The Big Deal?

This is typically what a Java heap looks like. There's lots of references everywhere, lots of pointer chasing. This is not very cache efficient because objects are not necessarily positioned spatially near each other. You often have to jump between different cache lines to load a field. With an object graph that looks like this, there's a high likelihood of cache misses, which is detrimental to performance as we saw in the chart before this. Another problem with this picture is that there's a lot of object headers, and that contributes to footprints. A large footprint makes it less likely that you'll be able to fit all the related data in the same cache line, making cache misses more probable. Also, it means that you're using more memory, so you end up having more GCs, which also reduces performance. This is what Project Valhalla is attempting to solve. It's attempting to fix this picture and make it more hardware friendly.

What We Need

The main solution to this problem is flattening. This is where you take a reference field and place it within its structure. In other words, you flatten it within its container. Here's a little example. We have points that has two fields, x and y, and with line which is composed of two points. When you flatten a point within this container, you're essentially taking the two points and putting it with inline, as you can see in this diagram. On the left, we'd have the reference layout, and on the right, we have the flattened layout. On the right, there's no pointer chasing in this case because the data is within the container. There's less footprints because we don't need the headers for points, and we don't have the references to point. This flattened representation takes up less space. You can do something similar with arrays. On the left, we have a pointArray, and it has references to each of the elements. On the right is a flattened representation, where each of the elements are placed within the body of the array. This is a more performant way to represent arrays in memory.

What Inline Types Are and How It Helps

What are inline types, and how does it help? Before we dive into inline types, I'll first motivate why we had the reference problem. I'll show how inline types solves that problem. One of the great things about the Java language is identity. Identity is useful because it allows one to keep track of state. A Java object has identity so even if its state mutates, it still remains the same object. This is a very appealing feature for software developers, which is why object oriented languages like Java are very popular. It means you can perform identity operations by acquiring and monitoring any object. However, there are some cases where you don't need identity as the value of the object does not mutate within its lifetime, or if you're simply using an object as a data carrier. In these cases, you still have to pay the cost of identity.

References

One of the biggest challenges in dealing with identity are references. In order to maintain a single view of an object state, you need to have a reference to that object, so everyone refers to the same thing. As a result, references are everywhere in the JVM. When the JVM allocates an object, it returns a reference to that object. When the object is pushed onto the stack, it is a reference to that object that's supposed to push on the stack as opposed to the object itself. If an object has object fields, then the fields themselves are references, and for the types of the cache table which contains an object array, there is more references. In these cases the elements themselves have more references. Eventually, you end up with this object graph that I showed you earlier.

Inline Types

The solution to this is inline types. Inline types are essentially objects that behave like primitives. Hence, the title, "Codes like a class and works like an int." The important part here is that it works like an int, specifically the performance aspects of the int. Inline types, this is the current working name. In the past, it's been called value types. It refers to the same thing. Inline types have three main characteristics. The first one is that they're identity-less. Identity is the reason why we have a lot of references today. Inline types are identity-less. A lot of those things we have to do to preserve identity, we don't have to do anymore. Identity-less means that an instance of the type, which has the same content is indistinguishable from all other instances of that type with the same content. If the payload is the same, it's the same thing. Immutability means that an instance cannot change once it's been created. Once you create it, that's it forever. If you want it to change, you have to create a new instance. Flattenable means that the JVM is free to embed or inline a field within its container. Inline types have a lot of the same characteristics as primitive types. Primitive types are immutable. They don't have identity. One way of looking at inline types is as programmable primitives, or you can think of them as restricted classes. They work like classes, but the restrictions make them more performant than classes.

Here is a little illustration. Let's say we define a point with two fields x and y, and we define a line with two point fields, start and end, just as in our previous example. The layout would look something like this in today's world. If you convert points to an inline type, instead of the disjointed layout, we have a contiguous layout. The two points are placed in line within the line object, which means better footprints and better cache locality. Also, the two point fields do not have identity, which means they can benefit from better optimizations by the JIT. What changed? How did we get all of this improvement? A single keyword was added. In red, you can see inline. This was prepended to the class definition. What this does is it indicates that this type is an inline type. It means that the type is now flattenable, it's immutable, and it's identity-less. Then we get all the benefits that we want.

Characteristics of Inline Types

Some of the other characteristics of inline types, we've seen that they're immutable, identity-less, and flattenable, but they can also define methods. Unlike primitive types, which needs to be boxed to the object equivalents in order to call methods in them, inline types don't need this. You can define methods and you can call methods in them directly. They can implement interfaces. They can implement abstract classes with some restrictions. These abstract classes cannot have any fields. They need to have an empty init method. They subclass object, and they also support the object APIs like equals to string. Their behavior is a little different because they don't have identity.

Inline Type Restriction

Inline types are great because they allow you to define data aggregates. However, there are some trade-offs when using inline types. You can think of them as restricted classes. Inline types cannot be subclassed, since an inline type may be flattened within this container. Allowing inline types to be subclassed would mean that a flattenable type may have variable size storage. For this reason, it's not allowed. Since inline types are identity-less, you can't perform any identity operations on them like synchronizing on them or defining instance synchronized methods. Inline types also do not implement cloneable, since inline types are identity-less, cloning is inconsequential. It's like trying to clone a primitive. Similarly, they can't define finalizers since finalization is a mechanism tied to the lifetime of an instance. Since inline types don't have identity, they don't have lifetimes. The concept of finalization doesn't work with inline types.

Flattenability

Inline types are flattenable, which means they can be flattened within the container. As a consequence of flattening, inline types are not nullable, meaning that you cannot assign null to an inline type container. When a field is flattened, all the data is used to represent the bytes of the instance. There is no way to represent null since an all zero memory is a valid instance of the type. All the bits are used up to represent the data, essentially. In addition, inline types cannot have instance fields that refer to themselves, either directly or indirectly. Since an inline type may be flattened, it's impossible to determine the flattened layout of an inline type that recursively defines itself. For that reason, it's not allowed. Also flattened fields are preloaded, so loaded before the container, as you need to know the size of the field before you can create an instance of the container. This is very similar to preloading a superclass or interfaces before loading the type. These are some of the restrictions. At the end of the day, it's the JVM that determines whether the field is flattened or not. The JVM will attempt to flatten as much as possible, as much as it's beneficial. However, if the type is too large, that it's too difficult to allocate the type or the particular architecture that's being run on, doesn't have large enough registers to load the type efficiently, then the JVM may decide to not flatten it.

Java Hierarchy

Let's look at how the Java hierarchy looks like with inline types. At the top is java.lang.Object. To the left, we have inline types. This is the new types that were introduced. To the right, there is a new interface called IdentityObject. This is the current working name. What it will be called in the future is still up for debate. Essentially, all types today that currently subclass java.lang.Object, will now implement the IdentityObject interface. This is to distinguish them from identity-less inline types. In cases where you need to know if it's safe to perform an identity sensitive operation, there'll be an interface that will indicate whether these operations are supported or not.

To the right, we have primitives. Primitives are separate. They're distinct types today. They don't really play nicely with the rest of the Java world. If you want to use them with generics, for example, you have to box it to container type. They're very difficult to use. One of the goals of Valhalla is bridging the gap between primitives and the rest of the Java world. In the future, there are plans to convert primitives to be inline types. Once this is done, then everything fits nicely together.

Inline Types in the JVM

With inline types, there are two new bytecodes introduced. The first is defaultvalue. This is a lot like the new bytecode for creating identity types. Defaultvalue creates an inline type and sets all the fields to zero. All primitives are zero. All references are null. Defaultvalue always produces an initialized instance. Unlike the new bytecode, where you have to do init sequence, defaultvalue is sufficient to create an initialized instance of a value type. The other bytecode is withfield. Inline types are immutable, which means you can't change the field. In order to effectively update an inline type, you have to create a new one, with a new value. Withfield takes an existing inline type and creates a new one with an updated field.

We'll take a look at some examples of what it's like to program with inline types. Their characteristics make them subtly different from reference types today. There are some cases where it might be a surprise to users. One of these cases deal with nullability. When you create an array today, the array elements are initialized to null. Writing code like this, you'd expect that as soon as you create the array, if you do a null check on the element, you expect that the element is null. With inline types, when you create an array, since inline types are not nullable, as soon as you create the array, all the elements are initialized to a valid inline type. If you wrote code like this, it wouldn't behave as you expected it to.

Today's APIs Assume All References Are Nullable

Here's another example. There are a lot of APIs today that accept types like object array or object. Today, all types of subclass objects are nullable. You can assign null to them. With inline types, that's not true. In this example, we have a method that accepts an object array, and then writes null to the first element. With inline types, you could potentially get a null pointer exception since it's illegal to write null to an inline type array. These are some of the issues that can occur when using inline types.

Reference Projections

There are cases where an indirection may be useful. One might need to create a type there first to itself, as in this example, or you might want to assign null. Inline types are not novel. There is one option. The option is to use a reference projection. It's effectively the box of an inline type. It's not really a box because a reference projection simply means that the container can contain null, or an inline type. Unlike primitive boxing where you have to create a new instance, with an inline reference projection, you're not creating a new instance, you're simply using a projection of an inline type. It's a much more performant model.

The Future of Valhalla

What is the future of Valhalla? We looked at inline types and how it can be a great benefit to performance. However, we still need to solve the issue with generics as these are very common use types. In today's world, when we want to write generic code with an int, it looks something like this, ListmyList = new ArrayList();. Ideally, we want to get to this picture, ListmyList = new ArrayList();. To date, there's been a lot of prototype work, but nothing concrete. This will likely be released after inline types. This is something that the expert group wants to look at in the future. Here's a roadmap. LW3, this is where we are now. LW10 will be the first release of inline types. LW100 will be the release with specialized generics. There'll be many releases in between those, but those serve as markers for the major releases.

 

See more presentations with transcripts

 

Recorded at:

Mar 05, 2021

BT