This post will dive into a PR I made to the Swift Core Libs project that improves the performance of NSIndexSet.isEqual. Instruments is used to profile performance. If you are not familiar with Instruments (part of Xcode) check out this Instruments Overview.

Previous isEqual Implementation

Internally, an NSIndexSet is represented as a collection of Range structs that together span the collection of integer values in the set. Determining if two NSIndexSet objects are equal is reduced to determining if the internal range representations are equal. The existing implementation accomplished this by mapping each Range from self to NSRange, then performing a comparison for each NSRange between self and indexSet.

open func isEqual(to indexSet: IndexSet) -> Bool {
    
    let otherRanges = indexSet.rangeView.map { NSRange(location: $0.lowerBound, length: $0.upperBound - $0.lowerBound) }
    if _ranges.count != otherRanges.count {
        return false
    }

    for (r1, r2) in zip(_ranges, otherRanges) {
        if r1.length != r2
            return false
        }
    }

    return true
}

Identifying The Performance Improvement

One strategy for identifying performance improvements is to look for cases where an exit condition can be moved earlier. Here, a map iterates through all ranges in indexSet.rangeView and creates NSRange structs.

In cases where the range count does not match, the entire map operation is wasted computation. This creates an opportunity to move map closer to the point of need: the loop comparing the two range collections.

Faster isEqual Implementation

The map operation can be unraveled and moved into the comparison loop, avoiding the map operation entirely if the range counts are unequal:

open func isEqual(to indexSet: IndexSet) -> Bool {
    // Exit early if the IndexSets do not have the same number of intervals
    if _ranges.count != indexSet.rangeView.count {
        return false
    }

    // Iterate over indexes to compare each
    for (range, element) in zip(_ranges, indexSet.rangeView) {
        let elementLength = element.upperBound - element.lowerBound

    // Return false if the ranges do not match
        if range.location != element.lowerBound || range.length != elementLength {
            return false
        }
    }

    return true
}

The performance improvement is significant in all cases. In cases where the NSIndexSet objects do not have an equal range count, the performance improvement is unbounded (a map operation is replaced with a fixed count comparison).

In cases where the NSIndexSet objects need to be compared using the for loop, a 250% speedup is observed when profiling with sets of 100, 1,000, and 2,000 ranges.