5 ms·
You can get automatic vectorization (with -O3) like this: bool is_sorted(const int32_t* input, size_t n) { int32_t sorted = true; for (size_t
by stabbles 9y ago
You can get automatic vectorization (with -O3) like this:
bool is_sorted(const int32_t* input, size_t n) {
int32_t sorted = true;
for (size_t i = 1; i < n; ++i) {
sorted &= input[i - 1] <= input[i];
}
return sorted;
}
And the performance is similar to the AVX version (benchmarked on a MacBook Air early 2015):
$ ./benchmark_avx2 1048576
input size 1048576, iterations 10
scalar : 6379 us
SSE (generic) : 3544 us
SSE : 3704 us
My example : 2769 us
AVX2 (generic) : 2679 us
AVX2 : 3360 us
So I'm getting 2769us with the above 5 simple lines of code. It's just 3% slower (that might be noise).
- Veedrac 9y agoThough this does throw away early-exit, which means it will be many times slower for unsorted cases.
- stabbles 9y agoTrue, I had hoped GCC would optimize that -- it doesn't :(.
- xamuel 9y agoIt would make no sense for GCC to automatically add early-exit: that requires a judgement call about the vectors the function is intended to run on. A priori, the function might be intended to run on vectors that are almost always sorted, in which case the extra branch would be severely suboptimal.
- banachtarski 9y agoI agree that the optimization isn't possible but this is for correctness reasons. The performance penalty of the extra branch is almost negligible due to branch prediction.
- deleted 9y ago[deleted]
- reza_n 9y agoMaybe have a parent function which passes in the array as 4k chunks/offsets and checks the return? 4k is a random size, there is probably a value which hits the sweet spot here.
- stochastic_monk 9y agoWhich compiler?
- stabbles 9y agoOnly tried GCC on Godbolt
- deleted 9y ago[deleted]