swift-collections
swift-collections copied to clipboard
`Deque.Iterator` is slower than `IndexingIterator`
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.
Steps to Reproduce
Run the upcoming Deque benchmarks, and look at the results.
self.add(
title: "Deque<Int> 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<Int> 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<Int> 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<Int> 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
![02 iteration](https://user-images.githubusercontent.com/608696/200986122-1f833b8e-1c34-4375-a45c-c22d8081f6d4.png)