[SR-7952] Performance of lazy compactMap is terrible

[tellowkrinkle]

Previous ID	SR-7952
Radar	rdar://problem/41005326
Original Reporter	@tellowkrinkle
Type	Bug
Status	Resolved
Resolution	Done

Additional Detail from JIRA

Votes	0
Component/s	Compiler
Labels	Bug, 4.1Regression, Optimizer
Assignee	@eeckstein
Priority	Medium

md5: 472a6fc38d023d4100ea2188bc387c7d

Issue Description:

In the following code, the flatMap (used for compatibility with swift 4.0.3) performs much worse than the filter + map under a -O build.

import Dispatch

func benchmark<T>(_ function: () -> T) -> (T, Double) {
    let start = DispatchTime.now()
    let res = function()
    let end = DispatchTime.now()
    return (res, Double(end.uptimeNanoseconds - start.uptimeNanoseconds) / 1_000_000_000)
}

let base = 0..<1_000_000

let (fmRes, flatMapTime) = benchmark { base.lazy.flatMap({ $0 % 4 == 0 ? nil : $0 }).reduce(0, +) }
let (mapRes, mapTime) = benchmark { base.lazy.filter({ $0 % 4 != 0 }).map({ $0 }).reduce(0, +) }

print("Flat Map: \(fmRes), took \(flatMapTime)\n     Map: \(mapRes), took \(mapTime)")

Output under swift 4.1 as far back as the 2017 October 25 snapshot (oldest I could find):

Flat Map: 375000000000, took 0.876876712
     Map: 375000000000, took 0.002207212

Output under swift 4.0.3 release:

Flat Map: 375000000000, took 0.002158283
     Map: 375000000000, took 0.002088703

[jckarter]

@swift-ci create

[eeckstein]

Fixed in #17885