An autotracked implementation of a ring-buffer-backed double-ended queue
BSD-2-CLAUSE License
⚠️ NOTE: this is the README for the upcoming v2 release! For the v1 README, see here. ⚠️
An autotracked implementation of a double-ended queue, implemented as a ring-buffer backed by a native JavaScript array, with optimal performance for all common operations:
N
This is handy for cases where you need to be able to push items onto and pop items off of either end of a queue of a fixed size, especially where you want to be able to have fast reads from anywhere in the queue.
For example, if you have a stream of events coming across a websocket connection, which you want to display to a user, but you only ever want to keep 1,000 of them in memory at any given time, this allows you to simply push onto the back of the queue as new items come in, with no need to manually manage the front of the queue to maintain the queue size.
Create a queue of a specified capacity, and then push items into it from existing arrays or individual values:
// Create a queue with capacity 5, from an existing array of elements:
import TrackedQueue from 'tracked-queue';
let queue = new TrackedQueue<string>({ capacity: 5 });
queue.append(['alpha', 'bravo', 'charlie']);
console.log(queue.size); // 3
console.log([...queue]); // ["alpha", "bravo", "charlie"]
queue.pushBack('delta');
console.log(queue.size); // 4
console.log([...queue]); // ["alpha", "bravo", "charlie", "delta"]
If you append more elements to the back of the queue, exceeding its capacity, it will drop the front of the queue, with the size
of the queue never exceeding its specified capacity, and any items removed to make room are returned. (The same goes for prepend
, on the front of the queue.)
let pushedOut = queue.append(["echo", "foxtrot");
console.log(queue.size); // 5
console.log([...queue]); // ["bravo", "charlie", "delta", "echo", "foxtrot"]
console.log(pushedOut); // ["alpha"]
You can also add and remove items to and from either end of the queue:
let poppedFromBack = queue.popBack();
console.log(poppedFromBack); // "foxtrot"
console.log([...queue]); // ["bravo", "charlie", "delta", "echo"]
let poppedFromFront = queue.popFront();
console.log(poppedFromFront); // "bravo"
console.log([...queue]); // ["charlie", "delta", "echo"]
queue.pushBack('golf');
queue.pushFront('hotel');
console.log([...queue]); // ["hotel", "charlie", "delta", "echo", "golf"]
These also return a value which had to be popped to make room for them, if any:
let poppedByPush = queue.pushBack('india');
console.log([...queue]); // ["charlie", "delta", "echo", "golf", "india"]
console.log(poppedByPush); // "hotel"
// make the queue non-empty
queue.popFront();
let nothingPopped = queue.pushFront('juliet');
console.log([...queue]); // ["juliet", "delta", "echo", "golf", "india"]
console.log(poppedByPush); // undefined
This project follows the current draft of the Semantic Versioning for TypeScript Types specification.
-private
module are publicThis project uses native Proxy
(via a dependency), and so is not compatible with IE11. It supports N-1 for all other browsers.
With npm:
npm install tracked-queue
With yarn:
yarn add tracked-queue
With ember-cli:
ember install tracked-queue
The "dummy app" includes two performance demos, which you can see by running ember serve
and navigating to http://localhost:4200
:
A render performance demo showing that the queue implementation itself is never the bottleneck for performance; the cost of rendering DOM elements is.
An ops performance demo, which allows you to see the behavior of pushing and popping to and from the front and back of the queue. (This is a naive measurement using the Performance
API.) A few things to observe:
When the queue capacity is much larger than the number of items pushed into or popped out of it, the performance of pushBack
and popBack
from the back of the queue is comparable to native array push and pop actions, because it is just those operations plus bumping the index for the "back" of the queue
When the number of items pushed exceeds the queue capacity, causing the queue to “wrap”, pushBack
and popBack
insertion times drops to around 100× worse than native, but space usage is bounded: native push
and pop
are fast because they allow the buffer to grow in an unbounded fashion. This is the fundamental tradeoff of a ring-buffer: it provides control over space usage in exchange for slightly higher costs for push and pop on the back of the queue
The performance of pushFront
and popFront
is about 10× worse than native unshift
and shift
up to a threshold (which varies per-browser), at which point the performance of the native methods becomes hundreds of times worse and degrades rapidly, to the point where pushFront
and popFront
will hang a browser tab when dealing with much more than around 100,000 operations, as the array resizing and moving around items grows in an unbounded fashion. Meanwhile, pushFront
and popFront
have consistent performance characteristics no matter how large the queue is.
You can see these dynamics clearly by varying the number of operations to perform and the size of the queue.
See the Contributing guide for details.
This project is licensed under the BSD 2-Clause License.