For vertical-only operations (vectorizable loops), people often using GPUs instead of SIMD in CPUs. Graphics cards have way more resources, both GFlops and memory bandwidth.
I don't think sorting an array has anything to do with vectorizing a loop.
int partition(int[] array, int from, int to, int pivot) {
int[] buf1 = new int[to - from];
int[] buf2 = new int[to - from]; // buffers could be preallocated, as in the blogpost
int idx1 = 0;
int idx2 = 0;
for (int i = from; i < to; i++) {
int value = array[i];
if (value < pivot) {
buf1[idx1++] = value;
}
}
for (int i = from; i < to; i++) {
int value = array[i];
if (value >= pivot) {
buf2[idx2++] = value;
}
}
System.arraycopy(buf1, 0, array, from, idx1);
System.arraycopy(buf2, 0, array, from, idx2);
}
This is despite unlike Java’s runtime, C++ compilers work offline, they don’t care too much about compilation speed, a JIT compiler simply doesn’t have time for expensive optimizations.
That is a common misconception, which might apply to some JIT compilers. For example, OpenJDK does not only need to compile only the hot methods, but even then it employs tiered compilation, where more powerful optimisations are made over time, and so the JIT can take as much time as needed (it runs concurrently with the already-compiled program) and has more profiling information than available to an AOT compiler. I.e. the same optimisation might be much quicker for a JIT than for an AOT compiler because the JIT doesn't need to do as deep an analysis of the program.
The advantage AOT compilers have over JITs is that they don't require warmup and they don't consume resources at runtime, but JITs have a greater potential for optimisation, and AOT compilers generally require more low-level information from the programmer to produce good code. There are various projects for caching JIT output and get something that's close to the best of both worlds.
Having said that, compilers aren't all developed on the same schedule, and different ones might prioritise different optimisations.
.NET Framework 4.6 did provide some mechanism (MGO, Managed PGO), but did required calling into runtime APIs and was a bit clunky. Starting with .NET 6 they are using an approach more similar to the JVMs.
As far as I am aware, only Java (including the Android stepchild) and .NET ecosystems do have such JITs with PGO feedback between runs.
Can you explain?
(Also, if you loop idx2 down from to, I think you need only one buffer and one System.arraycopy call, at the cost of no longer having a stable sort)
For non-AVX-512, it gets more complicated to do the compression part, but you can still do it with a shuffle & lookup table of indexes from the mask.