5 ms·
When compiling with GCC, the option `-fopt-info-vec-all` gives you information about the vectorization of the code. In this case, GCC reports // the for blo
by CodeArtisan 8y ago
When compiling with GCC, the option `-fopt-info-vec-all` gives you information about the vectorization of the code. In this case, GCC reports
// the for block
<source>:10:24: note: ===== analyze_loop_nest =====
<source>:10:24: note: === vect_analyze_loop_form ===
<source>:10:24: note: not vectorized: control flow in loop.
<source>:10:24: note: bad loop form.
<source>:5:6: note: vectorized 0 loops in function.
// the if block inside the for block
<source>:11:9: note: got vectype for stmt: _4 = *_3;
const vector(16) int
<source>:11:9: note: got vectype for stmt: _8 = *_7;
const vector(16) int
<source>:11:9: note: === vect_analyze_data_ref_accesses ===
<source>:11:9: note: not vectorized: no grouped stores in basic block.
<source>:11:9: note: ===vect_slp_analyze_bb===
<source>:11:9: note: ===vect_slp_analyze_bb===
<source>:11:9: note: === vect_analyze_data_refs ===
<source>:11:9: note: not vectorized: not enough data-refs in basic block.
edit: with intel compiler using `-qopt-report=5 -qopt-report-phase=vec -qopt-report-file=stdout`
Begin optimization report for: is_sorted(const int32_t *, size_t)
Report from: Vector optimizations [vec]
LOOP BEGIN at <source>(12,5)
remark #15324: loop was not vectorized: unsigned types for induction
variable and/or for lower/upper iteration bounds make
loop uncountable
LOOP END
- konschubert 8y agoAm I reading this right: GCC cannot vectorise because the loop terminates early in case of a non-sorted pair. It thereby contains control flow. I guess that's kind of logical. Even if the compiler recognised the early termination of the loop as the optimisation it is, it would still have to make the decision to give up on it in favour of vectorisation (?)
- justincormack 8y agoEven if you adjust it to not terminate early it finds other reasons (doesnt vectorise boolean operations).
- CJefferson 8y agoActually, this optimisation is illegal. I could line up memory such that it is illegal to read past the first location where the array is not sorted. The original code would be fine, the vectorised code would segfault. Similar annoying problems arise when people try to be clever with C strings, and read past the null. You can write optimisations which work, but they require care.
- ziedaniel1 8y agoActually, the illegal memory access would be undefined behavior, so it's fine for the compiler to assume that it's living in a world where the segfault never happens. Thus, it can optimize away the extra reads. If this weren't allowed, it would be very hard for compilers to eliminate any unnecessary reads. This sort of optimization reasoning can result in quite surprising behavior: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html?m=1 http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
- CJefferson 8y agoNo, not in this case. The original function is well defined and has no undefined behaviour (in the case I describe) as it would return before it reached "bad memory". The optimised version is what reaches further through memory (while vectorising).
- ziedaniel1 8y agoOh, good point, I didn't read what you wrote carefully enough.
- jjnoakes 8y agoI disagree. If I write a routine which walks an array one element at a time, in order, up to some max index N, and also stops early when it reaches some other condition (like an element equal to zero), then I am allowed to pass in memory which is only 3 elements long, and an N greater than 3, if I know that there is a zero in the first 3 elements. The function must not be optimized to read past the zero element, regardless of the N passed in, so removing the early exit would be an invalid optimization. There's no undefined behavior in the above that justifies that optimization.
- deleted 8y ago[deleted]
- stabbles 8y agoYou 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 8y agoThough this does throw away early-exit, which means it will be many times slower for unsorted cases.
- stabbles 8y agoTrue, I had hoped GCC would optimize that -- it doesn't :(.
- xamuel 8y 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 8y 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 8y ago[deleted]