averello/swift-mirror
1
0
Fork 0
mirror of https://github.com/apple/swift.git synced 2025-12-14 20:36:38 +01:00
Code Issues Packages Projects Releases Wiki Activity
Files
maxd/docc-compiler-docs
swift-mirror/docs/CompilerPerformance.md
ladd b23b335ac8 Update CompilerPerformance.md 
Typo fix, and fix parameter `--raw-clang-ast`
2020-10-05 14:16:59 -07:00

1306 lines
67 KiB
Markdown
Raw Permalink Blame History

# Swift Compiler Performance
This document is a guide to understanding, diagnosing and reporting
compilation-performance problems in the swift compiler. That is: the speed
at which the compiler compiles code, not the speed at which that code runs.
While this guide is lengthy, it should all be relatively
straightforward. Performance analysis is largely a matter of patience,
thoroughness and perseverance, measuring carefully and consistently, and
gradually eliminating noise and focusing on a signal.
## Table of Contents
<!-- TOC -->
- [Swift Compiler Performance](#swift-compiler-performance)
- [Table of Contents](#table-of-contents)
- [Outline of processes and factors affecting compilation performance](#outline-of-processes-and-factors-affecting-compilation-performance)
- [Compilation modes](#compilation-modes)
- [Primary-file vs. WMO](#primary-file-vs-wmo)
- [Amount of optimization](#amount-of-optimization)
- [Workload variability, approximation and laziness](#workload-variability-approximation-and-laziness)
- [Incremental compilation](#incremental-compilation)
- [Lazy resolution](#lazy-resolution)
- [Summing up: high level picture of compilation performance](#summing-up-high-level-picture-of-compilation-performance)
- [Known problem areas](#known-problem-areas)
- [How to diagnose compilation performance problems](#how-to-diagnose-compilation-performance-problems)
- [Tools and options](#tools-and-options)
- [Profilers](#profilers)
- [Instruments.app](#instrumentsapp)
- [Perf](#perf)
- [Diagnostic options](#diagnostic-options)
- [Post-processing tools for diagnostics](#post-processing-tools-for-diagnostics)
- [Artifact-analysis tools](#artifact-analysis-tools)
- [Minimizers](#minimizers)
- [Git bisect](#git-bisect)
- [Creduce](#creduce)
- [General bisection](#general-bisection)
- [Isolating a regression](#isolating-a-regression)
- [Driver diagnosis](#driver-diagnosis)
- [Finding areas in need of general improvement](#finding-areas-in-need-of-general-improvement)
- [Compiler counters](#compiler-counters)
- [Scale-test](#scale-test)
- [How to report bugs most usefully](#how-to-report-bugs-most-usefully)
- [How else to help out if you want to improve compile times](#how-else-to-help-out-if-you-want-to-improve-compile-times)
<!-- /TOC -->
## Outline of processes and factors affecting compilation performance
This section is intended to provide a high-level orientation around what the
compiler is doing when it's run -- beyond the obvious "compiling" -- and what
major factors influence how much time it spends.
When you compile or run a Swift program, either with Xcode or on the command
line, you typically invoke `swift` or `swiftc` (the latter is a symbolic link to
the former), which is a program that can behave in very different ways depending
on its arguments.
It may compile or execute code directly, but it will usually instead turn around
and run one or more copies of `swift` or `swiftc` as subprocesses. In typical
batch compilation, the first copy of `swiftc` runs as a so-called **driver**
process, and it then executes a number of so-called **frontend** subprocesses,
in a process tree. It's essential, when interpreting Swift compilation, to have
a clear picture of which processes are run and what they're doing:
- **Driver**: the top-level `swiftc` process in a tree of
subprocesses. Responsible for deciding which files need compiling or
recompiling and running child processes &mdash; so-called **jobs** &mdash;
to perform compilation and linking steps. For most of its execution, it is
idle, waiting for subprocesses to complete.
- **Frontend Jobs**: subprocesses launched by the driver, running `swift
-frontend ...` and performing compilation, generating PCH files, merging
modules, etc. These are the jobs that incur the bulk of the costs of
compiling.
- **Other Jobs**: subprocesses launched by the driver, running `ld`, `swift
-modulewrap`, `swift-autolink-extract`, `dsymutil`, `dwarfdump` and similar
tools involved in finishing off a batch of work done by the frontend
jobs. Some of these will be the `swift` program too, but they're not "doing
frontend jobs" and so will have completely different profiles.
The set of jobs that are run, and the way they spend their time, is itself
highly dependent on **compilation modes**. Information concerning those modes
that's relevant to compilation performance is recounted in the following
section; for more details on the driver, see [the driver docs](Driver.md), as
well as docs on [driver internals](DriverInternals.md)
and [driver parseable output](DriverParseableOutput.md).
After discussing compilation modes in the following section, we'll also touch on
large-scale variation in workload that can occur _without_ obvious hotspots, in
terms of laziness strategies and approximations.
### Compilation modes
There are many different options for controlling the driver and frontend jobs,
but the two dimensions that cause the most significant variation in behaviour
are often referred to as _modes_. These modes make the biggest difference, and
it's important when looking at compilation to be clear on which mode `swiftc` is
running in, and often to perform separate analysis for each mode. The
significant modes are:
- **Primary-file** vs. **whole-module**: this varies depending on whether the
driver is run with the flag `-wmo` (a.k.a. `-whole-module-optimization`).
- **Batch** vs. **single-file** primary-file mode. This distinction refines
the behaviour of primary-file mode, with the new batch mode added in the
Swift 4.2 release cycle. Batching eliminates much of the overhead of
primary-file mode, and will eventually become the default way of running
primary-file mode, but until that time it is explicitly enabled by passing
the `-enable-batch-mode` flag.
- **Optimizing** vs. **non-optimizing**: this varies depending on whether the
driver (and thus each frontend) is run with the flags `-O`, `-Osize`, or
`-Ounchecked` (each of which turn on one or more sets of optimizations), or
the default (no-optimization) which is synonymous with `-Onone` or
`-Oplayground`.
When you build a program in Xcode or using `xcodebuild`, often there is a
_configuration_ parameter that will switch both of these modes
simultaneously. That is, typical code has two configurations:
- **Debug** which combines primary-file mode with `-Onone`
- **Release** which combines WMO mode with `-O`
But these parameters can be varied independently and the compiler will spend its
time very differently depending on their settings, so it's worth understanding
both dimensions in a bit more detail.
#### Primary-file (with and without batching) vs. WMO
This is the most significant variable in how the compiler behaves, so it's worth
getting perfectly clear:
- In **primary-file mode**, the driver divides the work it has to do between
multiple frontend processes, emitting partial results and merging those
results when all the frontends finish. Each frontend job itself reads _all_
the files in the module, and focuses on one or more _primary_ file(s) among
the set it read, which it compiles, lazily analyzing other referenced
definitions from the module as needed.
This mode has two sub-modes:
- In the **single-file** sub-mode, it runs _one frontend job per file_, with
each job having a single primary.
- In the **batch** sub-mode, it runs _one frontend job per CPU_, identifying an
equal-sized "batch" of the module's files as primaries.
- In **whole-module optimization (WMO) mode**, the driver runs one frontend
job for the entire module, no matter what. That frontend reads all the files
in the module _once_ and compiles them all at once.
For example: if your module has 100 files in it:
- Running `swiftc *.swift` will compile in **single-file mode**, and will thus
run 100 frontend subprocesses, each of which will parse all 100 inputs (for
a total of 10,000 parses), and then each subprocess will (in parallel)
compile the definitions in its single primary file.
- Running `swiftc -enable-batch-mode *.swift` will compile in **batch** mode,
and on a system with 4 CPUs will run 4 frontend subprocesses, each of which
will parse all 100 inputs (for a total of 400 parses), and then each subprocess
will (in parallel) compile the definitions of 25 primary files (one quarter
of the module in each process).
- Running `swiftc -wmo *.swift` will compile in **whole-module** mode,
and will thus run _one_ frontend subprocess, which then reads all 100 files
_once_ (for a total of 100 parses) and compiles the definitions in all of them,
in order (serially).
Why do multiple modes exist? Because they have different strengths and weaknesses;
neither is perfect:
- Primary-file mode's advantages are that the driver can do **incremental
compilation** by only running frontends for files that it thinks are out of
date, as well as running multiple frontend jobs **in parallel**, making use
of multiple cores. Its disadvantage is that each frontend job has to read
_all the source files_ in the module before focusing on its primary-files of
interest, which means that a _portion_ of the frontend job's work is being
done _quadratically_ in the number of jobs. Usually this portion is relatively
small and fast, but because it's quadratic, it can easily go wrong. The addition
of **batch mode** was specifically to eliminate this quadratic increase in
early work.
- WMO mode's advantages are that it can do certain optimizations that only
work when they are sure they're looking at the entire module, and it avoids
the quadratic work in the early phases of primary-file mode. Its
disadvantages are that it always rebuilds everything, and that it exploits
parallelism worse (at least before LLVM IR code-generation, which is always
multithreaded).
Whole-module mode does enable a set of optimizations that are not possible when
compiling in primary-file mode. In particular, in modules with a lot of private
dead code, whole-module mode can eliminate the dead code earlier and avoid
needless work compiling it, making for both smaller output and faster compilation.
It is therefore possible that, in certain cases (such as with limited available
parallelism / many modules built in parallel), building in whole-module mode
with optimization disabled can complete in less time than batched primary-file
mode. This scenario depends on many factors seldom gives a significant advantage,
and since using it trades-away support for incremental compilation entirely, it
is not a recommended configuration.
#### Amount of optimization
This document isn't the right place to give a detailed overview of the compiler
architecture, but it's important to keep in mind that the compiler deals with
Swift code in memory in 3 major representations, and can therefore be
conceptually divided into 3 major stages, the latter 2 of which behave
differently depending on optimization mode:
- **ASTs** (Abstract Syntax Trees): this is the representation (defined in the
`lib/AST` directory) closest to what's in a source file, produced from Swift
source code, Swift modules and Clang modules (in `lib/Parse`,
`lib/Serialization` and `lib/ClangImporter` respectively) and interpreted by
resolution, typechecking and high-level semantics functions (in `lib/Sema`)
early-on in compilation.
- **SIL** (Swift Intermediate Language): this is a form that's private to the
Swift compiler, lower-level and more-explicit than the AST representation,
but still higher-level and more Swift-specific than a machine-oriented
representation like LLVM. It's defined in `lib/SIL`, produced by code in
`lib/SILGen` and _optionally optimized_ by code in `lib/SILOptimizer`.
- **LLVM IR** (Low Level Virtual Machine Intermediate Representation): this is
a form that's an abstract representation of the machine language being
compiled for; it doesn't contain any Swift-specific knowledge, rather it's a
form the Swift compiler _generates from SIL_ (in `lib/IRGen`) and then hands
off as input to the [LLVM backend](http://llvm.org), a library upon which
the Swift compiler depends. LLVM has its own _optional optimizations_ that
apply to LLVM IR before it's lowered to machine code.
When running the Swift compiler in optimizing mode, many SIL and LLVM
optimizations are turned on, making those phases of compilation (in each
frontend job) take significantly more time and memory. When running in
non-optimizing mode, SIL and LLVM IR are still produced and consumed along the
way, but only as part of lowering, with comparatively few "simple" optimizations
applied.
Additionally, the IRGen and LLVM phases can operate (and usually are operated)
in parallel, using multiple threads in each frontend job, as controlled by the
`-num-threads` flag. This option only applies to the latter phases, however: the
AST and SIL-related phases never run multithreaded.
The amount of work done to the AST representation (in particular: importing,
resolving and typechecking ASTs) does not vary between different optimization
modes. However, it does vary _significantly_ between different projects and
among seemingly-minor changes to code, depending on the amount of laziness the
frontend is able to exploit.
### Workload variability, approximation and laziness
While some causes of slow compilation have definite hotspots (which we will get
to shortly), one final thing to keep in mind when doing performance analysis is
that the compiler tries to be _lazy_ in a variety of ways, and that laziness
does not always work: it is driven by certain approximations and assumptions
that often err on the side of doing more work than strictly necessary.
The outcome of a failure in laziness is not usually a visible hotspot in a
profile: rather, it's the appearance of doing "too much work altogether" across
a generally-flat profile. Two areas in particular where this occurs &mdash; and
where there are significant, ongoing improvements to be made &mdash; are in
incremental compilation and lazy resolution.
#### Incremental compilation
As mentioned in the section on primary-file mode, the driver has an _incremental
mode_ that can be used to attempt to avoid running frontend jobs entirely. When
successful, this is the most effective form of time-saving possible: nothing is
faster than a process that doesn't even run.
Unfortunately judgements about when a file "needs recompiling" are themselves
driven by an auxiliary data structure that summarizes the dependencies between
files, and this data structure is necessarily a conservative approximation. The
approximation is weaker than it should be, and as a result the driver often runs
more frontend jobs than it should.
#### Lazy resolution
Swift source files contain names that refer to definitions outside the enclosing
file, and frequently outside of the enclosing module. These "external"
definitions are resolved lazily from two very different locations (both called
"modules"):
- C/ObjC modules, provided by the Clang importer
- Serialized Swift modules
Despite their differences, both kinds of modules support laziness in the Swift
compiler in one crucial way: they are both kinds of _indexed_ binary file
formats that permit loading _single definitions_ out of by name, without having
to load the entire contents of the module.
When the Swift compiler manages to be lazy and limit the number of definitions
it tries to load from modules, it can be very fast; the file formats support
very cheap access. But often the logic in the Swift compiler is unnecessarily
conservative about exploiting this potential laziness, and so it loads more
definitions than it should.
### Summing up: high level picture of compilation performance
Swift compilation performance varies _significantly_ by at least the following
parameters:
- WMO vs. primary-file (non-WMO) mode, including batching thereof
- Optimizing vs. non-optimizing mode
- Quantity of incremental work avoided (if in non-WMO)
- Quantity of external definitions lazily loaded
When approaching Swift compilation performance, it's important to be aware of
these parameters and keep them in mind, as they tend to frame the problem you're
analyzing: changing one (or any of the factors influencing them, in a project)
will likely completely change the resulting profile.
## Known problem areas
These are areas where we know the compiler has room for improvement,
performance-wise, where it's worth searching for existing bugs on the topic,
finding an existing team member who knows the area, and trying to relate the
problem you're seeing to some of the existing strategies and plans for
improvement:
- Incremental mode is over-approximate, runs too many subprocesses.
- Too many referenced (non-primary-file) definitions are type-checked beyond
the point they need to be, during the quadratic phase.
- Expression type inference solves constraints inefficiently, and can
sometimes behave super-linearly or even exponentially.
- Periodically the analysis phase of a SIL optimization fails to cache
overlapping subproblems, causing a super-linear slowdown.
- Some SIL-to-IR lowerings (eg. large value types) can generate too much
LLVM IR, increasing the time spent in LLVM.
(Subsystem experts: please add further areas of concern here.)
## How to diagnose compilation performance problems
Compiler performance analysis breaks down into two broad categories of work,
depending on what you're trying to do:
- Isolating a regression
- Finding areas that need general improvement
In all cases, it's important to be familiar with several tools and compiler
options we have at our disposal. If you know about all these tools, you can skip
the following section.
### Tools and options
You'll use several tools along the way. These come in 5 main categories:
- Profilers
- Diagnostic options built-in to the compiler (timers, counters)
- Post-processing tools to further analyze diagnostic output
- Tools to generally analyze the output artifacts of the compiler
- Tools to minimize the regression range or testcases
#### Profilers
The basic tool of performance analysis is a profiler, and you _will need_ to
learn to use at least one profiler for the purposes of this work. The main two
profilers we use are `Instruments.app` on macOS, and `perf(1)` on Linux. Both
are freely available and extremely powerful; this document will barely scratch
the surface of what they can do.
##### Instruments.app
Instruments is a tool on macOS that ships as part of Xcode. It contains
graphical and batch interfaces to a very wide variety of profiling services;
see
[here](https://developer.apple.com/library/content/documentation/DeveloperTools/Conceptual/InstrumentsUserGuide/index.html) for
more documentation.
The main way we will use `Instruments.app` is in "Counter" mode, to record and
analyze a single run of swiftc. We will also use it in simple push-button
interactive mode, as a normal application. While it's possible to run
Instruments in batch mode on the command-line, the batch interface is less
reliable than running it as an interactive application, and frequently causes
lockups or fails to collect data.
Before starting, you should also be sure you are going to profile a version of
Swift _without_ DWARF debuginfo; while in theory debuginfo will give a
higher-resolution, more-detailed profile, in practice Instruments will often
stall out and become unresponsive trying to process the additional detail.
Similarly, be sure that as many applications as possible (especially those with
debuginfo themselves!) are closed, so that Instruments has little additional
material to symbolicate as possible. It collects a _whole system profile_ at
very high resolution, so you want to make its life easy by profiling on a quiet
machine doing little beyond the task you're interested in.
Once you're ready, follow these steps:
- Open `Xcode.app`
- Click `Xcode` => `Open Developer Tool` => `Instruments` (Once it's open, you
might want to pin `Instruments.app` to the dock for ease of access)
- Select the `Counters` profiling template
- Open a terminal and get prepared to run your test-case
- Switch back to `Instruments.app`
- Press the red `record` button in the top-left of the instruments panel
- Quickly switch to your terminal, run the test-case you wish to profile, and
as soon as it's finished switch back to `Instruments.app` and press the stop
button.
That's it! You should have a profile gathered.
Ideally you want to get to a situation that looks like this:
![Instruments Profile with terminal](InstrumentsProfile.png)
In the main panel you can see a time-sorted set of process and call-frame
samples, which you can filter to show only swift processes by typing `swift` in
the `Input Filter` box at the bottom of the window. Each line in the main panel
can be expanded by clicking the triangle at its left, showing the callees as
indented sub-frames.
If you hover over the line corresponding to a specific `swift` process, you'll
see a small arrow enclosed in a grey circle to the right of the line. Click on
it and instruments will shift focus of the main panel to just that process'
subtree (and recalculate time-percentages accordingly). Once you're focused on a
specific `swift` process, you can begin looking at its individual stack-frame
profile.
In the panel to the right of the main panel, you can see the heaviest stack
trace within the currently-selected line of the main panel. If you click on one
of the frames in that stack, the main panel will automatically expand every
level between the current frame and the frame you clicked on. For example,
clicking 11 frames down the hottest stack, on the frame called
`swift::ModuleFile::getModule`, will expand the main panel to show something
like this:
![Instruments Profile with terminal](InstrumentsExpandedProfile.png)
Click around a profile by expanding and contracting nodes in the stack tree, and
you'll pretty quickly get a feeling for where the program is spending its
time. Each line in the main display shows both the cumulative sample count and
running time of its subtree (including all of its children), as well as its own
frame-specific `Self` time.
In the example above, it's pretty clear that the compiler is spending 66% of
its time in `Sema`, and the heaviest stack inside there is the time spent
deserializing external definitions (which matches a known problem area,
mentioned earlier).
If you want to keep notes on what you're seeing while exploring a profile, you
can expand and collapse frames until you see a meaningful pattern, then select
the displayed set of stack frames and copy them as text (using `⌘-C` as usual)
and paste it into a text file; whitespace indentation will be inserted in the
copied text, to keep the stack structure readable.
If you have _two_ profiles and want to compare them, Instruments does have a
mode for direct diffing between profiles, but it doesn't work when the profiles
are gathered from different binaries, so for purposes of comparing different
swift compilers, you'll typically have to do manual comparison of the profiles.
##### Perf
Perf is a Linux profiler that runs on the command line. In many Linux
distributions it's included in a package called `linux-tools` that needs to be
separately installed. It's small, fast, robust, flexible, and can be easily
scripted; the main disadvantages are that it lacks any sort of GUI and only runs
on Linux, so you can't use it to diagnose problems in builds that need macOS or
iOS frameworks or run under `xcodebuild`.
Perf is documented
[on the kernel wiki](https://perf.wiki.kernel.org/index.php/Main_Page) as well
as on [Brendan Gregg's website](http://www.brendangregg.com/perf.html).
Using `perf` requires access to hardware performance counters, so you cannot use
it in most virtual machines (unless they virtualize access to performance
counters). Further, you will need root access to give yourself permission to use
the profiling interface of the kernel.
The simplest use of perf just involves running your command under `perf
stat`. This gives high level performance counters including an
instructions-executed count, which is a comparatively-stable approximation of
total execution cost, and is often enough to pick out a regression when
bisecting (see below):
```
$ perf stat swiftc t.swift
Performance counter stats for 'swiftc t.swift':
2140.543052 task-clock (msec) # 0.966 CPUs utilized
17 context-switches # 0.008 K/sec
6 cpu-migrations # 0.003 K/sec
52,084 page-faults # 0.024 M/sec
5,373,530,212 cycles # 2.510 GHz
9,709,304,679 instructions # 1.81 insn per cycle
1,812,011,233 branches # 846.519 M/sec
22,026,587 branch-misses # 1.22% of all branches
2.216754787 seconds time elapsed
```
The fact that `perf` gives relatively stable and precise cost measurements means
that it can be made into a useful subroutine when doing other
performance-analysis tasks, such as bisecting (see section on `git bisect`) or
reducing (see section on `creduce`). A shell function like the following is very
useful:
```
count_instructions() {
perf stat -x , --log-fd 3 \
-e instructions -r 10 "$@" \
3>&1 2>/dev/null 1>&2 | cut -d , -f 1
}
```
To gather a full profile with perf -- when not just using it as a batch counter
-- use the `perf record` and `perf report` commands; depending on configuration
you might need to play with the `--call-graph` and `-e` parameters to get a
clear picture:
```
$ perf record -e cycles -c 10000 --call-graph=lbr swiftc t.swift
[ perf record: Woken up 5 times to write data ]
[ perf record: Captured and wrote 1.676 MB perf.data (9731 samples) ]
```
Once recorded, data will be kept in a file called `perf.data`, which is the
default file acted-upon by `perf report`. Running it should give you something
like the following textual user interface, which operates similarly to
`Instruments.app`, only using cursor keys:
![perf report](PerfReport.png)
#### Diagnostic options
The Swift compiler has a variety of built-in diagnostic options. Some are
interpreted by the driver, others are interpreted by the frontend jobs that the
driver runs: these have to be passed on the driver command-line with
`-Xfrontend` to get passed through to the frontends. In a multi-frontend,
primary-file-mode compilation, any such `-Xfrontend` option will be passed to
_all_ frontend job, which means the diagnostic output from _all_ frontend jobs
will be sent to standard output in sequence. This makes diagnosing problems with
these options somewhat challenging; they work better if you can reduce the
problem to a single frontend process before using these options.
Further, some of the diagnostic options depend on instrumentation that's only
present in assert compilers; if you pass them to release compilers, you will get
limited or no output. It's often useful to have both release and assert
compilers on hand while you're working.
- `-driver-time-compilation`: interpreted by the driver; emits a high-level
timing of the frontend and other jobs that the driver executes. It can guide
early investigation to see which file in a primary-file-mode compilation is
taking the majority of time, or is taking more or less time than when
comparing compilations. Its output looks like this:
```
===-------------------------------------------------------------------------===
Driver Compilation Time
===-------------------------------------------------------------------------===
Total Execution Time: 0.0001 seconds (0.0490 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
0.0000 ( 82.0%) 0.0001 ( 59.5%) 0.0001 ( 69.0%) 0.0284 ( 58.0%) {compile: t-177627.o <= t.swift}
0.0000 ( 18.0%) 0.0000 ( 40.5%) 0.0000 ( 31.0%) 0.0206 ( 42.0%) {link: t <= t-177627.o}
0.0001 (100.0%) 0.0001 (100.0%) 0.0001 (100.0%) 0.0490 (100.0%) Total
```
- `-Xfrontend -debug-time-function-bodies`: asks each frontend to print out
the time spent typechecking _every function_ in the program, sorted by time
taken. The output is therefore voluminous, but can help when reducing a
testcase to the "one bad function" that causes it. The output looks like
this:
```
9.16ms test.swift:15:6 func find<R>(_ range: R, value: R.Element) -> R where R : IteratorProtocol, R.Element : Eq
0.28ms test.swift:27:6 func findIf<R>(_ range: R, predicate: (R.Element) -> Bool) -> R where R : IteratorProtocol
2.81ms test.swift:40:6 func count<R>(_ range: R, value: R.Element) -> Int where R : IteratorProtocol, R.Element : Eq
0.64ms test.swift:51:6 func countIf<R>(_ range: R, predicate: (R.Element) -> Bool) -> Int where R : IteratorProtocol
...
```
- `-Xfrontend -debug-time-expression-type-checking`: similar to
`-debug-time-function-bodies`, but prints a separate timer for _every
expression_ in the program, much more detail than just the functions. The
output looks like this:
```
0.20ms test.swift:17:16
1.82ms test.swift:18:12
6.35ms test.swift:19:8
0.11ms test.swift:22:5
0.02ms test.swift:24:10
0.02ms test.swift:30:16
...
```
- `-Xfrontend -print-stats`: activates statistic counters inside each
frontend, printing them out when the frontend exits. By default, most
statistics are enabled only in assert builds, so in a release build this
option will do nothing. In an assert build, its output will look like this:
```
===-------------------------------------------------------------------------===
... Statistics Collected ...
===-------------------------------------------------------------------------===
4 BasicCalleeAnalysis - computeMethodCallees
6 Clang module importer - # of imported clang entities
11 Constraint solver largest system - # of connected components split
176 Constraint solver largest system - # of disjunction terms explored
9 Constraint solver largest system - # of disjunctions explored
59 Constraint solver largest system - # of constraints simplified
0 Constraint solver largest system - # of simplification iterations
232 Constraint solver largest system - # of solution states explored
42 Constraint solver largest system - # of type variable bindings attempted
38 Constraint solver largest system - # of type variables bound
79 Constraint solver largest system - # of constraints not simplified
94 Constraint solver largest system - # of the largest solution attempt
6 Constraint solver overall - Number of solutions discarded
361 Constraint solver overall - # of solution attempts
130 Constraint solver overall - # of connected components split
1898 Constraint solver overall - # of disjunction terms explored
119 Constraint solver overall - # of disjunctions explored
844 Constraint solver overall - # of constraints simplified
...
```
- `-Xfrontend -print-clang-stats`: prints counters associated with the clang
AST reader, which is operated as a subsystem of the swift compiler when
importing definitions from C/ObjC. Its output is added to the end of
whatever output comes from `-print-stats`, and looks like this:
```
*** AST File Statistics:
1/194 source location entries read (0.515464%)
5/182 types read (2.747253%)
7/318 declarations read (2.201258%)
6/251 identifiers read (2.390438%)
0/22 macros read (0.000000%)
0/70 statements read (0.000000%)
0/22 macros read (0.000000%)
1/22 lexical declcontexts read (4.545455%)
0/16 visible declcontexts read (0.000000%)
6 / 6 identifier table lookups succeeded (100.000000%)
...
```
- `-Xfrontend -print-stats -Xfrontend -print-inst-counts`: an extended form of
`-print-stats` that activates a separate statistic counter for every kind of
SIL instruction generated during compilation. Its output looks like this:
```
...
163 sil-instcount - Number of AllocStackInst
90 sil-instcount - Number of ApplyInst
92 sil-instcount - Number of BeginAccessInst
212 sil-instcount - Number of BranchInst
80 sil-instcount - Number of BuiltinInst
37 sil-instcount - Number of CondBranchInst
6 sil-instcount - Number of CondFailInst
136 sil-instcount - Number of CopyAddrInst
177 sil-instcount - Number of DeallocStackInst
21 sil-instcount - Number of DebugValueAddrInst
6 sil-instcount - Number of DebugValueInst
128 sil-instcount - Number of DestroyAddrInst
...
```
##### Unified stats reporter
In an attempt to unify collection and reporting of the various
statistic-gathering options, recent versions of the compiler support a partly
redundant command `-stats-output-dir <directory>` that writes _all_ driver and
primary frontend counters and timers (though not per-function timers) to JSON
files in `<directory>`.
This option also provides _some_ high-level counters that are "always available"
regardless of whether you're using an assert or release build, though assert
builds still get _more_ counters (all of those available through
`-print-stats`). If you are using a new-enough compiler, `-stats-output-dir`
often simplifies analysis, since its output is machine-readable and aggregates
all the jobs in a multi-job compilation, and there's a post-processing script
`utils/process-stats-dir.py` to work with these files in aggregate.
For example, to compile a file with the unified stats reporter enabled, first
make a directory in which to output the stats, then compile with the
`-stats-output-dir` flag:
```
$ mkdir /tmp/stats
$ swiftc -c test.swift -stats-output-dir /tmp/stats
$ ls /tmp/stats
stats-1518219149045080-swift-frontend-test-test.swift-x86_64_apple_macosx10.13-o-Onone-531621672.json
$ cat /tmp/stats/*.json
{
"AST.NumSourceBuffers": 1,
"AST.NumSourceLines": 1,
"AST.NumSourceLinesPerSecond": 3,
"AST.NumLinkLibraries": 0,
"AST.NumLoadedModules": 4,
"AST.NumTotalClangImportedEntities": 0,
...
"time.swift.Parsing.wall": 5.038023e-03,
"time.swift.Parsing.user": 7.200000e-05,
"time.swift.Parsing.sys": 4.794000e-03,
"time.swift-frontend.test-test.swift-x86_64_apple_macosx10.13-o-Onone.wall": 3.239949e-01,
"time.swift-frontend.test-test.swift-x86_64_apple_macosx10.13-o-Onone.user": 2.152100e-02,
"time.swift-frontend.test-test.swift-x86_64_apple_macosx10.13-o-Onone.sys": 2.897520e-01
}
```
###### Tracing stats events
Furthermore, recent versions `-stats-output-dir` have a secondary, experimental
(and much more voluminous mode) called `-trace-stats-events`, that writes _trace
files_ in CSV to the stats output directory. These trace files show -- in quite
verbose detail, declaration and expression at a time -- the costs incurred by
various phases of the compiler, both in terms of absolute time and in terms of
any changers to statistics being tracked by the unified stats reporter.
For example, to compile a small file with `-trace-stats-events`, pass it as an
extra argument to a compilation already using `-stats-output-dir`:
```
$ mkdir /tmp/stats
$ swiftc -c test.swift -stats-output-dir /tmp/stats -trace-stats-events
$ ls /tmp/stats
stats-1518219460129565-swift-frontend-test-test.swift-x86_64_apple_macosx10.13-o-Onone-1576107381.json
trace-1518219460129597-swift-frontend-test-test.swift-x86_64_apple_macosx10.13-o-Onone-1471252712.csv
$ head /tmp/stats/trace-1518219460129597-swift-frontend-test-test.swift-x86_64_apple_macosx10.13-o-Onone-1471252712.csv
Time,Live,IsEntry,EventName,CounterName,CounterDelta,CounterValue,EntityName,EntityRange
40032,0,"entry","typecheck-decl","Sema.NumDeclsDeserialized",91,91,"foo","[test.swift:1:1 - line:1:32]"
40032,0,"entry","typecheck-decl","Sema.NumLazyGenericEnvironments",40,40,"foo","[test.swift:1:1 - line:1:32]"
40032,0,"entry","typecheck-decl","Sema.NumLazyIterableDeclContexts",40,40,"foo","[test.swift:1:1 - line:1:32]"
40032,0,"entry","typecheck-decl","Sema.NumTypesDeserialized",106,106,"foo","[test.swift:1:1 - line:1:32]"
40032,0,"entry","typecheck-decl","Sema.NumUnloadedLazyIterableDeclContexts",40,40,"foo","[test.swift:1:1 - line:1:32]"
40135,0,"entry","typecheck-decl","Sema.InterfaceTypeRequest",1,1,"","[test.swift:1:13 - line:1:29]"
...
```
The data volume in these trace files can be quite overwhelming, and the contents
a little hard to read without formatting; for extraction and analysis it can be
helpful to load them into a separate tool such as
an [SQLite database](https://www.sqlite.org) or a command line CSV processor
such as [`xsv`](https://github.com/BurntSushi/xsv).
```
$ cat /tmp/stats/trace-1518219460129597-swift-frontend-test-test.swift-x86_64_apple_macosx10.13-o-Onone-1471252712.csv \
| xsv search --select CounterName DeclsDeserialized \
| xsv sort --reverse --numeric --select CounterDelta \
| xsv table
Time Live IsEntry EventName CounterName CounterDelta CounterValue EntityName EntityRange
43279 0 entry emit-SIL Sema.NumDeclsDeserialized 360 517 _ [test.swift:1:17 - line:1:17]
40032 0 entry typecheck-decl Sema.NumDeclsDeserialized 91 91 foo [test.swift:1:1 - line:1:32]
41324 735 exit typecheck-decl Sema.NumDeclsDeserialized 40 156 [test.swift:1:13 - line:1:29]
40432 0 entry typecheck-decl Sema.NumDeclsDeserialized 25 116 _ [test.swift:1:17 - line:1:17]
43712 206 exit emit-SIL Sema.NumDeclsDeserialized 18 535 _ [test.swift:1:17 - line:1:17]
41448 97 exit typecheck-fn Sema.NumDeclsDeserialized 1 157 _ [test.swift:1:17 - line:1:17]
```
#### Post-processing tools for diagnostics
If you dump diagnostic output using `-stats-output-dir <dir>`, the resulting
files in `<dir>` will be simple JSON files that can be processed with any
JSON-reading program or library, such
as [`jq`](https://stedolan.github.io/jq/). Alternatively, a bulk-analysis script
also exists in `utils/process-stats-dir.py`, which permits a variety of
aggregation and analysis tasks.
Here is an example of how to use `-stats-output-dir` together with
`utils/process-stats-dir.py` to analyze the difference in compilation
performance between two compilers, say `${OLD}/swiftc` and `${NEW}/swiftc`:
```
$ mkdir stats-old stats-new
$ ${OLD}/swiftc -stats-output-dir stats-old test.swift
$ ${NEW}/swiftc -stats-output-dir stats-new test.swift
$ utils/process-stats-dir.py --compare-stats-dirs stats-old stats-new
old new delta_pct name
1402939 1430732 1.98 AST.NumASTBytesAllocated
7 0 -100.0 AST.NumUsedConformances
232 231 -0.43 Constraint solver largest system.LargestNumStatesExplored
42 41 -2.38 Constraint solver largest system.LargestNumTypeVariableBindings
38 37 -2.63 Constraint solver largest system.LargestNumTypeVariablesBound
79 78 -1.27 Constraint solver largest system.LargestNumUnsimplifiedConstraints
2593 2592 -0.04 Constraint solver overall.OverallNumStatesExplored
589 588 -0.17 Constraint solver overall.OverallNumTypeVariableBindings
482 481 -0.21 Constraint solver overall.OverallNumTypeVariablesBound
972 971 -0.1 Constraint solver overall.OverallNumUnsimplifiedConstraints
2593 2592 -0.04 ConstraintSystem.incrementScopeCounter
2948 2947 -0.03 Generic signature builder.NumArchetypeAnchorCacheHits
14767 15924 7.84 Generic signature builder.NumConformanceConstraints
9701 10858 11.93 Generic signature builder.NumConformances
5013 4241 -15.4 Generic signature builder.NumPotentialArchetypes
5776 4084 -29.29 Generic signature builder.NumSameTypeConstraints
...
```
When comparing two stats directories that contain the combined results of
multiple projects, it can be helpful to select a single project with
`--select-module` and/or group counters by module with `--group-by-module`.
#### Artifact-analysis tools
Many performance issues manifest in the object files or module files produced by
the Swift compiler -- say, by generating too much code -- so it can sometimes be
helpful to look at the files the compiler outputs directly. The following tools
are helpful in such cases:
- `llvm-objdump`, `llvm-otool` and `llvm-size`, `llvm-nm` (which are
LLVM-project implementations of the `objdump`, `otool`, `size` and `nm`
tools) permit analysis of object files: their sizes, their headers, the
set of symbols within them, and even their complete disassembled contents.
- `c++filt` and `swift-demangle` are commands that read from stdin and
write to stdout, transforming the text they read by _demangling names_
in C++ and Swift, respectively. If you ever seen long, ugly symbol names
in diagnostic output from a tool reading a binary artifact, it may read
much better after being piped through one or another of these tools.
- `llvm-bcanalyzer` can print (in rough form) the contents of LLVM bitcode
streams, such as Swift module files and the PCH/PCM files clang stores its
serialized ASTs in. The latter requires combining `llvm-objdump` and
`llvm-bcanalyzer` in the following fashion: `llvm-objdump --raw-clang-ast
file.pcm | llvm-bcanalyzer -dump`
- `llvm-dwarfdump` and `llvm-dis` can be used to print textual representations
of DWARF debug information and LLVM bitcode, respectively. These are usually
a bit lower-level than necessary when doing performance analysis, but can be
helpful in certain cases.
- `utils/cmpcodesize/cmpcodesize.py` provides a detailed, organized set of
size comparisons between the artifacts in a pair of object files emitted by
the Swift compiler.
#### Minimizers
##### Git bisect
The `git` command has a sub-command called `bisect` that helps with -- and can
even completely automate -- the process of reducing a regression range from a
large period (weeks to months, hundreds of revisions) down to a single revision
that was the cause of a problem. As the name implies, bisect performs bisection
-- repeatedly dividing a range in half, then in quarters, and so forth -- so
usually within a matter of a dozen steps it can isolate a problem. It is
documented in full [here](https://git-scm.com/docs/git-bisect) as well as in the
`git-bisect` man page.
The `bisect` command can be run in manual mode or automatic mode. In manual
mode, you follow these steps:
1. Start with a command like `git bisect start <bad> <good>` that sets up the
initial regression range to between the revisions `<bad>` and `<good>`
(replace those with revisions you know to be bad and good).
2. Git will repeatedly check out the revision in the middle of the current
regression range, asking you to evaluate it.
3. Build the revision it checked out, evaluate it using whatever method you
like, and then either run `git bisect good` or `git bisect bad` (literally
those words: `bad` or `good`). If the revision it checked out can't be
evaluated, run `git bisect skip` and it will shift to an adjacent revision,
adjusting its search strategy accordingly.
4. When it's reduced to a single culprit, git will print out the "first bad
revision" log entry. At this point it's worth manually re-confirming that
the identified revision is indeed bad, and the revision
immediately-previous to it is indeed good. Periodically some confounding
issue will confuse the bisection search, and you'll be directed to the
wrong candidate.
In automatic mode, one simply runs the command `git bisect run test.sh` on some
shell script you've written `test.sh`, and `git-bisect` performs the entire
bisection search automatically. The shell script needs to exit with a return
value that tells `git bisect` whether the revision it's run on is good (`exit 0`),
bad (`exit 1`), or should be skipped (`exit 125`).
How the test-script determines the presence of a regression is up to you: a
typical approach is to measure against a baseline (eg. using
`utils/process-stats-dir.py --compare-to-csv-baseline`, if your regression range
covers compilers that all support `-stats-output-dir`). Alternatively, just
measure raw time or instruction counts. An example script that uses the
`perf`-based `count_instructions` shell function (see the section on `perf`) to
judge whether a revision contains a bug looks something like this:
```
#!/bin/sh
THRESHOLD=500000000
CURR=$(git describe)
utils/update-checkout --scheme main --reset-to-remote --clone --clean
git checkout ${CURR}
utils/update-checkout --scheme main --match-timestamp
git checkout ${CURR}
if utils/build-script -r
then
V=$(count_instructions ../build/Ninja-ReleaseAssert/swift-linux-x86_64/bin/swiftc -c test.swift)
if [ ${V} -gt ${THRESHOLD} ]
then
# Bad
exit 1
else
# Good
exit 0
fi
else
# Skip
exit 125
fi
```
Note that in the example, the `utils/update-checkout` script is called twice,
once to reset the adjacent repositories to their head state, and once with the
`--match-timestamp` argument to match the adjacent repositories to the latest
point in their history before the timestamp of the primary Swift repository
being bisected. This mechanism is necessary if the regression range includes
incompatible changes to `clang`, `llvm` or similar adjacent repositories.
##### Creduce
The `creduce` tool takes an input program and a script, and repeatedly cuts
pieces out of the input program and re-runs the script on the program to see if
the script still considers the residual input "interesting". It is
documented [here](https://embed.cs.utah.edu/creduce/) and is available through
Homebrew on macOS, or in most Linux package ecosystems.
You can use `creduce` to automate the otherwise-tedious task of taking a failing
or slow input and reducing it to "just the bad part" that triggers the problem
you're after.
For performance analysis, using `creduce` requires that the script can reliably
tell when it's "still seeing a regression" and when it's not. This means having
a reliable timer or cost-measurement tool; the simplest and most reliable we
know of is `perf` so we'll assume you're using it here, via the
`count_instructions` shell function described in the section on `perf`; but
other measurement tools also work, for example using
`utils/process-stats-dir.py` to test changes in performance counters. To use
`creduce` you need to write a script something like the following:
```
#!/bin/sh
INPUT=test.swift
OLD=${HOME}/old-toolchain/usr/bin/swift
NEW=${HOME}/new-toolchain/usr/bin/swift
THRESHOLD=50000000
VOLD=$(count_instructions ${OLD} -frontend -c ${INPUT})
VNEW=$(count_instructions ${NEW} -frontend -c ${INPUT})
VDIFF=$((${VNEW} - ${VOLD}))
if [ ${VDIFF} -gt ${THRESHOLD} ]
then
# Interesting
exit 0
else
# Not interesting
exit 1
fi
```
Note that, as with `git-bisect`, any measurement tool will work in place of
`count_instructions`; if you are looking at a regression-range in which all the
compilers have `-stats-output-dir` support, for example, you may well prefer to
use `utils/process-stats-dir.py --compare-to-csv-baseline`, for example.
##### General bisection
When all else fails, coding up a manual bisection is often possible given a
numbered set of testcases. The LLVM project ships with a very generic helper
script for this, `llvm/util/bisect`, that takes a numeric range and a general
subprocess and bisects the range until it finds the place the process changes
from success to failure.
### Isolating a regression
Follow these steps if you've observed (or think you're seeing) the compiler
getting slower between versions:
1. Make sure the before-and-after compilers you're comparing are as close to
identical as possible.
- Ensure both compilers are built the same way: same configuration options,
same host toolchains, same optimizations enabled.
- Ensure both compilers are _release_ compilers _without assertions_ (Note:
nightly snapshots from swift.org have assertions turned on.) You may
also want to build (or download) assertion-enabled compilers for
finer-grained counter analysis (see below) but keep in mind that they run
strictly slower and do significantly different work than release
(non-assert) compilers, so are not representative of what users will be
using.
2. Measure the high-level timing of the compilation, using `time(1)` or
`utils/rusage.py`. Run the compilation a few times to be sure you're not
seeing noise.
3. Determine the **compilation mode** in which the regression is
occurring. Check to see if changing the compilation mode keeps the
regression happening.
- If the regression occurs regardless of optimization setting, you have
reason to believe the cause is in `Sema` or a non-optimizing part of
`SILGen`, `IRGen` or `LLVM`. Alternatively if it only occurs in
optimizing builds, you have reason to believe the cause is in
`SILOptimizer`, `IRGen` or `LLVM`.
- If the regression occurs regardless of compilation mode, you have reason
to believe the cause is localized to frontend jobs. Alternatively if it
occurs only in primary-file mode, and goes away in whole-module mode, you
have reason to believe the driver may also be implicated.
4. Try to isolate your analysis to a specific frontend process in the compilation.
- If the regression only occurs in whole-module build then you're already
dealing with a single process (the sole frontend job).
- If the regression _also_ (or _only_) happens in primary-file mode, you
can compile with `-driver-time-compilation` to see which if any frontend
job is slower.
- If _all_ frontend jobs are slower, pick one at random to focus on for
purposes of analysis.
- If _no_ frontend jobs are slower but the overall compilation seems to be,
_or_ if a different number of frontend jobs are running depending on
which compiler is run, then the problem is likely in the driver. Skip to
the section on driver diagnosis.
5. Assuming you're looking at a frontend process: extract the command-line for
the single process (of the form `swift -frontend ...`) by running the build
in verbose mode, and put the command-line in a shell script so you can
re-run it on its own, without the interference of the driver or other
processes. Make a copy of the script that runs the old compiler and a
different copy that runs the new compiler (or make the compiler version a
parameter of the script). Reconfirm that _just those two isolated frontend
processes_ still show the regression you're interested in isolating.
6. Check the value of performance counters between the two compilers via the
unified stats reporter (`-stats-output-dir`).
7. Run both frontend processes under a profiler and compare the profiles in
detail. At this point there ought to be _some_ sign of a difference, either
in counters or profile; if everything looks identical, you either have a
deeper mystery than this document will cover, or you've lost the signal by
accidentally perturbing the environment / the input / the processes under
study. If the problem is _blindingly obvious_ at this point, stop and fix
the bug, otherwise proceed to narrowing the problem.
8. Reduce the testcase. That is, figure out the smallest input file that
causes the regression you're observing. If the problem you're looking at
occurs in the frontend, you might be able to do this manually by running
the input with `-Xfrontend -debug-time-function-bodies` and deleting all
but the most expensive function, or reduce even further from a function to
a single expression via `-Xfrontend -debug-time-expression-type-checking`;
but keep in mind these options only track the time spent _typechecking_ a
given function or expression; they do not help in reduction of testcases
for problems that occur in other subsystems of the compiler. For general
reduction, the normal approach is "bisection", also called
"delta-debugging": repeatedly delete half the remaining contents of the
file, and see if the regression remains. If so, repeat the process in the
remaining half; if not, restore the half you deleted and switch your
attention to it. This process -- along with several other reduction
heuristics that are sensitive to the structure of the code -- can also be
automated with the tool `creduce`. See the section on `creduce` for
details.
9. Bisect the regression range. That is, figure out the smallest range of
changes to the compiler (typically a single revision in the git history)
that caused the regression. If you have more network bandwidth than compute
power available, you might want to begin this part by downloading snapshots
of the compiler from swift.org. While only a handful of recent snapshots
are linked on the swift.org webpage, all historical snapshots remain
available to download by substituting the appropriate timestamp into the
snapshot URL. For example, the main-branch, macOS snapshot from June 9
2017 is available
at
[https://swift.org/builds/development/xcode/swift-DEVELOPMENT-SNAPSHOT-2017-06-09-a/swift-DEVELOPMENT-SNAPSHOT-2017-06-09-a-osx.pkg](https://swift.org/builds/development/xcode/swift-DEVELOPMENT-SNAPSHOT-2017-06-09-a/swift-DEVELOPMENT-SNAPSHOT-2017-06-09-a-osx.pkg),
and the July 10 2017, swift-4.0-branch Linux snapshot is
at
[https://swift.org/builds/swift-4.0-branch/ubuntu1604/swift-4.0-DEVELOPMENT-SNAPSHOT-2017-07-10-a/swift-4.0-DEVELOPMENT-SNAPSHOT-2017-07-10-a-ubuntu16.04.tar.gz](https://swift.org/builds/swift-4.0-branch/ubuntu1604/swift-4.0-DEVELOPMENT-SNAPSHOT-2017-07-10-a/swift-4.0-DEVELOPMENT-SNAPSHOT-2017-07-10-a-ubuntu16.04.tar.gz).
While such snapshots have asserts enabled -- so they do not entirely match
the performance characteristics of release compilers -- it is often the
case that a regression in a release compiler will still show up in an
assert compiler, and downloading snapshots to narrow a regression range can
often be much faster than building multiple compilers. Once you've narrowed
a regression range to within a few days (or however far you can get with
snapshots alone), you will likely also need to switch to bisection using
`git bisect`, which can semi-automate or totally-automate the remaining
search, depending on how much shell scripting you want to do and how
precisely you're able to measure the difference. See the section on
`git-bisect` for details.
10. File or fix the bug! You have everything necessary at this point, and if
you can't see how to fix the bug yourself, you should have enough
information to hand it off to the person whose change caused the
regression; they can usually make short work of fixing it (or at worst,
consider whether to just revert the culprit revision). You should include
in the bug report:
- A reduced single-file testcase to feed to a single frontend job
- A bisected culprit revision
- Evidence (in the form of a profile and/or change in counters) of a
definite performance problem caused by that revision, on that testcase.
#### Driver diagnosis
One special area where things rarely go wrong, but can be quite serious when
they do, is in the driver process orchestrating the frontend jobs. A sure sign
that something is amiss in the driver is when running the same compilation
scenario, from the same incremental state, but on different compilers, produces
a different set of frontend jobs (as seen by `-driver-time-compilation`).
To diagnose a driver problem, several additional diagnostic flags exist:
`-driver-print-actions`, `-driver-print-bindings`, `-driver-print-jobs`,
`-driver-show-incremental`, and `-driver-show-job-lifecycle`. By carefully
comparing these, one can sometimes determine the difference in
dependency-analysis and job-execution logic, between one compilation and
another.
It is usually also helpful to look at the `.swiftdeps` files generated by the
driver. These files contain the driver's summary-view of the dependencies
between entities defined and referenced in each source file; it is from these
files that the driver decides when a file "needs" to be rebuilt because it
depends on another file that needs to be rebuilt, and so on transitively. The
file format is [documented here](DependencyAnalysis.md).
### Finding areas in need of general improvement
If you're not hunting a particular regression, but just trying to improve some
problem area in the compiler in general, you usually want to focus on _sorting_
costs rather than _isolating_. That is: you'll want to use the tools discussed
above (profilers, timers, counters, etc.) to pick off the _largest_ cost-centers
in a problem area, and work on those first.
Sorting only tells you where a cost center is, though, not whether that cost
center is _reasonable_. That is, it's often helpful to try to differentiate
cost-centers that "should" be expensive (because they're compiling a lot of
code) from cost-centers that "shouldn't" be expensive (but are, because they
have a bug or design flaw). One tool that's useful for differentiating these
cases is the `utils/scale-test` script.
Scale-test runs on counters, so it's worth taking a short digression into
the set of counters that exist in the Swift compiler and how they fit together.
#### Compiler counters
The Swift compiler has two separate (though related) subsystems for counting
the work it does.
1. The LLVM `STATISTIC()` system included by `#include "llvm/ADT/Statistic.h"`
and lightly wrapped by `#include "swift/Basic/Statistic.h"`. This system
consists of macros and helper structures for atomic, static counters that
self-register in a global list. This subsystem is shared with Clang and
LLVM in general, and so decisions about whether to enable or disable it
(or indeed, conditionally compile it out) are typically shared across all
three projects. In practice, most of these definitions are compiled-out of
a non-assert build, because the level of atomic counting and memory-fencing
is considered inappropriate and potentially too expensive to count inner
loops in production builds. When present, these counters are reported
by `-Xfrontend -print-stats`
2. The Swift-specific `UnifiedStatsReporter` system also included by
`#include "swift/Basic/Statistic.h"`. This (newer) system consists of a
Swift-specific struct full of counters passed around between subsystems
of interest. These counters are _always compiled-in_ to a Swift build,
regardless of build setting. As such, should have _negligible cost_
when not counting/reporting: as much as possible, access is arranged
to either involve a non-atomic operation (in an inner loop) or a single
high-level check before a batch of measurements (outside a loop). These
counters are reported by `-stats-output-dir <dir>`
The `UnifiedStatsReporter` system has `Unified` in its name partly because it
_subsumes_ the other statistic and timer reporting systems in LLVM: it merges
its counters with any LLVM `STATISTIC()` counters that existed in the current
build, as well as any timers in the compiler, when reporting. Thus whenever
possible, you should rely on the output from this subsystem by passing
`-stats-output-dir <dir>` and parsing the resulting JSON files; it will always
be as good as the output from the `STATISTIC()` counters, if they're present.
#### Scale-test
This script works with parametrized templates of code (in the same `gyb` format
as other generated code in the compiler), repeatedly instantiating the template
with larger and larger parameter values, and measuring the relationship between
the input parameter value and the outputs of the compiler counters.
The `utils/scale-test` script works with the same counters inside the compiler
as the `-Xfrontend -print-stats` option mentioned above, so it should be used
with an assert compiler. It works in concert with the `utils/gyb` boilerplate
code-generation tool. The process is straightforward:
1. Write a small `.gyb` file that contains a code pattern that can be varied
by varying a numeric input parameter called `N`. For example, the
following file (taken from the testsuite) varies the number of nested
dictionaries:
```
private let _: [Any?] = [[
%for i in range(0, N):
"A": [
"B" : "C",
%end
%for i in range(0, N):
]
%end
]]
```
2. Run the file under the `utils/scale-test` script. You will at least need to
pass a `--swiftc-binary` and `.gyb` template filename; by default, it will
test on values of `N` ranging from `10` to `100` in steps of `10`, and fit
scaling curves to _all_ counters that it measures, printing any that scale
worse than `O(n^1.2)`. For example, the following will give an initial
survey of the script above:
```
$ utils/scale-test --swiftc-binary=/.../usr/bin/swiftc test.swift.gyb
O(n^0.0) : BasicCalleeAnalysis.computeMethodCallees
O(n^0.0) : Clang module importer.NumTotalImportedEntities
O(n^0.0) : Constraint solver largest system.LargestNumDisjunctionTerms
O(n^0.0) : Constraint solver largest system.LargestNumDisjunctions
...
O(n^1.0) : regalloc.NumCopies
O(n^1.0) : isel.NumFastIselSuccessIndependent
O(n^1.0) : regalloc.NumLoads
O(n^1.0) : Constraint solver overall.NumSolutionAttempts
O(n^1.9) : Constraint solver overall.TotalNumTypeVariables
O(n^2.0) : Constraint solver overall.OverallNumComponentsSplit
O(n^2.0) : Constraint solver largest system.LargestNumComponentsSplit
...
```
3. Focus in on a single problematic counter if you see any, and make a
regression scale-test -- a file with a `// RUN: %scale-test` line --
that runs in as little time as possible while still capturing the
scaling pattern. Adjust the scaling ranges with `--begin`, `--end`,
`--step` and the counters selected with `--select`. It can be helpful to
pass `--values` to see the values being extracted. Scale-test uses a
numerical nonlinear optimizer that needs at least 4 or 5 data points to fit
a curve properly, and will generally do better with 6 or 7 points. By
default, `utils/scale-test` will exit `1` (in error) if it fits a scaling
curve worse than `O(n^1.2)`, but this threshold can be adjusted up or down
to fit the scenario using `--polynomial-threshold` or
`--exponential-threshold`.
4. Add the test to the regression suite. If you're testing a case that you
have a fix for, commit the case along with the fix as a positive case, that
passes (i.e. shows the bug is fixed). If you're testing a case you do _not_
yet have a fix for, add a case with `// RUN: %scale-test --invert-result`
and leave it as essentially an XFAIL for others to look at: a test that
shows how the current code _scales badly_.
5. If you did _not_ find a problematic counter, it's still important to write
and commit a testcase, since it will be able to catch _future_ regressions
if the compiler ever starts scaling poorly in the area you've tested. In
general, the more scale tests, the more likely performance regressions will
be prevented.
6. If you do not see a counter covering a function in the compiler you're
interested in the scaling behaviour of, by all means add a new one!
Statistics are easy to add to a file, it takes only a few simple steps:
- Add a define like `#define DEBUG_TYPE "subsystem-name"` to the file
- Add an include like `#include <swift/Basic/Statistic.h>` to the file
- Add `SWIFT_FUNC_STAT;` to the first line of a function to measure
- Optionally, add separate `STATISTIC(SomeStat, "description");`
definitions and manually increment `SomeStat++;` where you like;
`SWIFT_FUNC_STAT;` is just a short-form of declaring and incrementing a
local `STATISTIC()` named by the function.
## How to report bugs most usefully
The three components that make a performance bug easiest to act on are:
1. A reduced testcase that reliably reproduces the problem
2. A revision range where it started going wrong
3. Measurement of how it's going wrong, numerically
If you can't get to #2 or #3, at least try for #1. The smaller the testcase the
better: a single file or even a single function is ideal, if you can run a
reducer. Much of the work a compiler engineer has to do when diagnosing a bug is
just reproduction and reduction, which does not take much knowledge of the
internals of the compiler, just time and patience.
## How else to help out if you want to improve compile times
- File bugs with reduced testcases and culprit revisions, if you see a
regression.
- If you can understand such a bug well enough to fix it, open a pull request
with the fix! Straightforward fixes to performance regressions are likely to
be merged straight away.
- Add `STATISTIC()` or `SWIFT_FUNC_STAT`-type counters to the compiler, as
described in the scale-tests section. Alternatively, if you want a
counter that will be "always available" in production builds (and
potentially tracked by Apple's performance-tracking CI system),
add a counter to `UnifiedStatsReporter`.
- Add scale-tests, to eliminate the possibility of the compiler performing
quadratic-or-worse work where it's expected to be linear, or linear-or-worse
work where it's expected to be constant.
- Add Open Source projects to the
[source-compatibility testsuite](https://swift.org/source-compatibility/).
Apple's internal CI infrastructure is now tracking selected non-assert-build
`UnifiedStatsReporter` counters on those projects, and the team is far
more likely to catch a regression if it's shown by a project in the testsuite.
- If you're comfortable making changes to the compiler itself, and don't have
a specific testcase you're concerned with, consider working on some of the
known problem areas listed above. Get in touch with the people regularly
working on those areas and see if there's some set of tasks you can look
at. Improvements add up!
Reference in New Issue View Git Blame Copy Permalink