This post summarizes a few strategies I used to make performance improvements to the Swift and Swift Core Libs projects. Instruments is used to profile performance. If you are not familiar with Instruments (part of Xcode) check out this Instruments Overview.

Copy-on-write Mechanics

Swift uses copy-on-write mechanics to copy structs that are mutated to in order to preserve correctness. A brief example:

// Create an array
var arr: [Int] = [0,1,2]

// Create another array
var newArr = arr

// At this point in execution, both arr and
// newArr point to the same object

// Mutate newArr by appending 3
newArr.append(3)

// The mutating call triggers a copy in order
// to preserve correctness. Since newArr and
// arr differ, they now point to different objects

Copy-on-write mechanics can also be used to increase performance. In the case of IndexSet.union, an existing implementation used two for loops to insert items from set A and set B into a resulting set C.

However, this implementation is redundant. There is no need to add items from both A and B into a new set. A faster implementation that uses copy-on-write mechanics starts by assigning the denser of set A or B to a new variable, then inserting the items from the sparser set.

In this scenario Swift will copy the denser set on the mutating insert call, a more performant operation than repeatedly inserting items from the denser set into a new set. I wrote more about improving IndexSet.union performance in another post: Making IndexSet.union Faster In Swift.

Loop Unraveling

Loop Unraveling is a general strategy that can be used in cases of staggered computation. The objective is to move computation closer to the point of need to avoid doing unnecessary work.

One example of this occurred in an implementation of NSIndexSet.isEqual. First, a map was performed to turn an internal range representation into a list of NSRange. Then if the set self and set other had an equal number of ranges, a for loop is used to check if each range in both sets are equal.

The major performance opportunity in this implementation is to unravel the map loop and integrate the computation into the for loop. Instead of performing the map up front, the same result will be computed sequentially at each step of the for loop. Since the for loop will exit early if internal range representations do not match, this may save significant computation.

To see the code and learn about another performance improvement within the same previous implementation, check out: Making NSIndexSet.isEqual Faster in Swift.

Early Exits

Early exits are easy to spot when code has a specific set of prerequisites before beginning more resource intensive computation. These early exits stem from processes and workflows.

Early exits stemming from algorithmic logic are harder to spot, and often overlooked. One such instance isSubset implementation for NSSet and NSOrderedSet.

One implementation of isSubset that perserves correctness is to check if each item of set A is also in set B. This was the existing implementation within the Swift Core Libs project.

Logically, we known that if set A is larger than set B then A cannot be a subset of B. Using this condition to create an early exit can significantly improve performance where we know isSubset should return false due to set A being larger.

Dive deeper into the performance impacts of adding an early exit to NSSet and NSOrderedSet: Making isSubset Faster For Sets In Swift.