7 ms·

SIMD accelerated sorting in Java – how it works and why it was 3x faster

154 points by CHY872 4y ago

geokon 4y ago
Great article. Very comprehensive and well written, while not skipping the gotchas the author hit along the way I don't really much about how the JVM works, but it's interesting that this is (if I understood correctly) in effect calling out to some native code. In the JVM world, when are things added to the byte code as a new instruction, and when are they wrapped up in a native code call? I'd expect a new vector instruction for the stack machine, but I'm guessing that's less flexible and less performant..? "Practically speaking, you end up with code that looks like it creates many objects, but actually compiles to code that allocates no memory. It is extremely disconcerting." It's interesting comparing people working in Java vs C++. Java makes it so impractical to really reason about the code directly that users ends up relying a lot more on tooling for benchmarking and introspection (and hence the tools are top-class) "Java’s ability to print its compiler output as assembly " How do you do this? Is this integrated into the IDE? While the tools are great and you can dissect all your performance problems, ultimately feedback from the compiler should be feeding back into the editor. I feel that some of the issues the author hit shouldn't happen. You should for instance be immediately able to see if a function is being inlining while you're editing and not having to run extra tools
- dzaima 4y ago
  You can't really have bytecode instructions for the vector API functions because they're generic. They're instead methods, which the JIT compiler can handle specially if it so chooses to. Effectively, for pure computational operations (i.e. not ones doing complex stack operations or jumps), there's no real difference between a method call and a new bytecode (except that adding a new bytecode is a lot more work because everything must be updated to support it, whereas a new method is just a new method).
- pjmlp 4y ago
  If you use Oracle's own IDE, it will support it out of the box, as it already did on Sun's days. Then there are other ways depending on which JVM implementation is used. On OpenJDK's case you can load runtime plugin to do it https://github.com/AdoptOpenJDK/jitwatch https://github.com/AdoptOpenJDK/jitwatch
  - geokon 4y ago
    Oh very cool. I'm really glad these things exist. I skimmed the intro video and it does looks like a separate tool though. Would be extra slick if these things got highlighted as you coded. But I get that usually you only really bring out the big guns when you're optimizing a tight loop somewhere - and then you probably want the whole toolbox and not just some annotations. Thanks for letting me know about this :)
    - pjmlp 4y ago
      The reasoning is that these are development tools and thus shouldn't be shipped by default. I don't agree, but it is as it is, at least it does exist in some form. Here .NET is better, you can just press F12 (Show Assembly) during debug session, and it will show it just like for C and C++ sessions. Compiler explorer and sharplab make use of it. Node allows to show some Assembly stuff, but if you want all the possible debugging options for Assembly code, you will need a debug build of nodejs.
- pron 4y ago
  > In the JVM world, when are things added to the byte code as a new instruction, and when are they wrapped up in a native code call? These aren't native code calls but compiler intrinsics. The Java compiler (the JIT compiler, that is) translates certain Java method invocations into specific machine instruction patterns. > Java makes it so impractical to really reason about the code directly that users ends up relying a lot more on tooling for benchmarking and introspection (and hence the tools are top-class) As others have mentioned, you can dump the generated machine code, but you are correct that Java is, by design, higher level than C++ in the sense that low level details are less under the programmer's control, but the compiler's. So when you see a `new Foo()` in Java, you cannot tell whether an object will actually be allocated on the heap, or perhaps "scalarized" and stored directly in registers. In fact, what happens is not even decided statically and could vary dynamically, depending on what other code does, as compilation is done JIT, and optimisations are decided based on the program's current execution profile. As a result, even though all instance methods in Java are semantically virtual, in practice they are very often inlined, and don't compile even to a call instruction, let alone a vtable call. Unlike C++, Java's goal — generally speaking — is to get very good average-case performance for little effort rather than give the programmer a lot of knobs to control the worst case. Of course, sometimes there are knobs — just like the Vector API, which is useful in cases the JIT cannot automatically vectorise loops — but the balance is different from C++.
  - Const-me 4y ago
    > Vector API, which is useful in cases the JIT cannot automatically vectorise loops For vertical-only operations (vectorizable loops), people often using GPUs instead of SIMD in CPUs. Graphics cards have way more resources, both GFlops and memory bandwidth. I don't think sorting an array has anything to do with vectorizing a loop.
    - CHY872 4y ago
      It would not be hard to write a quicksort which could be automatically vectorized. For example, this is a perfectly valid partition implementation of the pivot operation. int partition(int[] array, int from, int to, int pivot) { int[] buf1 = new int[to - from]; int[] buf2 = new int[to - from]; // buffers could be preallocated, as in the blogpost int idx1 = 0; int idx2 = 0; for (int i = from; i < to; i++) { int value = array[i]; if (value < pivot) { buf1[idx1++] = value; } } for (int i = from; i < to; i++) { int value = array[i]; if (value >= pivot) { buf2[idx2++] = value; } } System.arraycopy(buf1, 0, array, from, idx1); System.arraycopy(buf2, 0, array, from, idx2); } It would be relatively straightforward for a compiler to automatically vectorize the two loops I've coded up. I don't know if there's one that would, but with the vpcompress instruction I think the absence of a compiler doing it automatically would simply be a function of it not being a common use case.
- chrisseaton 4y ago
  > You should for instance be immediately able to see if a function is being inlining while you're editing But it’s a dynamic decision, except in the most trivial cases. How can you know it without running the program?
kaba0 4y ago
Would some of the mentioned drawbacks be solved by having Project Panama's other half be available? What I mean is allocating memory manually, instead of using Java primitive arrays inside the Vector API. Would the (de)serialization overhead be too much for it to be worth it?
grishka 4y ago
This whole "the JVM inlines things for you and avoids the allocation of objects altogether sometimes" goes so against my intuition after more than a decade of writing Java, mostly for Android. The idea that you should allocate as few short-lived objects as possible has stuck with me. So these new APIs do make me feel uncomfortable a bit, they make me think "oh man, this does look like it's gonna have some performance issues due to too much time spent in GC deleting all those objects". I do understand that the regular (Hotspot?) JVM must be much smarter with optimizations than the Android runtime, but still.
- kaba0 4y ago
  Android’s Java is pretty much a bastard child of OpenJDK - it is so behind on features that it is truly a shame.
  - my123 4y ago
    Android 13 started to give some OpenJDK 11 features... but ugh - nothing that we can widely rely on yet. Core Java 11 features will be backported to Android 12 with ART as an APEX module, but that didn't happen quite yet as far as I can see.
    - izacus 4y ago
      Which is why the language of choice for Android is Kotlin which has all modern features without the necessity of changing the runtime.
      - grishka 4y ago
        Actually, "desugaring" is a thing. It's a backport of those new parts of the standard library that the dex converter inserts into your app. Currently, it's only Java 8, but I had no trouble building an app that uses Java 17. You just can't use any features that rely on new classes or methods, like records. But purely syntactical ones do work flawlessly. I don't like Kotlin because of how much it tries to do in the language itself with maximally terse syntax, and because of its asinine defaults like final-by-default classes and immutable-by-default everything. Java's sugar is much better thought out.
hereforphone 4y ago
- kwizzt 4y ago
  What does Java have to do with Indian university? Java/JVM is widely popular in the enterprise world for backend services, and a ton of open source software, e.g. Cassandra, Hadoop. You need to learn more stuff for sure.
- ecshafer 4y ago
  Java is a very performant language. You get an awesome Jit, static type checking, some best in class stdlib libraries. Performance issues in Java typically say more about the programmer than the language.
kwizzt 4y ago
I'm really looking forward to when SIMD support is released in later versions of Java. If anyone here follows handmade hero (by Casey), he explained SIMD in some of his videos when implementing the software renderer. The speedup from regular code to SIMD is very impressive. You essentially get speedup of 2x-3x or even more for free. The downside is it makes the code much harder to read, so I think it should be applied only in very small sections of the code.
ErikCorry 4y ago
The section on "dictionary encoding" didn't make much sense to me. Is there an explanation of this technique somewhere? The example code took a list called "buffer" and then didn't use it for anything - perhaps something got lost when writing the code? The explanation was pretty opaque: Here’s one simple example I encountered recently. It’s common in columnar database code to ‘dictionary encode’ lists of values. Here, for some subset of the stored data, we store a dictionary containing the unique values that exist, assigning unique indices to each value, and we store a list of pointers into the list to represent each element. We store a list of pointers into which list? The dictionary contains the unique values as keys or as values? How do we pick which subset of the stored data we do this for?
- kwillets 4y ago
  The buffer in this case is the input to a max() function; his point is simply that sorting the dictionary indices before looking them up is a good idea for common data structures like arrays, disk blocks, or anything with caching or readahead.
  - deleted 4y ago
    [deleted]

154 points by CHY872 4y ago

Great article. Very comprehensive and well written, while not skipping the gotchas the author hit along the way I don't really much about how the JVM works, but it's interesting that this is (if I understood correctly) in effect calling out to some native code. In the JVM world, when are things added to the byte code as a new instruction, and when are they wrapped up in a native code call? I'd expect a new vector instruction for the stack machine, but I'm guessing that's less flexible and less performant..? "Practically speaking, you end up with code that looks like it creates many objects, but actually compiles to code that allocates no memory. It is extremely disconcerting." It's interesting comparing people working in Java vs C++. Java makes it so impractical to really reason about the code directly that users ends up relying a lot more on tooling for benchmarking and introspection (and hence the tools are top-class) "Java’s ability to print its compiler output as assembly " How do you do this? Is this integrated into the IDE? While the tools are great and you can dissect all your performance problems, ultimately feedback from the compiler should be feeding back into the editor. I feel that some of the issues the author hit shouldn't happen. You should for instance be immediately able to see if a function is being inlining while you're editing and not having to run extra tools

dzaima 4y ago
You can't really have bytecode instructions for the vector API functions because they're generic. They're instead methods, which the JIT compiler can handle specially if it so chooses to. Effectively, for pure computational operations (i.e. not ones doing complex stack operations or jumps), there's no real difference between a method call and a new bytecode (except that adding a new bytecode is a lot more work because everything must be updated to support it, whereas a new method is just a new method).
pjmlp 4y ago
If you use Oracle's own IDE, it will support it out of the box, as it already did on Sun's days. Then there are other ways depending on which JVM implementation is used. On OpenJDK's case you can load runtime plugin to do it https://github.com/AdoptOpenJDK/jitwatch https://github.com/AdoptOpenJDK/jitwatch
- geokon 4y ago
  Oh very cool. I'm really glad these things exist. I skimmed the intro video and it does looks like a separate tool though. Would be extra slick if these things got highlighted as you coded. But I get that usually you only really bring out the big guns when you're optimizing a tight loop somewhere - and then you probably want the whole toolbox and not just some annotations. Thanks for letting me know about this :)
  - pjmlp 4y ago
    The reasoning is that these are development tools and thus shouldn't be shipped by default. I don't agree, but it is as it is, at least it does exist in some form. Here .NET is better, you can just press F12 (Show Assembly) during debug session, and it will show it just like for C and C++ sessions. Compiler explorer and sharplab make use of it. Node allows to show some Assembly stuff, but if you want all the possible debugging options for Assembly code, you will need a debug build of nodejs.
pron 4y ago
> In the JVM world, when are things added to the byte code as a new instruction, and when are they wrapped up in a native code call? These aren't native code calls but compiler intrinsics. The Java compiler (the JIT compiler, that is) translates certain Java method invocations into specific machine instruction patterns. > Java makes it so impractical to really reason about the code directly that users ends up relying a lot more on tooling for benchmarking and introspection (and hence the tools are top-class) As others have mentioned, you can dump the generated machine code, but you are correct that Java is, by design, higher level than C++ in the sense that low level details are less under the programmer's control, but the compiler's. So when you see a `new Foo()` in Java, you cannot tell whether an object will actually be allocated on the heap, or perhaps "scalarized" and stored directly in registers. In fact, what happens is not even decided statically and could vary dynamically, depending on what other code does, as compilation is done JIT, and optimisations are decided based on the program's current execution profile. As a result, even though all instance methods in Java are semantically virtual, in practice they are very often inlined, and don't compile even to a call instruction, let alone a vtable call. Unlike C++, Java's goal — generally speaking — is to get very good average-case performance for little effort rather than give the programmer a lot of knobs to control the worst case. Of course, sometimes there are knobs — just like the Vector API, which is useful in cases the JIT cannot automatically vectorise loops — but the balance is different from C++.
- Const-me 4y ago
  > Vector API, which is useful in cases the JIT cannot automatically vectorise loops For vertical-only operations (vectorizable loops), people often using GPUs instead of SIMD in CPUs. Graphics cards have way more resources, both GFlops and memory bandwidth. I don't think sorting an array has anything to do with vectorizing a loop.
  - CHY872 4y ago
    It would not be hard to write a quicksort which could be automatically vectorized. For example, this is a perfectly valid partition implementation of the pivot operation. int partition(int[] array, int from, int to, int pivot) { int[] buf1 = new int[to - from]; int[] buf2 = new int[to - from]; // buffers could be preallocated, as in the blogpost int idx1 = 0; int idx2 = 0; for (int i = from; i < to; i++) { int value = array[i]; if (value < pivot) { buf1[idx1++] = value; } } for (int i = from; i < to; i++) { int value = array[i]; if (value >= pivot) { buf2[idx2++] = value; } } System.arraycopy(buf1, 0, array, from, idx1); System.arraycopy(buf2, 0, array, from, idx2); } It would be relatively straightforward for a compiler to automatically vectorize the two loops I've coded up. I don't know if there's one that would, but with the vpcompress instruction I think the absence of a compiler doing it automatically would simply be a function of it not being a common use case.
chrisseaton 4y ago
> You should for instance be immediately able to see if a function is being inlining while you're editing But it’s a dynamic decision, except in the most trivial cases. How can you know it without running the program?

kaba0 4y ago

Would some of the mentioned drawbacks be solved by having Project Panama's other half be available? What I mean is allocating memory manually, instead of using Java primitive arrays inside the Vector API. Would the (de)serialization overhead be too much for it to be worth it?

grishka 4y ago

This whole "the JVM inlines things for you and avoids the allocation of objects altogether sometimes" goes so against my intuition after more than a decade of writing Java, mostly for Android. The idea that you should allocate as few short-lived objects as possible has stuck with me. So these new APIs do make me feel uncomfortable a bit, they make me think "oh man, this does look like it's gonna have some performance issues due to too much time spent in GC deleting all those objects". I do understand that the regular (Hotspot?) JVM must be much smarter with optimizations than the Android runtime, but still.

kaba0 4y ago
Android’s Java is pretty much a bastard child of OpenJDK - it is so behind on features that it is truly a shame.
- my123 4y ago
  Android 13 started to give some OpenJDK 11 features... but ugh - nothing that we can widely rely on yet. Core Java 11 features will be backported to Android 12 with ART as an APEX module, but that didn't happen quite yet as far as I can see.
  - izacus 4y ago
    Which is why the language of choice for Android is Kotlin which has all modern features without the necessity of changing the runtime.
    - grishka 4y ago
      Actually, "desugaring" is a thing. It's a backport of those new parts of the standard library that the dex converter inserts into your app. Currently, it's only Java 8, but I had no trouble building an app that uses Java 17. You just can't use any features that rely on new classes or methods, like records. But purely syntactical ones do work flawlessly. I don't like Kotlin because of how much it tries to do in the language itself with maximally terse syntax, and because of its asinine defaults like final-by-default classes and immutable-by-default everything. Java's sugar is much better thought out.

hereforphone 4y ago

kwizzt 4y ago
What does Java have to do with Indian university? Java/JVM is widely popular in the enterprise world for backend services, and a ton of open source software, e.g. Cassandra, Hadoop. You need to learn more stuff for sure.
ecshafer 4y ago
Java is a very performant language. You get an awesome Jit, static type checking, some best in class stdlib libraries. Performance issues in Java typically say more about the programmer than the language.

kwizzt 4y ago

I'm really looking forward to when SIMD support is released in later versions of Java. If anyone here follows handmade hero (by Casey), he explained SIMD in some of his videos when implementing the software renderer. The speedup from regular code to SIMD is very impressive. You essentially get speedup of 2x-3x or even more for free. The downside is it makes the code much harder to read, so I think it should be applied only in very small sections of the code.

ErikCorry 4y ago

The section on "dictionary encoding" didn't make much sense to me. Is there an explanation of this technique somewhere? The example code took a list called "buffer" and then didn't use it for anything - perhaps something got lost when writing the code? The explanation was pretty opaque: Here’s one simple example I encountered recently. It’s common in columnar database code to ‘dictionary encode’ lists of values. Here, for some subset of the stored data, we store a dictionary containing the unique values that exist, assigning unique indices to each value, and we store a list of pointers into the list to represent each element. We store a list of pointers into which list? The dictionary contains the unique values as keys or as values? How do we pick which subset of the stored data we do this for?

kwillets 4y ago
The buffer in this case is the input to a max() function; his point is simply that sorting the dictionary indices before looking them up is a good idea for common data structures like arrays, disk blocks, or anything with caching or readahead.
- deleted 4y ago
  [deleted]