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.
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
However, this implementation is redundant. There is no need to add items from both
B into a new set. A faster implementation that uses copy-on-write mechanics starts by assigning the denser of set
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 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 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
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
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
NSOrderedSet: Making isSubset Faster For Sets In Swift.