16 ms·
AVX512 intrinsics for JDK’s Arrays.sort methods
- zmmmmm 3y agonice! This is the sort of area where it feels the JVM has some under utilised potential, as these type of optimisations can take advantage of the strong guarantees of the JVM runtime. Am curious though if it can work with other SIMD AVX versions since AVX512 is only selectively supported. And what's the potential to go all the way and add OpenCL or CUDA implementations?
- sakex 3y agoYou typically wouldn't want an OpenCL or CUDA implementation because developers expect their code to be running on a single core. If random functions started using multiple cores or running or the GPU, it would become very difficult to manage core allocation of highly parallel programs. On the other hand, they could provide a different function (GPUSort for instance) but they shouldn't replace the default one with different threading requirements.
- Cthulhu_ 3y agoI'm of a different opinion there. When I call e.g. sort on a list, I write what my intent is, the what; I don't care about the how, and I'd rather have the JVM decide to do a multicore / gpu driven optmized sort than that I have to think about implementation details like that. If I want to fine-tune my implementation and write code that works well with the underlying hardware, I'd write it in a language more appropriate for that particular goal. Java is for business applications, where the developer expresses what the code should do; lower level languages (C, Rust, etc) give the developer more options and responsibility in the how it should do it. Simple example, for-loops vs functional functions (map, reduce, etc); the former is the how, the latter is the what.
- h4x0rr 3y agoEven in java, you often times care about threads / core utilization. For example in a web api, you typically don't want to use multiple cores on a single client
- sakex 3y agoI agree to an extent, but you have to at least be aware of the complexity of your algorithms (time and space) and understand the trade offs. If the trade offs change depending on compiler optimisations, then you'll have some difficult debugging on your hands.
- xmcqdpt2 3y agoThe Java Streams API does various functional maps and reductions and can do them in a multithreaded fashion, when asked. I don't think it makes sense to parallelize by default. Although Java is used to write all kinds of business applications, it's also used to write the platform those applications run on, like Netty for example. If I'm writing a thread pool implementation (which is eventually going to be used by "business applications"), I want to have control over concurrency. I don't want to accidentally introduce pauses in my users web apps just because I sorted an array in my library. One could argue that web servers shouldn't be written in Java at all but you can't really support JVM applications efficiently on a non-JVM backend. All the great instrumentation tools that are available on the JVM will have trouble inspecting your library code, memory use becomes more complicated because the GC no longer knows how much memory is truly allocated, and users can't put breakpoints in your code easily in their IDE.
- rightbyte 3y agoThe computer gets unusable for multitasking you swamp the CPU.
- mschuster91 3y ago> And what's the potential to go all the way and add OpenCL or CUDA implementations? Wouldn't make sense outside of environments like Apple's M-series SoCs or some gaming consoles that have unified memory between CPU and GPU. Normal Intel-based architectures would waste too much time shuffling data over PCIe.
- kllrnohj 3y agoNearly every consumer Intel CPU sold for the last 10 years has had unified memory between the CPU & GPU. Similarly nearly every Qualcomm, ARM, etc... SoC for the last 10+ years has had unified memory. This isn't a rare or new architecture. Apple didn't invent this or popularize this with the M-series SoCs. Now since you mention PCIe you're almost certainly only thinking of discreet GPUs. Those of course are not unified memory. But the vast majority of consumer CPUs also have an integrated GPU and that is often unified.
- mschuster91 3y agoThese integrated GPUs however often are barely worth calling them by that name, and completely forget about the crap Qualcomm and others ship.
- touisteur 3y agoI wish I could easily use the 2 TFLOPS Xe GPU of the TigerLake gear I have with something else than the whole opencl/oneAPI/dpc++ kitchensink. I wish Intel really made an effort on the programability of all their offload hardware, be it GPUs or Myriad-X stuff... Either open everything and support a community, or make the sustained long-term CUDA effort... Hopefully SYCL gets us there but I still feel TigerLake was a grossly missed opportunity...
- re-thc 3y agoThere are all sorts of intrinsic in the JVM via feature detection.
- janwas 3y agoAs to portability to other SIMD instruction sets: vqsort[0] is portable to >10 different instruction sets, and actually faster than this when running on AVX-512. Disclosure: I am the main author; happy to discuss. 0: https://github.com/google/highway/blob/master/hwy/contrib/sort/ https://github.com/google/highway/blob/master/hwy/contrib/so...
- dtech 3y agoNice. I'm always slightly disappointed in the amount of optimization and intrinsics in the JDK for these kinds of fundamental and frequently-used methods, despite this always being one of the main arguments for JIT.
- saagarjha 3y agoWhy is it disappointing?
- WJW 3y agoNot GP, but in almost every introductory text to JIT compilers I've read there is a section called "advantages and disadvantages" and it almost always mentions that JIT compilers in theory have more information available than ahead-of-time compilers (ie all the information AOT compilers have and then also runtime information) and can use that information to safely do optimizations that AOT compilers cannot. But then when you look at the actual code of JIT compilers, such JIT-only optimizations seem extremely rare. The JVM, surely one of the platforms that have had more than enough dollars and top-level CS talent thrown at it, even after ~20 years it still apparently lacks many optimizations that you'd expect to be in there if you've only read the introductory texts about it. The linked MR about AVX optimizations for sorting is one such example IMO. AVX512 was first announced 10 years ago, and (not being deeply into JVM development myself) I might have assumed its use would be more prevalent in the JIT output than actually seems to be the case.
- nraynaud 3y agoI believe by having deeper inlining, unrolling and specialization in a JIT you can gain more performance than by static analysis. You squeeze more performance out of stupider algorithms.
- WJW 3y agoOf course, and dead code elimination can also be improved upon (compared to AOT compilers) because some inputs like command line flags will never change during the execution of the program. This means you can better predict which branches will be taken. These are optimizations that work for almost any program. OTOH, another way in which JITs "should" generate better-performing code is by tailoring their output to the platform on which the program is currently being run. With AVX being quite prevalent on the server-grade CPUs on which many big JVM programs run on, I don't think it would be unreasonable to expect the JVM to have more support for AVX512 in its code generator than it apparently does. Is low hanging fruit like 10x speed improvements in sorting something you'd expect out of a very mature platform like the JVM? I don't mean to harp on the JVM devs here, JIT development is a Very Hard Problem. It's just that I can understand why GGP is disappointed, JITs in general don't seem to quite deliver on the excitement they generated when they were new.
- rwmj 3y agoDoes AVX512 still have the issue that it works for microbenchmarks but may pessimize real workloads because it reduces clock speeds?
- touisteur 3y agoIf you want to deep dive there Travis Downs has written an amazing thing about it https://travisdowns.github.io/blog/2020/08/19/icl-avx512-freq.html https://travisdowns.github.io/blog/2020/08/19/icl-avx512-fre... and you should follow the links down to his github avx-turbo project that actually runs all sorts of 'frequency reducing' benchmarks and it's just clearer like this. For example I noticed that on some Intel Gold 6230 processors (2000+ USD each at the time), not only avx512 did bring down frequency, but also 'dense avx2' (sequences of heavy FMA). Explained a lot about measured latencies for some real-time processes. Can't thank Travis enough for cutting through all the vagueness there.
- _a_a_a_ 3y agoI believe the guy occasionally posts here, or has done, under the name BeeOnRope, also on StackOverflow. I printed out some of his posts here about memory bandwidth. The guy really, really knows his stuff.
- touisteur 3y agoI'm still salty that we needed him to put down time and energy in this, when Intel should have done the job... This license stuff was a major engineering tradeoff, a pain in the ass for many people, that should have been explained as clearly as Travis did, from the get go.
- dragontamer 3y agoThat was only on Skylake-X, which I admit was like 4 generations of Intel boxes. But its no longer true today. AMD's Zen4 doesn't downclock at all with AVX512 instructions, and modern Intel chips have only like 100Mhz (aka 0.1Ghz) of downclock measured in practice. In any case, AVX512 is certainly a win from a power-performance perspective. You get more compute-work done with far less decoding/other CPU-related internal core stuff. Even on Skylake-X, I'd expect that AVX512 sorting routines will heat up the CPU less than a non-AVX512 sorting routine... and otherwise be superior from a head and/or power limited perspective.
- nraynaud 3y agoa weird detail is that javac seems to have crashed in the CI: https://github.com/vamsi-parasa/jdk/actions/runs/5125771268/jobs/9219407026#step:5:854 https://github.com/vamsi-parasa/jdk/actions/runs/5125771268/... I really don't see why changing the JIT would influence the bytecode generation, I guess it's a co-morbidity ?
- deleted 3y ago[deleted]
- anthony88 3y agoLooking at the implementation, it is implemented in C++. I'd rather have an implementation using the new Vector API (still in incubation). It would be more Java like and provide a good demo for this new API.
- marginalia_nu 3y agoThis is an intrinsic JVM function though, not application code.
- anonymoushn 3y agoIt seems like you're saying you'd rather have a slower implementation given that a bunch of single instructions useful for this sort of thing aren't available in the Vector API and must be built from sequences of Vector methods that themselves must be implemented using multiple instructions.
- Kipters 3y agoI think he's referring to something similar to what .NET has been doing in the last few versions. They introduced a new Vector API that abstracts platform-specific SIMD instructions. The end result is the same, code using Vector128 will be directly compiled to equivalent AVX opcodes on x86/x64 and NEON on ARM* as if you would have written that directly, except that now you can add these kinds of optimizations across many architectures with a single codebase This [0] post by Stephen Toub goes in GREAT detail on that [0]: https://devblogs.microsoft.com/dotnet/performance_improvements_in_net_7/ https://devblogs.microsoft.com/dotnet/performance_improvemen... *I may get vector length wrong, but you get the idea
- anonymoushn 3y agoYou can just look up the IntVector API in the docs and see that there's no method corresponding to VCOMPRESSPS or whatever.
- Kipters 3y ago
- gigatexal 3y agoThe code changes have references to something that looks like it’s searching for a dll… isn’t that a windows thing? Or is that a generic search for a library?
- throwaway2037 3y agoI assume you are referring to "os::dll_locate_lib()". I'm sure that it is cross platform. While uncommon, it's not totally wrong to call a .so file a dynamically loaded library on a POSIX/UNIX platform. What interests me the most: The developer is employed by Intel! These big, essential open source projects always have a myriad of developers employed by the Big Guns of Silicon Valley hacking away. Is the thinking that if Intel adds vectorization optimization to OpenJDK that it might help sell more chips? The connection looks so loose; I'm a bit surprised that some senior bean counters approved this expenditure!
- YawningAngel 3y agoIntel adding things like AVX is only valuable to anyone if compilers actually smit AVX instructions
- gigatexal 3y agoYeah that's the code. I am not a low level dev or Java dev so it looked odd. Thanks for clarifying.
- kryptiskt 3y agoThey want their chips to beat AMD (which this might not help with) and ARM in Java benchmarks, so adding optimizations makes sense from a marketing perspective.
- re-thc 3y agoIntel has been doing this for a long time. It's a long term strategy just like nvidia helping optimize games.
- 5e92cb50239222b 3y agoWhy? this is pretty typical of them. They used to ship massive amounts of patches to various projects to make their CPUs look good as part of their Clear Linux project, although that seems to have stalled somewhat.
- throwaway2037 3y agoGlorious. Check out the implementation here: https://github.com/openjdk/jdk/blob/6d140d5b8bc4d6b3daa16f72e180b6b4a9fba82c/src/java.base/linux/native/libavx512_x86_64/avx512-64bit-qsort.hpp https://github.com/openjdk/jdk/blob/6d140d5b8bc4d6b3daa16f72...
- londons_explore 3y agoJust looking at a snippet of code: // Assumes zmm is bitonic and performs a recursive half cleaner template <typename vtype, typename zmm_t = typename vtype::zmm_t> X86_SIMD_SORT_INLINE zmm_t bitonic_merge_zmm_64bit(zmm_t zmm) { // 1) half_cleaner[8]: compare 0-4, 1-5, 2-6, 3-7 zmm = cmp_merge<vtype>( zmm, vtype::permutexvar(_mm512_set_epi64(NETWORK_64BIT_4), zmm), 0xF0); To me, this why AVX didn't get widespread use. The code is practically hieroglyphics. If you want humans to use a performance feature, it needs to be easy to use. Preferably fully integrated into the compiler so that you don't need to be aware of it at all. The level of abstraction is wrong - When they invent AVX1024, recompiling this code won't make use of it. Yet the code itself is probably harder to understand and reason about than just a few lines of assembly code.
- touisteur 3y agoAVX512 got far far FAR easier to read and write than previous iterations. Lots of 'missing' operations were added and the set seems far more thought for autovectorizer compiler passes. Still, yes, it's difficult to grok because it's a low-level vector assembler, and as any low-level assembler, can be hard to follow at first. AVX512 also has amazing features like mask registers, all the gfni, bit extract/compress and vpternlog, vpopcount, etc. features that once you've grokked you start seeing vector code as even more magic. My main gripe with AVX512 is that it's still hard to get amazing performance because of memory bandwidth, unoptimized streaming issues, cache locality issues. You can write amazing compact avx512 that will still have poor performance because it's all about feeding the FMA units. But, if you want to see a simpler high level language that will generate fast code for AVX512 targets, checkout ISPC, I've had very nice successes in the past, writing idiomatic code and getting better performance than my shitty experiments with intrinsics. It's not for every kind of code, but when it fits, it's just nice. And ISPC generates C-callable objects/libraries so it's relatively nice to integrate in a build pipeline.
- snemvalts 3y agox86 specific optimization for a language so focused on *portability*, heavy abstractions and business logic is kind of ehh. Especially with ARM is rearing its head. If you desire performance close to the chip, you chose the wrong language and should write code in a language closer to the chip. Unless the abstractions and concepts required for your primary work are so different from what you are using for day-to-day work (data science, ML python and C++ bindings for interacting with the GPU)
- Cthulhu_ 3y agoThe language is still portable; this is a change in the JVM, the runtime, which should have all the optimizations. I don't understand your issue. Java is a higher level language, you just want to call sort on a list without having to worry about low level performance characteristics, because there's people much smarter that can polish that.
- Kipters 3y agoI think what he's saying is that instead of writing that in platform-specific C++ they could have worked on a Vector API and use that instead to automatically work in other (future) SIMD implementations of the same width. A poster in another comment mentioned such API is being worked on, and what I described above is exactly how .NET is tackling this: they built a Vector API and are building optimizations like that in C# on top of that API, giving also developers the ability to write SIMD-oriented code in C# rather than resorting to platform-specific C++ and interop/JNI In my opinion that's a better approach, it's discussed in great detail here https://devblogs.microsoft.com/dotnet/performance_improvements_in_net_7/ https://devblogs.microsoft.com/dotnet/performance_improvemen...
- xmcqdpt2 3y agoThe Vector API exists to write SIMD code in Java. This is an intrinsic inserted by the JIT compiler. HotSpot intrinsics are always written in assembly or compiler IR because they are inserted in the generated assembly. Arrays.sort() could very conceivably be called in a hot loop, so you really don't want to allocate Java objects in it.
- neonsunset 3y agoC# let's you write intrinsics-based and cross-platform vectorized kernels without C++ code ;) (GC does have AVX512-based vxsort written in C++ though)
- kaba0 3y agoJava does as well, check out the Vector API.
- brewmarche 3y agoAFAIK the Java Vector API is like Vector<T> not like the intrinsics one
- za3faran 3y agoNot quite: * https://openjdk.org/jeps/417 https://openjdk.org/jeps/417 * https://youtu.be/1JeoNr6-pZw https://youtu.be/1JeoNr6-pZw
- rotifer 3y agoI expect they are referring to the "Vector API" described in JEP 426: Vector API [1]. From the summary: Introduce an API to express vector computations that reliably compile at runtime to optimal vector instructions on supported CPU architectures, thus achieving performance superior to equivalent scalar computations. [1] https://openjdk.org/jeps/426 https://openjdk.org/jeps/426
- brewmarche 3y agoYes. Where does it expose the AVX or ARM intrinsics? I only see generic add/neg/mul methods (thus the comparison to .NET Vector<T>) and not the intrinsics exposed thhemselves; here is a random pick from the .NET ones: https://learn.microsoft.com/en-us/dotnet/api/system.runtime.intrinsics.x86.avx2.loadalignedvector256nontemporal?view=net-7.0#system-runtime-intrinsics-x86-avx2-loadalignedvector256nontemporal(system-uint32 https://learn.microsoft.com/en-us/dotnet/api/system.runtime....*)
- misja111 3y agoImpressive, but I wonder what the practical benefit will be. How often do you need to sort an array of numbers? In practice you almost always want to sort an array of objects based on one of their properties.
- mjburgess 3y agoHash their properties
- hurril 3y agoAnd... then? You would essentially need a homomorphic hash function for that to work. I.e.: [ a, b, c ].map(hash) produces the same order. where hash: A -> B, where p, q in A. p < q => x, y in B. x < y.
- misja111 3y agoTrue and even then, you would only have a sorted list of the object's properties. But not a sorted list of the objects themselves.
- mjburgess 3y ago`ord` is a hash function which preserves alphabetical ordering, etc. It's not that hard, in many cases, to find an `f : DataDomain -> Int` st. `f(x1) < f(x2)` where `hash(x1) < hash(x2)`
- dtech 3y agosorting arrays of numbers is very often ultimately used under the hood of all the nice abstractions
- rightbyte 3y agoSorting an array of pointers is sorting by numbers.
- misja111 3y ago