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

Quadratic performance issue in AsyncQueue #1725

Open
ahoppen opened this issue Sep 29, 2024 · 1 comment · May be fixed by #1840
Open

Quadratic performance issue in AsyncQueue #1725

ahoppen opened this issue Sep 29, 2024 · 1 comment · May be fixed by #1840

Comments

@ahoppen
Copy link
Member

ahoppen commented Sep 29, 2024

Adding an item to AsyncQueue<Serial> is linear in the number of pending queue items, thus adding n items to an AsyncQueue before any can execute is in O(n^2). This decision was made intentionally because the primary use case for AsyncQueue was to track pending LSP requests, of which we don’t expect to have too many pending requests at any given time.

But we should be able to resolve the quadratic issue of AsyncQueue<Serial> by making a new task only depend on the last item in the queue, which then transitively depends on all the previous items.

@ahoppen
Copy link
Member Author

ahoppen commented Oct 14, 2024

Synced to Apple’s issue tracker as rdar://137886469

ahoppen added a commit to ahoppen/sourcekit-lsp that referenced this issue Nov 22, 2024
Adding an item to `AsyncQueue` was linear in the number of pending queue items, thus adding n items to an `AsyncQueue` before any can execute is in O(n^2). This decision was made intentionally because the primary use case for `AsyncQueue` was to track pending LSP requests, of which we don’t expect to have too many pending requests at any given time.

While we can't fix the quadratic performance issue in general, we can resolve the quadratic issue of `AsyncQueue<Serial>` by making a new task only depend on the last item in the queue, which then transitively depends on all the previous items. `AsyncQueue<Serial>` are the queues that are most likely to contain many items.

Fixes swiftlang#1725
rdar://137886469
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant