search

cpp-core / sort

Sorting
BSD 3-Clause "New" or "Revised" License
1 stars 0 forks source link

Parallel and/or vectorization support? #3

Open reuseman opened 1 year ago

reuseman commented 1 year ago

Hey @melton1968,

I was wondering, do you plan to add some vectorization or parallel support to the sorting algorithms?

melton1968 commented 1 year ago

That could be interesting. Is there a particular algorithm that you would like to see improved?

reuseman commented 1 year ago

I guess that the best candidates would be quick-sort and radix-mem-index-sort so that we can have a comparison vs a non-comparison based. Even the mergesort could be interesting just because at the end it does a scan and with the proper vectorization it may turn out to be quite efficient.

melton1968 commented 1 year ago

I have some preliminary results for multi-threaded quicksort. For sorting 100M uint64_t's, it takes ~7.5s using the standard sequential std::sort directly and ~4.1s using 2 threads with a divide-and-merge strategy with std::sort as the root computation. That is a speedup of 1.8x. I have some ideas for improving the merge to get closer to the theoretical maximum of 2x.