Why `joined()` is much slower than `flatMap()`?

Using Swift
, ,
1

I want to join a large array with joined(), and I found this method is very slow, it is much slower than flatMap(), here is the code to reproduce it.

As you can see, joined takes around 0.26s, flatMap takes around 0.0064s, do you know why this happened?

import Foundation

var datas = [Data]()
var count = 0
(0...10000).forEach { _ in
    let data = """
            public struct FlattenSequence<Base: Sequence> where Base.Element: Sequence {
            public struct FlattenSequence<Base: Sequence> where Base.Element: Sequence {
            """.data(using: .utf8)!
    datas.append(data)
    count += data.count
}



// 1st approach, it takes 0.0049s, around 40 times faster than the 2nd approach.
let start1 = Date()
var wholeData1 = Data(capacity: count)
datas.forEach {
    wholeData1.append($0)
}
print("Time 1: \(Date().timeIntervalSince(start1))")

// 2nd approach, it takes 0.26s,
let start2 = Date()
let wholeData2 = Data.init(datas.joined())
print("Time 2: \(Date().timeIntervalSince(start2))")

// 3rd approach, it takes 0.0064s
let start3 = Date()
let wholeData3 = Data.init(datas.flatMap { $0 })
print("Time 3: \(Date().timeIntervalSince(start3))")

print(wholeData1 == wholeData2)
print(wholeData1 == wholeData3)
print(count)
1 Like
2

Without taking anything away from your question:

bart-simpson-generator.php

Now, that aside, what you're observing does persist with optimizations enabled (and actually gets worse as a ratio!)

scanon@iMac-Pro Sandbox % swiftc joined.swift -O
scanon@iMac-Pro Sandbox % ./joined              
Time 1: 0.0010030269622802734
Time 2: 0.06337499618530273
Time 3: 0.0033309459686279297

The first thing I note is that doubling the count roughly doubles the time for all three, so nothing is accidentally quadratic here, it's just slow:

Time 1: 0.002376079559326172
Time 2: 0.12487602233886719
Time 3: 0.006898999214172363
3 Likes
3

Thanks, the next question is why ?
I suppose it's because of this

/// The `joined` method is always lazy, but does not implicitly
/// confer laziness on algorithms applied to its result.  In other
/// words, for ordinary sequences `s`:
///
/// * `s.joined()` does not create new storage
/// * `s.joined().map(f)` maps eagerly and returns a new array
/// * `s.lazy.joined().map(f)` maps lazily and return

But we already have a LazySequence, we can always call an array method lazily by array.lazy.method, why swift decide to make joined method be always lazy?
I did some more test, I have found out the performance of datas.lazy.flatMap { $0 }, datas.lazy.joined(), datas.joined() is quite similar, which means the slowness is indeed caused by laziness.

IMHO, the better option would be remove the laziness from joined, and we can still call it lazily by array.lazy.joined().

4

FlattenSequence.Iterator.next is the bulk of the work, which isn't that surprising according to instruments in release mode:

Screen Shot 2021-07-02 at 15.52.50
Screen Shot 2021-07-02 at 15.52.501190×82 29.1 KB

Screen Shot 2021-07-02 at 15.53.03
Screen Shot 2021-07-02 at 15.53.031190×82 24.5 KB

Screen Shot 2021-07-02 at 15.53.11
Screen Shot 2021-07-02 at 15.53.111190×82 28 KB

However, this discrepancy disappears when I use UInt8 instead of Data:

var datas = [[UInt8]]()
var count = 0
(0 ... 2_000_000).forEach { _ in
	let data = (0 ... Int.random(in: 10 ... 20)).map { _ in UInt8.random(in: .min ... .max) }
	datas.append(data)
	count += data.count
}

with some other changes yields

Time 1: 0.11238205432891846
Time 2: 0.13424193859100342
Time 3: 0.07867097854614258

But when I use String, flatMap does much worse

Time 1: 0.2581210136413574
Time 2: 0.569443941116333
Time 3: 43.00332498550415

Screen Shot 2021-07-02 at 16.21.10
Screen Shot 2021-07-02 at 16.21.101099×216 65.2 KB

2 Likes
5

I have the same result using UInt8 with the following code.

import Foundation

var datas = [[UInt8]]()
var count = 0
(0...10000).forEach { _ in
    let data = """
            public struct FlattenSequence<Base: Sequence> where Base.Element: Sequence {
            public struct FlattenSequence<Base: Sequence> where Base.Element: Sequence {
            """.data(using: .utf8)!
    let uint8s = [UInt8](data)
    datas.append(uint8s)
    count += data.count
}


// 1st approach, it takes 0.0049s, around 40 times faster than the 2nd approach.
let start1 = Date()
var wholeData1 = [UInt8]()
datas.forEach {
    wholeData1.append(contentsOf: $0)
}
print("Time 1: \(Date().timeIntervalSince(start1))")

// 2nd approach, it takes 0.26s,
let start2 = Date()
let wholeData2 = Array(datas.joined())
print("Time 2: \(Date().timeIntervalSince(start2))")

// 3rd approach, it takes 0.0064s
let start3 = Date()
let wholeData3 = Array(datas.flatMap { $0 })
print("Time 3: \(Date().timeIntervalSince(start3))")

// 4th approach, it takes 0.0064s
let start4 = Date()
let wholeData4 = Array(datas.lazy.flatMap { $0 })
print("Time 4: \(Date().timeIntervalSince(start3))")
print(count)
6

<insert same image but with text about transparency and background colors>

4 Likes