The current implementation of Sequence.reversed() creates a new Array from the Sequence and swaps the elements of that Array:
This is pretty simple and this makes sense.
From more modern runtimes we might be able to use MutableSpan:
extension Sequence {
@inlinable
public __consuming func reversedWithArray() -> [Element] {
var result = Array(self)
let count = result.count
for i in 0..<count/2 {
result.swapAt(i, count - ((i + 1) as Int))
}
return result
}
}
extension Sequence {
@inlinable
public __consuming func reversedWithSpan() -> [Element] {
guard #available(anyAppleOS 26.0, *) else {
return self.reversedWithArray()
}
var result = Array(self)
var span = result.mutableSpan
let count = span.count
for i in 0..<count/2 {
span.swapAt(i, count - ((i + 1) as Int))
}
return result
}
}
extension Sequence {
@inlinable
public __consuming func reversedWithSpanUnchecked() -> [Element] {
guard #available(anyAppleOS 26.0, *) else {
return self.reversedWithArray()
}
var result = Array(self)
var span = result.mutableSpan
let count = span.count
for i in 0..<count/2 {
span.swapAt(unchecked: i, unchecked: count - ((i + 1) as Int))
}
return result
}
}
This seems to lead to some decent perf wins:
import Foundation
func Measure<T>(_ body: () -> (T)) -> T {
let clock = ContinuousClock()
let instant = clock.now
let result = body()
let duration = instant.duration(to: clock.now).formatted(
.units(
allowed: [.milliseconds],
fractionalPart: .show(length: 2)
)
)
print(duration)
return result
}
func main() {
let a = Array(1...10_000_000)
do {
print("reversedWithArray")
let result = Measure {
a.reversedWithArray()
}
print(a.reversed() == result)
}
do {
print("reversedWithSpan")
let result = Measure {
a.reversedWithSpan()
}
print(a.reversed() == result)
}
do {
print("reversedWithSpanUnchecked")
let result = Measure {
a.reversedWithSpanUnchecked ()
}
print(a.reversed() == result)
}
}
main()
// swift run -c debug
//
// reversedWithArray
// 1,069.98 ms
// true
// reversedWithSpan
// 638.98 ms
// true
// reversedWithSpanUnchecked
// 610.69 ms
// true
//
// swift run -c release
//
// reversedWithArray
// 15.16 ms
// true
// reversedWithSpan
// 3.95 ms
// true
// reversedWithSpanUnchecked
// 3.48 ms
// true
//
Any reason not to make that change? Assuming we have to guard and control for OS version? Any other direction to measure this where the MutableSpan algorithm would run slower?
It might be worthwhile to test it on an older system where Span is not available, and particularly with short arrays. if #available is cheap but not free and so adds some overhead. Maybe there’s a way to work around this, such as by checking the deployment target rather than the OS version somehow?
So the constant factor of work to construct the MutableSpan does show up for very small arrays and erases the gains.
I'm pretty sure the measurement here would not have compiled that out and already calibrated for that performance hit? I am running on os 26 but the deployment target of this executable package is os 13 if that makes a difference.
I expect there’s going to be a lot of fairly low hanging fruit like this now that Span is available, and even more once we have the new iteration model. Even when there aren’t perf wins, converting existing UnsafePointer based implementations is nice for reducing the amount of unsafe code in the stdlib.
Do check on the availability check overhead as mentioned, but this sounds promising.
If you put PRs up and they aren’t getting noticed feel free to poke me in forum DMs.
To have no availability guards you can try to get a pointer and call .mutableSpan/.span on that pointer, but that might require you to operate on the specific type like (array.withUnsafeMutableBufferPointer(_:)), then ptr.mutableSpan.
By default for benchmarks, you should use SuspendingClock which does not count the time when your process is suspended (well I'm sure of that behavior on Linux since it uses CLOCK_MONOTONIC, I think it's the same behavior on Darwin as well).
To be clear I don't think it'd turn around the results or such, that's just a note for better accuracy.
extension Sequence {
@inlinable
public __consuming func control() -> [Element] {
var result = Array(self)
let count = result.count
for i in 0..<count/2 {
result.swapAt(i, count - ((i + 1) as Int))
}
return result
}
}
extension Sequence {
@inlinable
public __consuming func testWithAvailable() -> [Element] {
guard #available(anyAppleOS 26.0, *) else {
return self.control()
}
var result = Array(self)
let count = result.count
for i in 0..<count/2 {
result.swapAt(i, count - ((i + 1) as Int))
}
return result
}
}
extension Sequence {
@inlinable
public __consuming func testWithAvailableSpan() -> [Element] {
guard #available(anyAppleOS 26.0, *) else {
return self.control()
}
var result = Array(self)
var span = result.mutableSpan
let count = span.count
for i in 0..<count/2 {
span.swapAt(i, count - ((i + 1) as Int))
}
return result
}
}
extension Sequence {
@inlinable
public __consuming func testWithAvailableUncheckedSpan() -> [Element] {
guard #available(anyAppleOS 26.0, *) else {
return self.control()
}
var result = Array(self)
var span = result.mutableSpan
let count = span.count
for i in 0..<count/2 {
span.swapAt(unchecked: i, unchecked: count - ((i + 1) as Int))
}
return result
}
}
func Benchmark(
n: Int,
cycles: Int
) {
let a = Array(1 ... n)
do {
Measure("control", cycles) {
a.control()
} condition: { result in
result == a.reversed()
}
}
do {
Measure("testWithAvailable", cycles) {
a.testWithAvailable()
} condition: { result in
result == a.reversed()
}
}
do {
Measure("testWithAvailableSpan", cycles) {
a.testWithAvailableSpan()
} condition: { result in
result == a.reversed()
}
}
do {
Measure("testWithAvailableUncheckedSpan", cycles) {
a.testWithAvailableUncheckedSpan()
} condition: { result in
result == a.reversed()
}
}
}
func main() {
let sizes = [1, 10, 100, 1_000, 10_000]
for size in sizes {
print("--- Size: \(size) ---")
Benchmark(
n: size,
cycles: 1_000_000
)
print()
}
}
main()
We seem to be talking on the order of nanoseconds worth of difference but it's tough for me to see any statsig signal here from just inspecting the means. Probably I would need a better benchmark tool that measures throughput along with the confidence intervals between test and control.
Yeah that looks below the noise floor to me, given how testWithAvailable is actually faster than the control at size 1. An interesting experiment re: the constant overhead might be to try it on ContiguousArray, which has a back-deployable .span implementation and doesn't need to check for bridging.
Other than that my usual next steps would be "time profile in instruments" and "look at disassembly and see what it's actually doing".
extension Sequence {
@inlinable
public __consuming func testWithSpanFromContiguousArray() -> [Element] {
var result = ContiguousArray(self)
var span = result.mutableSpan
let count = span.count
for i in 0..<count/2 {
span.swapAt(i, count - ((i + 1) as Int))
}
return Array(result)
}
}
extension Sequence {
@inlinable
public __consuming func testWithUncheckedSpanFromContiguousArray() -> [Element] {
var result = ContiguousArray(self)
var span = result.mutableSpan
let count = span.count
for i in 0..<count/2 {
span.swapAt(unchecked: i, unchecked: count - ((i + 1) as Int))
}
return Array(result)
}
}
I'm still not able to get much statsig signal from inspecting the means… but if this means we do not need to guard on available then this looks like a good idea anyway.
At that point maybe there is some kind of heuristic threshold value where we work directly on ContiguousArray for smol counts and switch to MutableSpan for large collections?
I think that's certainly an expedient approach that would work fine, I'm mostly curious if there's something in the stdlib primitives you're using that could use further optimization work that would have broad benefits.
Apart from that I have noticed essentially none. And I've been taking looks at swiftc produced assemblies a lot lately, specifically to squeeze more performance.
One that I know is horrendous is the lazily bridged NSArray path in Array.span, but the optimizer is pretty good at propagating the "not bridged" information these days, and the check is cheap even if the slow path isn't.
I suggest you translate these tests into full benchmarks using the benchmark package. That way you can more reliably record and compare timing and a variety of other measurements over time.
I might not have too much time to work on this myself before the next branch cut… but I think this could make a pretty good First Issue for a new contributor.