Tag: Arrays

Queue Creation Options

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.

Array.Shift speed

I got to thinking tonight that before blindly assuming that unshift in JavaScript was slow, but shift was fast, that I should double check that.

As it turns out, shift is roughly as slow as unshift on arrays, which means I need to re-think how I would implement a queue in JavasScript. Just using array.push() and array.shift() works, but is unnecessarily slow.

My initial thought is to use a linked list that has both a head and a tail pointer. I’ll need to test out the speed of that kind of construct against the speed of array.push() and array.shift(). It’s possible that there are some other factors that would slow a linked list down in comparison for use as a queue.

More on that once I’m done testing.

Unshift in Javascript

For a very long time now, I had been under the understanding that since Javascript arrays were just a kind of object, that array.unshift() wasn’t any more costly that array.push().

Today I finally did some testing and found out that I was very much wrong. Now you know and won’t experience the same performance issues that I ran into.