<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Thank you for sharing the data. I haven't been following the
discussion, but this data made for very interesting reading on it's
own. <br>
<br>
Philip<br>
<br>
<div class="moz-cite-prefix">On 08/19/2015 03:39 PM, Rong Xu via
llvm-dev wrote:<br>
</div>
<blockquote
cite="mid:CAF1bQ=S559FToXv97bdr=FCupwkng2igf8kv0yGoUZ7ubBfTKA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>We collected more data to address some of the questions
from the reviewers. Note this time we use clang itself as the
benchmark. We choose clang because we think it's a typical C++
program and the reviewers here have good knowledge of the code
base.</div>
<div><br>
</div>
<div>What we measure is running time for clang to compile a
large preprocessed source file (4.98M lines of .ii file),
using different compilation modes. All the numbers reported
here are the average running time of 5 runs in seconds.</div>
<div><br>
</div>
<div><b>(1) Performance b/w late instrumentation v.s. not
instrumenting single BB functions</b></div>
<div><br>
</div>
<div>We first compare various instrumentation performance.</div>
<div><font face="monospace, monospace">----------------------------------------------------------------------------</font></div>
<div><font face="monospace, monospace"> Config
wall_time_for_instr ratio_vs_base profile_size</font></div>
<div><font face="monospace, monospace">(1) base O2
80.386 100.0% --</font></div>
<div><font face="monospace, monospace">(2) FE-based Instr
201.658 250.8% 65238880</font></div>
<div><font face="monospace, monospace">(3) late Instr
103.662 129.0% 14860144</font></div>
<div><font face="monospace, monospace">(4) (3) + w/o pre-inline
199.924 248.7% 70762720</font></div>
<div><font face="monospace, monospace">(5) (4) + Silva
119.904 149.2% 24499528</font></div>
<div><br>
</div>
<div>Config(5) used the simple heuristic that Sean Silva
proposed: not instrumenting single BB functions that contain
less than 10 instructions (excluding debug and phi stmts).</div>
<div><br>
</div>
<div>We can see:</div>
<div>1) Simple heuristic of not instrumenting small single BB
functions improves instrumentation performance as expected.</div>
<div>2) Using simple heuristic is still slower than late
instrumentation with pre-inlining: the later is 15% faster.</div>
<div>3) Late instrumentation produces the smallest profile size:
it's 39% smaller than using the simple heuristic.</div>
<div><br>
</div>
<div>The result is expected as pre-inlining can handle more
cases than the simple heuristic. There is significant
performance gap between the simple heuristic (5) and late
instrumentation (2).</div>
<div><br>
</div>
<div>We also used a few larger internal benchmarks to further
validate the above result. The following table shows the
slowdown compared to the base O2. The labels (2) to (5) refer
to the same config as in the previous table.</div>
<div><font face="monospace, monospace">------------------------------------------------------</font></div>
<div><font face="monospace, monospace">Program
(2) (3) (4) (5)</font></div>
<div><font face="monospace, monospace">C++benchmark16
-45.24% -12.93% -43.84% -24.74%</font></div>
<div><font face="monospace, monospace">C++benchmark17
-90.86% -58.19% -87.77% -80.62%</font></div>
<div><font face="monospace, monospace">C++benchmark18
-95.32% -54.75% -91.21% -82.56%</font></div>
<div><br>
</div>
<div><br>
</div>
<div>We can see the same trend as the clang benchmark: the
simple heuristic (5) recovers a lot of performance loss
compared with FE base instrumentation, but is still
significantly worse than late instrumentation (3).</div>
<div><br>
</div>
<div><b>(2) Performance impact of context sensitivity</b></div>
<div><br>
</div>
<div>LLVM does not use the profile information fully in the
back-end optimizations, for instance, inlining does not fully
use the profile counts -- it only marks hot/cold function
attribute based on function entry counts. To evaluate the
impact of profile context sensitivity, GCC is used in the
experiment. Note that GCC PGO improves clang performance a lot
more than clang PGO.</div>
<div><br>
</div>
<div>First we summarize the methodology used in the experiment:</div>
<div>0) build clang with GCC O2 without early inlining and
measure clang's performance. GCC early inlining (einline) is
similar to pre-inline used by late instrumentation.<br>
</div>
<div>1) build clang with GCC O2 with early inlining and measure
performance.</div>
<div><br>
</div>
<div>The performance difference of 1) and 0) is denoted as E
which measures the contribution of early inlining.</div>
<div><br>
</div>
<div>2) build clang with GCC O2 + PGO without early inlining.</div>
<div>3) build clang with GCC O2 + PGO with early inlining.</div>
<div><br>
</div>
<div>The performance difference of 3) and 2) is denoted as EC.
It constitutes roughly two parts a) early inlining
contribution b) context sensitive profiling enabled with early
inlining.</div>
<div><br>
</div>
<div>The contribution of context sensitive profiling can be
estimated by EC - E above.</div>
<div><font face="monospace, monospace">-------------------------------------------------------------------------------</font></div>
<div><font face="monospace, monospace">Config
wall_time_for_use speedup_vs_(0) speedup_vs_(1)</font></div>
<div><font face="monospace, monospace">(0) base w/o einline
84.946 1.000 0.934</font></div>
<div><font face="monospace, monospace">(1) base O2
79.310 1.071 1.000</font></div>
<div><font face="monospace, monospace">(2) profile-arcs w/o
einline 63.518 1.337 1.249</font></div>
<div><font face="monospace, monospace">(3) profile-arcs
48.364 1.756 1.640</font></div>
<div><br>
</div>
<div>We see the following:</div>
<div>1) GCC PGO with early inlining improves clang performance
by 64.0% (v.s. base O2 w/ early inline).</div>
<div>2) GCC PGO w/o early inlining improves clang performance by
33.7% (v.s. base O2 w/o early inline).</div>
<div>3) Early inlining performance contribution is about 7.1%.</div>
<div>4) Profile context sensitivity contribution is estimated to
be 22.2% (i.e. 64.0% -33.7% - 7.1%), which is pretty
significant.</div>
<div><br>
</div>
<div><b>(3) Pre-inline pass impact on the value profiling</b></div>
<div><br>
</div>
<div>Again, we use GCC as the platform to estimate:</div>
<div><br>
</div>
<div><font face="monospace, monospace">--------------------------------------------------------</font></div>
<div><font face="monospace, monospace"> Config
wall_time for_instr</font></div>
<div><font face="monospace, monospace">(2) profile-arcs
115.720</font></div>
<div><font face="monospace, monospace">(3) profile-arcs w/o
einline 310.560</font></div>
<div><font face="monospace, monospace">(4) profile-generate
139.952</font></div>
<div><font face="monospace, monospace">(5) profile-generate w/o
einline 680.910</font></div>
<div><br>
</div>
<div>In GCC, -fprofile-generate does -fprofile-arcs as well as
the value profiling. The above table shows that with value
profile, the impact of pre-inlining is even larger for
instrumented binary performance. Without value profiling,
disabling pre-inlining increases runtime by 1.7x, while with
value profiling, its impact is 3.9x increase in runtime.</div>
<div><br>
</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Tue, Aug 11, 2015 at 10:11 PM, Sean
Silva via llvm-dev <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.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"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote"><span class="">On Tue, Aug 11,
2015 at 11:07 AM, Diego Novillo via llvm-dev <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org"
target="_blank">llvm-dev@lists.llvm.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">
<div class="gmail_extra">One aspect of this that
I have not seen discussed is that middle-end
instrumentation enables PGO optimizations to
front-ends other than Clang.</div>
<div class="gmail_extra"><br>
</div>
<div class="gmail_extra">While I agree that FE
instrumentation could be improved, it still
requires every FE to implement essentially the
same common functionality. Having PGO
instrumentation generated in the middle-end,
allows us every FE to automatically take
advantage of PGO.</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>This is a really good point, and I agree with it.
We may have gotten off on the wrong foot since
Rong's email focused so heavily on comparing with
the frontend instrumentation. As far as I see it,
Rong's proposal has a couple different parts:</div>
<div><br>
</div>
<div>1. Infrastructure for IR-level
instrumentation-based PGO</div>
<div>2. Changes to the pass pipeline so that a
hypothetical IR-level instrumentation-based PGO is
more effective</div>
<div>3. MST algorithm with profile feedback for
optimal placement of counter updates.</div>
<div><br>
</div>
<div>I think 1. is a no-brainer, if only so that all
LLVM clients can benefit from PGO, and also (as you
pointed out below) so that it can have an exclusive
focus on performance. If it is sufficiently
flexible, it may even make sense to restrict clang's
frontend instrumentation-based profiling to
non-performance stuff, and have clang directly
interoperate with the IR-level PGO for
performance-related PGO use cases, just like any
other frontend would.</div>
<div><br>
</div>
<div>Philip and Sanjoy, out of curiosity do you guys
use your own instrumentation placement for PGO? Is
an IR-level PGO infrastructure upstream something
you guys would be interested in?</div>
<div><br>
</div>
<div>I think that 2. is something that once we have 1.
we will be able to evaluate better, but for now my
opinion is that we should be able to make good
progress without digging into that.</div>
<div><br>
</div>
<div>I think that 3. is a no-brainer if it provides a
really significant win, but without 1. we can't
really measure its effect in isolation. It also has
a usability problem since it requires feeding in an
existing profile for the *instrumented* build, but
if the benefit is very significant this may be worth
it for some users. We will probably be able to
easily refactor 1. as needed into an MST approach
that degrades gracefully to using static heuristics
in the absence of real profile information, so is
not a maintenance burden (maybe even helps by
providing a good framework in which to develop
effective static heuristics).</div>
<div><br>
</div>
<div>For the time being, I think we can avoid
discussion of 2. and 3. until we have more of 1.
working. So I think it would be most productive if
we focus this discussion on 1.</div>
<span class="">
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">
<div class="gmail_extra"><br>
</div>
<div class="gmail_extra">Additionally, some of
the overhead imposed by FE instrumentation is
not really all that easy to get rid of. You
end up duplicating functionality that is more
naturally implemented in the middle end.</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>Yeah, I was looking into a couple of other simple
approaches and quickly found out that I was
basically replicating much of the sort of logic that
the inliner already has.</div>
<div><br>
</div>
<div>-- Sean Silva</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex"><span
class="">
<div dir="ltr">
<div class="gmail_extra"><br>
</div>
<div class="gmail_extra">I see the two
approaches as supplementary, rather than
complementary. One does not negate the
other. Some of the optimizations we'd do in
the FE, may hurt coverage. Instead, by
instrumenting in the middle end, you can focus
exclusively on performance (coverage be
damned).</div>
<div class="gmail_extra"><br>
</div>
<div class="gmail_extra"><br>
</div>
<div class="gmail_extra">Diego.</div>
</div>
<br>
</span><span class="">_______________________________________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org"
target="_blank">llvm-dev@lists.llvm.org</a>
<a moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu" rel="noreferrer"
target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a moz-do-not-send="true"
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
<br>
</span></blockquote>
</div>
<br>
</div>
</div>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu" rel="noreferrer"
target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a moz-do-not-send="true"
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
<br>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</body>
</html>