Hello everyone, I’m Tim.
We all know that due to various issues with the Java language, vectorization has always been synonymous with C++ or Rust.
Recently, an open-source JSON parsing library called simdjson-java, which uses Java’s vectorization API, has emerged, offering a performance that is 2.5 times faster than the Fastjson2 parsing library!
This means that using Java vectorization technology brings at least a 2x performance improvement, which is quite significant. It opens up new explorations for vector optimization in projects originally implemented in Java.
Could this bring new life to big data frameworks like Hadoop, Spark, Hive, which were originally implemented in Java?
So today, let’s explore this. To understand the simdjson library, we first need to understand what Java vectorization is. Does it have advantages over vectorization implemented in C++ or Rust?
Now let’s discuss how Java implements and uses vector computation.
What Is Vectorization and SIMD Instructions
When it comes to vectorized computation, most people can describe it as a method of processing multiple data elements simultaneously to improve computational efficiency.
To illustrate, imagine harvesting corn on a farm. The traditional method is to manually cut each corn stalk with a sickle, which is inefficient.
The modern method uses a combine harvester, which can quickly harvest large areas of corn fields in a short time, thus improving harvesting efficiency.
In computing terms, traditional computation is akin to processing one piece of data at a time, like cutting corn with a sickle;
whereas vectorized computation can perform the same operation on multiple data points simultaneously, much like using a combine harvester.
It’s important to note that the way CPU SIMD is implemented differs fundamentally from GPU’s SIMT, which belongs to single instruction multiple threads.
The GPU acceleration method is like having one person cut corn one stalk at a time, but now having 10,000 middle school students harvesting corn at the same time.
Now, let’s look at an actual code example:
void foo(int[] d, int[] s) {
for (int i = 0; i < d.length - 4; i += 4) {
d[i] = s[i];
d[i+1] = s[i+1];
d[i+2] = s[i+2];
d[i+3] = s[i+3];
}
...
}
As shown above, we implement a loop copy in Java, where each loop executes four similar copy actions from different addresses.
So how can we use vectorization to optimize the above code?
void foo(int[] d, int[] s) {
for (int i = 0; i < d.length - 4; i += 4) {
d[i:i+3] = s[i:i+3];
}
...
}
As shown in the example, it’s simple; we can convert four copies into one large range copy.
Of course, the above implementation cannot be run directly, but that’s the gist of it.
Now the question arises: can we copy four int values at once?
Those familiar with compiler theory know that for numerical copying and assignment operations, we typically need to involve register usage.
On the X86_64 architecture, the size of the general-purpose register is 64 bits, or 8 bytes. However, merging four int values requires 16 bytes, which clearly cannot be accomplished.
Therefore, in practical applications, various processor architectures provide hardware support for SIMD instruction sets. For example, Intel’s SSE (Streaming SIMD Extensions), AVX (Advanced Vector Extensions), etc.
The SSE instruction set introduces 128-bit XMM registers, allowing us to merge the four int value elements in the above code into the XMM register for operation.
Additionally, it provides SIMD instructions such as PADDB, PADDW, PADDD, and PADDQ, which implement vector addition for byte, short, int, or long values.
Thus, the above code, after vectorization optimization, will use the PADDD instruction and implement d[i:i+3] = s[i:i+3] + d[i:i+3] through the XMM register.
Furthermore, with the support of the AVX instruction set on the X86 platform, the YMM register, which is 256 bits in size, was introduced.
The AVX512 instruction set, released a few years ago, upgraded the YMM register to 512 bits, renaming it to ZMM register.
In this case, the amount of data that CPU SIMD can process simultaneously can be significantly larger.
As we can see, SIMD is like a combine harvester for corn, but there won’t be an excessively large combine harvester, so the amount of data it can process at once is limited, maxing out at the size of ZMM.
However, GPUs use SIMT to accelerate computation, allowing a single instruction to operate on thousands of threads simultaneously, indicating that the acceleration limit of GPUs far exceeds that of CPUs.
JVM Automatic Vectorization
The automatic vectorization of the JVM is actually a sore point, as there are many limitations to implementing automatic vectorization in the JVM, and users cannot control whether vectorization is ultimately executed.
There are many limitations to JVM automatic vectorization, let’s take a look:
First, JVM automatic vectorization relies on the C2 JIT compiler;
Secondly, JVM automatic vectorization only targets counting loops that can be unrolled;
Even for constant counting loops, there are several conditions in Java 8:
-
The increment of the loop variable must be 1, allowing it to traverse the entire array.
-
The loop must have a condition of “AND” rather than “OR”.
-
The loop variable cannot be of long type, otherwise C2 cannot recognize the loop as a counting loop.
-
There should preferably be no data dependencies between loop iterations, such as a statement like a[i] = a[i-1]. If data dependencies exist after loop unrolling, C2 cannot perform automatic vectorization.
-
There should be no branch jumps within the loop body.
-
Do not manually unroll loops. If C2 cannot automatically unroll, it will not be able to perform automatic vectorization.
We can see that the conditions for automatic vectorization are quite stringent, which is why Java had to provide the Vector API later.
JVM Intrinsics for Vectorization
We know that the Java bytecode executed by the Java virtual machine is platform-independent. It is first interpreted and then the frequently executed parts are compiled into machine code by the Java virtual machine.
In other words, during just-in-time compilation, the Java virtual machine runs on the target CPU and can easily determine which instruction sets it supports.
However, due to the platform independence of Java bytecode, another issue arises: Java programs cannot directly use intrinsic methods provided by Intel that will be replaced by specific SIMD instructions, as C++ programs can.
The alternative provided by the HotSpot virtual machine is Java-level intrinsic methods, which are semantically much more complex than individual SIMD instructions.
During runtime, the HotSpot virtual machine decides whether to replace calls to these intrinsic methods with another efficient implementation based on the current architecture. If not, it uses the original Java implementation.
Currently, in the HotSpot virtual machine, all methods annotated with @HotSpotIntrinsicCandidate are HotSpot intrinsics, as shown below:
public final class java.lang.Class<T> implements … {
@HotSpotIntrinsicCandidate
public native boolean isInstance(Object obj);
In other words, the HotSpot virtual machine maintains an additional efficient implementation for methods annotated with @HotSpotIntrinsicCandidate.
If the developers of the Java core libraries change the original implementation, the efficient implementation in the virtual machine also needs to be modified accordingly to ensure program semantic consistency.
Why not directly use these efficient implementations in the source code?
This is because efficient implementations often depend on specific CPU instructions, which are difficult to express in Java source code.
Moreover, the JVM is portable, and switching runtime platforms might not have corresponding CPU instructions.
For example, the StringLatin1.indexOf method searches for one string (byte array) in another string (byte array) and returns the index when found, or -1 if not found.
It uses intrinsic because the SSE4.2 instruction set of the X86_64 architecture contains an instruction PCMPESTRI, allowing it to search for another string within 16 bytes and return the index when found.
Thus, the HotSpot virtual machine developed an efficient implementation on the X86_64 architecture around this instruction and replaces the original call to the StringLatin1.indexOf method.
Besides these, there are also System.arraycopy(), Arrays.copyOf(), Arrays.equals(), etc.
Vector API for Declarative Vectorization
The Java Vector API is a declarative way to perform vectorized computations.
Through the Java Vector API, developers can utilize the underlying hardware’s SIMD instruction set in a more intuitive and straightforward manner to perform parallel computations.
The Java Vector API provides a complete set of vectorization APIs for users to call, and simdjson-java is implemented using this method.
The Vector API (Sixth Incubator) introduces the java.util.vector package, which contains new classes and interfaces such as Vector, FloatVector, and IntVector. These classes provide a set of vectorized operation methods, such as addition, subtraction, multiplication, and corresponding mask operations.
Let’s start with a simple example and take a closer look at the following code snippet:
public static int[] simpleSum(int[] a, int[] b) {
var c = new int[a.length];
for (var i = 0; i < a.length; i++) {
c[i] = a[i] + b[i];
}
return c;
}
The same code converted to data-parallel accelerated code using the Vector API:
private static final VectorSpecies<Integer> SPECIES = IntVector.SPECIES_PREFERRED;
public static int[] vectorSum(int[] a, int[] b) {
var c = new int[a.length];
var upperBound = SPECIES.loopBound(a.length);
var i = 0;
for (; i < upperBound; i += SPECIES.length()) {
var va = IntVector.fromArray(SPECIES, a, i);
var vb = IntVector.fromArray(SPECIES, b, i);
var vc = va.add(vb);
vc.intoArray(c, i);
}
// Compute elements not fitting in the vector alignment.
for (; i < a.length; i++) {
c[i] = a[i] + b[i];
}
return c;
}
Now let’s explain the above code in detail:
1. Declare the width of the data
Before using the vectorization API to leverage SIMD acceleration, we must first determine the data width, which represents the amount of data processed in parallel during each computation.
private static final VectorSpecies<Integer> SPECIES = IntVector.SPECIES_PREFERRED;
Currently, AVX-compatible CPUs can handle a maximum of 256 bits, while AVX-512 can provide a maximum of 512 bits of data width.
2. Configure the loop size
From the above code, it can be seen that the typical for loop uses i++ as the iteration method for loop calculations, while in SIMD, it uses i += SPECIES.length(), where each iteration of the for loop adds the data width we set.
The exit condition for the for loop also needs to be calculated using methods provided by the data width.
var upperBound = SPECIES.loopBound(a.length);
Furthermore, during the computation, assuming the data width is 16, the first iteration computes a[0]+b[0] to a[15]+b[15], and the next operation computes a[16]+b[16] to a[31]+b[31], and so on…
3. Handle all remaining data not aligned within the data width
Assuming the length of the data cannot be evenly divided by the data width of 16, there will inevitably be unprocessed remaining data. In this case, we can continue to execute operations in a non-parallel manner starting from the first item not touched by the vector loop, as shown in the following code.
for (; i < a.length; i++) { // Cleanup loop
c[i] = a[i] + b[i];
}
It is important to note that while the Vector API (Sixth Incubator) can improve application performance, optimal performance also requires appropriate optimization, such as avoiding frequent vectorization operations and data copying.
How is the performance of the Vector API?
According to information provided on the official website, the Vector API has achieved a 16x performance improvement for benchmark programs focused on fused multiply-add, but there was no significant performance improvement for the aforementioned simple summation operation.
It can be said that the performance of the Java Vector API greatly depends on the complexity of the operations; more complex operations (FMA) often outperform simple operations (SimpleSum).
From the user experience perspective, the Vector API is not particularly simple; it generally requires complete adaptation and modification of the code to use it, and whether it is worth rewriting the entire algorithm for this small benefit needs careful consideration.
Conclusion
The automatic vectorization technology and JVM intrinsics provided by Java are very convenient and practical; however, their numerous limitations result in limited acceleration effects in most projects.
Since Java 9, Java has primarily promoted the implementation of a declarative Vector API, whose successful application in the simdjson-java project at least proves that the vectorization API is a direction worth exploring for performance optimization in Java.
However, achieving efficient vector API calculations in Java relies on using a higher version of Java; many domestic enterprises are still stuck on Java 8.
Moreover, the complexity of the Java vectorization API means that using it to accelerate old projects typically requires significant code refactoring.
Compared to C++ or Rust, Java’s GC issues and larger memory consumption for objects still do not provide an advantage.
For new projects, using a higher version of Java’s vectorization API can better achieve performance acceleration.
For older projects, such as Spark and Hadoop, if refactoring is necessary, why not consider using C++ or Rust for the refactor?
If you found this article helpful,
please give it a thumbs up or a look, it’s a recognition and support for me~