arrays - Does joined() or flatMap(_:) perform better in Swift 3? -

i'm curious performance characteristics of joined() , .flatmap(_:) in flattening multidimensional array:

let array = [[1,2,3],[4,5,6],[7,8,9]] let j = array(array.joined()) let f = array.flatmap{$0} 

they both flatten nested array [1, 2, 3, 4, 5, 6, 7, 8, 9]. should prefer 1 on other performance? also, there more readable way write calls?

tl; dr

when comes flattening 2d arrays (without transformations or separators applied, see @dfri's answer more info aspect), array.flatmap{$0} , array(array.joined()) both conceptually same , have similar performance.

---

the main difference between flatmap(_:) , joined() (note isn't new method, has just been renamed flatten()) joined() lazily applied (for arrays, returns special flattenbidirectionalcollection<base>).

therefore in terms of performance, makes sense use joined() on flatmap(_:) in situations want iterate on part of flattened sequence (without applying transformations). example:

let array2d = [[2, 3], [8, 10], [9, 5], [4, 8]]  if array2d.joined().contains(8) {     print("contains 8") } else {     print("doesn't contain 8") } 

because joined() lazily applied & contains(_:) stop iterating upon finding match, first 2 inner arrays have 'flattened' find element 8 2d array. although, @dfri correctly notes below, able lazily apply flatmap(_:) through use of lazysequence/lazycollection – can created through lazy property. ideal lazily applying both transformation & flattening given 2d sequence.

in cases joined() iterated through, conceptually no different using flatmap{$0}. therefore, these valid (and conceptually identical) ways of flattening 2d array:

array2d.joined().map{$0} 

array(array2d.joined()) 

array2d.flatmap{$0} 

---

in terms of performance, flatmap(_:) documented having time-complexity of:

o(m + n), m length of sequence , n length of result

this because its implementation simply:

  public func flatmap<segmentofresult : sequence>(     _ transform: (${gelement}) throws -> segmentofresult   ) rethrows -> [segmentofresult.${gelement}] {     var result: [segmentofresult.${gelement}] = []     element in self {       result.append(contentsof: try transform(element))     }     return result   } } 

as append(contentsof:) has time-complexity of o(n), n length of sequence append, overall time-complexity of o(m + n), m total length of sequences appended, , n length of 2d sequence.

when comes joined(), there no documented time-complexity, lazily applied. however, main bit of source code consider the implementation of flatteniterator, used iterate on flattened contents of 2d sequence (which occur upon using map(_:) or array(_:) initialiser joined()).

  public mutating func next() -> base.element.iterator.element? {     repeat {       if _fastpath(_inner != nil) {         let ret = _inner!.next()         if _fastpath(ret != nil) {           return ret         }       }       let s = _base.next()       if _slowpath(s == nil) {         return nil       }       _inner = s!.makeiterator()     }     while true   }  

here _base base 2d sequence, _inner current iterator 1 of inner sequences, , _fastpath & _slowpath hints compiler aid branch prediction.

assuming i'm interpreting code correctly & full sequence iterated through, has time complexity of o(m + n), m length of sequence, , n length of result. because goes through each outer iterator , each inner iterator flattened elements.

so, performance wise, array(array.joined()) , array.flatmap{$0} both have same time complexity.

if run quick benchmark in debug build (swift 3.1):

import quartzcore  func benchmark(repeatcount:int = 1, name:string? = nil, closure:() -> ()) {     let d = cacurrentmediatime()     _ in 0..<repeatcount {         closure()     }     let d1 = cacurrentmediatime()-d     print("benchmark of \(name ?? "closure") took \(d1) seconds") }  let arr = [[int]](repeating: [int](repeating: 0, count: 1000), count: 1000)  benchmark {     _ = arr.flatmap{$0} // 0.00744s }  benchmark {     _ = array(arr.joined()) // 0.525s }  benchmark {     _ = arr.joined().map{$0} // 1.421s } 

flatmap(_:) appears fastest. suspect joined() being slower due branching occurs within flatteniterator (although hints compiler minimise cost) – although why map(_:) slow, i'm not sure. interested know if else knows more this.

however, in optimised build, compiler able optimise away big performance difference; giving 3 options comparable speed, although flatmap(_:) still fastest fraction of second:

let arr = [[int]](repeating: [int](repeating: 0, count: 10000), count: 1000)  benchmark {     let result = arr.flatmap{$0} // 0.0910s     print(result.count) }  benchmark {     let result = array(arr.joined()) // 0.118s     print(result.count) }  benchmark {     let result = arr.joined().map{$0} // 0.149s     print(result.count) } 

(note order in tests performed can affect results – both of above results average performing tests in various different orders)