Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Vectorized and performance-portable Quicksort

opensource.googleblog.com

Post reply on HN
Print view View original

121–130 of 147 posts

Re: Vectorized and performance-portable Quicksort

#121

Post by inciampati »

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 quadratic in sequence divergence rather than length, a huge improvement over SWG for almost all applications.

In WFA the data dependencies are trivial and compilers easily auto-vectorize the inner loop of the algorithm. It's also possible to implement this in linear memory relative to sequence divergence with a bidirectional approach (biWFA).

All this is to say that vectorization and SIMD hardware is cool, but new theory and approach can completely overwhelm it's potential benefits.

Re: Vectorized and performance-portable Quicksort

#123

Post by inkyoto »

janwas wrote: post #36

Author here, happy to discuss.

Thanks for sharing results and for the write-up. It is another welcome addition to a series of recent reports attesting the SIMD instructions having entered the mainstream computing, from the high performance JSON parsing to now the quick sort.

The white paper is calling out the memory bandwidth as a major bottleneck, which is where I have a question.

The M1 Max sports a unusually wide (512 bit wide) memory bus coupled with 6.4Ghz DDR5 unified memory which, according to the available empirical evidence, allows a single CPU core at achieve 100Gb/sec circa memory transfer speed. M1 cores also feature a very large L1 D-cache as well as a large L2 cache (48 Mb has been reported). Results, however, are approximately 2.4x lower for the M1 Max. I do realise that the NEON SIMD processing will always be slower compared to AVX-512 SIMD based one due to a 4x difference of the vector size, but isn't the M1 Max supposed to perform somewhat faster than in observed figures due to the faster and much wider memory bus that would partially compensate for NEON inefficiency?

Other than the vector size difference between NEON and AVX-512, would you attribute the difference in performance to the small test batch size (~4/8/16 Mb for 32/64/128 unit sizes used in the test) thus being able to able to fit in the L2 cache nearly entirely, or due to GCC being unaware of cache line sizes on M1 Pro/Max therefore resulting in the cache underutilisation or inefficient instruction scheduling, or you would purely attribute it to NEON having not aged gracefully to meet current data processing demands?

Thank you.

Re: Vectorized and performance-portable Quicksort

#125

Post by jiggawatts »

wtallis wrote: post #117
jiggawatts wrote: post #110

Earlier quoted context omitted.

Something to note is that he was testing this on an 11-year old processor: https://ark.intel.com/content/www/us/en/ark/products/52269/i... The Google sorting algorithm seems to be optimised for the "latest and greatest" AVX-512 capable CPUs.

The Xeon E3-1220 v5 is not the same as the original E3-1220. You want this link: https://ark.intel.com/content/www/us/en/ark/products/88172/i... The E3 v5 series were part of the generation codenamed Skylake , introduced in 2015. But the Skylake microarchitecture was reused in each subsequent new Intel desktop processor generation through 2019's Comet Lake (due to Intel's 10nm failure). They didn't introduce a new mi…

Well spotted!

Re: Vectorized and performance-portable Quicksort

#126

Post by janwas »

inkyoto wrote: post #123
janwas wrote: post #36

Author here, happy to discuss.

Thanks for sharing results and for the write-up. It is another welcome addition to a series of recent reports attesting the SIMD instructions having entered the mainstream computing, from the high performance JSON parsing to now the quick sort. The white paper is calling out the memory bandwidth as a major bottleneck, which is where I have a question. The M1 Max sports a unusually wide (512 bit wide) memory bus coupl…

:) If I'm reading 100Gb/sec correctly as Gigabits, a Skylake core can also reach such bandwidth usage. The issue is that the system can only sustain that for roughly 8 cores. It would be very interesting to see bench_parallel results for an M1 Max, if anyone would like to give that a try? I suspect it will be comparable to Skylake-X, because 8 (performance) cores are not quite enough to utilize all the M1 Max bandwidth in this app. M1 may be more power efficient, though. It is also great to see more bandwidth per core. A hypothetical M2 with say 256-bit SVE vectors and 16 cores could be very interesting.

L2 caches are typically partitioned and private to a core. If that also applies to the M1 Max, then each core would only access 3 MB, thus the working set is larger than cache as intended.

I do believe NEON is the limiting factor here. I haven't looked into how many IPC we should expect, but even if it is 4 (the number of 128-bit NEON units), Skylake is often reaching 2 (with 512-bit vectors), so the measurement that an M1 core is about half as fast as SKX for this use case seems plausible.

Re: Vectorized and performance-portable Quicksort

#128

Post by janwas »

MrYellowP wrote: post #124
janwas wrote: post #36

Author here, happy to discuss.

Hey mate, can you throw some challenges/problems at me to optimize? I don't know what's worth looking at! Thanks!

Depends on your goals? If you'd like to contribute code under Apache2, I'd be happy to collaborate. Feel free to reach out to the email in the Highway README.

Some of the things on my short to medium-term todo list include:

- CompressStore for 8-bit lanes (before Icelake, that will likely require splitting up into runs of 8 bytes with one PSHUFB + store each)

- also ExpandLoad (analogous to CompressStore) and LeadingZeroCount

- the C++ STL isn't autovectorized much (http://0x80.pl/notesen/2021-01-18-autovectorization-gcc-clan...). Manual vectorization can help, we have some of the simpler algorithms already in hwy/contrib/algo, others such as unique, reverse, minmax_element, all_of are more interesting.

Re: Vectorized and performance-portable Quicksort

#129

Post by watmough »

jart wrote: post #31
wtallis wrote: post #27

Earlier quoted context omitted.

> it's the avx we can reliably use in open source I'm not sure what you mean by that. You can't assume the presence of AVX or AVX2 without explicitly checking for it, because Intel was still disabling those features on new low-end Pentium and Celeron parts at least a recently as Comet Lake (2020). Sure, AVX2 support is much more widespread than AVX512 support, but that has nothing to do with open-source and it's a bi…

Some of us like to think of ourselves writing open source as serving the public interest. It's hard to do that if you're focusing on an ISA the public doesn't have. I haven't seen any consumer hardware that has AVX512.

Tiger Lake https://ark.intel.com/content/www/us/en/ark/products/213803/...

Sniff, already superceded by Alder Lake.

Re: Vectorized and performance-portable Quicksort

#130

Post by dundarious »

janwas wrote: post #37
TontonNestor wrote: post #33

Earlier quoted context omitted.

djbsort uses a sorting network, not a quicksort. It is also designed to be in constant time, which is not the case with the linked blog post. So the restrictions are different. This is not my field, so I can't judge the relevance of this, but the author cites the state of the art. It just seems that djbsort is not the state of the art and therefore does not need to be cited. I still don't understand the hype around B…

:) FWIW we also use a constant-time sorting network as the base case of the Quicksort recursion, that's a widely used optimization.

For 32bits, djb has done light testing, indicating djbsort would be a better base case.

> So far I haven't been able to verify these vqsort speed claims. On the contrary, it seems that, for 32-bit data types on AVX2, vqsort would be faster if its base-case code were replaced by a call to the 2018 djbsort code. Similarly, vqsort should reuse vxsort-cpp for AVX-512.

https://twitter.com/hashbreaker/status/1533314687726538753

Post reply on HN