Why are Swift iterators slower than array building?

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 msFilling an array, and looping through it : 0.0069870000000000002 msLooping 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  mstest case 2 (large input, [Int] s)Filling an array                         : 2.125931            msFilling an array, and looping through it : 2.1169820000000001  msLooping through a generator              : 15.064767           ms Materializing the generator to an array  : 15.45152            ms Looping through a fast iterator          : 1.572919            msMaterializing the fast iterator          : 1.964912            ms test case 3 (large input, Int s)Filling an array                         : 2.9140269999999999  msFilling an array, and looping through it : 2.9064290000000002  msLooping through a generator              : 9.8297640000000008  msMaterializing 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