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

61–70 of 147 posts

Re: Vectorized and performance-portable Quicksort

#61

Post by bee_rider »

hinkley wrote: post #21
MontyCarloHall wrote: post #12

Earlier quoted context omitted.

I don’t see any mention in the paper of thermal clock throttling concerns, which can really neuter performance of tools that sustain use of AVX operations over a period of time. For the quick benchmarks presented in the paper, of course it will be faster. What if I’m continuously hammering my CPU with AVX operations? I expect it to severely downclock.

My laptop has been throttling itself for a while, I recently discovered. I had been trying to benchmark some code changes and have given up and am letting the CI machine run them, because my numbers are all over the place and go down with each run.

One option would be to go into BIOS and see if there's some way of just locking your CPU to one of the lower clock speeds. This will give lower benchmarking numbers of course, but at least they should be fairly stable. (in Linux, it also often possible to tinker with frequencies while the system is running).

Even on a desktop this sort of thing is sometimes necessary, for example my CPU has different clock speeds depending on how many processors are running, so I have to lock it to the all-core clock if I want to see proper parallel speedups.

This might be annoying for day-to-day usage (although, CPUs really are insanely performant nowadays so maybe it will not be too bad).

Re: Vectorized and performance-portable Quicksort

#62

Post by magicnubs »

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). FYI, I think the last two projects use some large research GPU bank that you have to have special access to use, so you'd be out of luck on implementing the projects for those.

[0] https://web.engr.oregonstate.edu/~mjb/cs575/ [1] https://media.oregonstate.edu/media/t/1_7wju0jtq [2] https://web.engr.oregonstate.edu/~mjb/cs575/Projects/proj04....

Re: Vectorized and performance-portable Quicksort

#65

Post by janwas »

nickysielicki wrote: post #56
janwas wrote: post #36

Author here, happy to discuss.

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 issue you pointed to, that we cannot have arrays of N vectors, it's a reasonable workaround to instead allocate an array of N vectors' worth of elements, and trust the compiler to elide unnecessary Load/Store. This often works using clang, and would avoid having to manually unroll here. I do prefer to minimize the amount of compiler magic required for good performance, though, so typically we're unrolling manually as shown in that code.

2) If there are compiler bugs, typically the workarounds have to stay in because in the open-source world people are still using that compiler years later.

Automatically detecting when things get better is an interesting idea but I am not yet aware of such infrastructure.

Re: Vectorized and performance-portable Quicksort

#66

Post by janwas »

convolvatron wrote: post #58
nostrademons wrote: post #23

Earlier quoted context omitted.

It's not new within Google either. I remember poking through Jeff Dean's original MapReduce code (written c. 2003) and finding a SIMD-based QuickSort that was the in-memory portion of the external sort algorithm. It looks like this algorithm is interesting in the specifics of how it works, eg. the use of a compress-store instruction for partitioning. The algorithm I mentioned above mostly focused on speeding up compa…

nothing happened before google https://dl.acm.org/doi/10.1145/113379.113380

hah, our paper actually cites "Radix sort for vector multiprocessors" by the same author, also from 1991 :)

Re: Vectorized and performance-portable Quicksort

#68

Post by janwas »

ComputerGuru wrote: post #55
janwas wrote: post #50

Earlier quoted context omitted.

I don't know about "most", but here is a list: https://en.wikipedia.org/wiki/List_of_column-oriented_DBMSes

No, this is a list of columnar database systems - gp was saying the index, which is often (but not always) stored separately from the main db records.

Ah, indeed, my mistake. FWIW I've observed increasing numbers of papers over the past couple of years mentioning entirely columnar databases.
Post reply on HN