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

51–60 of 147 posts

Re: Vectorized and performance-portable Quicksort

#51

Post by wenc »

Denvercoder9 wrote: post #24
VHRanger wrote: post #11

Earlier quoted context omitted.

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

The data in indexes is stored columnar by most RDBMSes, as far as I know.

Typically a rowstore index is a B-tree data structure (on a column) that points to data pages in a rowstore dataset.

It's not technically columnar as such.

You can sort with a rowstore index today, but I imagine you have to materialize the index in some way to take advantage of vectorization.

Re: Vectorized and performance-portable Quicksort

#52

Post by janwas »

unnouinceput wrote: post #16

Quote: "Today we're sharing open source code that can sort arrays of numbers about ten times as fast as the C++ std::sort...." and proceeds to explain about SIMD instructions. Well, to me sounds that C++ std::sort is simply lacking an optimization which can very easy be implemented in next iteration of the compiler/linker. I had high hopes this would be a really breakthrough algorithm, not lack of a simple optimizati…

CPU vendors have recently introduced SVE (Arm) and RVV (RISC-V) and we support those in Highway and thus also vqsort.

It's definitely interesting to discuss std::sort benefitting from such optimizations, but "very easy" seems rather optimistic.

Re: Vectorized and performance-portable Quicksort

#53

Post by olliej »

Re-implementation of stuff with SIMD is always amazing to me. I have done stuff with SIMD before: 4 element float vector operations; basic arithmetic on arrays of floats.

Those are things that are super simple, once you get past the scary mystique of SIMD.

It’s stuff like this that should be getting all the witch burning :D

Re: Vectorized and performance-portable Quicksort

#54

Post by janwas »

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?

Re: Vectorized and performance-portable Quicksort

#55

Post by ComputerGuru »

janwas wrote: post #50
Denvercoder9 wrote: post #24

Earlier quoted context omitted.

The data in indexes is stored columnar by most RDBMSes, as far as I know.

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.

Re: Vectorized and performance-portable Quicksort

#56

Post by nickysielicki »

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 find that when I’m asking these sort of questions I’m wasting a lot of time fitting my problem into godbolt so I can just get a rough idea of what’s coming out, because it’s so much faster (maybe 10x) to read the color tagged version from godbolt than it is to do the same with objdump.

Edit: along the same lines, what can people do (or rather, what do you do) about situations like this: https://github.com/google/highway/blob/master/hwy/examples/b... where things might get better in the future but for now we have to implement it another way? How do you avoid regressions and how do you track workarounds? I want some sort of database that tries competing implementations on every build and emits a compiler warning when things get better. How are you dealing with this?

Re: Vectorized and performance-portable Quicksort

#58

Post by convolvatron »

nostrademons wrote: post #23
orlp wrote: post #14

SIMD based sorting isn't new, e.g. djbsort: https://sorting.cr.yp.to/ . I find it strange the paper doesn't cite it or compare to it at all. EDIT: to be fair it does seem that Bramas' first published work on SIMD sorting (that I could find) predates djbsort, https://arxiv.org/abs/1704.08579 . A comparison would still be nice though.

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

Re: Vectorized and performance-portable Quicksort

#59

Post by janwas »

mchusma wrote: post #42
janwas wrote: post #36

Author here, happy to discuss.

Very cool work! What do you see as the typical process of getting code like this into use in well known codebases? I'm trying to get a sense of when a typical engineer (operating with higher level language or libraries) might get to take advantage of this. Thanks for open sourcing!

Thanks! Highway is included in Chrome and Firefox. Not sure what you mean by process? It's pretty easy for example using git submodules - you tell Git the Highway version you want to depend on, notify your CMake or Bazel build system of the hwy library dependency, and that's it.

One requirement is C++11 or later - some people have asked about supporting C but I believe that's infeasible.

Re: Vectorized and performance-portable Quicksort

#60

Post by kjeetgill »

Denvercoder9 wrote: post #24
VHRanger wrote: post #11

Earlier quoted context omitted.

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

The data in indexes is stored columnar by most RDBMSes, as far as I know.

I mean, I guess you could call a B-Tree over a subset of columns "columnar"... And bit-map indexes are by columns too — but that's really bending the definition of what most people mean by columnar storage in databases.
Post reply on HN