js-queues.js

var hrtime;

if (typeof process !== 'undefined') {
    hrtime = process.hrtime;
} else {
    // taken from https://github.com/kumavis/browser-process-hrtime
    hrtime = (function() {
        // polyfil for window.performance.now
        var performance = typeof performance !== 'undefined' ? performance : {};
        var performanceNow =
            performance.now ||
            performance.mozNow ||
            performance.msNow ||
            performance.oNow ||
            performance.webkitNow ||
            function() {
                return (new Date()).getTime()
            }

        // generate timestamp or delta
        // see http://nodejs.org/api/process.html#process_process_hrtime
        return function(previousTimestamp) {
            var clocktime = performanceNow.call(performance) * 1e-3
            var seconds = Math.floor(clocktime)
            var nanoseconds = Math.floor((clocktime % 1) * 1e9)
            if (previousTimestamp) {
                seconds = seconds - previousTimestamp[0]
                nanoseconds = nanoseconds - previousTimestamp[1]
                if (nanoseconds < 0) {
                    seconds--
                    nanoseconds += 1e9
                }
            }
            return [seconds, nanoseconds]
        }
    })();
}

// define the maximum benchmark length
var MAXIMUM_BENCHMARK_LENGTH = 65536;

// initialise the benchmark length
var benchmarkLength = 1;

console.log(['Length', 'Queue', 'LLQ', 'Array'].join('\t'));
setTimeout(benchmarkQueues, 100);

/* Runs a single iteration of the benchmark, and sets the next iteration
 * to run after a delay.
 */
function benchmarkQueues() {
    // run the benchmark
    var queueResult = benchmarkQueue(benchmarkLength, new Queue());
    var linkedListResult = benchmarkQueue(benchmarkLength, new LinkedListQueue());
    var arrayResult = benchmarkQueue(benchmarkLength, []);
    console.log([benchmarkLength, Math.round(queueResult), Math.round(linkedListResult), Math.round(arrayResult)].join('\t'));
    // run another iteration if necessary
    benchmarkLength *= 2;
    if (benchmarkLength <= MAXIMUM_BENCHMARK_LENGTH) {
        setTimeout(benchmarkQueues, 500);
    }
}

/* Returns the number of operations performed in a millisecond for a queue
 * of the specified length and type. The parameters are:
 *
 * length   - the length of the queue
 * queue    - a queue instance
 */
function benchmarkQueue(length, queue) {
    // fill the queue to the appropriate length
    // for (var index = 0; index < length; index++) queue.push(null);
    // initialise the count of operations
    var operations = 0;
    // initialise the start and end times
    var start = hrtime();
    var nanos;
    var index;
    var count = 0;
    // loop until the benchmark has run for at least half a second
    while (nanos === undefined || nanos < 5e8) {
        if (count < 0) {
            count = 0;
        }
        for (index = 0; index < length; index++) {
            queue.push(null);
        }
        for (index = 0; index < length; index++) {
            queue.shift();
            // Simulate random alternation between pushing and shifting
            if (count % index === 0) {
                var j = length / 4;
                operations += j * 2;
                for (var k = j; k > 0; k--) queue.push(0);
                for (var k = j; k > 0; k--) queue.shift();
            }
        }
        operations += length * 2;
        var diff = hrtime(start);
        nanos = diff[0] * 1e9 + diff[1];
        count++;
    }
    // if (queue.isEmpty) console.log(queue.isEmpty());
    // return the number of operations performed per millisecond
    return operations / (nanos / 1e6);
}

function Queue() {
    var array = [],
        head = 0;
    this.push = function(item) {
        array.push(item);
    };
    this.shift = function() {
        var item = array[head];
        array[head] = null;
        if (++head >= 100 && head * 2 >= array.length) {
            array = array.slice(head);
            head = 0;
        }
        return item;
    };
    this.isEmpty = function() {
        return head === array.length;
    };
}

function LinkedListQueue() {
    var head = null,
        tail = null;
    this.push = function(item) {
        var node = { value: item, next: null };
        if (head === null) {
            head = tail = node;
        } else {
            tail = tail.next = node;
        }
    };
    this.shift = function() {
        if (head === null) {
            return undefined;
        }
        var item = head.value;
        head = head.next;
        if (head === null) {
            tail = null;
        }
        return item;
    };
    this.isEmpty = function() {
        return head === null;
    };
}