Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[SR-11956] SynchronizedQueue in SwiftPM has a Quadratic Dequeue Operation #4634

Closed
CodaFi opened this issue Dec 16, 2019 · 2 comments
Closed

[SR-11956] SynchronizedQueue in SwiftPM has a Quadratic Dequeue Operation #4634

CodaFi opened this issue Dec 16, 2019 · 2 comments

Comments

@CodaFi
Copy link
Member

CodaFi commented Dec 16, 2019

Previous ID SR-11956
Radar rdar://41727810
Original Reporter @CodaFi
Type Improvement
Status Closed
Resolution Invalid
Additional Detail from JIRA
Votes 0
Component/s Package Manager
Labels Improvement, StarterBug
Assignee None
Priority Medium

md5: 7d5f08f9fb8b80be909346608f5e40c2

relates to:

  • SR-8190 Introduce a RingBuffer to the Standard Library

Issue Description:

SynchronizedQueue in the Basic library is using Array.removeFirst() to implement dequeueing which is O👎 in the length of the array making the dequeue operation quadratic in the number of dequeues. It is not a huge bottleneck because it’s all array memory ops, but a (growable) ring buffer or a future Deque-like thing in Swift’s Standard Library would make for a better backing store.
@CodaFi
Copy link
Member Author

CodaFi commented Dec 16, 2019

OK, so

O(n)

emojifies as that, and I'm leaving it. Anyhow, this bug can be fixed one of two ways, but both are going to involve a new kind of backing data structure. There's the way that just fixes SwiftPM's library, and there's the way where SR-8190 gets implemented, then this gets squashed afterwards.

@swift-ci
Copy link
Contributor

Comment by Tim Gymnich (JIRA)

SynchronizedQueue is using a linked list as storage since March of 2020 (#2656) so this no longer applies.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
@shahmishal shahmishal transferred this issue from apple/swift May 4, 2022
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@CodaFi @swift-ci