swiftperformancerange

Why is ClosedRange<Int>.contains 3.4 million times slower than expected?


The contains method in a ClosedRange in Swift seems very slow.

I create the following Swift Playground on macOS for testing:

import Foundation

func measure(fn: @escaping ()->Void) -> CFAbsoluteTime {
    let startTime = CFAbsoluteTimeGetCurrent()
    fn()
    let endTime = CFAbsoluteTimeGetCurrent()
    return endTime - startTime
}

let r1: ClosedRange<Int> = 1222450723...1308640992
let r2: ClosedRange<Int> = 41218238...462709950

let dt_a = measure { let _ = r1.lowerBound <= r2.lowerBound && r1.upperBound >= r2.upperBound }
let dt_b = measure { let _ = r1.contains(r2) }

Shouldn't the contains method simply do the range comparison I'm doing for dt_a in the code above?

  • dt_a gives me 95 microseconds, whereas
  • dt_b gives me 326.9 seconds (~5.45 minutes)

That's 3.4 million times slower than expected.

It would seem that it's checking all the values in the range, which doesn't make sense. Could it be a bug in Swift? Or is this the expected behavior?

I'm using Xcode 15.0.1 (Swift 5)

(*) Note: for context, I found this while solving Part 2 of 2023 Advent of Code Day 5

In a real project, Release build with optimizations turned on (Optimize for speed [-O]), dt_b gave me 356 seconds, worse than in Playgrounds...


Solution

  • ClosedRange<Int> conforms to Collection, and the contains you are calling is this method from Collection:

    func contains<C>(_ other: C) -> Bool where C : Collection, Self.Element == C.Element
    

    This checks if self contains all the elements in other. Notice that other is an arbitrary Collection. This method is not specifically for ranges. ClosedRange<Int> uses the default implementation of this method, so there is no special cases for ranges. The default implementation goes through every element of other and checks if they are in self.

    In other words, there is no built-in method specifically for checking whether one range contains another. See this post for other ways of writing such a method yourself.