Why are Swift iterators slower than array building

问题:

This is kind of related to this question, where it was assumed that using generators (iterators) to traverse a nested array would be optimal for iterating through the elements, as long as you didn’t need to store the result, while using repeated array concatenation was best if you just wanted to flatten the array.

However, I decided to do some testing, and implementing this function (that flattens an array [Any] containing either Ints or [Int]s) in both lazy and stored form, it turns out the stored form is faster, even when just used for iterating through the elements! That means that somehow, iterating through the generator takes more time than both constructing a new array in memory, and then iterating through that.

Incredibly, it is even about 5–70% slower than a python implementation of the same program, which worsens with smaller input. Swift was built with the -O flag.

Here were the three test cases 1. small input, mixed; 2. large input, [Int] dominant, 3. large input, Int dominant:

Swift

let array1: [Any] = [Array(1...100), Array(101...105), 106, 
                     Array(107...111), 112, 113, 114, Array(115...125)]
let array2: [Any] = Array(repeating: Array(1...5), count: 2000)
let array3: [Any] = Array(repeating: 31, count: 10000)

Python

A1 = [list(range(1, 101)), list(range(101, 106)), 106, 
      list(range(107, 112)), 112, 113, 114, list(range(115, 126))]
A2 = list(range(1, 6)) * 2000
A3 = [31] * 10000

The generator and the array builder:

Swift

func chain(_ segments: [Any]) -> AnyIterator<Int>{
    var i = 0
    var j = 0
    return AnyIterator<Int> {
        while i < segments.count {
            switch segments[i] {
                case let e as Int:
                    i += 1
                    return e
                case let E as [Int]:
                    if j < E.count {
                        let val = E[j]
                        j += 1
                        return val
                    }
                    j = 0
                    i += 1

                default:
                    return nil
            }
        }
        return nil
    }
}


func flatten_array(_ segments: [Any]) -> [Int] {
    var result = [Int]()
    for segment in segments {
        switch segment {
            case let segment as Int:
                result.append(segment)
            case let segment as [Int]:
                result.append(contentsOf: segment)
            default:
                break
        }
    }
    return result
}

Python

def chain(L):
    for i in L:
        if type(i) is int:
            yield i
        elif type(i) is list:
            yield from i


def flatten_list(L):
    result = []
    for i in L:
        if type(i) is int:
            result.append(i)
        elif type(i) is list:
            result.extend(i)
    return result

And the benchmark results (100000 loops on the first test case, 1000 on the others):

Swift

test case 1 (small mixed input)
    Filling an array                         : 0.068221092224121094 s
    Filling an array, and looping through it : 0.074559926986694336 s
    Looping through a generator              : 1.5902719497680664   s *
    Materializing the generator to an array  : 1.759943962097168    s *

test case 2 (large input, [Int] s)
    Filling an array                         : 0.20634698867797852  s
    Filling an array, and looping through it : 0.21031379699707031  s
    Looping through a generator              : 1.3505551815032959   s *
    Materializing the generator to an array  : 1.4733860492706299   s *

test case 3 (large input, Int s)
    Filling an array                         : 0.27392101287841797  s
    Filling an array, and looping through it : 0.27670192718505859  s
    Looping through a generator              : 0.85304021835327148  s
    Materializing the generator to an array  : 1.0027849674224854   s *

Python

test case 1 (small mixed input)
    Filling an array                         : 0.1622014045715332   s
    Filling an array, and looping through it : 0.4312894344329834   s
    Looping through a generator              : 0.6839139461517334   s
    Materializing the generator to an array  : 0.5300459861755371   s

test case 2 (large input, [int] s)
    Filling an array                         : 1.029205083847046    s
    Filling an array, and looping through it : 1.2195289134979248   s
    Looping through a generator              : 1.0876803398132324   s
    Materializing the generator to an array  : 0.8958714008331299   s

test case 3 (large input, int s)
    Filling an array                         : 1.0181667804718018   s
    Filling an array, and looping through it : 1.244570255279541    s
    Looping through a generator              : 1.1220412254333496   s
    Materializing the generator to an array  : 0.9486079216003418   s

Clearly, Swift is very, very good at building arrays. But why are its generators so slow, even slower than Python’s in some cases? (Marked with an * in the table.) Testing with extremely large input ( > 100,000,000 elements, which nearly crashes Swift) suggests that even at the limit, the generator settles out to be slower than array filling by at least a factor of 3.25 in the best case.

If this is really intrinsic to the language, it has some funny implications. For example, common sense (to me as a python programmer anyway) would have it that if we were trying to synthesize an immutable object (like a string), we should first feed the source to a generating function to unfold it, and then hand off the output to a joined() method which works on a single shallow sequence. Instead, it looks like the most efficient strategy is serialization via array; unfolding the source to an intermediate array, and then constructing the output from the array.

Is building an entire new array and then iterating through it that faster that a lazy iteration on the original array? Why?

(Possibly related javascript question)

Edit

Here is the testing code:

Swift

func time(test_array: [Any], cycles: Int = 1000000) -> (array_iterate: Double, 
                                                        array_store  : Double, 
                                                        generate_iterate: Double, 
                                                        generate_store: Double) {
    func start() -> Double { return Date().timeIntervalSince1970 }
    func lap(_ t0: Double) -> Double {
        return Date().timeIntervalSince1970 - t0
    }
    var t0 = start()

    for _ in 0..<cycles {
        for e in flatten_array(test_array) { e + 1 }
    }
    let ΔE1 = lap(t0)

    t0 = start()
    for _ in 0..<cycles {
        let array: [Int] = flatten_array(test_array)
    }
    let ΔE2 = lap(t0)

    t0 = start()
    for _ in 0..<cycles {
        let G = chain(test_array)
        while let g = G.next() { g + 1 }
    }
    let ΔG1 = lap(t0)

    t0 = start()
    for _ in 0..<cycles {
        let array: [Int] = Array(chain(test_array))
    }
    let ΔG2 = lap(t0)

    return (ΔE1, ΔE2, ΔG1, ΔG2)
}

print(time(test_array: array1, cycles: 100000))
print(time(test_array: array2, cycles: 1000))
print(time(test_array: array3, cycles: 1000))

Python

def time_f(test_array, cycles = 1000000):
    lap = lambda t0: time() - t0
    t0 = time()

    for _ in range(cycles):
        for e in flatten_list(test_array):
            e + 1

    ΔE1 = lap(t0)

    t0 = time()
    for _ in range(cycles):
        array = flatten_list(test_array)

    ΔE2 = lap(t0)

    t0 = time()
    for _ in range(cycles):
        for g in chain(test_array):
            g + 1

    ΔG1 = lap(t0)

    t0 = time()
    for _ in range(cycles):
        array = list(chain(test_array))

    ΔG2 = lap(t0)

    return ΔE1, ΔE2, ΔG1, ΔG2

print(time_f(A1, cycles=100000))
print(time_f(A3, cycles=1000))
print(time_f(A2, cycles=1000))

回答1:

You asked "why are its [Swift] generators so slow, even slower than Python’s in some cases?"

My answer is that I do not think that they are nearly as slow as your results may indicate. In particular, I will try to demonstrate that looping through an iterator should be faster than constructing an array for all your test cases.

In earlier work (see a related blog post at http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/), I found that Swift iterators were about half as fast as the equivalent in Java when working over a bitset class. That's not great but Java is very efficient in this respect. Meanwhile, Go does worse. I submit to you that Swift iterators are probably not ideally efficient, but they are probably within a factor of two of what is possible with raw C code. And the performance gap probably has to do with insufficient function inlining in Swift.

I see that you are using an AnyIterator. I suggest deriving a struct from IteratorProtocol instead which has the benefit of insuring that there does not have to be any dynamic dispatch. Here is a relatively efficient possibility:

public struct FastFlattenIterator: IteratorProtocol {
   let segments: [Any]
    var i = 0 // top-level index
    var j = 0 // second-level index
    var jmax = 0 // essentially, this is currentarray.count, but we buffer it
    var currentarray : [Int]! // quick reference to an int array to be flatten

   init(_ segments: [Any]) {
       self.segments = segments
   }

   public mutating func next() -> Int? {
     if j > 0 { // we handle the case where we iterate within an array separately
       let val = currentarray[j]
       j += 1
       if j == jmax {
         j = 0
         i += 1
       }
       return val
     }
     while i < segments.count {
        switch segments[i] {
          case let e as Int: // found an integer value
            i += 1
            return e
          case let E as [Int]: // first encounter with an array
            jmax = E.count
            currentarray = E
            if jmax > 0 {
              j = 1
              return E[0]
            }
            i += 1
          default:
            return nil
        }
     }
     return nil
   }
}

With this class, I am getting the following numbers. For each test case, the first four approaches are taken from your code sample whereas the last two (fast iterator) are build using the new struct. Notice that "Looping through a fast iterator" is always fastest.

test case 1 (small mixed input)
Filling an array                         : 0.0073099999999999997 ms
Filling an array, and looping through it : 0.0069870000000000002 ms
Looping through a generator              : 0.18385799999999999   ms 
Materializing the generator to an array  : 0.18745700000000001   ms 
Looping through a fast iterator          : 0.005372              ms 
Materializing the fast iterator          : 0.015883999999999999  ms

test case 2 (large input, [Int] s)
Filling an array                         : 2.125931            ms
Filling an array, and looping through it : 2.1169820000000001  ms
Looping through a generator              : 15.064767           ms 
Materializing the generator to an array  : 15.45152            ms 
Looping through a fast iterator          : 1.572919            ms
Materializing the fast iterator          : 1.964912            ms 

test case 3 (large input, Int s)
Filling an array                         : 2.9140269999999999  ms
Filling an array, and looping through it : 2.9064290000000002  ms
Looping through a generator              : 9.8297640000000008  ms
Materializing the generator to an array  : 9.8297640000000008  ms 
Looping through a fast iterator          : 1.978038            ms 
Materializing the fast iterator          : 2.2565339999999998  ms 

You will find my complete code sample on GitHub: https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/extra/swift/iterators