A long time ago when I used a browser that didn't support the shift or
unshift methods of the array object, I came up with an implementation of
queues that guaranteed amortised constant time dequeuing by only moving
elements in the array when the 'space' at the front of the array was as
long as the queue it represented. In modern Javascript it would look like
this:
function Queue(){
var queue=new Array();
var queueSpace=0;
this.enqueue=function(element){
queue.push(element);
}
this.dequeue=function(){
if (queue.length){
var element=queue[queueSpace];
if (++queueSpace*2 >= queue.length){
for (var i=queueSpace;i<queue.length;i++)
queue[i-queueSpace]=queue[i];
queue.length-=queueSpace;
queueSpace=0;
}
return element;
}else{
return undefined;
}
}
}
An unencapsulated version of this had been sitting on a page on my website
for a few years when someone e-mailed me to ask if I knew how well this
performed in various browsers (I didn't) and if I'd be interested in the
results of some tests he would do (I would). Unfortunately he never
e-mailed back, so recently I did some basic tests on my own comparing it,
in Opera, Firefox, and IE, to a basic implementation using the shift
method, and an implementation using a linked list. The results (complete
with pretty graphs) can be seen at the bottom of this page:
http://www.safalra.com/programming/javascript/queues/
I now have some questions about the results I obtained, and wonder if
anyone here who knows how the browsers' Javascript engines work internally
may be able to help.
Comparing this 'delayed shift queue' (DSQ) to a queue using the shift
method showed the DSQ to be significantly faster for larger queues, which
is to be expected as dequeuing is O(1) rather than O(n). Opera was the
fastest (which makes a change from the days when its Javascript engine was
painfully slow), followed by Firefox and then IE, and the slower the
browser the smaller the queue length for which it showed improvements with
the DSQ.
I was puzzled, however, by the comparison of the DSQ to the linked-list
queue, whose graphs is lacking the smooth curves of the first comparison.
In Opera the linked-list queue was about twice as fast until large queue
lengths (over 100000 elements), at which point performance suddenly
declined dramatically, with the linked-list queue taking twice as long as
the DSQ for 500000 elements. In IE the two implementations had very similar
running times, until about 500000 elements when the linked-list queue toook
three times as long as the DSQ. In Firefox the DSQ was always faster, but
the linked-list queue didn't suffer from the sudden drop in performance
that occured in the other two browsers. I was wondering if any of you had
theories (or even better, firm knowledge) of why the three browsers behave
like this.
--
Safalra (Stephen Morley)
http://www.safalra.com/programming/javascript/
