<div dir="ltr"><div>I generally agree with your whole answer and I shouldn't have posted the video's code verbatim because it probably threw anyone reading it off (i.e. focus on the outer loop while for me the main issue is the inner loop, even if we remove the outer).</div><div>Because yes, in practice only the inner loop will exist, and that doesn't have a difference of 4x (not nearly). Still though, IMHO opinion,</div><div>the codegen even for only the inner is bad (and I'm not sure too why that happens but, like you, I guess that it's because the stores dominate the loads, so LLVM's unneeded loads don't matter that much).</div><div><br></div><div>That said, I'm with you on this:</div><div><br></div><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Personally I try to take a look at the bright side: more potential for further optimizations! I also don’t think there’s some fundamental transformations missing here. It appears the main issue is the llvm.memcpy calls, which means we have to go through memory in the main loop instead of hoisting the invariant ‘load’ part out of the loop (in the original, un-interchanged version).<br>As for LLVM not removing the redundant loop after interchanging: this is indeed surprising, but again is likely caused by the memcpys, which loop invariant code motion does currently not hoist out in that case. However adding support for that should be relatively straight forward. If corresponding load/store pairs are used instead of the memcpy, LLVM should also eliminate the loop as well.</blockquote></div><div><br></div><div>Also:</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">But going back to my original point, I’d said that if the goal is to compare the performance of the generated code to initialize a large array of matrixes, the most interesting comparison would be comparing GCC & Clang with interchanging disabled for GCC.</blockquote><div><br></div><div>It wouldn't be fair :p But yes it's interesting: <a href="https://godbolt.org/z/5on8MM">https://godbolt.org/z/5on8MM</a> (GCC does a good job).</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">(Also there appears to be a phase-ordering issue in GCC, because the `run` loop is not removed when automatically interchanged)</blockquote><div><br></div><div>True. Btw, I think that the outer loop should be removed either the interchange happens or not (MSVC removes it in the original code completely, although I don't know if an interchange happened first down the pipeline).</div><div><br></div><div>Best,</div><div>Stefanos</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Παρ, 2 Οκτ 2020 στις 12:27 μ.μ., ο/η Florian Hahn <<a href="mailto:florian_hahn@apple.com">florian_hahn@apple.com</a>> έγραψε:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><br><div><br><blockquote type="cite"><div>On Oct 1, 2020, at 23:16, Stefanos Baziotis <<a href="mailto:stefanos.baziotis@gmail.com" target="_blank">stefanos.baziotis@gmail.com</a>> wrote:</div><div><div dir="ltr"><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">While the code for the initialization is not ideal, it appears the main issue causing the slowdown is the fact that GCC interchanges the main loops, but LLVM does not. After interchanging, the memory access patterns are completely different</blockquote><div><br>Well, definitely that's one thing and without interchange cache locality plays a big role but I think two things should be noted:<br>1) GCC, even though it interchanges the original code, still runs 25 iterations, so it still kind of does the benchmark.</div></div></div></blockquote><div><br></div>Agreed, the benchmark does exactly the same computation, just in a different order.</div><div><br></div><div>I didn’t write the benchmark so I can only assume what it is intended to benchmark. From the title of the email and the code, it seems the goal is to benchmark the performance of initializing a large array of matrixes and the outer `run` loop has been added to make sure the benchmark runs a sufficiently large number of times to get more stable timings.</div><div><br></div><div>With that assumption in mind, I don’t think the benchmark really measures the same thing after interchanging. In other words, say interchanging gives a 4x speedup on the benchmark, but that is unlikely to translate into practice for loops that just initialize matrixes with constants without the artificial ’no-op’ outer loop. Granted, it is easy to come up with code where interchanging is highly beneficial for the interesting parts of the computation.</div><div><br></div><div><blockquote type="cite"><div><div dir="ltr"><div>2) Most importantly, even if we interchange the code ourselves, Clang's codegen is still very bad both compared to GCC and in general. Also, GCC does the obvious thing of completely removing the inner loop (now that with IV `run`), while</div><div>Clang doesn't. Basically, these are problems that I feel loop optimizations should not suffer from at this point :/<br></div></div></div></blockquote></div><br><div>Personally I try to take a look at the bright side: more potential for further optimizations! I also don’t think there’s some fundamental transformations missing here. It appears the main issue is the llvm.memcpy calls, which means we have to go through memory in the main loop instead of hoisting the invariant ‘load’ part out of the loop (in the original, un-interchanged version).</div><div><br></div><div>As for LLVM not removing the redundant loop after interchanging: this is indeed surprising, but again is likely caused by the memcpys, which loop invariant code motion does currently not hoist out in that case. However adding support for that should be relatively straight forward. If corresponding load/store pairs are used instead of the memcpy, LLVM should also eliminate the loop as well.</div><div><br></div><div>And with load/stores instead of memcpy, LLVM’s loop interchange pass should also be able to interchange the loops (it’s disabled by default though).</div><div><br></div><div><blockquote type="cite"><div dir="ltr">Oh also another thing that's important:<br><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">on top of manually interchanging the loops, which gives a ~3x speedup).</blockquote><div><br></div><div>Indeed in my machine too. Although I understand that this speedup is not the important thing here, it has to be noted what<br>GCC does with them interchanged:<br><br>Clang:<br>- Original: 2.04<br>- Interchanged: 0.60<br><br>G++:<br>- Original: 0.43<br>- Interchanged: 0.15<br><br>So, GCC gets a 3x speedup too and also the interchanged version of GCC is still 4x faster.</div></div></blockquote><br></div><div>Right, but as you indicated earlier, if you manually interchange the loops first, GCC will completely remove the `run` loop while LLVM does not currently, so we are now even further removed from benchmarking the performance of the matrix array initialization code. The example certainly doesn’t make LLVM look great compared to GCC. (Also there appears to be a phase-ordering issue in GCC, because the `run` loop is not removed when automatically interchanged).</div><div><br></div><div>But going back to my original point, I’d said that if the goal is to compare the performance of the generated code to initialize a large array of matrixes, the most interesting comparison would be comparing GCC & Clang with interchanging disabled for GCC.</div><div><br></div><div>On my system, the runtime difference of the un-interchanged versions generated by Clang with and without SROA are in the noise, which is not too surprising I think, because it will be dominated by the memory writes and that hides the other smaller codegen differences. On different processors, e.g. smaller in-order ones, the difference will be more visible.</div><div><br></div><div>To summarize, I think the benchmark is very interesting and highlights some important issues with how different optimizations deal with llvm.memcpy and how SROA decides to use memcpy, which would be good to address. Will those changes make loops that initialize large arrays with constant matrixes 2x or 4x faster in practice? I doubt it.</div><div><br></div><div>Cheers,</div><div>Florian</div></div></blockquote></div>