A few weeks ago I posted a code snippet about an async queue. I wrongly implied that this queue was performant but this was not the case (I mostly said it was performant according to other solutions I analyzed at the time) as stated by @peerreynders.
He came with an algorithm based on swapping arrays so the queue would stay performant without having an O(n) time complexity. I found some other algorithms here and there and I wondered wich solution would be the best one, so I benchmarked them.
To simplify the benchmarking, I dropped all the
async handling layer, to focus only on the queue itself.
I tested 4 different algorithms. The related code is available on Github if you want to see the different implementations and the benchmark:
- first algo:
Array.shift()calls (that's what I used); when dequeuing, we simply call
shift()on the item list
- second algo: swapping arrays (@peerreynders's solution); it uses two arrays, one for enqueuing items, and one for dequeuing them; when the dequeuing array is empty, the arrays are quickly resized and swapped
- third algo: ring array; this code is using two indexes with one array to keep track of its start and end offsets; when dequeuing a
deleteoperation is called on the current index
- fourth algo: half size clean up; when reaching the half size of the queue on dequeuing operation, the array is sliced up
If you know other algorithms, please tell me and I'll add it to the benchmarks.
Here's the results:
When enqueuing/dequeuing 1 item:
queue1.ts is the fastest 2.89x faster than queue4.ts 4.73x faster than queue2.ts 11.67x faster than queue3.ts
For 1000 items:
queue2.ts is the fastest 1.17x faster than queue4.ts 7.18x faster than queue1.ts 10.21x faster than queue3.ts
For 10 000 items:
queue2.ts is the fastest 1.2x faster than queue4.ts 8.63x faster than queue1.ts 12.81x faster than queue3.ts
For 100 000 items:
queue2.ts is the fastest 1.19x faster than queue4.ts: enqueue/dequeue 100_000 items 8.26x faster than queue3.ts: enqueue/dequeue 100_000 items 5523.86x faster than queue1.ts: enqueue/dequeue 100_000 items
The first algorithm is performing better when there's only some elements in the queue. But the performance drastically decreases when reaching a few hundreds of them, and it becomes really critical when reaching thousands of items where enqueuing/dequeuing only one element on a queue of 100 000 items takes
The second algorithm is clearly the winner. But we could optimize things when there's only a few elements in the queue.
The third algorithm is the slower implementation, after the first one. This is because of the
delete operation executed at each
The fourth algorithm is performing well, but can be optimized. Currently, it updates the internal array when reaching the half size of it. It can lead to some performance issues when enqueuing/dequeuing items completely and constantly. To improve that, we could compute dynamically an ideal items count so we slice the array up more often.
To conclude: I need to update my code snippet 😀