qheap - npm Package Compare versions

Comparing version 1.3.4 to 1.4.0

lib/qheap.js

@@ -7,3 +7,3 @@ /**
  *
- * Copyright (C) 2014-2015 Andras Radics
+ * Copyright (C) 2014-2017 Andras Radics
  * Licensed under the Apache License, Version 2.0
@@ -109,2 +109,23 @@ */
 
+/*
+ * Free unused storage slots in the _list.
+ * The default is to unconditionally gc, use the options to omit when not useful.
+ */
+Heap.prototype.gc = function Heap_gc( options ) {
+    if (!options) options = {};
+
+    var minListLength = options.minLength;      // smallest list that will be gc-d
+    if (minListLength === undefined) minListLength = 0;
+
+    var minListFull = options.minFull;          // list utilization below which to gc
+    if (minListFull === undefined) minListFull = 1.00;
+
+    if (this._list.length >= minListLength && (this.length < this._list.length * minListFull)) {
+        // gc reallocates the array to free the unused storage slots at the end
+        // use splice to actually free memory; 7% slower than setting .length
+        // note: list.slice makes the array slower to insert to??  splice is better
+        this._list.splice(this.length+1, this._list.length);
+    }
+}
+
 Heap.prototype._trimArraySize = function Heap__trimArraySize( list, len ) {
@@ -111,0 +132,0 @@ if (len > 10000 && list.length > 4 * len) {

package.json

 {
   "name": "qheap",
-  "version": "1.3.4",
+  "version": "1.4.0",
   "description": "binary heap priority queue",
@@ -21,4 +21,3 @@ "license": "Apache-2.0",
     "coverage": "env NODE_COVERAGE=1 nyc --reporter lcov --reporter text npm test",
-    "clean": "rm -rf .nyc_output coverage",
-    "coveralls": "env NODE_COVERAGE=1 nyc --reporter text-lcov npm test | & coveralls"
+    "clean": "rm -rf .nyc_output coverage"
   },
@@ -28,2 +27,4 @@ "dependencies": {
   "devDependencies": {
+    "qnit": "0.16.0",
+    "qtimeit": "0.19.0"
   },
@@ -30,0 +31,0 @@ "keywords": [

Readme.md

@@ -5,3 +5,3 @@ qheap
 [![Build Status](https://api.travis-ci.org/andrasq/node-qheap.svg?branch=master)](https://travis-ci.org/andrasq/node-qheap)
-[![Coverage Status](https://coveralls.io/repos/github/andrasq/node-qheap/badge.svg)](https://coveralls.io/github/andrasq/node-qheap)
+[![Coverage Status](https://codecov.io/github/andrasq/node-qheap/coverage.svg?branch=master)](https://codecov.io/github/andrasq/node-qheap?branch=master)
 
@@ -75,45 +75,55 @@ Qheap is a very fast classic heap / priority queue.
 
+### gc( [options] )
 
+Resize the storage array to free all unused array slots.  The options, if
+specified, control when to gc for more efficient operation.
+
+Options:
+
+- `minLength` - do not resize arrays smaller than this cutoff.
+  Default 0, resize even the smallest arrays.
+- `minFull` - do not resize arrays that are more full than this fraction.
+  Default 1.00, resize unless 100% full.
+
+
 Performance
 -----------
 
-The [fastpriorityqueue](https://www.npmjs.com/package/fastpriorityqueue) repo
-includes a handy comparison test, it reports
+Running the `fastpriorityqueue` benchmark:
 
-    Platform: linux 4.3.0-0.bpo.1-amd64 ia32
-    AMD Phenom(tm) II X4 B55 Processor
-    Node version 5.10.1, v8 version 4.6.85.31
+    function rand(i) {
+        i = i + 10000;
+        i = i ^ (i << 16);
+        i = (i >> 5) ^ i ;
+        return i & 0xFF;
+    }
+    function testLoop() {
+        var i, b = new qheap();
+        for (i = 0; i < 128; i++) { b.insert(rand(i)) }
+        for (i = 128; i < 1280; i++) { b.insert(rand(i)) ; b.remove() }
+    }
 
-    Comparing against: 
-    js-priority-queue: https://github.com/adamhooper/js-priority-queue
-    heap.js: https://github.com/qiao/heap.js
-    binaryheapx: https://github.com/xudafeng/BinaryHeap
-    priority_queue: https://github.com/agnat/js_priority_queue
-    js-heap: https://github.com/thauburger/js-heap
-    queue-priority: https://github.com/augustohp/Priority-Queue-NodeJS
-    priorityqueuejs: https://github.com/janogonzalez/priorityqueuejs
-    qheap: https://github.com/andrasq/node-qheap
-    yabh: https://github.com/jmdobry/yabh
+    new heap + 128 inserts + 1152 insert/removes
+    qtimeit=0.19.0 node=6.10.2 v8=5.1.281.98 platform=linux kernel=3.16.0-4-amd64 up_threshold=11
+    arch=ia32 mhz=4419 cpuCount=8 cpu="Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz"
+    name                  speed           rate
+    jsprioqueue           6,037 ops/sec   1000 >>>>>
+    heap                 29,913 ops/sec   4955 >>>>>>>>>>>>>>>>>>>>>>>>>
+    fastpriorityqueue    38,264 ops/sec   6338 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+    qheap                41,139 ops/sec   6814 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
 
-    FastPriorityQueue x 13,869 ops/sec ±0.31% (100 runs sampled)
-    js-priority-queue x 3,290 ops/sec ±0.07% (102 runs sampled)
-    heap.js x 4,762 ops/sec ±0.13% (100 runs sampled)
-    binaryheapx x 2,804 ops/sec ±0.41% (100 runs sampled)
-    priority_queue x 1,977 ops/sec ±0.52% (100 runs sampled)
-    js-heap x 141 ops/sec ±0.30% (83 runs sampled)
-    queue-priority x 244 ops/sec ±0.95% (92 runs sampled)
-    priorityqueuejs x 3,691 ops/sec ±0.75% (74 runs sampled)
-    qheap x 14,692 ops/sec ±0.11% (104 runs sampled)
-    yabh x 3,182 ops/sec ±0.26% (101 runs sampled)
-    Fastest is qheap
 
-    54.568u 0.068s 0:54.47 100.2%   0+0k 0+0io 0pf+0w
+Todo
+----
 
+- might be more efficient to periodically gc the heap on a timer instead of checking
+  on every remove
 
+
 Related Work
 ------------
 
-- [heap](https://www.npmjs.com/package/heap) - the classic, but slow
+- [heap](https://www.npmjs.com/package/heap) - the classic, slow with custom comparator
 - [qheap, this](https://www.npmjs.org/package/qheap) - very fast heap and priority queue
 - [fastpriorityqueue](https://www.npmjs.com/package/fastpriorityqueue) - very fast, includes comprehensive list nodejs heaps
 - [qlist](https://www.npmjs.com/package/qlist) - very fast circular buffer

test/test-qheap.js

 /**
- * Copyright (C) 2014 Andras Radics
+ * Copyright (C) 2014-2017 Andras Radics
  * Licensed under the Apache License, Version 2.0
@@ -143,2 +143,37 @@ */
 
+    'gc': {
+
+        'should always gc if no options': function(t) {
+            var h = new Heap();
+            h.push(1);
+            h.gc();
+            t.equal(h._list.length, 2);
+            t.done();
+        },
+
+        'should gc if meet options': function(t) {
+            var h = new Heap({ size: 10 })
+            h.gc({ minLength: 0, minFull: 0.00001 });
+            t.equal(h._list.length, 1);     // list[0] is always present but is unused
+            t.done();
+        },
+
+        'should not gc if list is too small': function(t) {
+            var h = new Heap({ size: 10 });
+            h.gc({ minLength: 100 });
+            t.equal(h._list.length, 10);
+            t.done();
+        },
+
+        'should not gc if list utilization is high': function(t) {
+            var h = new Heap();
+            for (var i=0; i<20001; i++) h.push(i);
+            for (var i=0; i<5000; i++) h.shift();
+            h.gc({ minFull: 0.50 });
+            t.equal(h._list.length, 20002);
+            t.done();
+        },
+
+    },
+
     'options': {
@@ -154,2 +189,15 @@ 'should accept comparator': function(t) {
 
+        'should accept comparBefore': function(t) {
+            var cmp = function(){};
+            var h = new Heap({ comparBefore: cmp });
+            t.equal(h._isBefore, cmp);
+            t.done();
+        },
+
+        'should accept size': function(t) {
+            var h = new Heap({ size: 3 });
+            t.equal(h._list.length, 3);
+            t.done();
+        },
+
         'should accept freeSpace': function(t) {
@@ -156,0 +204,0 @@ var h = new Heap({ freeSpace: true });

No alert changes

Improved metrics

Total package byte prevSize

24787

increased by35.04%

Lines of code

519

increased by50%

Number of lines in readme file

128

increased by8.47%

Worsened metrics

Dev dependency count

2

increased byInfinity%

No dependency changes