<div dir="ltr"><span style="font-size:13px">Hi Matt,</span><div style="font-size:13px"><br></div><div style="font-size:13px">Thanks for the input. </div><div style="font-size:13px"><br></div><div style="font-size:13px">I ran the same program attached earlier "Loop.cpp" with -O3. Using shell script on terminal i ran it for 10000 times and redirected the data to a file.</div><div style="font-size:13px"><br></div><div style="font-size:13px">1. clang++ -O3 Loop.cpp</div><div style="font-size:13px">2. $ <span style="font-size:12.8000001907349px">for i in {1..10000}; do ./a.out >> qwerty; done</span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px">3. Sorted out the result in excel sheet.</span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px">I have also looked at the assembly generated, and agree to your point that there is not much difference in instructions.</span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px">However, in my opinion, and as some of the papers in links pasted in previous mail suggest, that this might open up opportunity for some other optimizations to come into picture. </span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px">For ex as shown earlier, </span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:13px"><div><span style="font-size:12.8000001907349px">do i = 1, n</span></div><div><span style="font-size:12.8000001907349px"> do j = 1, n </span></div><div><span style="font-size:12.8000001907349px"> a[i,j] = a[i-1,j+1] + 1</span></div><div><span style="font-size:12.8000001907349px"> end do</span></div><div><span style="font-size:12.8000001907349px">end do</span></div></div><div style="font-size:13px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px">for above example, we cannot interchange or parallelize inner loop because of (1, -1 ) dependency.</span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px">However, if we traverse the inner loop in reverse,</span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:13px">do i = 1, n</div><div style="font-size:13px"> do j = n, 1, -1</div><div style="font-size:13px"> a[i,j] = a[i-1,j+1] + 1</div><div style="font-size:13px"> end do</div><div style="font-size:13px">end do</div><div style="font-size:13px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px">the resultant dependency is (1, 1), which can now be used for inner loop parallelization or loop interchange (which might improve locality reference and result in less cache miss). Loop Interchange pass is already there in llvm trunk.</span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px">What are your thoughts on it - this pass creating opportunities for other passes to kick in? I might be wrong though.</span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:13px"><span style="font-size:12.8000001907349px">Awaiting for your valuable inputs.</span>(sorry for late reply because of difference in time zone)</div><div style="font-size:13px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:13px"><div style="color:rgb(80,0,80)">Regards,</div><div style="color:rgb(80,0,80)">Vishal Sarda,</div><div style="color:rgb(80,0,80)">3rd Year Undergraduate,</div><div style="color:rgb(80,0,80)">Department of Computer Engineering,</div><div style="color:rgb(80,0,80)">College of Engineering, Pune</div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Mar 18, 2015 at 11:14 PM, Matt Godbolt <span dir="ltr"><<a href="mailto:matt@godbolt.org" target="_blank">matt@godbolt.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Vishal,<div><br></div><div>I am still a little confused - can you share your new code? Be aware that you're relying on undefined behaviour: the "unisgned int" you are adding to is overflowing, and clang will use this fact.</div><div><br></div><div>I was able to replicate your initial results but I found that if I ran the counting code twice, the second time both types of loop took much the same time:</div><div><br></div><div><div>$ make; and ./loop </div><div>make: Nothing to be done for `all'.</div><div>First run:</div><div>0:834</div><div>0:405</div><div>Second run:</div><div>0:381</div><div>0:384</div></div><div><br></div><div>(on a 3.5GHz Haswell).</div><div><br></div><div>I hacked together a very simplistic version using a memory barrier to defeat the optimizer instead of adding (which means the loop actually gets compiled: <a href="http://url.godbolt.org/hqwkx" target="_blank">http://url.godbolt.org/hqwkx</a> ). Additionally, I used the CPU cycle counter on x86 (again, very simplistically, there's a huge art to this: I can share other resources if you're interested). Counting to 2.4 billion takes an appreciable amount of time now :)</div><div><br></div><div>The results from that:</div><div><br></div><div><div>/t/lop $ make; and ./loop2</div><div>First run:</div><div>Counting up: 2528555165 cycles</div><div>Counting down: 2524361064 cycles</div><div>Second run:</div><div>Counting up: 2495025808 cycles</div><div>Counting down: 2511668857 cycles</div></div><div><br></div><div>Source and makefile attached.</div><div><br></div><div>If you look at the code clang is producing in both cases (see the URL) it has already transformed the code into effectively the same: adding and/or subtracting until hitting zero. At least in this case, where the loop counter value itself isn't used.</div><div><br></div><div>Sorry I haven't added much to the discussion, but hopefully this email is useful in gauging the relevance of the feature.</div><div><br></div><div>Best regards, Matt</div><div><br></div></div><div class="gmail_extra"><div><div class="h5"><br><div class="gmail_quote">On Wed, Mar 18, 2015 at 10:33 AM, vishal sarda <span dir="ltr"><<a href="mailto:vishalksarda@gmail.com" target="_blank">vishalksarda@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><span style="font-size:13px">Hi Matt, All, </span><div style="font-size:13px"><br></div><div style="font-size:13px">Thanks for looking into this and your suggestions.</div><div style="font-size:13px"><br></div><div style="font-size:13px">I compiled the program with -O3 optimization level (clang -O3) on X86_64 target.</div><div style="font-size:13px">After your suggestion, i ran the program with iteration of 10000 runs and found that average runtimes are (attaching data collected as well)</div><div style="font-size:13px"><br></div><div style="font-size:13px">Forward loop traverse : 2.006 milli seconds</div><div style="font-size:13px">Reverse loop traverse : 1.531 milli seconds</div><div style="font-size:13px"><br></div><div style="font-size:13px">Yes, i agree that this sample program may not be sufficient to say that loop reversal traversing will always be faster, however, difference in runtime is visible though. And that's where the profitability calculation comes into picture. </div><div style="font-size:13px"><br></div><div style="font-size:13px">I found mention of loop traverse in various papers (links mentioned in previous mail), and hence thought of implementing it.</div><div style="font-size:13px"><br></div><div style="font-size:13px">I am not sure though if its really helpful. Above papers mentioned that it might not be beneficial in itself, but opens up the opportunity for other optimizations.</div><div style="font-size:13px"><br></div><div style="font-size:13px">Suggestions on this are most welcomed. Waiting for others to pitch in too.</div><span><div style="font-size:13px"><br></div><div style="font-size:13px">Regards,</div><div style="font-size:13px">Vishal Sarda,</div><div style="font-size:13px">3rd Year Undergraduate,</div><div style="font-size:13px">Department of Computer Engineering,</div><div style="font-size:13px">College of Engineering, Pune</div></span></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Mar 18, 2015 at 1:20 AM, Matt Godbolt <span dir="ltr"><<a href="mailto:matt@godbolt.org" target="_blank">matt@godbolt.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi,<br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Mar 17, 2015 at 2:00 PM, vishal sarda <span dir="ltr"><<a href="mailto:vishalksarda@gmail.com" target="_blank">vishalksarda@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">
<p style="margin-bottom:0.35cm;line-height:115%">[snip]</p><span>
<p style="margin-bottom:0.35cm;line-height:115%">Loop counting up
0.15 ms</p>
<p style="margin-bottom:0.35cm;line-height:115%">Loop counting
down 0.08 ms</p></span></div></blockquote><div>I'm no llvm expert, but as an interest bystander: I suspect you compiled the source without any optimizations applied - I tried to replicate this behaviour and found the optimzer happily replaces both the inner loops you had with a constant, and thus I got the same time on both loops. (e.g. see <a href="http://goo.gl/aXFkVb" target="_blank">http://goo.gl/aXFkVb</a> ) </div><div><br></div><div>Benchmarks of this nature where the run time is so small are notoriously prone to measurement errors, so I'd be a little careful drawing conclusions from the sample you listed. Also; what architecture did you measure on, and what spec machine?</div><div><br></div><div>Not at all to dissuade you from investigating this optimization! I'm just a little sceptical of the benchmark you posted!</div><div><br></div><div>Best regards, </div><span><font color="#888888"><div><br></div><div>Matt</div><div><br></div></font></span></div>
</div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br><br clear="all"><div><br></div></div></div><span class="HOEnZb"><font color="#888888">-- <br><div>Matt</div>
</font></span></div>
</blockquote></div><br></div>