3 ms·

I don't understand why you are so insistent that the technology has been lost, e.g. it's been pointed out to you before that LLVM can do optimisations in this v

• Animats 11y ago
  That's for the easy case of iterating through an array sequentially. Of course, in languages with only 1D arrays, most of the hard cases don't come up. The classic is a matrix multiply, where you're progressing through one array on one axis and a second array on the other axis using the same index variable.
  • 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.