Sequence.Map: Why not initialize contiguous array with a lazy map?


(Anthony Latsis) #1

Here are two versions of map, the first one representing the current implementation, slightly simplified. I've tested some expensive transforms with a class and struct and the difference in speed seems negligible. I have two questions:

  • Is the head-on reserve -> append expected to be faster than initializing the contiguous array with a lazy map wrapper (_copyToContiguousArray)?
  • If not, does map intendedly stick to the head-on approach?
extension Sequence {
  @inlinable func map2<T>(
    _ transform: (Element) -> T
  ) -> [T] {
    let initialCapacity = underestimatedCount
    var result = ContiguousArray<T>()
    result.reserveCapacity(initialCapacity)
    
    var iterator = self.makeIterator()
    
    for _ in 0..<initialCapacity {
      let next = iterator.next()!
      result.append(transform(next))
    }
    while let element = iterator.next() {
      result.append(transform(element))
    }
    return Array(result)
  }
}
extension Sequence {
  @inlinable func map1<T>(
    _ transform: @escaping (Element) -> T
  ) -> [T] {
    let result = ContiguousArray(lazy.map(transform))
    return Array(result)
  }
}

(Jordan Rose) #2

I suspect that this is mostly just because the current implementation of Sequence's map predates lazy. Sequence.map also takes a non-escaping closure, so you'll need a withoutActuallyEscaping somewhere in there.

Put up a pull request and let's benchmark it!


(Anthony Latsis) #3

@jrose I just realized I can't use the lazy map with the real map because it doesn't accept throwing closures :sweat_smile:. Perhaps that's the reason.


(Anthony Latsis) #4

The ability to specify the throwing context would be very useful here.

@inlinable 
func map<T>(
  _ transform: (Element) throws -> T
) rethrows -> [T] {
  return withoutActuallyEscaping(transform) { escaping in
    return Array(
        ContiguousArray(
          self.lazy.map { elt in try(map) escaping(elt) }
        )                            ~~~
      )
    )
  }
}