1

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
2

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

3

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
4

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

5

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
6

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
7

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!

8

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

9

... which means that

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

does not print anything, and never terminates.

10

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.