## 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.
For your implementation of the mutable version of `permute()` 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
> }
> }
This gives me a benchmark time down of ~2.65 seconds (running it with a Swift 3.1 -O build). Here's some improvements we can make to improve upon this...
### 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 consider defining 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.
But regardless of these details, 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 also use `Range`'s [`init(uncheckedBounds:)`][2] initialiser to skip the precondition check that `lowerBound <= upperBound`, given that we know<br> `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 the target benchmark time of ~0.02 seconds for your 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 glance, 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 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 collections to have a `first(where:)` implementation that uses 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 else can.
---
## Mutating vs. non-mutating
> Which API is clearer?
I think both are fairly clear in terms of their usage (although they will require documenting in order to inform to the user that they do the permutations lexicographically). It's often common to implement a mutating and non-mutating version of the same logic (there are lots of examples in the stdlib), 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 with that in this case.
[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