This post will dive into an accepted PR I made to the Swift project that improves the performance of NSSet.isSubset and NSOrderedSet.isSubset. Instruments is used to profile performance. If you are not familiar with Instruments (part of Xcode) check out this Instruments Overview.

Previous isSubset Implementation

The function isSubset(of other:) determines if self is a subset of another set other, meaning all items contained in the set self are also contained in the set other. The existing Swift Foundation implementation used contains(_:) to verify each item is in other, otherwise returning false:

open func isSubset(of other: NSOrderedSet) -> Bool {
    for item in self {
        if !other.contains(item) {
            return false
        }
    }
    return true
}

Identifying The Performance Improvement

Comparison operations frequently contained opportunities to improve performance. In the existing implementation, we notice that the iteration through all items in other is performed on every invocation of isSubset(of other:). Is there a case where this loop does not need to be evaluated?

If self contains more items than other, then isSubset must return false. In the case of many overlapping self and other, exiting early can provide a significant performance improvement.

Faster isSubset Implementation

If self is larger than other, no matter what items other contains isSubset should return false. An if condition can be added to isSubset to exit early in this case:

open func isSubset(of other: NSOrderedSet) -> Bool {
    // If self is larger then self cannot be a subset of other
    if count > other.count {
        return false
    }

    for item in self {
        if !other.contains(item) {
            return false
        }
    }
    return true
}

Exiting early in the case where self is larger than other can save significant computation if the sets overlap. For example, consider a set A with 1001 items and a set B with 1000 items. Further, assume A and B share all items except one.

In this example, the early exit of isSubset can increase the performance of isSubset by over 2,000%.