4 ms·
Why won't that optimisation handle such a case? It's still fundamentally the same "shape" of iteration: some_operation(x[i,j], y[j,i]) has checks essential
by dbaupp 11y ago
Why won't that optimisation handle such a case?
It's still fundamentally the same "shape" of iteration:
some_operation(x[i,j], y[j,i])
has checks essentially looking like:
if (i < min(x.n, y.m) && j < min(x.m, y.n)) {
// do things
} else {
out_of_bounds()
}
and moving each of those outside their respective loops should work with IRCE-style optimisations.
E.g. -O3 with clang 3.5.0 and gcc 4.9.2 leave only one comparison (out of 4) in the inner loop the following implementation of transpose (I've tried to make it mirror what the "obvious" implementation in a high-level language would do, i.e. bounds check accesses to y and then separately bounds check them to x, but the precise details don't seem to make much difference):
#include<stdlib.h>
void transpose(float * restrict x, size_t xn, size_t xm,
const float * restrict y, size_t yn, size_t ym) {
size_t i, j;
if (xn != ym || xm != yn) {
abort();
}
for (i = 0; i < yn; i++) {
for (j = 0; j < ym; j++) {
float tmp;
if (i < yn && j < ym) {
tmp = y[ym * i + j];
} else {
abort();
}
if (i < xm && j < xn) {
x[xm * j + i] = tmp;
} else {
abort();
}
}
}
}
And, if I use clang 3.7 and run the LLVM output through `opt-3.7 -irce -O3` (since IRCE isn't enabled in clang by default), then the inner loop has no bounds checks and is even unrolled once:
.LBB0_7:
movl -4(%r9), %ebx
movl (%r9), %r10d
movl %ebx, (%rcx)
movl %r10d, (%r13,%rcx)
addq %r11, %rcx
addq $8, %r9
addq $-2, %rdi
jne .LBB0_7
In any case, naive code in this manner is not a good way to write high-performance code for modern CPUs: iterating with large strides (i.e. b > 1, per the article's notation) is a bad memory access pattern for caches, and optimising memory accesses has a much larger impact than bounds checking. Point is: it's a bit of a strawman to talk about performance with such an example since these naive algorithms just aren't good enough if performance matters.