denque - npm Package Compare versions

Comparing version 2.0.1 to 2.1.0

CHANGELOG.md

@@ -0,1 +1,8 @@
+## 2.1.0
+
+ - fix: issue where `clear()` is still keeping references to the elements (#47)
+ - refactor: performance optimizations for growth and array copy (#43)
+ - refactor: performance optimizations for toArray and fromArray (#46)
+ - test: add additional benchmarks for queue growth and `toArray` (#45)
+
 ## 2.0.1
@@ -2,0 +9,0 @@

index.js

@@ -8,10 +8,12 @@ 'use strict';
   var options = options || {};
+  this._capacity = options.capacity;
 
   this._head = 0;
   this._tail = 0;
-  this._capacity = options.capacity;
-  this._capacityMask = 0x3;
-  this._list = new Array(4);
+
   if (Array.isArray(array)) {
     this._fromArray(array);
+  } else {
+    this._capacityMask = 0x3;
+    this._list = new Array(4);
   }
@@ -360,2 +362,3 @@ }
 Denque.prototype.clear = function clear() {
+  this._list = new Array(this._list.length);
   this._head = 0;
@@ -394,3 +397,10 @@ this._tail = 0;
 Denque.prototype._fromArray = function _fromArray(array) {
-  for (var i = 0; i < array.length; i++) this.push(array[i]);
+  var length = array.length;
+  var capacity = this._nextPowerOf2(length);
+
+  this._list = new Array(capacity);
+  this._capacityMask = capacity - 1;
+  this._tail = length;
+
+  for (var i = 0; i < length; i++) this._list[i] = array[i];
 };
@@ -401,19 +411,32 @@
  * @param fullCopy
+ * @param size Initialize the array with a specific size. Will default to the current list size
  * @returns {Array}
  * @private
  */
-Denque.prototype._copyArray = function _copyArray(fullCopy) {
-  var newArray = [];
-  var list = this._list;
-  var len = list.length;
+Denque.prototype._copyArray = function _copyArray(fullCopy, size) {
+  var src = this._list;
+  var capacity = src.length;
+  var length = this.length;
+  size = size | length;
+
+  // No prealloc requested and the buffer is contiguous
+  if (size == length && this._head < this._tail) {
+    // Simply do a fast slice copy
+    return this._list.slice(this._head, this._tail);
+  }
+
+  var dest = new Array(size);
+
+  var k = 0;
   var i;
   if (fullCopy || this._head > this._tail) {
-    for (i = this._head; i < len; i++) newArray.push(list[i]);
-    for (i = 0; i < this._tail; i++) newArray.push(list[i]);
+    for (i = this._head; i < capacity; i++) dest[k++] = src[i];
+    for (i = 0; i < this._tail; i++) dest[k++] = src[i];
   } else {
-    for (i = this._head; i < this._tail; i++) newArray.push(list[i]);
+    for (i = this._head; i < this._tail; i++) dest[k++] = src[i];
   }
-  return newArray;
-};
 
+  return dest;
+}
+
 /**
@@ -424,12 +447,15 @@ * Grows the internal list array.
 Denque.prototype._growArray = function _growArray() {
-  if (this._head) {
-    // copy existing data, head to end, then beginning to tail.
-    this._list = this._copyArray(true);
+  if (this._head != 0) {
+    // double array size and copy existing data, head to end, then beginning to tail.
+    var newList = this._copyArray(true, this._list.length << 1);
+
+    this._tail = this._list.length;
     this._head = 0;
+
+    this._list = newList;
+  } else {
+    this._tail = this._list.length;
+    this._list.length <<= 1;
   }
 
-  // head is at 0 and array is now full, safe to extend
-  this._tail = this._list.length;
-
-  this._list.length <<= 1;
   this._capacityMask = (this._capacityMask << 1) | 1;
@@ -447,3 +473,15 @@ };
 
+/**
+ * Find the next power of 2, at least 4
+ * @private
+ * @param {number} num 
+ * @returns {number}
+ */
+Denque.prototype._nextPowerOf2 = function _nextPowerOf2(num) {
+  var log2 = Math.log(num) / Math.log(2);
+  var nextPow2 = 1 << (log2 + 1);
 
+  return Math.max(nextPow2, 4);
+}
+
 module.exports = Denque;

package.json

 {
   "name": "denque",
-  "version": "2.0.1",
+  "version": "2.1.0",
   "description": "The fastest javascript implementation of a double-ended queue. Used by the official Redis, MongoDB, MariaDB & MySQL libraries for Node.js and many other libraries. Maintains compatability with deque.",
@@ -28,3 +28,6 @@ "main": "index.js",
     "benchmark_remove": "node benchmark/remove",
-    "benchmark_removeOne": "node benchmark/removeOne"
+    "benchmark_removeOne": "node benchmark/removeOne",
+    "benchmark_growth": "node benchmark/growth",
+    "benchmark_toArray": "node benchmark/toArray",
+    "benchmark_fromArray": "node benchmark/fromArray"
   },
@@ -31,0 +34,0 @@ "repository": {

No alert changes

Improved metrics

Total package byte prevSize

30361

increased by4.89%

Lines of code

469

increased by6.59%

No dependency changes