AVX512 intrinsics for JDK’s Arrays.sort methods
github.com
github.com
¹: https://chipsandcheese.com/2023/04/16/codecs-for-the-4k-era-...
A policy of AVX-512-off-by-default seems pessimistic now that Intel Icelake+ have basically no throttling, and AMD Zen4 definitely none.
This is especially true for CPU and I/O benchmarks that typically have an onion's worth of caching layers in hardware and OS.
The argument isn't that microbenchmarks are never useful, but rather that they are usually not very applicable and extremely hard to get right, and even harder to interpret.
If you're doing JVM optimizations, it may be a useful tool, but like in practice, it's questionable whether these 12x optimizations will result in even a 0.1% improvement in performance in the median Java application.
It's pretty simple when you think about it. If you're optimizing effects that are hard to isolate and in many ways barely measurable in the noise of process memory alignment and similar factors, then in most cases, whatever optimization you make is likewise going to be barely measurable in the noisy hardware/software landscape.
It's good for benchmarks. This is sponsored by Intel so that benchmarks will show x86_64 running faster than arm64 and you should not switch.
Epyc vs. Xeon is what this is about as the datacenter is the last holdout for OpenJDK at this point.
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.
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.
So its a lot of effort to think about a problem that's only identified on a relatively small number of server processors, and (probably) won't be a problem moving forward.
// 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);
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.
I do agree that it is the wrong level of abstraction. Explicitly stating the SIMD width leads to a compatibility nightmare. RISC-V vector instructions instead use an explicit "vector width" register, which pretty much entirely solves this problem.
Take it from experience: sure you can write high-level code that is SIMD-compatible. But the compiler is garbage at understanding the semantics and will write terrible SIMD code.
[1] https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html
Examples of what's missing: interleaved load/store, compress/expand, software AES/CLMUL, popcount, lzcnt, saturated add/sub, 128-bit compare/minmax, fixed-point mul, mask find/set, masked load/store, scatter/gather, reductions.
Highway supports those (and >200 operations in total) on all platforms.
I do believe that compilers can optimize any movement pattern into the right butterfly shuffles (not today in the general case. Modern compilers in CUDA are impressive but this is a hard problem) but I'm convinced that the programmer needs to be aware of the low level difficult nature of many-to-many data movements on a 16-wide AVX512 register, or a 32-wide GPU block / warp / wavefront.
--------
EDIT: I'm like 90% sure some dude at Bell Labs from 1950s working on CLOS network or Benes network design probably has an efficient representation for many-to-many data shuffles on a parallel architecture. But I'm not PH.d enough to have read all those papers or keep up with those old designs.
Many-to-many data movements is traditionally a networking and routing problem. But SIMD-programmers and SIMD-chip designers are starting to run up against this problem... because a ton of parallel programming is about efficient movements of data between conceptual lanes and/or threads.
Compilers can't generally rewrite your scalar code as vector code for the same reason they can't rewrite your b-tree as a skip list.
It's not that bad if you just study it a bit and put your mind into it. Just a sequence of relatively simple operations (+ masking when you need a partial operation), data shuffling, loads and stores.
Unfortunately to extract all of that performance, you do need to know your target architecture, be it SSE, AVX2/512, NEON, SVE or whatever.
You might also need to know some architectural details, like register renaming, out of order execution, branch prediction, load/store buffers, automatic prefetching, cache architecture, sometimes even details like CPU internal ring bus. That's just how it is when you want to extract the last drop of performance.
Sometimes compilers can be pretty great, just not always. Unfortunately sometimes beautifully autovectorized code just stops being so due to some small change in code somewhere.
Luckily most of us don't need to care. Most people can just use optimized libraries instead.
I'll never forget hand-optimizing some DNA analysis code into assembly and achieving the theoretical performance bottleneck that is the memory throughput between the CPU and main RAM on a server with 800GB of RAM.
Taking something that took minutes and turning it into something that takes seconds is a flipping amazing feeling.
Could it get even faster? Probably, but that would require very significant data structure changes with an algorithmic change to match. Would it be worth it? Well, probably when the database reaches multiple TB in size. But I've since moved on from that company so it's someone else's problem.
Arrays.sort(arr)
A.s(arr)
AVX has seen very, very widespread use across mobile, desktop, gaming, and server platforms. It's over 10 years old. Probably every hand-optimized vectorized x86 routine in the past 10 years has seen AVX thrown at it. Not every programmer can write it, but it sees absolutely tons of widespread usage and can be written by many competent programmers.
> If you want humans to use a performance feature, it needs to be easy to use.
In practice for general purpose "messy" compute kernels (e.g. parse this JSON/CBOR bullshit with SIMD) there is still a very wide gap between hand-written intrinsic code and what the compiler can generate. Most compilers in popular languages don't have the leeway to automatically perform the necessary optimizations/"setup" that a human must perform to fully exploit these tools, so this is not an easy fight to win.
For limited domains, and with the correct semantic design, however, you can either achieve or exceed human performance with high level semantics e.g. Halide.
> Yet the code itself is probably harder to understand and reason about than just a few lines of assembly code.
It's really not. Hacker news sucks shit to read code on, but the above code is in no way harder or worse than a raw assembly routine using AVX instructions. If anything it's less error prone, because the compiler takes care of a ton of incidental but necessary drudgery too, such as handling PIC (something 99% of people forget immediately) and eliminating the need for an outlined function. Not to mention you can leave the compiler to do all the annoying shit like sinking or coalescing stores/loads along the codepath, accurate DWARF/debug information without things breaking, etc.
>every hand-optimized vectorized x86 routine
is approximately 0 percent of code.
I know I've seen pretty huge speedups in my own code for "free" just from switching to an AVX version of BLAS. You can just think about how many different programs use BLAS (which is itself highly arcane internally), and AVX is definitely in a ton of other low level libraries out there.
But very often approximately 0 percent of a code is 90+% of a runtime
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.
Have you ever written bitonic sort? It's not an easy algorithm to do quickly.
This seems to have implemented bitonic sort in just a few short primitives you can look up at https://www.intel.com/content/www/us/en/docs/intrinsics-guid...
--------
How would you write a fixed 16 element bitonic sort? In Python or whatever?
I dunno, the recursive template seems brilliant to me. Bitonic sort is innately a recursive process, but here we get compile time recursion and optimal assembly code at the end...
This is flat out false. The rest of the comment is therefore superfluous.
This [0] post by Stephen Toub goes in GREAT detail on that
[0]: https://devblogs.microsoft.com/dotnet/performance_improvemen...
*I may get vector length wrong, but you get the idea
[0]: https://docs.oracle.com/en/java/javase/19/docs/api/jdk.incub...
If you need the vpshufb behavior of zeroing elements where the index is negative, I think you will need to build something out of multiple operations. The compiler is of course free to match those multiple operations to one target instruction, i.e., recognize that what you are trying to say is really a vpshufb. It can do this in the same way that it can match multiple operations like x + y * 8 + 12 to a single lea instruction.
I am concerned that it takes like 6 instructions (2 to put copies of each lane into all lanes, 2 shuffles, cmpgt, blend) including a load and using an extra register to implement rearrange for use cases that would be fine with vpshufb for 32-byte registers and maybe 14 instructions (4 to put copies of each lane into all lanes, 4 shuffles, 3 compares, 3 blends) with 3 loads and 3 extra registers to implement rearrange for 64-byte registers. Maybe you can do better for the latter case though, I haven't had a thorough try at it.
A common use of vpshufb is to get a mask of character positions from a string matching a small set of characters, which you can do with cmpeq(in_slice, vpshufb(c, in_slice)), where the input substring in_slice is used as the shuffle and c is chosen so that input characters in the set of characters of interest (e.g. {'\n' '\r' '\t' '\"' '\\'}) map to themselves and other characters map to something other than themselves. rearrange doesn't seem to define what happens when indices in the shuffle are negative or too large, so it seems like to use rearrange we need to mask off some bits and do cmpeq(in_slice, rearrange(c, and(d, in_slice))) where the `and` is only there because of the nit about invalid indices and `rearrange` is 1 or 6 or 14 instructions depending on what register width we're working with. That could be unfortunate.
You don't need this stuff for sorting primitives though!
It's a pity because you clearly have a lot of knowledge that you could put to use to provide very helpful feedback to implementors of the Vector API. (I'm doing this for the GraalVM compiler.)
The folks on the JDK side probably didn't even research how to parallelize sort.
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?
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.
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.
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.
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.
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.
0: https://github.com/google/highway/blob/master/hwy/contrib/so...
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.
It's not that hard, in many cases, to find an `f : DataDomain -> Int` st. `f(x1) < f(x2)` where `hash(x1) < hash(x2)`
And? If your objects are immovable then one level of indirection (pointers or indices) solves that. If your objects are moveable, then there's many (!) times where having your container sorted will improve performance.
2. Have another container named `indices` representing the index or iterator into your Persons container
In C++:
3. `std::sort(begin(indices), end(indices), [&](int lhs, int rhs)->bool{ return persons[lhs].age() < persons[rhs].age(); });`
I don't know Java but I am sure there are many ways to do it in Java.
It's quite hard to come up with something that we could use in every day programming that will benefit from the new optimizations.
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.
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.
But it doesn't unless your "almost" is very generous. Java is pretty consistently 2-10x slower than the major performance-focused AOT offerings (C, C++, Rust)
Now maybe you call 2x "almost", but let's phrase it in terms of CPU performance over time. That's equivalent to 10 years of CPU hardware advancements.
To me that's a lot of overhead. Depending on who is paying for the CPU time vs. the developer time it's regularly a cost worth paying, but at the same time don't pretend it's "almost native speed", either. It is a cost and a rather significant one at that. Just, so are engineers. They also aren't cheap.
Also, which 10 years of CPU advancement do you mean? It is definitely not a linear graph, we have reached an almost plateau on single-core performance.
And even code that does have an overhead is not as simple to judge. Could you write that same code in a lower level language that it will still remain correct and safe? Is the algorithm actually expressible in Rust’s much more restrictive style (to stay safe)? If you do locks and ref counting everywhere, will that code actually be still faster? For example, a compiler might very well be faster in Java/haskell/another managed language.
Because it's not really interesting to debate. Nobody writes Java code like that, and even when they do there's still overhead to it. The exact amount of overhead is kinda irrelevant since the language very obviously doesn't want you to write code like that.
> Could you write that same code in a lower level language that it will still remain correct and safe?
Rust is safer than Java, so yes :)
But you're drifting into the productivity argument anyway, which I already pointed out is a reasonable reason to pay runtime overhead to get.
Rust has data-race freedom, while java has “safe” data races (it is tear-free, so even in case of a data race you won’t corrupt the memory, which is not true of rust with any number of unsafe parts). So I don’t really buy the argument that Rust would be safer.
Likewise if you code in C, C++ or Rust with allocations everywhere, bad algorithms or data structures, being AOT won't help.
GraalVM does it much better than OpenJDK, then there are OpenJ9, PTC, Aicas, Azul, ART (yeah not really, but close enough), microEJ, and a couple of nameless others from Ricoh, Xerox, Cisco, Gemalto,... on their devices.
Even if we stick to OpenJDK, the distributions based on it aren't all the same, for example Microsoft's fork has additional JIT improvements (-XX:+ReduceAllocationMerges).
JITs do regularly have a lot more specialization optimizations, though, but is that really because it's a JIT instead of an AOT or is it more because JIT'd languages just often tend to also be more dynamic ones as well?
Nonsense. What evidence do you have for this claim?
> JITs often have preset heuristics for figuring out where to split the code that's practical to implement rather than being the most performant possible. After all, the code needs to hot-swapped in without much disruption.
You seem to be talking about JITs without on-stack replacement. So not state of the art high performance JITs.
Nonetheless, you might find the Graal compiler doing a better job at autovectorization than C2.
Maybe Array.sort() isn’t that frequently used, as data sorting is often done by the database?
Most Java application code doesn't, but it typically uses libraries that do. A sorted array is a priority queue, a binary search tree, etc.
If you have an application that is truly bottlenecked the performance of number-sorting in any measurable way, then you most probably didn't write it in Java. It's not really a number crunching language for a variety of reasons.
You end up using libraries like fastutil, which is "generic code" templated by C preprocessor macros,
This is planned as phase two of Project Valhalla [0]:
The second phase will focus on generics, extending the generic type system
to support instantiation with inline classes (which will include primitives),
and extending the JVM to support specialized layouts.
This includes JEP 401 "Flattened Heap Layouts for Value Objects" [1, JEP 402 "Enhanced Primitive Boxing" [2], and I think also "Value Objects" [3] and "Universal Generics" [4].
It is a huge task with many dependencies and requires careful design. It feels like it might finally make it in the next long term release.
[0] https://openjdk.org/jeps/12
[1] https://openjdk.org/jeps/401
[2] https://openjdk.org/jeps/402
(Scala has specialization and value classes and opaque types so that covers a fairly big range but they make interop with Java tricky.)
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!
I really don't see why changing the JIT would influence the bytecode generation, I guess it's a co-morbidity ?
(GC does have AVX512-based vxsort written in C++ though)
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.
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)
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.
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_improvemen...
Arrays.sort() could very conceivably be called in a hot loop, so you really don't want to allocate Java objects in it.
What I was thinking is something similar to how they implemented things like IndexOf [0] which is a pure C# implementation that gets translated by the JIT in C++ equivalent code. The advantage is of doing this kind of things this way is that when ARM adds a 256-bit wide SIMD extensions they will only need to support that as a Vector256 implementation to get that code working with no other changes.
[0]: https://github.com/dotnet/runtime/blob/2a1b52a1b691c42a7f407...
Portability is not a problem. The C/C++ compilers have nice wrappers on them to let JVM take advantage of them. And there’s always the non-simd version to fall back to.
JVM is the correct abstraction layer to implement this for portability. Any Java program doing sorting benefited from this on all supported platforms.