Hacker News Reader

Comment by sagarm | Hacker News Reader

On an Ice Lake GCE instance, Highway's vqsort was 40% faster when sorting uint64s. vqsort also doesn't require avx512, and supports a wider array of types (including 128-bit integers and 64-bit k/v pairs), so it's more useful IMO. It's a much heavier weight dependency though.

Code / scripts here: https://github.com/funrollloops/parallel-sort-bench

I had to use a cloud instance for testing since I don't have an avx512-capable personal machine.

View on HN

Thanks for sharing the benchmark :D Is there anything we could do to make Highway/vqsort (feel like) a lighter dependency?

I made that comment because the Intel library is header only. While header only libraries can be convenient, for non-trivial projects I prefer a well engineered CMake-based build for better compile times.

Got it. Highway is mostly header-only and we can move towards fully if anyone is interested.

We also have a CMake build, not sure about well-engineered but patches welcome from anyone with more CMake expertise :)

I think as long as FetchContent works it's super easy to try out your library and see if its something that should be pulled in as a real dependency.

I have heard that FetchContent can make something unreliable, as in dependent on having a connection, but I think it opens up the door for a lot of people to be willing to try it :) (That, and you can turn off mandatory updates, making it work offline too).

I think the basic rule for making FetchContent work is to just put the CMakeLists.txt in the root directory and then make sure that you can use the project as a CMake sub-project.

OK, I think we meet those criteria. JPEG XL can use Highway via add_subdirectory, assuming that is what you mean by sub-project.

Yes, exactly!

Interesting! The benchmark appears to be using only random data though. Any measurements for partially sorted or reverse sorted data?

Good question. I added a test for sorted runs in addition to random data, and added pdqsort for comparison.

avx512_qsort benefits from sorted runs while vqsort does not, but vqsort is still 20% faster in this case as well.

The full results are in the README, but a short version:

  --------------------------------------------------                                                                   
  Benchmark                            Time      CPU                                                                   
  --------------------------------------------------                                                                   
  TbbSort/random                     3.17 s  16.7  s                                                                   
  HwySort/random                     2.27 s   2.27 s                                                                   
  StdPartitionHwySort/random         2.06 s   4.01 s                                              
  PdqSort/random                     5.67 s   5.67 s                                              
  IntelX86SIMDSort/random            3.73 s   3.73 s                                              
  TbbSort/sorted_runs                1.58 s   8.02 s                                              
  HwySort/sorted_runs                2.38 s   2.38 s                                              
  StdPartitionHwySort/sorted_runs    1.11 s   3.21 s                                              
  PdqSort/sorted_runs                5.30 s   5.30 s                                                                   
  IntelX86SIMDSort/sorted_runs       2.90 s   2.90 s

Thanks for sharing. I've posted bench_sort results in another thread. vqsort is about 1.8 times as fast for uniform random, a bit more of an advantage than your results here.

Note that there appears to be some bug because our benchmark's verification fails.

(For completeness, the bug was only x86-simd-sort lacking support for reverse sort, which our benchmark tests for.)

Here's the vqsort discussion from the last time I saw it on this site: https://news.ycombinator.com/item?id=31622548

Reply on news.ycombinator.com