2 ms·

I don’t see an easy way to vectorize those loops, given that the loop iterations have a dependency on idx1, respectively idx2. Can you explain? (Also, if you

I don’t see an easy way to vectorize those loops, given that the loop iterations have a dependency on idx1, respectively idx2. 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)

dzaima 4y ago
In AVX-512, there's an instruction vpcompressd, which literally does the equivalent of 16 iterations of that loop (the "store a subset of items to memory contiguously" part at least). The compiler would have to figure out how the conditional write & increment work together, but it's definitely possible as ICC manages to: https://godbolt.org/z/n68ca4aYe https://godbolt.org/z/n68ca4aYe 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.