Swift has a protocol Sequence<Element>, which is used to support for-in loops. It has a bunch of extension methods to support functional programming style, such as map and filter. One pair of these methods is called "reduce", which are implemented roughly as follows:
extension Sequence {
func reduce<T>(_ start: T, _ combine: (T, Element) throws -> T) rethrows -> T {
var result = start
for el in self {
result = try combine(result, el)
}
return result
}
func reduce<T>(into start: T, _ combine: (inout T, Element) throws -> Void) rethrows -> T {
var result = start
for el in self {
try combine(&result, el)
}
return result
}
}
These seem like fairly innocuous and useful methods. However, there's one pitfall that people tend not to be aware of. Consider using these to implement a "flatten" method. Either one could be used:
func flatten1<T>(_ arr: [[T]]) -> [T] {
arr.reduce([], +)
}
func flatten2<T>(_ arr: [[T]]) -> [T] {
arr.reduce(into: [], +=)
}
However, there's a hidden performance issue. Do you see it?
flatten1 is $O(n^2)$. Consider the implementations of the operators + and +=, which could look something like this at a high level:
func + <T>(lhs: [T], rhs: [T]) -> [T] {
let destBuffer = calloc(lhs.count + rhs.count, MemoryLayout<T>.stride)!
memcpy(destBuffer, lhs.buffer, lhs.count * MemoryLayout<T>.stride)
memcpy(destBuffer + lhs.count, rhs.buffer, rhs.count * MemoryLayout<T>.stride)
return makeArray(buffer: destBuffer, count: lhs.count + rhs.count)
}
func += <T>(lhs: inout [T], rhs: [T]) {
if lhs.capacity < lhs.count + rhs.count {
lhs.capacity = max(lhs.count + rhs.count, lhs.capacity * 2)
lhs.buffer = realloc(lhs.buffer, lhs.capacity * MemoryLayout<T>.stride)!
}
memmove(lhs.buffer + lhs.count, rhs.buffer, rhs.count * MemoryLayout<T>.stride)
lhs.count += rhs.count
}
Every call to + must allocate a new buffer and copy both of its operands in, while calls to += usually don't have to. The optimizer is allowed to elide the unnecessary copies, but it is not required to. Swift 5.8 doesn't, even when bounds checking is disabled.
Every time I mention this, someone is appalled that this footgun exists in the language. However, I can't think of any obvious ways to avoid this. So, my question is: How could Swift have designed these methods better to avoid performance traps?
count(where:)as well, but ultimately decided not to because the problem mentioned there is O(n) either way. $\endgroup$