web-locks icon indicating copy to clipboard operation
web-locks copied to clipboard

Implement better queue for the purposes of performance

Open JaoodxD opened this issue 1 year ago • 2 comments

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 avatar Feb 17 '23 18:02 JaoodxD