I should be sleeping right now, but I really wanted to figure out what the best option is for creating a queue in Javascript.
It’s not super relevant since it can’t be used as a queue, but for reference purposes, I ran a loop for 100,000,000 (100 million) iterations, pushing values 0-99,999,999 into an array and then popping the values back out. On my system that took ~4.5 seconds.
Trying to place those same values into a linked list that had both a head and a tail attribute resulted in the process crashing after 32 seconds. Dropping the items being stored down by an order of magnitude to 10 million resulted in the process taking ~2 seconds.
I tried storing just the value 1 in each of the nodes, hoping that would stop the thread from crashing, but that didn’t make any kind of difference–we still crashed at around 32 seconds.
Also for comparison purposes, I pushed a million records (0-999,999) into and array and then used shift to pull them all back out. This is an order of magnitude less than the 10 million records that I put into my linked list and pulled back out in ~2 seconds. I let the algorithm run for more 200 seconds before canceling it.
That’s indicative that using push and shift is at least 3 orders of magnitude slower than a linked list at those kinds of sizes.
If you push and item and then immediately shift it back off of an array 100,000,000 times, the process takes less than 2 seconds, so the issue is with shift having to run through the existing items in the array.
If your queue is always going to be fairly small, then it’s entirely possible that push and shift is the way to go, however, if your queue is going to get very large, then it appears that a linked list would be a better option–as long as it doesn’t get so large that you run into other problems.
It might be worth trying out a map. A map can be iterated through, and it stores the order that things were added into it, but my best guess is that the fact that it is storing the order keys were inserted is going to work against it and we’ll have the same kind of issue that we have with shift and unshift on arrays.