Menu
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:
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)
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:
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
}
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):
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 *
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)
Here is the testing code:
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))
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))
353
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
118
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
