Why is `Array.flatMap` so slow?

Using Swift
27

From some experimentation, it seems to be the intermediate temporary arrays that are the problem. You can see this by changing the input array from [(Int,Int,Int,Int)] to [[Int]]. That pretty much eliminates the disparity, at least on my Darwin machine.

But it appears you can do even better if you conform the struct to itself be a collection, allowing it to be flat mapped directly:

extension S: RandomAccessCollection {
  var startIndex: Int { return 0 }
  var endIndex: Int { return 4 }
  subscript(i: Int) -> Int {
    switch i {
    case 0: return a
    case 1: return b
    case 2: return c
    case 3: return d
    default: fatalError()
    }
  }
}

// then either
func structCollectionFunctional(_ input: [S]) -> [Int] {
  return input.flatMap { $0 }
}

// or
func structCollectionLoopNoRes(_ input: [S]) -> [Int] {
  var flattened: [Int] = []
  for s in input {
    flattened += s
  }
  return flattened
}

This seems to give the optimizer a much better handle on what's going on, resulting in big speedups with both the functional and imperative approaches.

5 Likes