## Optimising the functional approach
> Iterative vs functional approach: Is it possible to use the (existing) functional methods without losing performance?
I don't think it's possible to use the standard library's *existing* collection methods without losing performance here – as I go onto investigate, there are quite a few inefficiencies with them. We can however make quite a few improvements by defining methods of our own to bring the performance close to the iterative approach.
Taking a look at your implementation of the mutable version of `permuate()` that uses the existing standard library collection methods:
> extension Array where Element: Comparable {
>
> mutating func permute2() -> Bool {
>
> // Nothing to do for empty or single-element arrays:
> if count <= 1 {
> return false
> }
>
> // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
> // exists.
> guard let j = indices.reversed().dropFirst()
> .first(where: { self[$0] <= self[$0 + 1] })
> else { return false }
>
> // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
> let l = indices.reversed()
> .first(where: { self[j] <= self[$0] })!
> swap(&self[j], &self[l])
>
> // L4: Reverse elements j+1 ... count-1:
> replaceSubrange(j+1..<count, with: self[j+1..<count].reversed())
> return true
> }
> }
Here are some performance improvements you can make...
### Reversing a slice
The first thing that stands out to me is the line:
replaceSubrange(j+1..<count, with: self[j+1..<count].reversed())
The problem with this is that `self[j+1..<count].reversed()` returns a reversed *view* onto the `ArraySlice` – which in turn has a view onto the array's buffer. Therefore when you come to call `replaceSubrange`, the array's buffer is not uniquely referenced. This therefore forces a copy of the array, which is a costly operation to be doing at every call of `permute()`.
One nice syntactic (and a slight performance) improvement over this would be to instead call `reverse()` on the `ArraySlice` itself:
self[j + 1 ..< count].reverse()
Note that I've added whitespace around the binary operators, which I think makes it much more readable.
Performance-wise this is slightly better because we're now mutating (a temporary) `ArraySlice`, before re-assigning it to back to `Array`'s subscript – therefore now *only* the slice itself needs to be copied (not the entire array).
This brings my benchmark time down from ~2.65 seconds to ~2.06 seconds.
However, we're still doing an unnecessary copy (although really I think the compiler should be able optimise this away and mutate the array directly – but this doesn't currently appear to be the case).
One way in order to allow us to mutate the array directly, rather than going through `ArraySlice` is to simply define a method to reverse the elements of an array between two given indices:
extension Array {
mutating func reverse(indices: Range<Index>) {
if isEmpty { return }
var low = indices.lowerBound
var high = index(before: indices.upperBound)
while low < high {
swap(&self[low], &self[high])
formIndex(after: &low)
formIndex(before: &high)
}
}
}
This implementation is based off [the standard library's own `reverse()` method][1]. Note that it may be more natural to express the `indices` parameter as a `ClosedRange`, due to the fact that the range should never be empty – however for increased interoperability, I would simply suggest adding this as another overload for this, if desired.
It's also worth noting that in practise, I would define this as an extension of<br> `MutableCollection where Self : BidirectionalCollection`, rather than `Array`. However, unfortunately, it appears to compiler is unable to specialise its implementation when doing so, which leads to reduced performance.
Now we can say:
reverse(indices: j + 1 ..< count)
Which brings my benchmark time down from ~2.06 seconds to ~1.46 seconds.
If we're going for maximal performance here, we can use `Range`'s [`init(uncheckedBounds:)`][2] initialiser to skip the precondition check that `lowerBound <= upperBound`, given that we know `j + 1 < count` (as the maximum value of `j` is `count - 2`).
reverse(indices: Range(uncheckedBounds: (lower: j + 1, upper: count)))
This brings my benchmark time down from ~1.46 seconds to ~1.45 seconds. However, we're still way off my target benchmark time of ~0.02 seconds for the original mutating version of `permute()`.
### Optimising `first(where:)`
The major bottleneck here appears to be with `Sequence`'s `first(where:)` method. If we take a look at its implementation, we can see it's implemented as:
internal enum _StopIteration : Error {
case stop
}
// ...
extension Sequence {
public func first(
where predicate: (Iterator.Element) throws -> Bool
) rethrows -> Iterator.Element? {
var foundElement: Iterator.Element?
do {
try self.forEach {
if try predicate($0) {
foundElement = $0
throw _StopIteration.stop
}
}
} catch is _StopIteration { }
return foundElement
}
}
}
As first, this looks insane. Using `forEach(_:)` and a throwing a dummy `Error` type to exit the loop?
Turns out this is an attempted optimisation by the standard library team in order to allow for sequences to implement their own version of `forEach(_:)` in a more efficient manner than iterating over their iterator. This is discussed in both [SR-3166][3] and [this (closed) pull request][4].
However, unfortunately, this implementation of `first(where:)` is causing a big performance bottleneck for our implementation of `permute()`. From what I can *tell*, the main suspect appears to be the throwing of the `_StopIteration` error, which involves the wrapping in an existential `Error` container.
A simple fix to this problem is to simply define our own `first(where:)` method for random-access collections that simply uses a for-in loop. This allows us to take advantage of a more performant version of the method, while still allowing for complicated non-random-access sequences to use `first(where:)` with their (potentially) customised `forEach` implementation.
extension RandomAccessCollection {
func first(where predicate: (Iterator.Element) throws -> Bool) rethrows -> Iterator.Element? {
for element in self {
if try predicate(element) {
return element
}
}
return nil
}
}
This now brings my benchmark time down from ~1.45 seconds to a nice ~0.04 seconds, which is only 2x slower than your original version of `permute()`, but is implemented with more functional methods. For your convenience, [here's a gist][5] with all the changes that I've made.
I couldn't find any other immediately obvious candidates for optimisation – but would certainly be interested if anyone can.
---
## Mutating vs. non-mutating
> Which API is clearer?
I think both are fairly clear in terms of their usage – it's often common to implement a mutating and non-mutating version of the same logic, as both have can their uses in different circumstances.
Although for the non-mutating version, there's no need to completely re-invent the wheel – you can simply refactor it to use the mutating version's implementation:
extension Array where Element : Comparable {
func nextPermutation() -> Array? {
var result = self
return result.permute() ? result : nil
}
}
This doesn't impact the performance due to the fact that `Array` has copy-on-write semantics, so the array buffer won't actually be copied unless `permute()` actually does a permutation.
But really, for *most* common usages of this logic, I think [the Sequence-based API][6] would probably be the clearest API to use – as I *imagine* most use cases will revolve around having to iterate through different permutations.
> Can we make the non-mutating method as fast as the mutating one?
I don't believe so – if you want to have a copy of the array prior to the mutation, you'll have to pay the cost of a copy. I suspect the compiler *may* be able to optimise cases where the caller doesn't rely on the value of the original array remaining the same – but that's up to the compiler, and AFAIK there's no easy way to assist it in that.
[1]: https://github.com/apple/swift/blob/master/stdlib/public/core/Reverse.swift#L13
[2]: https://developer.apple.com/reference/swift/range/1785569-init
[3]: https://bugs.swift.org/browse/SR-3166
[4]: https://github.com/apple/swift/pull/5867
[5]: https://gist.github.com/hamishknight/ffdd1b9901cb8dc403c46e4f109b92f2
[6]: http://codereview.stackexchange.com/q/158799/104723