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

101–110 of 147 posts

Re: Vectorized and performance-portable Quicksort

#101

Post by robertlagrant »

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.

> Some of us like to think of ourselves as

I don't see how this is relevant to anything.

Re: Vectorized and performance-portable Quicksort

#103

Post by viraptor »

sydthrowaway wrote: post #100
carbocation wrote: post #96

Looks like djb is giving it a spin: https://twitter.com/hashbreaker/status/1533201734369103872

And he shat all over Google yet again

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

Re: Vectorized and performance-portable Quicksort

#105

Post by celrod »

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?

The bigger the vectors, the better the performance per watt.

Re: Vectorized and performance-portable Quicksort

#106

Post by celrod »

janwas wrote: post #65
nickysielicki wrote: post #56

Earlier quoted context omitted.

Highway looks awesome from a quick glance. Definitely going to set some time aside to play with it and read it. Sort of tangentially related, what sort of tools are you using for disassembly in 2022? Is there anything better than objdump today? What I really want is a version of godbolt that reads compile_commands.json and can show me the godbolt-style color-coded disassembly for an entire binary, any function. I fin…

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, unrolling by 4 should be more or less ideal.

But, ideally, the compiler could make the decision based on the target architecture.

Without enabling associative math, it isn't legal to duplicate floating point accumulators and change the order of the accumulation. Perhaps compiling under `-funsafe-math` would help. If you're using GCC, you'll probably need `-fvariable-expansion-in-unroller`, too.

I think highway looks great. I'm sure I'll procrastinate on something important to play with it reasonably soon.

Re: Vectorized and performance-portable Quicksort

#107

Post by Const-me »

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

Re: Vectorized and performance-portable Quicksort

#109

Post by noisy_boy »

VHRanger wrote: post #11
slackerIII wrote: post #9

What would it take for something like this to make it into Postgres?

unlikely - postgres stores data row-wise and this assumes sequentially stored columns. They even mention that issue in the blog post. It would be more likely to show up in something like Apache Arrow which is designed columnar to leverage these sort of tricks

How about AWS Redshift which is columnar (though that is also based on Postgres)...

Re: Vectorized and performance-portable Quicksort

#110

Post by jiggawatts »

viraptor wrote: post #103
sydthrowaway wrote: post #100

Earlier quoted context omitted.

And he shat all over Google yet again

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.

Post reply on HN