libCat VS highway

That's awesome! I'm working on something that sounds similar. https://github.com/cons-cat/libcat

I'd love to see your work if you're willing to share it here!

It's worse in the standard library than it has to be. When I refactored my traits to minimize template instantiations and lean on concepts as much as possible, I measured over 30% improvement to clean build compile times. It's not possible for the standard to do this, because it would subtly change the API. For instance, you can't instantiate or take the address of a concept, but you can for a type-trait class. No reason you'd want to do that, but you can, so they can't "break" the standard library by optimizing this.

This doesn't have to be true. Over the past year I've made progress towards demonstrating how even non-freestanding C++ can be written without any C or C++ standard library headers or DLLs (with large benefits). There are a few names which the compilers require to be in the std:: namespace, though, but they're very special features like source_location and construct_at with semantics that can't be expressed otherwise.

It isn't that hard to put a predicate into a type. We have lambdas in an unevaluated context, CTAD, and templated type aliases. https://github.com/Cons-Cat/libCat/blob/main/src/libraries/scaredy/cat/scaredy https://github.com/Cons-Cat/libCat/blob/main/src/global_includes.hpp#L70 https://github.com/Cons-Cat/libCat/blob/main/src/libraries/linux/cat/linux#L289 You do it like this.

I use clang-tidy. These are my current linting rules.

I'm working on this! https://github.com/Cons-Cat/LibCat

Disclosure: I am the main author; happy to discuss.

0: https://github.com/google/highway/blob/master/hwy/contrib/so...

If all you care about is integers I recommend taking a look at vqsort, it can even be parallelized with ips4o as seen in the whitepaper.

Implementing Arm semantics or x86 on the other requires ~5 instructions, but if we generalize the definition to allow reordering (e.g. Highway's ReorderWidenMulAccumulate [1]), it's only 2 instructions.

1: https://github.com/google/highway/blob/master/g3doc/quick_re...

Also, are you familiar with https://github.com/google/highway? That gives you portable intrinsics so you can write your code only once (but still specialize per arch if it's helpful). Disclosure: I am the main author of this library.

Nice. Would you like to add our vqsort to your benchmark? (Note: we haven't yet implemented a workaround specifically for AMD's compressstoreu, but do not use it for 64 nor 128-bit keys.)

Benchmark results using vqsort's bench_sort on Skylake workstation (patch: https://github.com/google/highway/pull/1140)

vqsort is about 1.9x and 1.8x as fast on 1M keys and 100M uniform random keys, respectively.

Note that this code did not pass the benchmark's verification.

      AVX3:           vq:     i32: uniform32: 1.00E+06 1051 MB/s ( 1 threads)

It would be interesting to see it benchmarked against the highway qsort[1] Google published last year.

[1] https://github.com/google/highway/tree/master/hwy/contrib/so...

sagarm has posted one result in another thread. I'll also look into adding their code to our benchmark :)

It's great to see more vector code, but caveat for anyone using this: the pivot sampling is quite basic, just median of 16 evenly spaced samples. This is will perform poorly on skewed distributions including all-equal and very few unique values. Yes, in the worst case it can resort to std::sort but that's a >10x speed hit and until recently also potentially O(N^2)!.

We have drawn larger samples (nine vectors, not one), and subsequently extended the vqsort algorithm beyond what is described in our paper, e.g. special handling for 1..3 unique keys, see https://github.com/google/highway/blob/master/hwy/contrib/so....

I didn't try it but google's highway supposed to do this with `HWY_DYNAMIC_DISPATCH`.

Google Highway "Performance-portable, length-agnostic SIMD with runtime dispatch" from last october