2 ms·

(For other readers:) This is what our Highway library does - wrapper functions around intrinsics, plus a (constexpr if possible) Lanes() function to query the l

by janwas 1y ago

(For other readers:) This is what our Highway library does - wrapper functions around intrinsics, plus a (constexpr if possible) Lanes() function to query the length. For very many cases, writing the code once for an 'unknown to the programmer' vector length indeed works. One example that doesn't work so well is a sorting network; its size depends on the vector length. (I see you mention this below.)

camel-cdr 1y ago
I quite like highway. As mentioned, last time I tried vqsort for RVV it was surprisingly slow. I tried to replicate it yesterday, but noticed that vqsort is now disabled for RVV: https://github.com/google/highway/blob/400fbf20f2e40b984be129b88f83d4748cfc26a0/hwy/contrib/sort/shared-inl.h#L152 https://github.com/google/highway/blob/400fbf20f2e40b984be12... Does highway support sorting networks for non-128-bit vector registers? When I tried to compile it for AVX512, the BaseCase seems to only use xmm registers: https://godbolt.org/z/qr9xoTGKn https://godbolt.org/z/qr9xoTGKn
- janwas 1y ago
  :) Yes, vqsort recently tickled a bug in clang. I've seen a steady stream of issues, many caused by SLP or the seeming absence of CI. You might try re-enabling it on GCC. Yes, the issue with the sorting network is that it is limited to 16x16 to reduce code explosion. With uint16_t, XMM are sufficient for the 8-column case; your Godbolt link does have some YMM for the 16-column case. When changing the type to sort to uint32_t, we see ZMM as expected.
  - camel-cdr 1y ago
    Btw, here is a VLA vector register sort: https://godbolt.org/z/Env64961q https://godbolt.org/z/Env64961q It has a few more instructions then the VLS version, but the critical dependency chain is the same. It's also slightly less optimal on x86, because it alway uses lane crossing permutes. For AVX512 that is 5 out of 15 permutations that are vperm, but could've been vshuf. (if the loop isn't unrolled and optimized by the compiler) I wasn't able to figure out how to implement the multi vector register sort in a VLA way.
    - janwas 1y ago
      Nice work :) Clang x86 indeed unrolls, which is good. But setting the CC and AA mask constants looks fairly expensive compared to fixed-pattern shuffles. Yes, the 2D aspect of the sorting network complicates things. Transposing is already harder to make VLA and fusing it with the other shuffles certainly doesn't help.

by janwas 1y ago

camel-cdr 1y ago

I quite like highway. As mentioned, last time I tried vqsort for RVV it was surprisingly slow. I tried to replicate it yesterday, but noticed that vqsort is now disabled for RVV: https://github.com/google/highway/blob/400fbf20f2e40b984be129b88f83d4748cfc26a0/hwy/contrib/sort/shared-inl.h#L152 https://github.com/google/highway/blob/400fbf20f2e40b984be12... Does highway support sorting networks for non-128-bit vector registers? When I tried to compile it for AVX512, the BaseCase seems to only use xmm registers: https://godbolt.org/z/qr9xoTGKn https://godbolt.org/z/qr9xoTGKn

janwas 1y ago
:) Yes, vqsort recently tickled a bug in clang. I've seen a steady stream of issues, many caused by SLP or the seeming absence of CI. You might try re-enabling it on GCC. Yes, the issue with the sorting network is that it is limited to 16x16 to reduce code explosion. With uint16_t, XMM are sufficient for the 8-column case; your Godbolt link does have some YMM for the 16-column case. When changing the type to sort to uint32_t, we see ZMM as expected.
- camel-cdr 1y ago
  Btw, here is a VLA vector register sort: https://godbolt.org/z/Env64961q https://godbolt.org/z/Env64961q It has a few more instructions then the VLS version, but the critical dependency chain is the same. It's also slightly less optimal on x86, because it alway uses lane crossing permutes. For AVX512 that is 5 out of 15 permutations that are vperm, but could've been vshuf. (if the loop isn't unrolled and optimized by the compiler) I wasn't able to figure out how to implement the multi vector register sort in a VLA way.
  - janwas 1y ago
    Nice work :) Clang x86 indeed unrolls, which is good. But setting the CC and AA mask constants looks fairly expensive compared to fixed-pattern shuffles. Yes, the 2D aspect of the sorting network complicates things. Transposing is already harder to make VLA and fusing it with the other shuffles certainly doesn't help.