Demystify parallelization in Xcode builds

♪ ♪ Hello, and welcome to WWDC 2022. My name is Ben, and I'm an engineer on the Xcode build system team. Hi, my name is Artem, and I'm an engineer on the Swift Compiler team. In this talk we're gonna give you a deep dive into Xcode's build process to demystify parallelization inside builds. Ben is going to start with an introduction of the core concepts about builds and look at the available tools that Xcode offers to help investigate build performance issues. He will then explain how Xcode increases parallelization while building a target. Building on top of that, I will explain how Xcode parallelizes a build holistically while building projects consisting of many targets and summarize the takeaways in the end. Ben? Let's re-iterate on what happens when pressing CMD+B in Xcode to build an app. The build system, as part of Xcode, gets invoked with a representation of the whole project, including all source files, assets, build settings, and other configurations like the run destination. The build system is the single source of truth about how an app should be built. It knows which tools to invoke using which settings and which intermediate files to produce to eventually create an app. In the next step, the build system invokes the tools to process the project's input files, for example, the compilers.

Both compilers, Clang and Swift, will produce object files that the linker needs to link the executable program that represents the app. While this order makes sense, it's not obvious where it comes from. So let's take a look at one example of that process and how the build system decides in which order to execute all tasks.

Using the input source-files, the Swift compiler captures the programmer's intent and translates it into a machine-executable binary, checking the source code for errors along the way. This process can fail, which would cancel the build, but if it succeeds, it creates an object file for each input. Those object files are used to invoke the linker which combines them and adds references to externally linked libraries to produce the executable. The two tasks have a dependency based on what they consume and produce. The object files produced by the compiler get consumed by the linker. This creates a dependency on the build system graph. The file contents itself are not of interest to the build system, but the dependency between the tasks is. While executing the build, it needs to make sure that a task that produces another task's input finishes before said task can start. And since this core concept is valid for all kind of tasks, let's switch to a more generic visualization that shows a dependency between Task A and Task B. In this case, A produces some or all of B's inputs.

Compiling and Linking are only a few of many different task types that need to be executed to build a whole target, so let's add some more generic tasks to the graph that represent other types like compiling assets, copying files or codesigning. Together, they represent building a Framework target. Again, those tasks have defined dependencies based on their inputs and outputs. So completing executing task A unblocks running task B and C, while finishing task B unblocks task D and E. Tasks that get unblocked are called 'downstream' and tasks that block 'upstream'. Many projects contain more than one framework target, so let's add two more targets representing an app and an app extension. Targets define dependencies between each other in the project via explicit or implicit dependencies. For example, by getting added to the 'Link Binary with Libraries' build phase.

In this case, the app embeds the app extension and links against the Framework. The app extension is not using the Framework, so they don't have a dependency relationship.

When executing the build graph, different tasks take a different amount of time. This comes down to the level of complexity that is necessary to complete the work, depending on the computation that's needed as well as the size of the input. Compiling many files takes usually much more time than copying a few header files, and taking this into consideration will end up with something like this. When the build system executes this build, it starts by running tasks that don't have dependencies. And once those completed, they unblock downstream tasks and so on, following this process until all planned tasks finished.

On following builds, the build system is able to skip tasks for which inputs haven't changed while the output is still up to date. If a task needs to re-run due to a changed input, like B of the App target in this case, downstream tasks have to re-run too if its output changed. Skipping all other tasks allows for very fast turnaround times when iteratively working on the project. This is called an incremental build, but let's stick to full builds for now.

The dependencies and duration of the task execution defines the first possible time a downstream task can start. With this information it's possible to calculate the critical path which is the shortest time the build needs to run with theoretical unlimited resources. A common pattern throughout this talk will be to shorten this path to create a highly parallelizable and scalable build graph. A shorter critical path does not necessarily result in a shorter overall build time, but it ensures that the build scales with the hardware. The critical build path defines the limiting factor of how fast a build can be– it cannot complete faster, even if the hardware would allow it. Shortening the critical path is done by breaking up dependencies within it. When looking at how a build performed and to understand more about its execution, the data needs to be plotted based on the time they executed. The width still indicates the length of tasks. Wide elements like these two indicate a long running task while narrow elements like these represent fast finishing tasks.

The height of the graph shows the number of parallel executing tasks at a given time. Be aware that this does not directly map to CPU or memory utilization.

Empty space originates by tasks blocking its downstream tasks like in those two scenarios. And finally, the color of the elements represent their associated target. I'm very excited to announce that this visualization is new in Xcode 14 and will help understand a build's performance after it finished. The Xcode Build Timeline is a great new addition to the build log. It visualizes based on parallelization, rather than hierarchy to understand the build's performance. The number of rows at given time represents the level of parallelism during that time. The horizontal length of individual tasks represent the duration they needed to finish their work. Empty space in the graph shows where unfinished tasks blocked downstream tasks from starting to execute. Different colors applied to the timeline elements help distinguish the different targets that were part of the build. And on incremental builds, the timeline will only contain tasks that got actually executed, allowing to spot long-running tasks, especially ones which might not have been expected to run during this build.

Here's a demo of the Build Timeline in Xcode 14. In this window I opened a copy of the swift-docc project from Github which builds the documentation compiler. To get an overview about the targets that are built for the scheme, let's check out the scheme editor. To open that I click on the scheme and select "Edit scheme".

The 'build' tab contains a list of all targets. Targets can explicitly get added to the scheme or implicitly by being a dependency of a target that is already part of the scheme. In this case I'm using a Swift package with an automatically generated scheme for the package, so all targets from the manifest are explicitly defined.

This log represents a build of that scheme that I executed earlier. In contains entries for all tasks that the build system executed. The entries are organized in a hierarchy based on the targets they belong to, like the 'docc' target here. To successfully build the executable of that target, Xcode ran all tasks that are represented by the children of this node. Since the build log is currently in its 'All' state, it also shows tasks from previous builds that didn't need to re-run in an incremental build. Selecting 'Recent' only shows tasks that got actually executed, hiding all skipped tasks. In addition to that, the build log also supports filters to only show tasks that had issues or even failed.

To open the build timeline for this build, I go to the editor options and open the assistant. The build timeline opens next to the build log. Like usual, the editor options provide settings to show the assistant on the right or bottom. I'll stay with bottom for now. The timeline visualizes the same data as the 'recent' build log based on the parallelization of the build. Selecting an element in one also selects it in the other. This enables to see a task's execution in context. The timeline here gives a sense about the tasks that executed in parallel to the selected task. I'm using a pinch gesture on the trackpad to zoom out again.

Selecting an element in the timeline shows it in the build log. And since the build log visualizes based on the hierarchical structure, it enables to view which files were compiled as part of this compiler invocation. It also enables to view the whole command line of that invocation.

Holding down Option while selecting an area in the build timeline adjusts the view port to fit this timeframe. Here we can verify that linking of the target ArgumentParser is in fact waiting for compilation of the same target. Holding Option while scrolling up allows me to zoom out quickly. The number of rows in the timeline represents the number of tasks that ran in parallel at that time. An empty space like this indicates tasks waiting for un-produced inputs. Ideally, the timeline is vertically filled and has as little empty space as possible. This scales the build graph the best and makes builds faster, the faster the hardware. To achieve this, Xcode comes with many improvements this year to shorten the critical path. Next, let's check out how Xcode defines and builds individual targets as well as how it can increase parallelization. When configuring a target, build phases describe the work that needs to be done to produce that target's product. They are defined in the project editor and can contain a set of source code files and assets to compile, files that need to be copied like headers or resources, as well as libraries that should be linked or scripts that should be executed. Many build phases describe tasks with inputs or outputs from other build phases, creating dependencies between them. For example, a target's source files must be compiled before it is linked. However, this doesn't apply to all build phases. Instead of running tasks from each build phase in a linear order, the build system will consider the inputs and outputs of build phases to determine if they can run in parallel. For example, Compilation and Resource copying can run in parallel because neither depends on any outputs of the other. However, linking must still follow compilation because it depends on the object files produced by that phase. Now, let's consider a different target which contains 'Run Script' build phases. Unlike other build phases, the inputs and outputs of script phases must be manually configured in the target editor. As a result, the build system will run consecutive script phases one at a time to avoid introducing a data race in the build process. If the scripts in a target are configured to run based on dependency analysis and specify their complete list of inputs and outputs, then the build setting FUSE_BUILD_SCRIPT_PHASES can be set to YES to indicate the build system should attempt to run them in parallel. However, when running script phases in parallel, the build system has to rely on the specified inputs and outputs. So be aware that an incomplete list of the inputs or outputs of a script phase can lead to data races which are very hard to debug. To mitigate this, Xcode supports user script sandboxing to precisely declare the dependencies of each script phase. Sandboxing is an opt-in feature that blocks shell scripts from accidentally accessing source files and intermediate build objects, unless those are explicitly declared as an input or output for the phase. In this example, neither input nor output.txt are declared as a dependency for that script phase. The sandbox will block the script from reading and writing to both files when building the project. When the script violates the sandbox, it will fail with a non-zero exit code causing the build to fail. In addition to that, Xcode will list all the paths that the script phase was trying to access without properly declaring them. Adding both files as dependency information to this script phase fixes this issue. This way the sandbox ensures that the script is not mistakenly accessing any file other than its declared inputs and outputs. Now, let's explore an example with more than one script phase and see how sandboxing prevents data races and incorrect builds. There are two script phases. The first one reads a text file, calculates a checksum of its content, and writes that value to an intermediate file in DERIVED_FILE_DIR. The other script reads the same text file as well as the produced checksum and injects them into an html file for later display in the app. If the precise set of input and output dependencies for these phases is not declared, Xcode will run the two scripts in parallel when FUSE_BUILD_SCRIPT_PHASES is on. Let's inspect this problematic scenario in detail. Let's assume "Generate HTML" is missing the input declaration of "checksum.txt", but all other inputs and outputs of both scripts have been correctly declared. Without sandboxing, this misconfiguration might stay unnoticed, causing problems in the build. It means Xcode will fail to infer the dependency relation between both phases, and schedule to run them in parallel when FUSE_BUILD_SCRIPT_PHASES is switched on. There are a few hazards here. Since checksum.txt is not listed as an input dependency for "Generate HTML" during a clean build the script will attempt to read the file without it being available on the filesystem. The other hazard is if checksum.txt is available on disk because of previous runs of "Calculate Checksum", "Generate HTML" may pick up the outdated file when the two scripts run in parallel. This is a user error, and executing the scripts in a sandbox helps preventing this issue. With sandboxing switched on, "Generate HTML" will fail immediately when it attempts to read "checksum.txt". The error message will guide adding the missing input for that build phase. Having the inputs and outputs correctly defined guides Xcode to respect the dependency relation between both phases so that "calculate checksum" runs before "Generate HTML". While unrelated build phases can still execute in parallel. To enable Sandboxed Shell Scripts for a target, set ENABLE_USER_SCRIPT_SANDBOXING to YES in the build settings editor or an xcconfig file. In summary, sandboxed shell scripts allow having correct dependency information to enable faster and more robust incremental builds since the build system has the confidence to skip script phases if the inputs haven't changed and the outputs are still valid, while re-running the script otherwise. Enabling the build setting for a script's target blocks access to files inside the source root of the project as well as the derived data directory if they are not explicitly defined as inputs or outputs of the script in the project. The sandbox will not prevent unauthorized access to any other directory, so don't consider this a security feature. Using this feature helps to debug missing inputs or outputs of existing script phases to ensure a valid configuration And in combination with the previously explained build setting FUSE_BUILD_SCRIPT_PHASES, script phases with correctly defined dependency edges through sandboxing can execute in parallel to reduce the critical path of the build. That's it for parallelizing the steps of building a target. Now Artem is going to demystify parallelization hen building many targets. Artem: Thanks, Ben. Now that we've covered the basics of build system tasks and phases that may go into building a target in your project, let's take a more global view and explore how Xcode uses dependencies between Swift targets to extract the maximum amount of parallelism out of your builds and how the structure and organization of your project can affect build times. There are likely to be several levels of hierarchy composing your project. For example, an App target depending on a collection of local libraries broken up into targets along semantic boundaries, and in several frameworks. Each target containing many different build phases and steps, producing and consuming file dependencies to and from build phases in other targets. As the size of your project grows, these task graphs tend to increase in size and complexity. While the Xcode Build System flattens these hierarchies, breaking down the build into a sea of tasks that correspond to build phases of all targets. One kind of task that is special for a Swift target is compilation. Building a Swift target's source code into binary product's is a complex operation that typically consists of many sub-tasks for build planning, compilation, and linking. Coordination of these tasks is delegated to a specialized tool in the Xcode toolchain– the Swift Driver. The Driver has specialized knowledge on when and how to construct the required compiler and linker invocations for the target's source code. Any target that includes Swift code also corresponds to a unit of code distribution: a module. A binary module file capturing the public interface of this target is a build product that is required for downstream targets to begin a compilation. Let's take a closer look at an example of what Swift Driver does to build one of the targets. Your target probably consists of a collection of several source files. In release or optimized builds the driver will schedule one compiler task including all source files to maximize opportunities for optimization. This single compile task will also produce the target's Swift module. In debug or incremental compilation modes, the Swift Driver breaks down the required compilation effort into smaller sub-tasks which can run in parallel, some of which may not need to re-run on an incremental build. Producing a Swift module then requires an additional step to merge together partial intermediate products of each compile task. If, like in this example, the number of source files in your target is high, individual files may also be assigned to batch compilation sub-tasks, according to the build-system's heuristics. The build log highlights which source files get assigned to batch compilation jobs, with a separate entry for each file's diagnostics. Being able to parallelize a target's build across different source files is crucial for both faster and smaller incremental builds, so make sure your Debug builds are using the Incremental Compilation Mode setting. Before Xcode 14, because of the boundary between the Xcode Build System and Swift Driver, orchestration of target build phases, and compilation sub-tasks spawned by each target's instance of the Driver happened independently of each other, with each component doing its best to make the most of available system resources. Let's take this example build graph and dive deeper into what goes into scheduling its compilation phases with respect to each other. As we've learned earlier, Swift target dependencies are resolved by having their dependents provide a binary module file that captures the dependent's public interface. Resolving these dependency relationships leads us to the following ordering, captured in a timeline showing the top-level Swift Driver tasks for each target, as well as their individual sub-tasks. With Xcode 14, thanks to an entirely new implementation of Swift Driver– itself now written in Swift– the build system and the compiler are fully integrated. The Xcode Build System acts as the central scheduler for all tasks that must be performed to compile your code. This central planning mechanism allows Xcode to make fine-grained scheduling decisions providing better guarantees that building your project will use only as much resources as available, without oversubscribing your CPU and reducing overall system performance.

And what was previously a collection of islands of sub-tasks outside of Xcode Build System's purview are now fully in a domain of the build-system's scheduler.

With all the individual sub-tasks in a central task pool, it is important to consider the trade-offs made by the build scheduler. For example, on an 8-core machine the scheduler's default is to assign available tasks– those tasks whose dependencies have been satisfied and are ready to go– to one of eight available execution slots. As soon as one of the slots frees up, the Build System attempts to fill it with more outstanding work. On a higher-core-count machine, we're able to perform more concurrent work. But that means we're also more likely to have idle cores which are available to perform more work, but all of the outstanding tasks are still awaiting their inputs, as produced by other tasks that are currently in-flight or waiting. The new integrated build system allows the scheduler to significantly reduce this idle time. To see how, let's revisit how a target's dependencies for compilation, binary module files, are resolved.

As we've covered earlier, the partial results of compilation sub-tasks are merged into a target's final module product. Once this product is available, downstream targets may begin compilation. New in Xcode 14 and Swift 5.7, construction of a target's module is done in a separate emit-module task directly from all program source files. This means a target's dependencies can begin compilation as soon as the emit-module task is complete without waiting for all of the other compiler tasks of the dependency target. Being able to unblock downstream target compilation this much sooner cuts down on the time spent waiting for available work with idle CPU cores– that empty space in between spurs of activity in the build timeline.

Extending this to the rest of our project shows that although we are performing a similar amount of overall work, the build system is able to use the computer's resources more efficiently, often completing the build significantly faster.

Now, let's take a look at a second cross-target optimization the build system can perform when building Swift– Eager Linking. Building on the previous example, we've added the linker tasks for each target, which are both on the build's critical path. In this case, because Target B links Target A, Target B's link task must wait for Target A's linked output to be produced and its own compilation tasks to complete before it can run. However, with eager linking, Target B's link task can depend on Target A's emit-module task instead. As a result, Target B can begin linking earlier in the build, running in parallel with linking Target A and shortening the critical path. How does this work? Normally, the dependency graph of two targets with a linked product dependency looks something like this. Linking the dependent target requires the linked product of its dependencies in addition to the target's own compilation outputs. When linking eagerly, this dependency is broken, allowing the dependent target to start linking earlier. Instead of depending on a linked product of the dependency, it now depends on a text-based dynamic library stub produced earlier in the build process by the emit-module task. This stub contains a list of symbols which will appear in the linked product for use by dependents. You can enable this optimization using the Xcode build setting shown on screen. Eager Linking applies to all pure Swift targets that are dynamically linked by their dependents. To summarize, the Xcode Build System is a sophisticated scheduling engine that seeks to extract as much parallelism as possible by running build phases in parallel. And features like Script Sandboxing allow you to ensure your builds are both maximally parallel and reliable. Xcode and Swift are more integrated than ever. And project structure: its modularization, the overall shape of the graph made up of dependencies between target products and the number and complexity of build phases within them, combined with the available computational resources of your machine– all these are contributing factors to the degree Xcode is able to parallelize and speed up your builds. With this knowledge, and powerful new tools like the build timeline, you are well equipped to examine your project and gain insight into your builds. And if you're curious to learn even more of the behind-the-scenes technical details, many of the technologies we described that are used by Xcode are developed in the open-source. You can find the repository for Swift Driver on GitHub at the link below. For more great sessions about Xcode, check out all new features and improvements from this year in "What's new in Xcode". And learn how Xcode 14's linker improves link times up to two times in the session "Link fast: Improve build and launch times". Thanks for following along. We hope you learned some new insights about Xcode builds. We can't wait to see what you're going to create. Have a great rest of the conference.