Project Valhalla: Fast and Furious Java

Performance Improvements of New Inline Types

Project Valhalla is one of the most interesting projects concerning the future of Java and of all JVM. It is still in an experimental state, but in this post, we will look at how to use it and implement a small program to verify possible performance improvements.

Valhalla's aim is to bring a new Inline Types (aka Value Types) that will: "Codes like a class works like an int."

You may also like: Project Valhalla: A First Look at L-World Value Types

Currently, in the JVM, there are eight kinds of primitive types, each one is associated with a "signature letter" of the alphabet:

B — byte signed byte
C — char Unicode character encoded with UTF-16
D — double double-precision floating-point value
F — float single-precision floating-point value
I — int integer
J — long long integer
S — short signed short
Z — boolean true or false

On top of these, we have objects:

L — ClassName reference an instance of class ClassName

You may have noted the signature letter if you printed out the result of toString() method for a generic object.

Project Valhalla introduces a new letter for a new kind of types:

Q — ClassName inline types

These new types will eventually replace the primitive types in our applications, removing current boxed types (Integer and such) and bringing a new seamless world based on Reference and Inline types only.

This is still in the future. For the moment, let's enjoy what is already available in the current early-access build.

Getting Started

To simplify the set-up, the Project Valhalla team released an Early-Access Build on August 30, 2019.

You can download it here and configure it in JAVA_HOME as a normal JDK (version 14): http://jdk.java.net/valhalla/

Unfortunately, at the moment (December 2019), IntelliJ and Gradle are not able to compile a source with the new features of the language. We need to use the JDK command-line tools or ant.

I shared on GitHub a repository with several examples and the ant build scripts needed to run them.

A Valhalla Point

Let's start with something very simple. Let's define a Point type with two fields for the coordinates.

The only change is the inline keyword on line 1. Point is an Inline Type, and now, we will look at the differences with a normal class.

Code Like a Class

• It can be created using new
• As you can see, you can declare fields, constructors, and methods like a normal class
• It can implement an Interface, overriding the methods.
• It can be used by generics and can have generic parameters

Work Like an Int

• The typePoint is immutable. The fields x and y are automatically treated as final. We can decide if we want them private or public but we cannot change them.
• Point has automatically generated methods equals, toString, and hashcode. We can test its equality using the == operator like int and double.
• Point has no null value. If you want to represent a null Point, you need to use the new "inline widening," which is a kind of boxing on steroids.
• Point instances are not allocated separately from their references; they are represented directly in memory, like int now.
• Point has a default value that corresponds to Point(0,0). It can be created with Point.default.
• Point cannot inherit from another type and nothing can inherit from it.

Work in Progress

Some characteristics are still unfinished and they may not work in the current build or change how they work in future releases. In particular:

• It is not possible to use synchronization operations on Inline Types. So no synchronized methods, locks, wait/notify.
• Reflection: It's not possible to distinguish them from reference objects. There will be some special interface for this.
• Thread-safe: It's currently not possible to have a volatile behavior and to use them in Atomic operations.

For a more comprehensive look at Project Valhalla features, see the articles linked at the end of this post. Below, we will concentrate on the performance aspect of these features.

Compact Arrays

One of the most exciting features of the Inline Classes is the way in which arrays are created.

In the case of primitives, each position of the array has the direct representation of the type; for example, the 64 bits of a long in case of an array of long.

In the case of the referenced object instead, the array will only contain the reference to the object allocated memory on the heap.

This means that reading an object from an array involves first reading the reference and then fetching the memory from its actual location. If the object has referenced fields, those would also cause data to be fetched from a remote memory location.

Inline Types on the other side work like primitives.

To have a taste of how much this matters, let's make a simple test program to sum all trades from a given account in a big array.

Here is our trade's simple representation, with an amount, an account, and a traded security.

Similarly, we will define a TradeInline class, identical with the inline modifier:

After the compilation, we can use javap from the command line to print the generated ByteCode:

And this is the output:

Note the value modifier in the first line and the methods hashCode, equals, and toString that are not present in our class.

Encoding a String Into a Long

Our TradeInline class has still two String inside as fields. Can we inline them?

Unfortunately, at the moment, it is not possible to flatten String and Arrays inside an Inline type. There are future plans for something called Array 2.0 that would allow for that.

What we can do now is squeeze a String inside a long type. Although, we need to accept some limitations.

The long type has 64 bits, so using a base 64 encoding (6 bits), we can store up to 10 characters inside.

In our case, we assume that the Security and the Account have a maximum length of 10 characters and they are composed only of uppercase letters, numbers, and a limited number of special characters.

This is the code of our MiniString inline type, with the encoding and decoding static functions:

xxxxxxxxxx

public final value class com.ubertob.ministring.TradeMiniString {

  final double amount;

    descriptor: D

  final com.ubertob.ministring.MiniString account;

    descriptor: Qcom/ubertob/ministring/MiniString;

  final com.ubertob.ministring.MiniString security;

    descriptor: Qcom/ubertob/ministring/MiniString;

  public final int hashCode();

    descriptor: ()I

  public final boolean equals(java.lang.Object);

    descriptor: (Ljava/lang/Object;)Z

  public final java.lang.String toString();

    descriptor: ()Ljava/lang/String;

  public static com.ubertob.ministring.TradeMiniString com.ubertob.ministring.TradeMiniString(double, java.lang.String, java.lang.String);

    descriptor: (DLjava/lang/String;Ljava/lang/String;)Qcom/ubertob/ministring/TradeMiniString;

}

Note how the descriptor for the MiniString account starts with the Q of inline types and not with the L of the reference types.

Finally, to have a fair comparison, we also define a TradeRefEncoded class using the same trick to encode an Account and Security in a field of type long.

You can find the complete code in my GitHub repository.

Before looking at the performance, let's look at how our Trade objects are using the memory.

First, the standard TradeRef object:

On the left, there is our big array. Then a pointer to theTradeRef object, and then two other pointers to the strings.

Depending on the order of creation, these can be quite far apart in our heap.

This is a performance problem because fetching memory from different regions is one of the slowest operations for a CPU.

This classic post from Martin Thomson is one of the better explanations:
https://mechanical-sympathy.blogspot.com/2012/08/memory-access-patterns-are-important.html

Let's look at a simple diagram of the  InlineTrade value memory representation now:

Here, the whole value is directly on the array. For this reason, the array is actually bigger than in the first case. If you don't allocate all objects, in other words, if your array mostly contains null values, this can be a drawback.

Finally, let's see how the TradeMiniString is allocated in the memory:

You can see that it stays completely inside the array element, with no external pointers.

This is possible only because we accept big limitations on what can be contained in those strings; still, it's an acceptable compromise when using strings only for storing ID from a database or the stock ticker symbols.

Performance Comparison

To compare the performance, we can create four arrays of 5 million elements, one for each of our trade types:

Then, we fill them with identical random values:

And finally, we do searches on each one repeatedly, printing out the time elapsed.

We can filter and sum using two methods: a for loop or a nicer stream map and reduce:

Unfortunately, streams are not (yet) working with Inline Classes:

So, for the moment, we can only measure performance using for loops.

Fancy Graphs (Finally)

The actual numbers are not very important here, so I just grabbed a significative sample running the application on my Linux laptop.

Rather than the numbers, we are interested in how fast they are relative to each other.

We can see here how in this case the improvement is really huge — inline TradeMiniString is more than 20x faster!

Event compared with the TradeRefEncoded is still 6x faster!

This seems almost too good to be true, so we can use a better method to measure the actual performance.

Brendan Gregg wrote some very useful tools to use Linux kernel perf tool to profile Java programs.

There are several blog posts on how to produce and how to read flame graphs:
https://medium.com/netflix-techblog/java-in-flames-e763b3d32166.

And here are our flames:

You can find the actual svg file in the GitHub repository here.

We can see four green blocks (including the one with the arrow) that are a representation of how much time these four methods used the CPU. In this graph, the green blocks are Java calls, while the red ones are kernel system calls.

The spikes are other methods, related to the print out of results and garbage collection. We can ignore them.

From the left, the first block is the InlineTrade, using normal strings. It is clearly smaller than the last two blocks which represent the TradeRef and TradeRefEncoded.

As you may have guessed, the block pointed by the arrow is the TradeMiniString duration; it is so brief that you can read only a few characters of the name.

The relative duration of each method from the perf profile is reported in this graph:

The relative timings are similar, Inline is 6 times faster than Ref and Inline Encoded is 5.5 times faster than Ref Encoded.

Conclusions

It is still too early for precise measurements, but it is already clear that Valhalla inline types have the potential to bring a massive performance boost for a certain type of critical applications.

There are still many rough edges and painful decisions to make but the overall shape of the Valhalla project is very exciting.

Since the last EAB, there have already been many improvements in the source code. So let's hope to have another stable build to test soon with more features.

This post was originally published as part of the Java Advent series. If you like it, please spread the word by sharing it on Twitter, Facebook, etc.!

Want to write for the Java Advent blog? We are looking for contributors to fill all 24 slots and would love to have your contribution! Contact the Java Advent Admin at contribute@javaadvent.com!

To Learn More...

The full code of this and other examples:
https://github.com/uberto/testValueTypes

A Recent video about Valhalla at Devoxx BE
https://devoxx.be/talk/?id=41660

Brian Goetz on the State of Valhalla
http://cr.openjdk.java.net/~briangoetz/valhalla/sov/02-object-model.html

An in-depth explanation of Inline Types from Ben Evans:
https://www.infoq.com/articles/inline-classes-java

My post on the previous early-access build:
https://medium.com/@ramtop/a-taste-of-value-types-1a8a136fcfe2