The "Parallel Checkout" feature attempts to use multiple processes to parallelize the work of uncompressing the blobs, applying in-core filters, and writing the resulting contents to the working tree during a checkout operation. It can be used by all checkout-related commands, such as clone, checkout, reset, sparse-checkout, and others.

These commands share the following basic structure:

  • Step 1: Read the current index file into memory.

  • Step 2: Modify the in-memory index based upon the command, and temporarily mark all cache entries that need to be updated.

  • Step 3: Populate the working tree to match the new candidate index. This includes iterating over all of the to-be-updated cache entries and delete, create, or overwrite the associated files in the working tree.

  • Step 4: Write the new index to disk.

Step 3 is the focus of the "parallel checkout" effort described here.

Sequential Implementation

For the purposes of discussion here, the current sequential implementation of Step 3 is divided in 3 parts, each one implemented in its own function:

  • Step 3a: unpack-trees.c:check_updates() contains a series of sequential loops iterating over the cache_entry's array. The main loop in this function calls the Step 3b function for each of the to-be-updated entries.

  • Step 3b: entry.c:checkout_entry() examines the existing working tree for file conflicts, collisions, and unsaved changes. It removes files and creates leading directories as necessary. It calls the Step 3c function for each entry to be written.

  • Step 3c: entry.c:write_entry() loads the blob into memory, smudges it if necessary, creates the file in the working tree, writes the smudged contents, calls fstat() or lstat(), and updates the associated cache_entry struct with the stat information gathered.

It wouldn’t be safe to perform Step 3b in parallel, as there could be race conditions between file creations and removals. Instead, the parallel checkout framework lets the sequential code handle Step 3b, and uses parallel workers to replace the sequential entry.c:write_entry() calls from Step 3c.

Rejected Multi-Threaded Solution

The most "straightforward" implementation would be to spread the set of to-be-updated cache entries across multiple threads. But due to the thread-unsafe functions in the object database code, we would have to use locks to coordinate the parallel operation. An early prototype of this solution showed that the multi-threaded checkout would bring performance improvements over the sequential code, but there was still too much lock contention. A perf profiling indicated that around 20% of the runtime during a local Linux clone (on an SSD) was spent in locking functions. For this reason this approach was rejected in favor of using multiple child processes, which led to better performance.

Multi-Process Solution

Parallel checkout alters the aforementioned Step 3 to use multiple checkout--worker background processes to distribute the work. The long-running worker processes are controlled by the foreground Git command using the existing run-command API.

Overview

Step 3b is only slightly altered; for each entry to be checked out, the main process performs the following steps:

  • M1: Check whether there is any untracked or unclean file in the working tree which would be overwritten by this entry, and decide whether to proceed (removing the file(s)) or not.

  • M2: Create the leading directories.

  • M3: Load the conversion attributes for the entry’s path.

  • M4: Check, based on the entry’s type and conversion attributes, whether the entry is eligible for parallel checkout (more on this later). If it is eligible, enqueue the entry and the loaded attributes to later write the entry in parallel. If not, write the entry right away, using the default sequential code.

Note: we save the conversion attributes associated with each entry because the workers don’t have access to the main process' index state, so they can’t load the attributes by themselves (and the attributes are needed to properly smudge the entry). Additionally, this has a positive impact on performance as (1) we don’t need to load the attributes twice and (2) the attributes machinery is optimized to handle paths in sequential order.

After all entries have passed through the above steps, the main process checks if the number of enqueued entries is sufficient to spread among the workers. If not, it just writes them sequentially. Otherwise, it spawns the workers and distributes the queued entries uniformly in continuous chunks. This aims to minimize the chances of two workers writing to the same directory simultaneously, which could increase lock contention in the kernel.

Then, for each assigned item, each worker:

  • W1: Checks if there is any non-directory file in the leading part of the entry’s path or if there already exists a file at the entry' path. If so, mark the entry with PC_ITEM_COLLIDED and skip it (more on this later).

  • W2: Creates the file (with O_CREAT and O_EXCL).

  • W3: Loads the blob into memory (inflating and delta reconstructing it).

  • W4: Applies any required in-process filter, like end-of-line conversion and re-encoding.

  • W5: Writes the result to the file descriptor opened at W2.

  • W6: Calls fstat() or lstat() on the just-written path, and sends the result back to the main process, together with the end status of the operation and the item’s identification number.

Note that, when possible, steps W3 to W5 are delegated to the streaming machinery, removing the need to keep the entire blob in memory.

If the worker fails to read the blob or to write it to the working tree, it removes the created file to avoid leaving empty files behind. This is the only time a worker is allowed to remove a file.

As mentioned earlier, it is the responsibility of the main process to remove any file that blocks the checkout operation (or abort if the removal(s) would cause data loss and the user didn’t ask to --force). This is crucial to avoid race conditions and also to properly detect path collisions at Step W1.

After the workers finish writing the items and sending back the required information, the main process handles the results in two steps:

  • First, it updates the in-memory index with the lstat() information sent by the workers. (This must be done first as this information might be required in the following step.)

  • Then it writes the items which collided on disk (i.e. items marked with PC_ITEM_COLLIDED). More on this below.

Path Collisions

Path collisions happen when two different paths correspond to the same entry in the file system. E.g. the paths a and A would collide in a case-insensitive file system.

The sequential checkout deals with collisions in the same way that it deals with files that were already present in the working tree before checkout. Basically, it checks if the path that it wants to write already exists on disk, makes sure the existing file doesn’t have unsaved data, and then overwrites it. (To be more pedantic: it deletes the existing file and creates the new one.) So, if there are multiple colliding files to be checked out, the sequential code will write each one of them but only the last will actually survive on disk.

Parallel checkout aims to reproduce the same behavior. However, we cannot let the workers racily write to the same file on disk. Instead, the workers detect when the entry that they want to check out would collide with an existing file, and mark it with PC_ITEM_COLLIDED. Later, the main process can sequentially feed these entries back to checkout_entry() without the risk of race conditions. On clone, this also has the effect of marking the colliding entries to later emit a warning for the user, like the classic sequential checkout does.

The workers are able to detect both collisions among the entries being concurrently written and collisions between a parallel-eligible entry and an ineligible entry. The general idea for collision detection is quite straightforward: for each parallel-eligible entry, the main process must remove all files that prevent this entry from being written (before enqueueing it). This includes any non-directory file in the leading path of the entry. Later, when a worker gets assigned the entry, it looks again for the non-directory files and for an already existing file at the entry’s path. If any of these checks finds something, the worker knows that there was a path collision.

Because parallel checkout can distinguish path collisions from the case where the file was already present in the working tree before checkout, we could alternatively choose to skip the checkout of colliding entries. However, each entry that doesn’t get written would have NULL lstat() fields on the index. This could cause performance penalties for subsequent commands that need to refresh the index, as they would have to go to the file system to see if the entry is dirty. Thus, if we have N entries in a colliding group and we decide to write and lstat() only one of them, every subsequent git-status will have to read, convert, and hash the written file N - 1 times. By checking out all colliding entries (like the sequential code does), we only pay the overhead once, during checkout.

Eligible Entries for Parallel Checkout

As previously mentioned, not all entries passed to checkout_entry() will be considered eligible for parallel checkout. More specifically, we exclude:

  • Symbolic links; to avoid race conditions that, in combination with path collisions, could cause workers to write files at the wrong place. For example, if we were to concurrently check out a symlink a → b and a regular file A/f in a case-insensitive file system, we could potentially end up writing the file A/f at a/f, due to a race condition.

  • Regular files that require external filters (either "one shot" filters or long-running process filters). These filters are black-boxes to Git and may have their own internal locking or non-concurrent assumptions. So it might not be safe to run multiple instances in parallel.

    Besides, long-running filters may use the delayed checkout feature to postpone the return of some filtered blobs. The delayed checkout queue and the parallel checkout queue are not compatible and should remain separate.

    Note: regular files that only require internal filters, like end-of-line conversion and re-encoding, are eligible for parallel checkout.

Ineligible entries are checked out by the classic sequential codepath before spawning workers.

Note: submodules' files are also eligible for parallel checkout (as long as they don’t fall into any of the excluding categories mentioned above). But since each submodule is checked out in its own child process, we don’t mix the superproject’s and the submodules' files in the same parallel checkout process or queue.

The API

The parallel checkout API was designed with the goal of minimizing changes to the current users of the checkout machinery. This means that they don’t have to call a different function for sequential or parallel checkout. As already mentioned, checkout_entry() will automatically insert the given entry in the parallel checkout queue when this feature is enabled and the entry is eligible; otherwise, it will just write the entry right away, using the sequential code. In general, callers of the parallel checkout API should look similar to this:

int pc_workers, pc_threshold, err = 0;
struct checkout state;

get_parallel_checkout_configs(&pc_workers, &pc_threshold);

/*
 * This check is not strictly required, but it
 * should save some time in sequential mode.
 */
if (pc_workers > 1)
        init_parallel_checkout();

for (each cache_entry ce to-be-updated)
        err |= checkout_entry(ce, &state, NULL, NULL);

err |= run_parallel_checkout(&state, pc_workers, pc_threshold, NULL, NULL);