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

Implement better queue for the purposes of performance #50

Open
JaoodxD opened this issue Feb 17, 2023 · 2 comments
Open

Implement better queue for the purposes of performance #50

JaoodxD opened this issue Feb 17, 2023 · 2 comments

Comments

@JaoodxD
Copy link

JaoodxD commented Feb 17, 2023

Internaly web-locks uses default array as a queue and it can cause performance issues in case of drasticaly growing consumers amount.

The solution would be to replace current queue with more efficient implementation.

I propose to either use single-linked list or more perfomant implementation of array queue.

First approach would be to use my implementation of queue that can be found here.
Queue based on default array leads to O(n) time complexity of retrieving because of reindexing every other element in queue.
Single-linked list changes it to O(1) time consumption.

Another approach would be to use improved version of default array based queue from @datastructures-js/queue which also gives us O(1) time complexity but with additional memory consumption.

Benchmarks shows us that they both works much faster than original one.
Actually second one is a bit faster (on average) than first because of less memory allocation for each node of the queue.

Since performance of resource access is crucial in this plot I believe it's necessary to change the implementation.

@JaoodxD JaoodxD changed the title Implement better queue for the purposes of perfomance Implement better queue for the purposes of performance Feb 17, 2023
@JaoodxD
Copy link
Author

JaoodxD commented Feb 23, 2023

@tshemsedinov up

@JaoodxD
Copy link
Author

JaoodxD commented Feb 23, 2023

@datastructures-js/queue has one disadvantage. It has no 'shift' method to retrieve element from queue.
To keep interface push/shift unchanged we can build adapter over that implementation of queue.

@JaoodxD JaoodxD mentioned this issue Mar 14, 2023
5 tasks
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

No branches or pull requests

1 participant