[HN Gopher] AVX512 intrinsics for JDK's Arrays.sort methods
___________________________________________________________________
AVX512 intrinsics for JDK's Arrays.sort methods
Author : mfiguiere
Score : 149 points
Date : 2023-05-31 07:30 UTC (15 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| throwaway2037 wrote:
| Glorious. Check out the implementation here:
| https://github.com/openjdk/jdk/blob/6d140d5b8bc4d6b3daa16f72...
| londons_explore wrote:
| Just 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 wrote:
| AVX512 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.
| vardump wrote:
| Hieroglyphs or not, with some human cleverness you can
| achieve pretty amazing performance.
|
| 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.
| inetknght wrote:
| > _Hieroglyphs or not, with some human cleverness you can
| achieve pretty amazing performance._
|
| 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.
| vardump wrote:
| It's often about memory bandwidth nowadays. That and
| locality of reference, random access is expensive. You
| can compute a ton for the cost of one random memory
| access.
| kjs3 wrote:
| Tangential Question (purely curious): How to you validate
| your code produces the same (presumedly correct) results
| as the non-optimized (presumedly HLL) code for something
| as complex and variable as DNA analysis? I run into an
| analogous concern when people talk about "we need to
| rewrite this exhaustively tested with decades of track
| record Fortran 77 code in (whatever the new hotness in
| PLT is)".
| PhilipRoman wrote:
| Damn if only someone could write a fancy helper function so
| that everyone doesn't have to wrestle with AVX... Oh, wait...
| roywashere wrote:
| Writing a virtual machine or compiler is always hard! If you
| write code for the JVM, going forward you will now use the
| instructions while writing nice clean Java...
| aseipp wrote:
| > To me, this why AVX didn't get widespread use
|
| 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.
| thfuran wrote:
| But their point is that
|
| >every hand-optimized vectorized x86 routine
|
| is approximately 0 percent of code.
| ithinkso wrote:
| Approximately 0 percent of a code needs optimization.
|
| But very often approximately 0 percent of a code is 90+%
| of a runtime
| gh02t wrote:
| Sure but OP's point is that that tiny fraction of code is
| (probably, I'm just guessing) responsible for a
| disproportionately large fraction of time spent actually
| running work. AVX is AFAIK mostly used in hand rolled,
| low level library code that then is used by a whole lot
| of consumers.
|
| 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.
| temporal828 wrote:
| > To me, this why AVX didn't get widespread use.
|
| This is flat out false. The rest of the comment is therefore
| superfluous.
| halffullbrain wrote:
| But this is exactly that: Source code for a compiler
| integrating SIMD instructions into an intrinsic function.
| janwas wrote:
| It doesn't have to be as verbose and cryptic as intrinsics;
| wrapper functions can help a lot :) Is this more readable? ht
| tps://github.com/google/highway/blob/master/hwy/contrib/so...
| crote wrote:
| You're not really supposed to write AVX yourself - the
| compiler should be doing that for you. And it will, if you
| write your code in a SIMD-compatible way and turn on the
| right compiler flags.
|
| 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.
| janwas wrote:
| hm, that seems optimistic for this use-case. I heard from a
| compiler engineer that autovectorizing a sort (which is
| full of permutes/shuffles) is much harder and is likely to
| remain infeasible for quite some time.
| dragontamer wrote:
| GPUs have a crossbar that allows for high speed lane-to-
| lane permutes and bpermutes, but it's still slow compared
| to butterfly shuffles.
|
| 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.
| jandrewrogers wrote:
| Compilers will always be terrible at vectorizing code
| because the required transformation is architectural. It
| would require the compiler to understand your code well
| enough to replace the scalar algorithms and data structures
| with new ones that are semantically equivalent in all
| contexts with all necessary invariants preserved (e.g. how
| memory is organized). The code transformation would be very
| non-local.
|
| 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.
| inetknght wrote:
| > _You 're not really supposed to write AVX yourself - the
| compiler should be doing that for you. And it will, if you
| write your code in a SIMD-compatible way and turn on the
| right compiler flags._
|
| 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.
| arthur2e5 wrote:
| The best thing a current compiler can provide is probably
| replacing intrinsics with more conventional-looking
| things like GCC's Vector extensions[1] and C++'s simd<T>.
| Even then you'd need to do a little bit of union work for
| the cooler operations.
|
| [1] https://gcc.gnu.org/onlinedocs/gcc/Vector-
| Extensions.html
| inetknght wrote:
| I 100% agree that there's a lot of room for improvement
| here.
| xmcqdpt2 wrote:
| Luckily for us, we don't need to actually understand this C++
| code to use AVX 512 for faster sorting. We can just do
| Arrays.sort(arr)
|
| in Java!
| re-thc wrote:
| But then people say it's too verbose. Maybe it needs to be:
|
| A.s(arr)
| tialaramex wrote:
| arr.sort() or sort(arr) seem reasonable to me
| kaba0 wrote:
| You can static import Arrays.sort, so the second option
| could work.
| verytrivial wrote:
| The way I see it, you could argue for say, wing-nuts to be
| used everywhere because they can be used tool-free, but then
| you can't tighten them as much, can't put them is confined
| spaces etc. AVX is meant to be used with a specialist tool
| interface that has knowledge of lower level details and is
| made by someone else who adds a simple handle for you,
| Array.sort being this example.
| dragontamer wrote:
| Erm... No it isn't.
|
| 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...
| rwmj wrote:
| Does AVX512 still have the issue that it works for
| microbenchmarks but may pessimize real workloads because it
| reduces clock speeds?
| touisteur wrote:
| If 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-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_ wrote:
| I 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.
| pizza234 wrote:
| I don't know the details, but for example, "x265 disables
| AVX-512 support by default due to clock speed regressions on
| Intel Skylake-X systems"[1], which means that yes, this is an
| existing problem.
|
| 1: https://chipsandcheese.com/2023/04/16/codecs-for-
| the-4k-era-...
| skavi wrote:
| Skylake X was one of the first platforms with AVX-512.
| Everything since Icelake has been fine.
| janwas wrote:
| That's surprising, I would expect that codecs are doing
| enough work that the faster processing from AVX-512 more than
| pays for the downclocking. In JPEG XL we saw 1.4x end to end
| speedup (including this downclocking) and that was for
| images, which are often less data than videos.
|
| A policy of AVX-512-off-by-default seems pessimistic now that
| Intel Icelake+ have basically no throttling, and AMD Zen4
| definitely none.
| touisteur wrote:
| The thing is now your codec (or libc as it was once!) is
| having a complex side effect. The clamping and ramping back
| up of the frequency is not immediate and it has an impact
| of overall latency on the core it's running. I even saw
| once funny traces on a heavily loaded machine where the
| avx512 code was rescheduled on other cores almost all the
| time, because overall the core running the avx512 code
| seemed to 'be more loaded' and the scheduler would find a
| new home for the avx512-crunching process. Kind of a 'fun'
| runaway process.
| janwas wrote:
| Fair point :) I wonder why the kernel is so aggressive
| about migrating threads, it also loses the cache
| contents. FWIW our command line tools at one point pinned
| themselves to the current core, which did help
| performance.
| gpderetta wrote:
| OS kernels should be relatively sticky. Possibly it was
| power/temperature management where the load was moved to
| an unloaded core to even out power dissipation?
| saagarjha wrote:
| Not for several years. If you're still rocking Skylake you may
| have issues but beyond that, no, not really.
| marginalia_nu wrote:
| In most cases even beside this issue, microbenchmarks are in
| general very difficult to interpret for a slew of reasons. I
| get the impetus to try and isolate a single variable, but in
| practice you're often isolating away real world applicability
| of the result as well.
|
| This is especially true for CPU and I/O benchmarks that
| typically have an onion's worth of caching layers in hardware
| and OS.
| throwaway2037 wrote:
| What you say may be true, but both Oracle and Google have
| significant investments in parallel microbenchmark tools:
| Java Microbenchmark Harness and Caliper. Aleksey Shipilev
| (@shipilev) famously worked on the Oracle one for a while. He
| used it extensively in his analysis of core Java code
| changes. And, I recall that the Google Guava team used
| Caliper similarly.
| jeffbee wrote:
| Google has published not just one but two different papers
| about how and why to ignore microbenchmark signals when
| making global optimizations.
|
| https://people.ucsc.edu/~hlitz/papers/asmdb.pdf
|
| https://www.usenix.org/system/files/osdi21-hunter.pdf
| marginalia_nu wrote:
| Mr Shipilev is pretty well aware of this. He used to give a
| talk "JMH: The Lesser of Two Evils" that goes into some
| detail about a lot of the problems and pitfalls with
| microbenchmarks.
|
| 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.
| re-thc wrote:
| > it's questionable whether these 12x optimizations will
| result in even a 0.1% improvement in performance in the
| median Java application
|
| 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.
| adgjlsfhk1 wrote:
| except that zen4 has avx and Intel's new consumer chips
| don't
| kllrnohj wrote:
| Most zen4 consumer reviews didn't even have any Java
| benchmarks at all much less any that would have
| significantly changed the narrative around those CPUs.
|
| Epyc vs. Xeon is what this is about as the datacenter is
| the last holdout for OpenJDK at this point.
| unnah wrote:
| You're thinking of AVX-512. Current Intel and AMD
| consumer chips support both AVX and AVX2.
| dragontamer wrote:
| That 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.
| comex wrote:
| Sounds like you'd still want a non-AVX512 path for
| sufficiently small arrays, though. As an extreme case,
| sorting a 4-element array presumably doesn't get enough
| speedup from AVX512 to be worth downclocking by 100Mhz. I
| wonder where the cutoff is.
| dragontamer wrote:
| The 100MHz downclocking is only seen in Icelake, and not in
| Rocketlake (no perceptive downclocking behavior from any
| AVX512).
|
| 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.
| snemvalts wrote:
| x86 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)
| ww520 wrote:
| SIMD is not Intel only. ARM has SIMD support. So does AMD.
|
| 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.
| Cthulhu_ wrote:
| The 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 wrote:
| I 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/perfo
| rmance_improvemen...
| xmcqdpt2 wrote:
| The 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.
| Kipters wrote:
| Yeah, that work in C# required a lot of other things to
| minimize allocations.
|
| 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/2a1b52a1b691c
| 42a7f407...
| usrusr wrote:
| A precedent for x86 SIMD in those low level performance
| building blocks would also set a precedent for the inclusion of
| ARM equivalents. A heavy abstraction environment is exactly the
| right spot to place a set of ergonomic, long SIMD levers, one
| for each architecture.
| janwas wrote:
| Or a portable one that already works on Arm, RISC-V, AVX2 etc
| :) See the vqsort link above.
| misja111 wrote:
| Impressive, 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.
| rightbyte wrote:
| Sorting an array of pointers is sorting by numbers.
| misja111 wrote:
| Sure, but what use is that? You will have your objects sorted
| by the absolute value of their pointer. I guess this means
| you'll have your objects sorted by the order in which they
| are allocated in the heap. Cool, but not very useful.
| rightbyte wrote:
| You can do a sorted array of pointers and later check if a
| specific pointer is in it with binary search, etc.
| revelio wrote:
| Not in Java you can't.
| mjburgess wrote:
| Hash their properties
| hurril wrote:
| And... 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 wrote:
| True 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 wrote:
| `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)`
| inetknght wrote:
| > _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._
|
| 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.
| misja111 wrote:
| I don't see how you can add that level of indirection if you
| can only sort an array of numbers. Let's say you have a
| Person object with property 'age' which is an Int. I can put
| the Person's ages into an Int Array and sort that. Where to
| add this indirection to get to the sorted array of Person
| objects?
| inetknght wrote:
| 1. Have an immutable container of Persons named `persons`
|
| 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.
| dtech wrote:
| sorting arrays of numbers is very often ultimately used under
| the hood of all the nice abstractions
| nraynaud wrote:
| a weird detail is that javac seems to have crashed in the CI:
| 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]
| anthony88 wrote:
| Looking 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.
| mgaunard wrote:
| They just copied a library provided by Intel themselves.
|
| The folks on the JDK side probably didn't even research how to
| parallelize sort.
| e4m2 wrote:
| The author of the PR works for Intel, though.
| pdhborges wrote:
| With the Vector API comming I don't see this PR going through.
| A light search on the OpenJDK mailing list found no discussion.
| marginalia_nu wrote:
| This is an intrinsic JVM function though, not application code.
| anonymoushn wrote:
| It 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 wrote:
| I 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_improv
| emen...
|
| *I may get vector length wrong, but you get the idea
| anonymoushn wrote:
| You can just look up the IntVector API in the docs and see
| that there's no method corresponding to VCOMPRESSPS or
| whatever.
| Kipters wrote:
| You mean this IntVector[0], which I assume is the Java
| experimental API anthony88 was referring to, correct? If
| that operation being missing is a blocker, I feel there
| may be some middle ground other than implementing the
| whole thing in C++ (like adding it or fast tracking work
| on this API)
|
| [0]: https://docs.oracle.com/en/java/javase/19/docs/api/j
| dk.incub...
| gergo_barany wrote:
| The compress operation being missing is not a blocker,
| since the compress operation is not missing: https://docs
| .oracle.com/en/java/javase/19/docs/api/jdk.incub...
| zmmmmm wrote:
| nice!
|
| 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?
| mschuster91 wrote:
| > 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 wrote:
| Nearly 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 wrote:
| These integrated GPUs however often are barely worth
| calling them by that name, and completely forget about the
| crap Qualcomm and others ship.
| touisteur wrote:
| I 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 wrote:
| There are all sorts of intrinsic in the JVM via feature
| detection.
| janwas wrote:
| As 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/so...
| zmmmmm wrote:
| looks amazing - does this include JVM bindings or is it just
| something that would be the basis for that?
| janwas wrote:
| Thanks :) We do not have JVM bindings. I am not familiar
| with Java internals but would be happy to consider
| maintaining them if someone wants to add them (plus a
| test).
| sakex wrote:
| You 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_ wrote:
| I'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.
| rightbyte wrote:
| The computer gets unusable for multitasking you swamp the
| CPU.
| sakex wrote:
| I 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 wrote:
| The 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.
| h4x0rr wrote:
| Even 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
| gigatexal wrote:
| The 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 wrote:
| I 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!
| re-thc wrote:
| Intel has been doing this for a long time. It's a long term
| strategy just like nvidia helping optimize games.
| 5e92cb50239222b wrote:
| Why? 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.
| YawningAngel wrote:
| Intel adding things like AVX is only valuable to anyone if
| compilers actually smit AVX instructions
| gigatexal wrote:
| Yeah that's the code. I am not a low level dev or Java dev so
| it looked odd. Thanks for clarifying.
| kryptiskt wrote:
| They 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.
| dtech wrote:
| Nice. 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.
| MrBuddyCasino wrote:
| One would think such relatively low-hanging fruit (dispatching
| to an existing avx512 lib) would have been picked by now,
| considering the massive effort to improve the JVM in other
| areas (virtual threads, value objects, C interop, Graal, novel
| GCs).
|
| Maybe Array.sort() isn't that frequently used, as data sorting
| is often done by the database?
| carpenecopinum wrote:
| The big issue here (provided that I'm reading the PR
| correctly) is that it's purely for arrays of the primitive
| number types. Whereas most real applications (that I've seen)
| will be sorting objects by some (potentially computed)
| property, be it an ID, a timestamp or a name. For all of
| these cases, the linked pull request won't be doing anything
| useful. The most useful application for this (outside of
| getting nicer numbers on a benchmark) that I see is computing
| the median/quantiles of some property on a bunch of objects
| that aren't already sorted by the interesting property.
| marginalia_nu wrote:
| You still see quite a lot of primitive number sorting in
| library code. If you want your Java code to go fast, you
| typically stick to primitives in arrays.
|
| 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.
| marginalia_nu wrote:
| I think the number of applications that will see a measurable
| speed-up from this improvements is very small.
|
| 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.
| xmcqdpt2 wrote:
| Java high-performance programming would be significantly
| improved by generics over primitive types. Writing
| performant code in Java feels like writing Fortran or C.
|
| You end up using libraries like fastutil, which is "generic
| code" templated by C preprocessor macros,
|
| https://fastutil.di.unimi.it/
| MrBuddyCasino wrote:
| > _Java high-performance programming would be
| significantly improved by generics over primitive types._
|
| 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.
|
| [0] https://cr.openjdk.org/~briangoetz/valhalla/sov/01-ba
| ckgroun...
| dtech wrote:
| Project Valhalla has been announced 9 years ago and
| nothing relevant is in the JDK yet, I don't think this
| will be relevant for day-to-day Java for several more
| years at least.
| MrBuddyCasino wrote:
| Probably, but "nothing relevant is in the JDK yet" is not
| quite fair. Several sub-projects are in "Preview Feature"
| [0] status, which is defined as "a new feature of the
| Java language, Java Virtual Machine, or Java SE API that
| is fully specified, fully implemented, and yet
| impermanent".
|
| 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
|
| [3] https://openjdk.org/jeps/8277163
|
| [4] https://openjdk.org/jeps/8261529
| saagarjha wrote:
| Why is it disappointing?
| WJW wrote:
| Not 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.
| kaba0 wrote:
| Autovectorization is a famously difficult optimization and
| runtime information doesn't make it any easier. That is
| more useful for optimistic assumptions, like these pointers
| won't be zero, only a single instance exists for this
| interface, etc.
|
| Nonetheless, you might find the Graal compiler doing a
| better job at autovectorization than C2.
| [deleted]
| nraynaud wrote:
| I 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.
| kllrnohj wrote:
| AOTs consistently do much more inlining & unrolling than
| JITs do. 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. And then similarly JITs need to optimize for
| compilation speed which limits the amount of optimization
| passes it'll do, because the JIT result is itself a "hot
| path."
|
| 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?
| gergo_barany wrote:
| _> AOTs consistently do much more inlining & unrolling
| than JITs do._
|
| 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.
| WJW wrote:
| Of 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.
| kaba0 wrote:
| I don't know -- having almost native speed with all the
| benefits of a fat runtime like attaching a debugger to a
| prod process to check the number of objects, or streaming
| runtime logs without almost any overhead sounds like they
| do deliver.
| kllrnohj wrote:
| > having almost native speed
|
| 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.
| kaba0 wrote:
| That's not so simple that we could reduce it to a number.
| Java is _very_ close to C performance when you operate on
| primitives only. But it does have an overhead for objects
| and it can't "hide" it as well as languages that have
| developer-control on stack allocation (List <Complex>
| will be an array of pointers in java, while it can be
| inlined values layed out sequentially in C/C++/Rust).
|
| 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.
| kllrnohj wrote:
| The most recent 10 years and that's exactly the point -
| we're plateauing on hardware advancements, so software
| inefficiencies are more of an issue now than ever before.
| 2x is now a _huge_ change in performance. You 're not
| getting that "for free" from just waiting a couple of
| years anymore.
| kaba0 wrote:
| You did not take into account my point about code
| operating on primitives definitely not having that kind
| of overhead.
|
| 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.
| kllrnohj wrote:
| > You did not take into account my point about code
| operating on primitives definitely not having that kind
| of overhead.
|
| 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.
| pjmlp wrote:
| On the other hand .NET is much closer, because it
| supports value types and CLR was designed to be targed by
| C++ as well, so it supports most of the crazy C and C++
| stuff (not counting UB related ones).
|
| Likewise if you code in C, C++ or Rust with allocations
| everywhere, bad algorithms or data structures, being AOT
| won't help.
| dtech wrote:
| Unfortunately, Hotspot does not do all that much in that
| regards either in my experience. Graal is better but lags
| in language support and usage.
| dtech wrote:
| You might not be me, but formulated my point extremely
| well.
| neonsunset wrote:
| C# 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 wrote:
| Java does as well, check out the Vector API.
| brewmarche wrote:
| AFAIK the Java Vector API is like Vector<T> not like the
| intrinsics one
___________________________________________________________________
(page generated 2023-05-31 23:02 UTC)