apple / apple/swift-algorithms

Strange performance decline of nested `chain()` application

Open
#196 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Swift
Stars
6.3k
Forks
483
PR merge metrics
No merged PRs in 30d

Description

Hi! I'm recently find that `chain` function in Swift Algorithms is really convenience tool for making better performance and still writing clear code. And because I was curious for how performance is improved, I made a performance test project. I found that, for `chain(chain(x, y), z)`, there is great performance improvement. However, when it comes to `chain(chain(chain(w, x), y), z)`, the performance becomes rapidly worse (still better than mere array addition though).

The test code is available here. Sample result is also in README.md.
https://github.com/ensan-hcl/swift_chain_performance

**Swift Algorithms version:** `1.0.0`
**Swift version:** swift-driver version: 1.75.2 Apple Swift version 5.8 (swiftlang-5.8.0.124.2 clang-1403.0.22.11.100) Target: x86_64-apple-macosx13.0

### Checklist
- [x] If possible, I've reproduced the issue using the `main` branch of this package
- [x] I've searched for [existing GitHub issues](https://github.com/apple/swift-algorithms/issues)

### Steps to Reproduce
For this function, I took performance test.
```swift
// MARK: function used to test performance
func takeSequence(_ sequence: some Sequence) {
for i in sequence {
_ = i + 1
}
}
```

Like this, three patterns are tested. First is `a+b`, second is `chain(a, b)`, and third is just a repetition of the same process. It is desired that the second and the third make similar performance, but when the argument increase more than four, the performance of the second pattern suddenly becomes much worse than the third pattern.
```swift
// MARK: test for 2 array chaining
func testTake2ArrayAdditionPerformance() throws {
measure {
let a = Array(0 ..< 100)
let b = Array(100 ..< 200)
for _ in 0..<1000000 {
takeSequence(a + b)
}
}
}

func testTake2ArrayChainPerformance() throws {
measure {
let a = Array(0 ..< 100)
let b = Array(100 ..< 200)
for _ in 0..<1000000 {
takeSequence(chain(a, b))
}
}
}

func testTake2ArrayPerformance() throws {
measure {
let a = Array(0 ..< 100)
let b = Array(100 ..< 200)
for _ in 0..<1000000 {
takeSequence(a)
takeSequence(b)
}
}
}
```

Contributor guide

Open the contributing guide

Research direction

Start with the linked swift_chain_performance project and its README.md, then run the provided benchmarks around takeSequence and nested chain calls. Compare the two-array and deeper nested cases; done means the performance behavior is explained and any regression is covered by a reproducible benchmark or test.

Written by the indexing model from the issue text.

Assessment

Tech stack
swift
Domain
performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.