<div dir="ltr">I've run one proprietary benchmark that reflects a large portion of the google's server side code.<div>-fprofile-instr-generate leads to 14x slowdown due to counter contention. That's serious. <br>
</div><div>Admittedly, there is a single hot function that accounts for half of that slowdown, </div><div>but even if I rebuild that function w/o -fprofile-instr-generate, the slowdown remains above 5x.</div><div>This is not a toy code that I've written to prove my point -- this is real code one may want to profile with -fprofile-instr-generate.</div>
<div>We need another approach for threaded code. </div><div><br></div><div>There is another ungood feature of the current instrumentation. Consider this function: </div><div><div>std::vector<int> v(1000);</div><div>
void foo() { v[0] = 42; }<br></div></div><div><br></div><div>Here we have a single basic block and a call, but since the coverage is emitted by the </div><div>FE before inlining (and is also emitted for std::vector methods) we get this assembler at -O2:</div>
<div><div>0000000000400b90 <_Z3foov>:</div><div> 400b90: 48 ff 05 11 25 20 00 incq 0x202511(%rip) # 6030a8 <__llvm_profile_counters__Z3foov></div><div> 400b97: 48 ff 05 42 25 20 00 incq 0x202542(%rip) # 6030e0 <__llvm_profile_counters__ZNSt6vectorIiSaIiEEixEm></div>
<div> 400b9e: 48 8b 05 4b 26 20 00 mov 0x20264b(%rip),%rax # 6031f0 <v></div><div> 400ba5: c7 00 2a 00 00 00 movl $0x2a,(%rax)</div><div> 400bab: c3 retq </div>
</div><div><br></div><div>Suddenly, an innocent function that uses std::vector becomes a terrible point of contention.</div><div>Full test case below, -fprofile-instr-generate leads to 10x slowdown. </div><div><br></div>
<div>=========================</div><div>
<br></div><div>Now, here is a more detailed proposal of logarithmic self-cooling counter mentioned before. Please comment. </div><div>The counter is a number of the form (2^k-1). </div><div>It starts with 0.</div><div>After the first update it is 1.</div>
<div>After *approximately* 1 more update it becomes 3</div><div>After *approximately* 2 more updates it becomes 7<br></div><div>After *approximately* 4 more updates it becomes 15<br></div><div>...</div><div>After *approximately* 2^k more updates it becomes 2^(k+2)-1<br>
</div><div><br></div><div>The code would look like this:</div><div><div> if ((fast_thread_local_rand() & counter) == 0)</div><div> counter = 2 * counter + 1;</div></div><div><br></div><div>Possible implementation for fast_thread_local_rand: </div>
<div><div>long fast_thread_local_rand() {</div><div> static __thread long r;</div><div> return r++;</div><div>}</div></div><div>Although I would try to find something cheaper that this. (Ideas?)</div><div><br></div><div>
<br></div><div>The counter is not precise (well, the current racy counters are not precise either).</div><div>But statistically it should be no more than 2x away from the real counter. </div><div>Will this accuracy be enough for the major use cases? </div>
<div><br></div><div>Moreover, this approach allows to implement the counter increment using a callback: </div><div><div><div> if ((fast_thread_local_rand() & counter) == 0) __cov_increment(&counter);</div></div>
</div><div>which in turn will let us use the same hack as in AsanCoverage: use the PC to map the counter to the source code. </div><div>(= no need to create separate section in the objects).</div><div><br></div><div>Thoughts? </div>
<div><br></div><div>--kcc</div><div><br></div><div><br></div><div><div>% clang++ -O2 -lpthread coverage_mt_vec.cc && time ./a.out </div><div>TIME: real: 0.219; user: 0.430; system: 0.000</div><div>% clang++ -O2 -lpthread -fprofile-instr-generate coverage_mt_vec.cc && time ./a.out </div>
<div>TIME: real: 3.743; user: 7.280; system: 0.000</div><div><br></div><div>% cat coverage_mt_vec.cc</div></div><div><div>#include <pthread.h></div><div>#include <vector></div><div><br></div><div>std::vector<int> v(1000);</div>
<div><br></div><div>__attribute__((noinline)) void foo() { v[0] = 42; }</div><div> </div><div>void *Thread1(void *) {</div><div> for (int i = 0; i < 100000000; i++)</div><div> foo(); </div><div> return 0;</div><div>
} </div><div><br></div><div>__attribute__((noinline)) void bar() { v[999] = 66; }</div><div><br></div><div>void *Thread2(void *) {</div><div> for (int i = 0; i < 100000000; i++)</div><div> bar();</div><div> return 0;</div>
<div>} </div><div> </div><div>int main() {</div><div> static const int kNumThreads = 16;</div><div> pthread_t t[kNumThreads];</div><div> pthread_create(&t[0], 0, Thread1, 0);</div><div> pthread_create(&t[1], 0, Thread2, 0);</div>
<div> pthread_join(t[0], 0);</div><div> pthread_join(t[1], 0);</div><div> return 0;</div><div>}</div></div><div><br></div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Apr 18, 2014 at 11:45 PM, Xinliang David Li <span dir="ltr"><<a href="mailto:xinliangli@gmail.com" target="_blank">xinliangli@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"><br><div class="gmail_extra"><br><br><div class="gmail_quote"><div class="">On Fri, Apr 18, 2014 at 12:13 AM, Dmitry Vyukov <span dir="ltr"><<a href="mailto:dvyukov@google.com" target="_blank">dvyukov@google.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">Hi,<br><br>This is long thread, so I will combine several comments into single email.<div><br><br>
>> - 8-bit per-thread counters, dumping into central counters on overflow.<br></div><div>>The overflow will happen very quickly with 8bit counter.<br>
<br></div>Yes, but it reduces contention by 256x (a thread must execute at least 256 loop iterations between increments). In practice, if you reduce contention below some threshold, it does not represent a problem anymore.<div>
<br>
<br>
<br>>> - per-thread counters. Solves the problem at huge cost in RAM per-thread<br></div><div>>It is not practical. Especially for TLS counters -- it creates huge pressure on stack memory.<br><br></div>
Do we have any numbers about number of counters? If there are 100K 1-byte counters, I would consider it as practical.<div><br></div></div></blockquote><div><br></div></div><div>A medium sized app I looked at has about 10M counters (arcs only). It is also not uncommon to see such apps running with hundreds of threads.</div>
<div class="">
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><br></div><div><br>
<br><br>> In Google GCC, we implemented another technique which proves to be very effective -- it is called FDO sampling.<br>> Basically counters will be updated every N samples.<br><br></div>How does it work?</div>
</blockquote><div><br></div></div><div>Similar to how occurrences based PMU sampling work. Setting sampling period to 100 can reduce the instrumentation overhead by close to 100x without introducing much precision loss.</div>
<div>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class=""><div><br><br><br>
>> It seems to me like we’re going to have a hard time getting good multithreaded performance without significant impact on the single-threaded behavior.<br></div><div>> I don't really agree.<br><br>
</div></div><div><br><div class="">>We are talking about developers here. Nobody would know the exact thread counts, but developers know the ballpark number<br><br></div></div><div class="">I strongly believe that we must relief developers from this choice during build time, and do our best to auto-tune (if the final scheme requires tuning).<br>
</div></div></blockquote><div><br></div><div><br></div><div>That really depends. If the tuning space is small, it won't be a problem for the developer/builder. </div><div class=""><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">
First, such questions puts unnecessary burden on developers. We don't ask what register allocation algorithm to use for each function, right?<br></div></blockquote><div><br></div></div><div>Crazy developers can actually do that via internal options, but this is totally different case. People just needs one flag to turn on/off sharding. When sharding is on, compiler can pick the best 'N' according to some heuristics at compile time.</div>
<div class="">
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Second, there are significant chances we will get a wrong answer, because e.g. developer's view of how threaded is the app can differ from reality or from our classification.<br>
Third, the app can be build by a build engineer; or the procedure can be applied to a base with 10'000 apps; or threaded-ness can change; or the app can work in different modes; or the app can have different phases.<div>
<br></div></div></blockquote><div><br></div></div><div>We have forgotten to mention the benefit of implementation simplicity. If the static/simple solution solves the problem for most of the use cases, designing fancy dynamic solution sounds like over-engineering to me. It (overhead reduction technique) may also get in the way of easier functional enhancement in the future.</div>
<span class="HOEnZb"><font color="#888888">
<div><br></div><div> David</div></font></span></div><br></div></div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br></div>