<p>Swift has a protocol <code>Sequence&lt;Element&gt;</code>, which is used to support <code>for</code>-<code>in</code> loops. It has a bunch of extension methods to support functional programming style, such as <code>map</code> and <code>filter</code>. One pair of these methods is called &quot;reduce&quot;, which are implemented roughly as follows:</p>
<pre class="lang-swift prettyprint-override"><code>extension Sequence {
  func reduce&lt;T&gt;(_ start: T, _ combine: (T, Element) throws -&gt; T) rethrows -&gt; T {
    var result = start
    for el in self {
      result = try combine(result, el)
    }
    return result
  }

  func reduce&lt;T&gt;(into start: T, _ combine: (inout T, Element) throws -&gt; Void) rethrows -&gt; T {
    var result = start
    for el in self {
      try combine(&amp;result, el)
    }
    return result
  }
}
</code></pre>
<p>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 &quot;flatten&quot; method. Either one could be used:</p>
<pre class="lang-swift prettyprint-override"><code>func flatten1&lt;T&gt;(_ arr: [[T]]) -&gt; [T] {
  arr.reduce([], +)
}

func flatten2&lt;T&gt;(_ arr: [[T]]) -&gt; [T] {
  arr.reduce(into: [], +=)
}
</code></pre>
<p>However, there's a hidden performance issue. Do you see it?</p>
<p><code>flatten1</code> is <span class="math-container">$O(n^2)$</span>. Consider the implementations of the operators <code>+</code> and <code>+=</code>, which could look something like this at a high level:</p>
<pre class="lang-swift prettyprint-override"><code>func + &lt;T&gt;(lhs: [T], rhs: [T]) -&gt; [T] {
  let destBuffer = calloc(lhs.count + rhs.count, MemoryLayout&lt;T&gt;.stride)!
  memcpy(destBuffer, lhs.buffer, lhs.count * MemoryLayout&lt;T&gt;.stride)
  memcpy(destBuffer + lhs.count, rhs.buffer, rhs.count * MemoryLayout&lt;T&gt;.stride)
  return makeArray(buffer: destBuffer, count: lhs.count + rhs.count)
}

func += &lt;T&gt;(lhs: inout [T], rhs: [T]) {
  if lhs.capacity &lt; lhs.count + rhs.count {
    lhs.capacity = max(lhs.count + rhs.count, lhs.capacity * 2)
    lhs.buffer = realloc(lhs.buffer, lhs.capacity * MemoryLayout&lt;T&gt;.stride)!
  }
  memmove(lhs.buffer + lhs.count, rhs.buffer, rhs.count * MemoryLayout&lt;T&gt;.stride)
  lhs.count += rhs.count
}
</code></pre>
<p>Every call to <code>+</code> <em>must</em> allocate a new buffer and copy both of its operands in, while calls to <code>+=</code> usually don't have to. The optimizer is <em>allowed</em> to elide the unnecessary copies, but it is not <em>required</em> to. <a href="https://godbolt.org/z/e9qxsMYnW" rel="nofollow noreferrer">Swift 5.8 doesn't, even when bounds checking is disabled.</a></p>
<p>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: <strong>How could Swift have designed these methods better to avoid performance traps?</strong></p>

<functional-programming><standard-library><swift>
How to avoid hidden performance problems in functional interfaces?
CC BY-SA 4.0
2023-06-16T18:07:05.703Z
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.
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-06-16T18:09:53.083Z
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?
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-06-16T19:02:57.730Z
@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:)`](https://github.com/apple/swift-evolution/blob/main/proposals/0220-count-where.md#motivation) as well, but ultimately decided not to because the problem mentioned there is O(n) either way.
Bbrk24
CC BY-SA 4.0
2023-06-16T21:32:10.577Z
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.
kaya3
CC BY-SA 4.0
2023-06-16T21:35:47.097Z
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.
kaya3
<h2>Documentation &amp; Culture</h2>
<p>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.</p>
<h1>Put Algorithmic Complexity into the Type System</h1>
<p>You can go one step further and put this into the language's type system.
This <a href="https://www.reddit.com/r/ProgrammingLanguages/comments/scsddv/time_complexity_as_part_of_the_type_system/" rel="nofollow noreferrer">reddit thead</a> has links to some research in this area:</p>
<ul>
<li><a href="https://dl.acm.org/doi/abs/10.1145/3498670" rel="nofollow noreferrer">https://dl.acm.org/doi/abs/10.1145/3498670</a></li>
</ul>
<blockquote>
<p>&quot;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.&quot;</p>
</blockquote>
<ul>
<li><a href="http://isilmar-4.linta.de/%7Eaehlig/university/pub/12-raml.pdf" rel="nofollow noreferrer">http://isilmar-4.linta.de/~aehlig/university/pub/12-raml.pdf</a></li>
</ul>
<blockquote>
<p>&quot;This paper augments a simpler language (basically OCaml without a module system) with automatic cost inference.&quot;</p>
</blockquote>
<ul>
<li>An implementation exists here: <a href="https://www.raml.co/interface/" rel="nofollow noreferrer">https://www.raml.co/interface/</a></li>
</ul>
<blockquote>
<p>&quot;The same group recently released this paper: <a href="https://dl.acm.org/doi/abs/10.1145/3434308" rel="nofollow noreferrer">https://dl.acm.org/doi/abs/10.1145/3434308</a>
&quot;</p>
</blockquote>
<p>Credit to <a href="https://www.reddit.com/user/MattCubed/" rel="nofollow noreferrer">MattCubed</a> in that thread for those links and descriptions.</p>
<p>A risk with this approach is that your type system becomes more complex and perhaps needs to support <a href="https://proofassistants.stackexchange.com/questions/261/what-makes-a-proof-assistant-a-proof-assistant">full mathematical proofs</a> some of which could be undecidable.</p>

CC BY-SA 4.0
2023-06-16T23:51:56.117Z
2023-06-16T23:51:56.117Z
Bruce Adams
# How to avoid hidden performance problems in functional interfaces?
Posted by: username_0 on 2023-06-16
Swift has a protocol Sequence, 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(_ 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(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(_ arr: [[T]]) -> [T] {
  arr.reduce([], +)
}

func flatten2(_ 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 + (lhs: [T], rhs: [T]) -> [T] {
  let destBuffer = calloc(lhs.count + rhs.count, MemoryLayout.stride)!
  memcpy(destBuffer, lhs.buffer, lhs.count * MemoryLayout.stride)
  memcpy(destBuffer + lhs.count, rhs.buffer, rhs.count * MemoryLayout.stride)
  return makeArray(buffer: destBuffer, count: lhs.count + rhs.count)
}

func += (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.stride)!
  }
  memmove(lhs.buffer + lhs.count, rhs.buffer, rhs.count * MemoryLayout.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?
**Tags:** functional-programming standard-library swift
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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?  
> **username_0**: @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:)`](https://github.com/apple/swift-evolution/blob/main/proposals/0220-count-where.md#motivation) as well, but ultimately decided not to because the problem mentioned there is O(n) either way.  
> **username_2**: 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.  
> **username_2**: 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.  
---
## 1 answers
### Answer by username_3 on 2023-06-16. Score: 3 | Accepted answer
## 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](https://www.reddit.com/r/ProgrammingLanguages/comments/scsddv/time_complexity_as_part_of_the_type_system/) has links to some research in this area:

* <https://dl.acm.org/doi/abs/10.1145/3498670>

> "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."

* [http://isilmar-4.linta.de/~aehlig/university/pub/12-raml.pdf](http://isilmar-4.linta.de/%7Eaehlig/university/pub/12-raml.pdf)

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

* An implementation exists here: <https://www.raml.co/interface/>

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

Credit to [MattCubed](https://www.reddit.com/user/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](https://proofassistants.stackexchange.com/questions/261/what-makes-a-proof-assistant-a-proof-assistant) some of which could be undecidable.
---
