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

111–120 of 147 posts

Re: Vectorized and performance-portable Quicksort

#111

Post by janwas »

jiggawatts wrote: post #110
viraptor wrote: post #103

Earlier quoted context omitted.

He's just investigating how to reproduce the claimed result. Not sure where you got your take from.

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.

Oh, thanks for pointing that out. Golly, Sandy Bridge is a bit old, yes - but still the result is surprising.

djb reports 8000 cycles for int32 x 256 - this is much slower than we benchmark in bench_sort.cc, even for AVX2 (which he confirms is being reached). Not sure what's going on.

Re: Vectorized and performance-portable Quicksort

#112

Post by janwas »

celrod wrote: post #106
janwas wrote: post #65

Earlier quoted context omitted.

Thanks! Feel free to raise Github issues if you'd like to ask/discuss anything. I'm also a huge fan of Godbolt/Compiler Explorer. Highway is integrated there, so you can just copy in your functions. Here's the last throwaway test that I was using: https://gcc.godbolt.org/z/5azbK95j9 > things might get better in the future but for now we have to implement it another way There's several possible answers. 1) For the iss…

// Compiler doesn't make independent sum* accumulators, so unroll manually. // We cannot use an array because V might be a sizeless type. For reasonable // code, we unroll 4x, but 8x might help (2 FMA ports * 4 cycle latency). That code needs 2 loads per FMA. So a CPU with 2 FMA ports would need at least 4 load ports to be able to feed the 2 FMA ports. Given that most CPUs with 2 FMA ports have just 2 load ports, unr…

Thanks :) I'd be interested to hear how it goes for you.

Agree that 4x unrolling is getting most of the low-hanging fruit without excessive code size. I saw only very slightly better performance on SKX with 8x.

You're right that it's nicer when the compiler can decide about the unrolling - for example with knowledge whether we have 16 or 32 regs. The unsafe/fast-math flags are pretty dangerous, though :/ https://simonbyrne.github.io/notes/fastmath/ Especially when they enable flush-to-zero, which would be unacceptable for a library loaded into some other application.

Re: Vectorized and performance-portable Quicksort

#113

Post by janwas »

BeeOnRope wrote: post #87
janwas wrote: post #36

Author here, happy to discuss.

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 :)

Re: Vectorized and performance-portable Quicksort

#114

Post by janwas »

superjan wrote: post #69
janwas wrote: post #36

Author here, happy to discuss.

Great work! Does it also support sorting object pointers by a numeric key?

Thanks :) If I understand correctly, you have tuples of (number, T*) and want to sort by number? That can be done by storing these tuples interleaved, reinterpret_casting to hwy::uint128_t (making sure that the pointer bits are in the least-significant half), and sorting those.

Re: Vectorized and performance-portable Quicksort

#115

Post by janwas »

BeeOnRope wrote: post #91

Are there instructions for building & reproducing the performance results?

I'd recommend building using Bazel (perhaps via the bazelisk launcher), then it would be: bazel run -c opt :bench_sort (or :bench_parallel). Will verify that on Tue and put it in a README in contrib/sort.

Re: Vectorized and performance-portable Quicksort

#116

Post by janwas »

aaaaaaaaaaab wrote: post #104

This works only with integers, right? Then radix sort is gonna be still faster on sufficiently large inputs…

Actually we also support floating-point (32/64 bit, possibly even 16). I've previously also looked into radix sort: https://arxiv.org/abs/1008.2849

Radix sort may actually be faster if you know that only a few bytes are guaranteed to distinguish keys, but that's difficult to guarantee/assume at the library level.

Re: Vectorized and performance-portable Quicksort

#117

Post by wtallis »

jiggawatts wrote: post #110
viraptor wrote: post #103

Earlier quoted context omitted.

He's just investigating how to reproduce the claimed result. Not sure where you got your take from.

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 microarchitecture in that product segment until Rocket Lake and Alder Lake, both in 2021. So despite being almost 7 years old, the E3-1220v5 is still representative of most of the installed base for Intel desktops and entry-level workstations, and a large chunk of their mobile installed base.

(The original E3-1220 predates AVX2 by two years, so this code wouldn't even run on it.)

Re: Vectorized and performance-portable Quicksort

#119

Post by janwas »

mikevm wrote: post #118
janwas wrote: post #36

Author here, happy to discuss.

How does Highway compare to SIMDe ( https://github.com/simd-everywhere/simde )?

SIMDe implements the exact semantics of a given ISA using either the native intrinsics, or other platform's intrinsics when possible, otherwise autovectorization. This is great when you've already written code using e.g. NEON intrinsics and want it to run on x86 (similar to neon2sse), or the reverse. It's an impressive undertaking to implement thousands of instructions for each platform :)

Highway instead aims for a path that each platform can implement efficiently. For example, ReorderWidenMulAccumulate bridges differences between NEON and x86 which user code need not care about if they just want a dot product, and CountTrue is efficient on both platforms without requiring NEON to go to the extra trouble of matching the exact x86 movmskb semantics. Also, Highway uses only intrinsics and does not rely on autovectorization (+), which makes for more predictable performance.

+ except in the EMU128 target, which is only used if SIMD/intrinsics are disabled

Re: Vectorized and performance-portable Quicksort

#120

Post by sitkack »

heavenlyblue wrote: post #98
janwas wrote: post #43

Earlier quoted context omitted.

Yes, we can sort 64-bit ints. The speedup on AVX2 is roughly 2/3 of the 10x we see on AVX-512. Longsort appears to be an autovectorized sorting network. That's only going to be competitive or even viable for relatively small arrays (thousands). See comments above on djbsort. Why not use whichever AVX the CPU has? Not a problem when using runtime dispatch :)

What about performance-per-watt?

Main memory accesses dominate energy consumption, so the lower your total memory bandwidth the less energy an algorithm will take.

https://www.researchgate.net/figure/Data-movement-is-overtak...

The chart above shows a 1000x (3 orders of magnitude base 10) increase in energy consumption relative to a register move (it really should be called copy).

Post reply on HN