<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 8, 2015 at 12:55 AM, Chandler Carruth <span dir="ltr"><<a href="mailto:chandlerc@google.com" target="_blank">chandlerc@google.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"><div class="gmail_extra"><span><br><div class="gmail_quote">On Thu, Dec 18, 2014 at 2:16 PM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@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>Okay, so I've cast doubt on the use of standard deviation (and actually an argument could be made against the mean too for similar reasons). On a more constructive note, what *is* a good small set of parameters to summarize measurements of program run time? One interesting model that was brought to my attention by Nick Lewycky is based on the following observation: most "perturbations" of the run time of a fixed program binary on a fixed chip and fixed OS are due to externalities that contend for (or otherwise deprive the program of) execution resources and therefore almost always make it *slower*.</div><div><br></div><div>The model is then that there is a "true" execution time for the program, which is a completely deterministic function of the program, chip, and OS; intuitively, this is time occurs when the program is e.g. able to execute by itself, on a single execution unit of the CPU, with no interrupts knocking it off CPU, and no other threads using any of the execution resources of this CPU. On top of this, we assume that there is a set of perturbations that contend for execution resources and slow the program down.</div><div><br></div><div>For this model, it makes sense to approximate the "true" value by the maximum of the recorded values. If we want to use two numbers to summarize the data, it probably makes sense to look at a way of characterizing the extent of the variation from this "true" value. In the absence of proper characterization of the perturbations (such as the distribution of when they occur and how much effect they have when they occur), one simple solution is the minimum. Max and min might be *too* sensitive to the perturbations (especially disk cache of the program itself on the first run), so a pair of percentiles might be a bit more reliable, such as 10th percentile and 90th percentile.</div><div></div></blockquote></div><br></span>I used to subscribe to this thinking. I no longer do, and I think it has serious problems. Let me try to explain with a hopefully entertaining analogy. =D</div><div class="gmail_extra"><br></div><div class="gmail_extra">Back in physics class we would analyze the behavior of basic principles of physics as they would act upon a brave cadre of scientifically savvy penguins sliding down slopes under the effect of gravity. Naturally, these slopes were very slick ice, and the physics problems would be solved "neglecting friction"[1]. That made the analysis much more tractable and predictable. It also makes it really inaccurate in the real world.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Now, I'm not actually deriding this approach to physics. The results from neglecting friction are *very* informative as to the basic principles at work. In a very similar way, I don't think the model of a "true" execution time is very informative, but much more about the principles at work than about the actual performance of the software.</div></div></blockquote><div><br></div><div>Absolutely. One the one hand a good model is a useful predictor of reality when its assumptions are met. Conversely, looking at how reality deviates from the model helps you understand the thing which is causing a deviation from the model. The penguins will have a much easier time analyzing dirt slopes if they already understand gravity from the frictionless slopes.</div><div><br></div><div>Of course, it has to actually be a *good* model for this to apply. I don't know if what I described is a good model. However, it was the first model for program performance that I've seen that actually seemed to be based on a pretty sound idea: characterizing externalities as contending for (or otherwise depriving the program of) execution resources.</div><div> </div><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"><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">The reality I have observed these days, especially in larger software systems, is that there is inherently no deterministic and representative execution to rely on for finding "true" execution time. And too many of the random fluctuations are actually by-products of the program itself. Some examples:</div><div class="gmail_extra"><br></div><div class="gmail_extra">- If the program runs uninterrupted on a single core, it may cause that core to be throttled due to the thermals generated. This can have the effect of lowering the overall performance more than what you would see if the program ran *just* under that level without repeated drops in frequency.</div><div class="gmail_extra"><br></div><div class="gmail_extra">- Different optimizations can change the thermal profile by using different execution units. This is especially true for vector units.</div><div class="gmail_extra"><br></div><div class="gmail_extra">- If you fully leverage the AVX unit of some intel chips, my understanding is that regardless of the specific thermals, those units run at a lower clock!</div><div class="gmail_extra"><br></div><div class="gmail_extra">- Naturally, things like ASLR or other sources of correct but non-deterministic layout of data in memory will cause fluctuations in the rate at which cache misses occur. This is probably the most common cause of non-external fluctuations in performance. Different generated code, register spill frequencies, etc., can dramatically change these cache collision rates.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Now, with all of these factors, we have to assume that in real world scenarios, the programs will not always run at the maximal speed. Instead, there is, much as you describe in your email, some distribution of performance that will be observed in practice. The interesting question is -- can generating different code from the compiler shift the distribution in a meaningful way that is not correlated with the fastest measurement (or the N fastest measurement). And I think the above examples are all places where this can happen. =/</div><div class="gmail_extra"><br></div></div></blockquote><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"><div class="gmail_extra"></div><div class="gmail_extra">As a consequence, I am increasingly in favor of using very simple but aggregated statistics for measuring performance and acknowledging the lack of precision when it is present. We can still very often measure precisely those localized improvements provided by a specific change even when very small. We just won't see a reflection from them in many cases when measuring large systems that have a high noise floor. Hopefully, we can at least observe good trends in the large system to confirm we are making progress, and at times we can make large improvements that actually rise above the noise floor.</div></div></blockquote><div><br></div><div>If I'm understanding you correctly, you are emphasizing the need to be sure that the holistic system we ultimately care about improving is tracking the improvements we think we're making based on more localized measurements. I fully agree.</div><div><br></div><div>-- Sean Silva</div><div><br></div><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"><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Anyways, my somewhat rambling 2 cents on this. Sorry for the not entirely structured email. =]</div></div>
</blockquote></div><br></div></div>