janwas

33 ms·

1. 361.▲
   by janwas 4y ago

   :) If I'm reading 100Gb/sec correctly as Gigabits, a Skylake core can also reach such bandwidth usage. The issue is that the system can only sustain that for roughly 8 cores. It would be very interesting to see bench_parallel resu
2. 362.▲
   by janwas 4y ago

   SIMDe implements the exact semantics of a given ISA using either the native intrinsics, or other platform's intrinsics when possible, otherwise autovectorization. This is great when you've already written code using e.g. NEON intr
3. 363.▲
   by janwas 4y ago

   Actually we also support floating-point (32/64 bit, possibly even 16). I've previously also looked into radix sort: https://arxiv.org/abs/1008.2849 Radix sort may actually be faster if you know that only a fe
4. 364.▲
   by janwas 4y ago

   I'd recommend building using Bazel (perhaps via the bazelisk launcher), then it would be: bazel run -c opt :bench_sort (or :bench_parallel). Will verify that on Tue and put it in a README in contrib/sort.
5. 365.▲
   by janwas 4y ago

   Thanks :) If I understand correctly, you have tuples of (number, T*) and want to sort by number? That can be done by storing these tuples interleaved, reinterpret_casting to hwy::uint128_t (making sure that the pointer bits are in the least
6. 366.▲
   by janwas 4y ago

   Thanks for sharing the pointers. I hadn't come across that, will read soon :)
7. 367.▲
   by janwas 4y ago

   Also discussed here: https://news.ycombinator.com/item?id=31622548
8. 368.▲
   by janwas 4y ago

   Thanks :) I'd be interested to hear how it goes for you. Agree that 4x unrolling is getting most of the low-hanging fruit without excessive code size. I saw only very slightly better performance on SKX with 8x. You're right that i
9. 369.▲
   by janwas 4y ago

   Oh, thanks for pointing that out. Golly, Sandy Bridge is a bit old, yes - but still the result is surprising. djb reports 8000 cycles for int32 x 256 - this is much slower than we benchmark in bench_sort.cc, even for AVX2 (which he confirms
10. 370.▲
    by janwas 4y ago

    Ah, indeed, my mistake. FWIW I've observed increasing numbers of papers over the past couple of years mentioning entirely columnar databases.
11. 371.▲
    by janwas 4y ago

    hah, our paper actually cites "Radix sort for vector multiprocessors" by the same author, also from 1991 :)
12. 372.▲
    by janwas 4y ago

    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
13. 373.▲
    by janwas 4y ago

    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 o
14. 374.▲
    by janwas 4y ago

    Definitely, I have on my TODO to give turbostat a try.
15. 375.▲
    by janwas 4y ago

    :) 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
16. 376.▲
    by janwas 4y ago

    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
17. 377.▲
    by janwas 4y ago

    I don't know about "most", but here is a list: https://en.wikipedia.org/wiki/List_of_column-oriented_DBMSes
18. 378.▲
    by janwas 4y ago

    The CPU has a certain upper bound on power, TDP. That limit is independent of whether it is reached by executing scalar code on lots of cores, or SIMD on a few. One little-known fact is that out of order CPUs burn lots of energy just on sch
19. 379.▲
    by janwas 4y ago

    I agree AVX-512 is not exactly widespread on client CPUs but as akelly mentions, it does exist (e.g. Icelake). What we do is dispatch to the best available instruction set at runtime - that costs only an indirect branch, plus somewhat large
20. 380.▲
    by janwas 4y ago

    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 array
21. 381.▲
    by janwas 4y ago

    We also compare with state of the art platform-specific code. The interesting thing here is that they turn out to be slower than our approach using portable intrinsics (github.com/google/highway) :)
22. 382.▲
    by janwas 4y ago

    Interesting, I did not know that, thanks for the pointer. There is also an effort underway to update LLVM std::sort to BlockQuicksort, which can use some SIMD instructions similarly to what you describe.
23. 383.▲
    by janwas 4y ago

    :) FWIW we also use a constant-time sorting network as the base case of the Quicksort recursion, that's a widely used optimization.
24. 384.▲
    by janwas 4y ago

    Author here, happy to discuss.
25. 385.▲
    by janwas 4y ago

    What exactly should be cited? I had a quick look and djbsort seems to be a constant-time algorithm, presumably a sorting network. They report about 2 GB/s for 768 int32 on 3 GHz Skylake; IIRC our sorting network reaches 3-4 GB/s,
26. 386.▲
    by janwas 4y ago

    :) Are you thinking of ips4o (sample sort)? That's about 2-3x std::sort. There's also a pending patch to std::sort that replaces it with BlockQuicksort which would narrow that gap. We integrate vqsort into ips4o, calling it once s
27. 387.▲
    by janwas 4y ago

    Fair :) Sorting is useful in DB joins/group-by, though. (Author here, happy to discuss.)
28. 388.▲
    Vectorized and Performance-Portable Quicksort(opensource.googleblog.com)

    3 points by janwas 4y ago|0 comments
29. 389.▲
    by janwas 4y ago

    We mean energy, right? The surprising fact is that the energy cost of executing an instruction (scheduling etc.) is much higher than the actual operation. Thus SIMD amortizes that per-instruction overhead over multiple elements, leading to
30. 390.▲
    by janwas 4y ago

    Explicit vectors can be made portable (to SSE4/AVX2/AVX-512/NEON/SVE/SVE2/RISC-V V/WASM SIMD) using the Highway library which gives you wrapper functions over the platform's intrinsics, emulating miss