[LLVMdev] Postponing more passes in LTO

[Sean Silva]

In the future could you please do some sort of visualization of your data,
or at least provide the raw data in a machine-readable format so that
others can do so?

It is incredibly easy to come to incorrect conclusions when looking at
lists of numbers because at any given moment you have a very localized view
of the dataset and are prone to locally pattern-match and form a selection
bias that corrupts your ability to make a proper decision in the context of
the entire dataset. Even if you go on to look at the rest of the data, this
selection bias limits your ability to come to a correct "global" conclusion.

Appropriate reliable summary statistics can also help, but are not panacea.
In using, say, 2 summary statistics (e.g. mean and standard deviation), one
is discarding a large number of degrees of freedom from the dataset. This
is fine if you have good reason to believe that these 2 degrees of freedom
adequately explain the underlying dataset (e.g. there is a sound
theoretical description of the phenomenon being measured that suggests it
should follow a Gaussian distribution; hence mean and stddev completely
characterize the distribution). However, in the world of programs and
compiler optimizations, there is very rarely a good reason to believe that
any particular dataset (e.g. benchmark results for SPEC for a particular
optimization) is explained by a handful of common summary statistics, and
so looking only at summary statistics can often conceal important insights
into the data (or even be actively misleading). This is especially true
when looking across different programs (I die a little inside every time I
see someone cite a SPEC geomean).

In compilers we are usually more interested in actually discovering *which
parameters* are responsible for variation, rather than increasing
confidence in the values of an a priori set of known parameters. E.g. if
you are measuring the time it takes a laser beam to bounce off the moon and
come back to you (in order to measure the distance of the moon) you have an
a priori known set of parameters that well-characterize the data you
obtain, based on your knowledge of the measurement apparatus, atmospheric
dispersion, the fact that you know the moon is moving in an orbit, etc. You
can perform repeated measurements with the apparatus to narrow in on the
values of the parameters. In compilers, we rarely have such a simple and
small set of parameters that are known to adequately characterize the data
we are trying to understand; when investigating an optimization's results,
we are almost always investigating a situation that would resemble (in the
moon-bounce analogy) an unknown variation that turns out to be due to
whether the lab assistant is leaning against the apparatus or not. You're
not going to find out that the lab assistant's pose is at fault by looking
at your "repeatedly do them to increase confidence in the values"
measurements (e.g. the actual moon-bounce measurements; or looking at the
average time for a particular SPEC benchmark to run); you find it by
getting up and going to the room with the apparatus and investigating all
manner of things until you narrow in on the lab assistant's pose (usually
this takes the form of having to dig around in assembly, extract kernels,
time particular sub-things, profile things, look at what how the code
changes throughout the optimization pipeline, instrument things, etc.;
there are tons of places for the root cause to hide).

If you have to remember something from that last paragraph, remember that
not everything boils down to click "run" and get a timing for SPEC. Often
you need to take some time to narrow in on the damn lab assistant.
Sometimes just the timing of a particular benchmark leads to a "lab
assistant" situation (although hopefully this doesn't happen too often; it
does happen though: e.g. I have been in a situation where a benchmark
surprisingly goes 50% faster on about 1/10 runs). When working across
different programs, you are almost always in a "lab assistant" situation.

-- Sean Silva

On Mon, Dec 15, 2014 at 11:27 AM, Daniel Stewart <stewartd at codeaurora.org>
wrote:
>
> I have done some preliminary investigation into postponing some of the
> passes to see what the resulting performance impact would be. This is a
> fairly crude attempt at moving passes around to see if there is any
> potential benefit. I have attached the patch I used to do the tests, in
> case anyone is interested.
>
>
>
> Briefly, the patch allows two different flows, with either a flag of
> –lto-new or –lto-new2. In the first case, the vectorization passes are
> postponed from the end of populateModulePassManager() function to midway
> through the addLTOOptimizationPasses(). In the second case, essentially the
> entire populateModulePassManager() function is deferred until link time.
>
>
>
> I ran spec2000/2006 on an ARM platform (Nexus 4), comparing 4
> configurations (O3, O3 LTO, O3 LTO new, O3 LTO new 2). I have attached a
> PDF presenting the results from the test. The first 4 columns have the spec
> result (ratio) for the 4 different configurations. The second set of
> columns are the respective test / max(result of 4 configurations). I used
> this last one to see how well/poor a particular configuration was in
> comparison to other configurations.
>
>
>
> In general, there appears to be some benefit to be gained in a couple of
> the benchmarks (spec2000/art, spec2006/milc) by postponing vectorization.
>
>
>
> I just wanted to present this information to the community to see if there
> is interest in pursuing the idea of postponing passes.
>
>
>
> Daniel
>
>
>
> *From:* llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] *On
> Behalf Of *Daniel Stewart
> *Sent:* Wednesday, September 17, 2014 9:46 AM
> *To:* llvmdev at cs.uiuc.edu
> *Subject:* [LLVMdev] Postponing more passes in LTO
>
>
>
> Looking at the existing flow of passes for LTO, it appears that most all
> passes are run on a per file basis, before the call to the gold linker. I’m
> looking to get people’s feedback on whether there would be an advantage to
> waiting to run a number of these passes until the linking stage. For
> example, I believe I saw a post a little while back about postponing
> vectorization until the linking stage. It seems to me that there could be
> an advantage to postponing (some) passes until the linking stage, where the
> entire graph is available. In general, what do people think about the idea
> of a different flow of LTO where more passes are postponed until the
> linking stage?
>
>
>
> Daniel Stewart
>
>
>
> --
>
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
> by The Linux Foundation
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141218/b1e1ec9c/attachment.html>