apple / apple/swift-collections
`Deque.Iterator` is slower than `IndexingIterator`
- Dominant language
- Swift
- Stars
- 4.5k
- Forks
- 405
- Avg merge
- 3d 3h
- Merged PRs (30d)
- 10
Description
`Deque` implements a custom iterator that's supposed to be faster than just going through integer indices, but in actual benchmarks it turns out be slower. Either fix it to be faster, or if that cannot be done, just revert to the standard `IndexingIterator`.
### Information
- **Package version:** release/1.1
- **Platform version:** macOS 13
- **Swift version:** Swift 5.7
### 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-collections/issues).
### Steps to Reproduce
Run the upcoming Deque benchmarks, and look at the results.
```swift
self.add(
title: "Deque sequential iteration (contiguous, iterator)",
input: [Int].self
) { input in
let deque = Deque(input)
return { timer in
for i in deque {
blackHole(i)
}
}
}
self.add(
title: "Deque sequential iteration (discontiguous, iterator)",
input: [Int].self
) { input in
let deque = Deque(discontiguous: input)
return { timer in
for i in deque {
blackHole(i)
}
}
}
self.add(
title: "Deque sequential iteration (contiguous, indices)",
input: [Int].self
) { input in
let deque = Deque(input)
return { timer in
for i in deque.indices {
blackHole(deque[i])
}
}
}
self.add(
title: "Deque sequential iteration (discontiguous, indices)",
input: [Int].self
) { input in
let deque = Deque(discontiguous: input)
return { timer in
for i in deque.indices {
blackHole(deque[i])
}
}
}
```
### Expected behavior
I expected `Deque.Iterator` to be at least slightly faster than simply indexing from `0` to `count`.
### Actual behavior

Contributor guide
Research direction
Run the upcoming Deque benchmarks described in the issue and compare sequential iterator results with indexed iteration for contiguous and discontiguous deques. Trace the existing Deque.Iterator implementation and determine whether it can outperform IndexingIterator; done means the iterator is faster, or the implementation uses the standard indexed iterator if that cannot be achieved.
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
- 45/100