I benchmarked several queue algorithms

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 delete operation 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 4.5s...

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 dequeue() call.

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 😀

Last note: Array.shift() is getting optimized on some platforms, but we shouldn't rely on this to implement algorithms, IMHO.

Credits: Photo by Adrien Delforge on Unsplash