1
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ A lot of languages have similar n² behavior in their standard library. It's not specific to functional interfaces. It's a classic when concatenating strings in Java (among others), for example. Anybody who's “appalled” about this has probably not paid attention to their favorite language. $\endgroup$ Jun 16, 2023 at 18:07
  • 1
    $\begingroup$ I'm not sure the question has a narrow enough scope to be answerable. Please edit it (especially the title) to clarify what you expect: specifically concatenation patterns? Iterate/reduce patterns? Or more generally potentially surprising performance? $\endgroup$ Jun 16, 2023 at 18:09
  • $\begingroup$ @Gilles'SO-stopbeingevil' I was thinking of the more general idea, but I used this example specifically because of the reaction I've gotten when I bring it up. I considered linking to the example from the proposal for count(where:) as well, but ultimately decided not to because the problem mentioned there is O(n) either way. $\endgroup$
    – Bbrk24
    Jun 16, 2023 at 19:02
  • 1
    $\begingroup$ I am not sure any satisfying answer is possible; the more a language lets the programmer describe what the result should be rather than exactly how it should be computed, the more opportunities for performance bugs where the programmer didn't realise that the result they asked for would be computed in a suboptimal way. The ultimate answer is to write imperative instead of declarative code, so the programmer is in control of how results are computed and hence what the performance characteristics of their code are. But this sacrifices too much expressiveness to be a good trade-off, usually. $\endgroup$
    – kaya3
    Jun 16, 2023 at 21:32
  • 1
    $\begingroup$ The more expressive the language, the easier it is to also express suboptimal solutions, and the real solution is education ─ programmers must learn to identify accidental quadratic behaviour and other performance bugs, by understanding what happens "under the hood" when they use declarative features of the language. Perhaps automated warnings when certain operations like string or list concatenation are used in a loop could help; some linters already do this. I would count that under education, though, since it doesn't involve changing the design of the operations themselves. $\endgroup$
    – kaya3
    Jun 16, 2023 at 21:35

1 Answer 1

3
$\begingroup$

Documentation & Culture

Firstly performance footguns are better avoided if the standard library documents the algorithmic complexity of its functions. This of course does not immediately help you when composing your own functions outside of the library. However, if its part of the culture to always document the complexity of such utilities including those you add yourself that will help.

Put Algorithmic Complexity into the Type System

You can go one step further and put this into the language's type system. This reddit thead has links to some research in this area:

"This paper augments a dependently typed language with constructs to specify cost, along with the ability to distinguish between the cost-relevant (intensional) behavior of code, and the cost-irrelevant (extensional) behavior of code."

"This paper augments a simpler language (basically OCaml without a module system) with automatic cost inference."

"The same group recently released this paper: https://dl.acm.org/doi/abs/10.1145/3434308 "

Credit to MattCubed in that thread for those links and descriptions.

A risk with this approach is that your type system becomes more complex and perhaps needs to support full mathematical proofs some of which could be undecidable.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .