2 ms·
> It is obvious that c[i], b[k] and a[i][k] can be moved out of the inner loop to reduce the frequency of matrix access. [...] However, most other languages can
by lifthrasiir 3y ago
> It is obvious that c[i], b[k] and a[i][k] can be moved out of the inner loop to reduce the frequency of matrix access. [...] However, most other languages cannot optimize this nested loop. If we manually move a[i][k] to the loop above it, we can often improve their performance.
This is only true when three matrices are independent of each other, and also why C has a `restrict` qualifier that enables this assumption. The benchmark itself has no such assumption because all three variables are defined as `double **`, and it can be verified by assembly outputs. Clang's excellent performance in matmul is probably much more due to autovectorization.
- yxhuvud 3y agoIn some cases there are other reasons for hoiting the dereference too. For example, Crystal will check if the array access is out of bounds and by hoisting variables that will be done a lot less seldom, which can have huge effects for code that does a lot of that, like matmul.
- cm2187 3y agoDoesn’t that get mostly optimised away by the cpu branch prediction?
- beagle3 3y agoThe branch does, but you still have the comparison itself, and also the branch instruction to decide and skip (although thanks to branch prediction, your pipeline doesn’t get flushed). If you have enough idle execution units, you might not see a difference in wall clock time. But with many algorithms you can put those units to good use.
- yxhuvud 3y agoThe branch does, but not optimizations that could be done, like vectorization.