Vectorized and performance-portable Quicksort • Hacker News Board

Re: Vectorized and performance-portable Quicksort

#131

Post by watmough » Sun, Jun 05, 2022, 2:31 PM UTC

gww wrote: post #46

I am always amazed at the algorithms re-implemented using SIMD. One of my favorites is the Striped Smith-Waterman approach used for sequence alignment. Does anyone have any good resources on learning to use SIMD? I've found it heard to make the "plunge".

Agner Fog's VCL library is extremely approachable. Just download it and get stuck in.

  Manual
  https://www.agner.org/optimize/vcl_manual.pdf

  GitHub
  https://github.com/vectorclass/version2

Even for trivial stuff like linebreaking input files, massive speedups are there for the taking.

Re: Vectorized and performance-portable Quicksort

#132

Post by jonstewart » Sun, Jun 05, 2022, 5:48 PM UTC

janwas wrote: post #36

Author here, happy to discuss.

I started reading through Highway docs, and maybe I missed something, but I’m surprised it’s a built library to be linked against, instead of a header-only library —- at least when using static targeting. If using static targeting, wouldn’t function call overhead be severe, or are a lot of implementations in the headers?

Re: Vectorized and performance-portable Quicksort

#133

Post by gww » Sun, Jun 05, 2022, 6:22 PM UTC

magicnubs wrote: post #62

gww wrote: post #46

I am always amazed at the algorithms re-implemented using SIMD. One of my favorites is the Striped Smith-Waterman approach used for sequence alignment. Does anyone have any good resources on learning to use SIMD? I've found it heard to make the "plunge".

The lectures and assignments for Oregon State's CS475 (Parallel Programming) are all available online. [0] There are lectures [1] and a project [2] about SIMD. I really enjoyed the entire course as a survey of parallel and high-performance computing. The full course covers multi-processing, multi-threading, caching, SIMD, GPUs (CUDA and OpenCL) and MPI. The projects are in C/C++ (along with OpenMP, CUDA and OpenCL).…

Thanks these are really great. That's a course I wish my CS program had.

Re: Vectorized and performance-portable Quicksort

#134

Post by gww » Sun, Jun 05, 2022, 6:23 PM UTC

janwas wrote: post #54

gww wrote: post #46

I am always amazed at the algorithms re-implemented using SIMD. One of my favorites is the Striped Smith-Waterman approach used for sequence alignment. Does anyone have any good resources on learning to use SIMD? I've found it heard to make the "plunge".

:) How about Chapter 12 of Agner's awesome manual ( https://agner.org/optimize/optimizing_cpp.pdf ), http://const.me/articles/simd/simd.pdf , https://en.algorithmica.org/hpc/simd/ ? Does anyone have others to share?

These are really helpful too. Another reply to my question suggests a course that looks really good too.

Re: Vectorized and performance-portable Quicksort

#135

Post by gww » Sun, Jun 05, 2022, 6:24 PM UTC

inciampati wrote: post #121

gww wrote: post #46

I am always amazed at the algorithms re-implemented using SIMD. One of my favorites is the Striped Smith-Waterman approach used for sequence alignment. Does anyone have any good resources on learning to use SIMD? I've found it heard to make the "plunge".

The performance benefit of SIMD implementation of Smith-Waterman-Gotoh is moot relative to the gains provided by a total reformulation of the pairwise sequence alignment problem. The Wavefront Algorithm (WFA) flips the problem on its head by progressively exploring the best scoring alignment until a global alignment is attained. Then no more work needs to be done to fill the matrix. The total work is actually quadrat…

I agree with you about WFA. I was just very impressed when the striped SW first came out when I was still a fledgling PhD student.

Re: Vectorized and performance-portable Quicksort

#136

Post by gww » Sun, Jun 05, 2022, 6:25 PM UTC

Const-me wrote: post #107

gww wrote: post #46

I am always amazed at the algorithms re-implemented using SIMD. One of my favorites is the Striped Smith-Waterman approach used for sequence alignment. Does anyone have any good resources on learning to use SIMD? I've found it heard to make the "plunge".

I wrote that article some time ago: http://const.me/articles/simd/simd.pdf

This is helpful. Thank you

Re: Vectorized and performance-portable Quicksort

#137

Post by gww » Sun, Jun 05, 2022, 6:25 PM UTC

watmough wrote: post #131

gww wrote: post #46

I am always amazed at the algorithms re-implemented using SIMD. One of my favorites is the Striped Smith-Waterman approach used for sequence alignment. Does anyone have any good resources on learning to use SIMD? I've found it heard to make the "plunge".

Agner Fog's VCL library is extremely approachable. Just download it and get stuck in. Manual https://www.agner.org/optimize/vcl_manual.pdf GitHub https://github.com/vectorclass/version2 Even for trivial stuff like linebreaking input files, massive speedups are there for the taking.

Thank you

Re: Vectorized and performance-portable Quicksort

#138

Post by janwas » Sun, Jun 05, 2022, 6:47 PM UTC

jonstewart wrote: post #132

janwas wrote: post #36

Author here, happy to discuss.

I started reading through Highway docs, and maybe I missed something, but I’m surprised it’s a built library to be linked against, instead of a header-only library —- at least when using static targeting. If using static targeting, wouldn’t function call overhead be severe, or are a lot of implementations in the headers?

Good question. There are only a few functions implemented in .cc files, tagged with HWY_DLLEXPORT, notably memory allocation and detecting x86 CPU capabilities. If it were necessary, we could likely strip those out or do a header-only library. The ops/intrinsics called from user code are inlined in headers.

Re: Vectorized and performance-portable Quicksort

#139

Post by BeeOnRope » Sun, Jun 05, 2022, 8:48 PM UTC

janwas wrote: post #113

BeeOnRope wrote: post #87

Earlier quoted context omitted.

Interesting post and paper, thanks! Sometimes the state of the art is not found in another paper but somewhere else, e.g,. there is vxsort by Dan Shechter (damageboy): https://github.com/damageboy/vxsort-cpp/tree/master He uses a similar approach and while I'm not sure how it compares to the older Blacher et al version, I expect it to be in the ballpark. He's written an excellent series of blog posts on the design &…

Thanks for sharing the pointers. I hadn't come across that, will read soon :)

Interestingly from the portability angle, this was all written in C# but with the SIMD intrinsics there he was still able to obtain ~SOTA performance.

The repo I linked is his C++ version of the C# original.

It was submitted to the C# standard library but was rejected (as an observer, the rejection was disappointing) – had it been accepted C# would have been in the interesting position of having a faster sort than any native language standard library, at least for integer keys.

Re: Vectorized and performance-portable Quicksort

#140

Post by jonstewart » Sun, Jun 05, 2022, 9:50 PM UTC

janwas wrote: post #138

jonstewart wrote: post #132

Earlier quoted context omitted.

I started reading through Highway docs, and maybe I missed something, but I’m surprised it’s a built library to be linked against, instead of a header-only library —- at least when using static targeting. If using static targeting, wouldn’t function call overhead be severe, or are a lot of implementations in the headers?

Good question. There are only a few functions implemented in .cc files, tagged with HWY_DLLEXPORT, notably memory allocation and detecting x86 CPU capabilities. If it were necessary, we could likely strip those out or do a header-only library. The ops/intrinsics called from user code are inlined in headers.

Got it, thank you!