3 ms·
> the most trivial example to demonstrate this is looping on a grid by column vs by row. The by-column iteration will be slower due to bad utilization of the CP
by rrss 5y ago
> the most trivial example to demonstrate this is looping on a grid by column vs by row. The by-column iteration will be slower due to bad utilization of the CPU cache, and no compiler will ever rearrange the loop
I think LLVM’s polyhedral optimization (Polly) probably will. I played with it a while back and found that if I handed it a naive matrix multiply with terrible locality, it was able to transform it to rearrange the iteration order and use tiling such that the naive w/ Polly ewas faster than any optimized version I could write. (my optimized versions probably weren’t great, but I tried the basics and got the normal speedups - Polly was just faster).
https://polly.llvm.org/ https://polly.llvm.org/
https://releases.llvm.org/12.0.1/tools/polly/docs/UsingPollyWithClang.html https://releases.llvm.org/12.0.1/tools/polly/docs/UsingPolly...
- hsn915 5y ago> matrix multiply probably one of the easy cases? I suppose the compiler must be able to somehow prove to itself that the code does not do anything else. What if, for example, within the loop you "printf(column)" or something like that? In this case re-arranging the loop would produce a different result, wouldn't it? So the compiler probably will not optimize it in that case, would it?