Performance of prefix(while:)

It seems that limiting an iteration with prefix(while:) is significantly slower than testing the condition with an if-statement.

As an example, take these two (functionally identical) prime checking functions (implemented for n >= 2 only):

func isPrime1(_ n: Int) -> Bool {
    for j in 2... {
        if j * j > n { break }
        if n % j == 0 { return false }
    }
    return true
}

func isPrime2(_ n: Int) -> Bool {
    for j in (2...).prefix(while: { $0 * $0 <= n }) {
        if n % j == 0 { return false }
    }
    return true
}

I measured the performance with

do {
    let start = Date()
    let b = isPrime1(1000000000000037)
    let end = Date()
    print(b, end.timeIntervalSince(start))
}
do {
    let start = Date()
    let b = isPrime2(1000000000000037)
    let end = Date()
    print(b, end.timeIntervalSince(start))
}

on a 1.2 GHz Intel Core m5 MacBook, compiled with Xcode 9.3.1 in the Release configuration. The result was approximately

isPrime1:  0.35 sec
isPrime2:  0.88 sec

i.e. the prefix(while:) version is slower by a factor greater than 2.

I wonder if that is to be expected, and if there is a way to use the sequence manipulator without losing performance.

1 Like

You could go full functional:

func isPrime3(_ n: Int) -> Bool {
  return (2...).lazy
    .prefix { $0 * $0 <= n }
    .reduce(true) { $0 && n % $1 != 0 }
}

My results using your benchmarking code:

isPrime1: true 0.25676703453064
isPrime2: true 0.688589096069336
isPrime3: true 0.274294972419739

It's not negligible, but it's a bit closer

Actually, just making the original version lazy makes it faster:

func isPrime2(_ n: Int) -> Bool {
    for j in (2...).lazy.prefix(while: { $0 * $0 <= n }) {
        if n % j == 0 { return false }
    }
    return true
}

Result:

true 0.199643969535828
true 0.198938012123108
1 Like

Wow, that is interesting! Being lazy is faster! – Can that be explained?

Being lazy seems to be the magic, as Jon also noticed. I would write the “fully functional” version as

 func isPrime3(_ n: Int) -> Bool {
    return !(2...).lazy
        .prefix(while: { $0 * $0 <= n })
        .contains(where: { n % $0 == 0 })
 }

so that it early-returns if a divisor is found.

1 Like

Lazy means that the value in the subsequence produced by prefix(while:) aren't actually produced until you try to access them, allowing the loop to perform as if you weren't producing a subsequence at all, like in the first example.

2 Likes

I had (wrongly) assumed that (2...).prefix(while:) produces the values lazily. That is not the case, as you demonstrated.

Thanks to both of you for the feedback and the clarification!

Yes, Swift isn't lazy by default, unlike most truly functional languages.

... which means that

for x in (1...)
    .prefix(while: { $0 > 0 })
    .prefix(while: { $0 < 10 }) {
    print(x)
}

does not print anything, and never terminates.

Actually SE-0045 Add prefix(while:) and drop(while:) to the stdlib states this clearly:

These default implementations produce an AnySequence that wraps an Array (as the functions must be implemented eagerly so as preserve the convention of not holding onto a user-provided closure past the function call without the explicit appearance of .lazy).

I should have read the details.