dw-cache - npm Package Compare versions

Comparing version 0.0.34 to 0.0.35

dist/index.js

@@ -1,2 +0,2 @@
-/*! dw-cache v0.0.34 https://github.com/falsandtru/dw-cache | (c) 2021, falsandtru | (Apache-2.0 AND MPL-2.0) License */
+/*! dw-cache v0.0.35 https://github.com/falsandtru/dw-cache | (c) 2021, falsandtru | (Apache-2.0 AND MPL-2.0) License */
 (function webpackUniversalModuleDefinition(root, factory) {
@@ -353,2 +353,4 @@ if(typeof exports === 'object' && typeof module === 'object')
 
+const heap_1 = __webpack_require__(818);
+
 const assign_1 = __webpack_require__(401);
@@ -364,2 +366,3 @@
       age: global_1.Infinity,
+      earlyExpiring: false,
       limit: 950,
@@ -376,5 +379,5 @@ capture: {
       LRU: new invlist_1.List(),
-      LFU: new invlist_1.List(),
-      OVL: new invlist_1.List()
+      LFU: new invlist_1.List()
     };
+    this.expiries = new heap_1.Heap();
     this.stats = {
@@ -419,2 +422,4 @@ LRU: (0, tuple_1.tuple)(0, 0),
     this.limit = this.settings.limit;
+    this.earlyExpiring = this.settings.earlyExpiring;
+    this.disposer = this.settings.disposer;
   }
@@ -433,18 +438,12 @@
     const index = node.value;
-    callback &&= !!this.settings.disposer;
+    callback &&= !!this.disposer;
     record = callback ? record ?? this.memory.get(index.key) : record;
     this.overlap -= +(index.region === 'LFU' && node.list === this.indexes.LRU);
     node.delete();
-    node.value.overlap?.delete();
     this.memory.delete(index.key);
     this.SIZE -= index.size;
-    callback && this.settings.disposer?.(record.value, index.key);
+    callback && this.disposer?.(record.value, index.key);
   }
 
   ensure(margin, skip) {
-    if (skip) {
-      // Prevent wrong disposal of `skip`.
-      skip.value.expiry = global_1.Infinity;
-    }
-
     let size = skip?.value.size ?? 0;
@@ -454,15 +453,11 @@ if (margin - size <= 0) return;
       LRU,
-      LFU,
-      OVL
+      LFU
     } = this.indexes;
 
     while (this.length === this.capacity || this.size + margin - size > this.space) {
-      const lastNode = OVL.last ?? LFU.last;
-      const lastIndex = lastNode?.value;
       let target;
 
       switch (true) {
-        // NOTE: The following conditions must be ensured that they won't be true if `lastNode` is `skip`.
-        case lastIndex && lastIndex.expiry !== global_1.Infinity && lastIndex.expiry < (0, clock_1.now)():
-          target = lastNode.list === OVL ? lastNode.value.node : lastNode;
+        case (target = this.expiries.peek()) && target !== skip && target.value.expiry < (0, clock_1.now)():
+          target = this.expiries.extract();
           break;
@@ -480,4 +475,3 @@
             if (this.ratio > 500) break;
-            target.value.node = LRU.unshiftNode(target);
-            target.value.overlap = target.value.expiry !== global_1.Infinity ? OVL.unshift(target.value) : void 0;
+            LRU.unshiftNode(target);
             ++this.overlap;
@@ -498,8 +492,8 @@ }
 
-  put(key, value, size = 1, age = this.settings.age) {
-    if (size >= 1 === false) throw new Error(`Spica: Cache: Size must be 1 or more.`);
-    if (age >= 1 === false) throw new Error(`Spica: Cache: Age must be 1 or more.`);
-
+  put(key, value, {
+    size = 1,
+    age = this.settings.age
+  } = {}) {
     if (size > this.space || age <= 0) {
-      this.settings.disposer?.(value, key);
+      this.disposer?.(value, key);
       return false;
@@ -512,11 +506,18 @@ }
     if (record) {
-      const node = record.index;
+      const node = record.inode;
       const val = record.value;
       const index = node.value;
       this.ensure(size, node);
-      index.expiry = expiry;
       this.SIZE += size - index.size;
       index.size = size;
+      index.expiry = expiry;
+
+      if (this.earlyExpiring && expiry !== global_1.Infinity) {
+        index.enode ? this.expiries.update(index.enode, -expiry) : this.expiries.insert(-expiry, node);
+      } else if (this.earlyExpiring) {
+        index.enode && this.expiries.delete(index.enode);
+      }
+
       record.value = value;
-      this.settings.disposer?.(val, key);
+      this.disposer?.(val, key);
       return true;
@@ -530,16 +531,22 @@ }
     this.SIZE += size;
+    const node = LRU.unshift({
+      key,
+      size,
+      expiry,
+      region: 'LRU'
+    });
     this.memory.set(key, {
-      index: LRU.unshift({
-        key,
-        size,
-        expiry,
-        region: 'LRU'
-      }),
+      inode: node,
       value
     });
+
+    if (this.earlyExpiring && expiry !== global_1.Infinity) {
+      node.value.enode = this.expiries.insert(-expiry, node);
+    }
+
     return false;
   }
 
-  set(key, value, size, age) {
-    this.put(key, value, size, age);
+  set(key, value, opts) {
+    this.put(key, value, opts);
     return this;
@@ -551,3 +558,3 @@ }
     if (!record) return;
-    const node = record.index;
+    const node = record.inode;
     const expiry = node.value.expiry;
@@ -572,6 +579,6 @@
     if (!record) return false;
-    const expiry = record.index.value.expiry;
+    const expiry = record.inode.value.expiry;
 
     if (expiry !== global_1.Infinity && expiry < (0, clock_1.now)()) {
-      this.evict(record.index, record, true);
+      this.evict(record.inode, record, true);
       return false;
@@ -586,3 +593,3 @@ }
     if (!record) return false;
-    this.evict(record.index, record, this.settings.capture.delete === true);
+    this.evict(record.inode, record, this.settings.capture.delete === true);
     return true;
@@ -592,2 +599,3 @@ }
   clear() {
+    this.overlap = 0;
     this.SIZE = 0;
@@ -598,4 +606,4 @@ this.ratio = 500;
     this.indexes.LFU.clear();
-    this.indexes.OVL.clear();
-    if (!this.settings.disposer || !this.settings.capture.clear) return void this.memory.clear();
+    this.expiries.clear();
+    if (!this.disposer || !this.settings.capture.clear) return void this.memory.clear();
     const memory = this.memory;
@@ -607,3 +615,3 @@ this.memory = new global_1.Map();
     }] of memory) {
-      this.settings.disposer(value, key);
+      this.disposer(value, key);
     }
@@ -667,4 +675,2 @@ }
     index.region = 'LFU';
-    index.overlap?.delete();
-    index.overlap = void 0;
     this.indexes.LFU.unshiftNode(node);
@@ -675,4 +681,4 @@ return true;
   accessLFU(node) {
+    if (node.list !== this.indexes.LFU) return false;
     const index = node.value;
-    if (node.list !== this.indexes.LFU) return false;
     ++this.stats[index.region][0];
@@ -807,2 +813,136 @@ node.moveToHead();
 
+/***/ 818:
+/***/ ((__unused_webpack_module, exports, __webpack_require__) => {
+
+
+
+Object.defineProperty(exports, "__esModule", ({
+  value: true
+}));
+exports.Heap = void 0;
+
+const alias_1 = __webpack_require__(406); // Max heap
+
+
+const undefined = void 0;
+
+class Heap {
+  constructor(stable = false) {
+    this.stable = stable;
+    this.array = [];
+    this.$length = 0;
+  }
+
+  get length() {
+    return this.$length;
+  }
+
+  insert(priority, value) {
+    const array = this.array;
+    const node = array[this.$length] = [priority, value, this.$length++];
+    upHeapify(array, this.$length, priority);
+    return node;
+  }
+
+  replace(priority, value) {
+    const array = this.array;
+    if (this.$length === 0) return void this.insert(priority, value);
+    const replaced = array[0][1];
+    array[0] = [priority, value, 0];
+    downHeapify(array, 1, this.$length, this.stable);
+    return replaced;
+  }
+
+  extract() {
+    if (this.$length === 0) return;
+    const node = this.array[0];
+    this.delete(node);
+    return node[1];
+  }
+
+  delete(node) {
+    const array = this.array;
+    if (array[node[2]] !== node) throw new Error('Invalid node');
+    array[node[2]] = array[--this.$length];
+    array[node[2]][2] = node[2]; // @ts-expect-error
+
+    array[this.$length] = undefined;
+    node = array[node[2]];
+    node && this.sort(node);
+
+    if (array.length > 2 ** 16 && array.length > this.$length * 2) {
+      array.splice(array.length / 2, array.length);
+    }
+  }
+
+  update(node, priority, value = node[1]) {
+    const array = this.array;
+    if (array[node[2]] !== node) throw new Error('Invalid node');
+    node[1] = value;
+    if (node[0] === priority) return;
+    node[0] = priority;
+    this.sort(node);
+  }
+
+  sort(node) {
+    const array = this.array;
+    return upHeapify(array, node[2] + 1, node[0]) || downHeapify(array, node[2] + 1, this.$length, this.stable);
+  }
+
+  peek() {
+    return this.array[0]?.[1];
+  }
+
+  clear() {
+    this.array = [];
+    this.$length = 0;
+  }
+
+}
+
+exports.Heap = Heap;
+
+function upHeapify(array, index, priority) {
+  let changed = false;
+
+  while (index > 1) {
+    const parent = (0, alias_1.floor)(index / 2);
+    if (array[parent - 1][0] >= priority) break;
+    [array[parent - 1], array[index - 1]] = [array[index - 1], array[parent - 1]];
+    [array[parent - 1][2], array[index - 1][2]] = [array[index - 1][2], array[parent - 1][2]];
+    index = parent;
+    changed ||= true;
+  }
+
+  return changed;
+}
+
+function downHeapify(array, index, length, stable) {
+  let changed = false;
+
+  while (index < length) {
+    const left = index * 2;
+    const right = index * 2 + 1;
+    let max = index;
+
+    if (left <= length && (stable ? array[left - 1][0] >= array[max - 1][0] : array[left - 1][0] > array[max - 1][0])) {
+      max = left;
+    }
+
+    if (right <= length && (stable ? array[right - 1][0] >= array[max - 1][0] : array[right - 1][0] > array[max - 1][0])) {
+      max = right;
+    }
+
+    if (max === index) break;
+    [array[index - 1], array[max - 1]] = [array[max - 1], array[index - 1]];
+    [array[index - 1][2], array[max - 1][2]] = [array[max - 1][2], array[index - 1][2]];
+    index = max;
+    changed ||= true;
+  }
+
+  return changed;
+}
+
+/***/ }),
+
 /***/ 452:
@@ -809,0 +949,0 @@ /***/ (function(__unused_webpack_module, exports, __webpack_require__) {

package.json

 {
   "name": "dw-cache",
-  "version": "0.0.34",
+  "version": "0.0.35",
   "description": "Dual window cache adaptively coordinates the ratio of LRU to LFU using the two sliding windows.",
@@ -53,3 +53,3 @@ "private": false,
     "npm-check-updates": "^13.1.1",
-    "spica": "0.0.560",
+    "spica": "0.0.563",
     "ts-loader": "^9.3.0",
@@ -56,0 +56,0 @@ "typescript": "4.7.3",

README.md

@@ -18,3 +18,3 @@ # Dual Window Cache
 |Algorithm|Key size|
-|---------|--|
+|:-------:|:-:|
 |LRU      |x1|
@@ -25,2 +25,4 @@ |DWC      |x1|
 
+https://github.com/ben-manes/caffeine/wiki/Efficiency
+
 ## Benchmark
@@ -52,3 +54,3 @@
 
-https://github.com/ben-manes/caffeine/wiki/Efficiency#search
+https://github.com/dgraph-io/ristretto#search
 
@@ -90,24 +92,24 @@ ### Throughput
 ```
-'LRUCache simulation 100 x 4,921,231 ops/sec ±0.65% (64 runs sampled)'
+'LRUCache simulation 100 x 5,161,510 ops/sec ±2.47% (58 runs sampled)'
 
-'DW-Cache simulation 100 x 3,932,885 ops/sec ±0.48% (66 runs sampled)'
+'DW-Cache simulation 100 x 3,699,800 ops/sec ±1.56% (60 runs sampled)'
 
-'LRUCache simulation 1,000 x 4,643,937 ops/sec ±0.63% (64 runs sampled)'
+'LRUCache simulation 1,000 x 4,374,297 ops/sec ±0.62% (61 runs sampled)'
 
-'DW-Cache simulation 1,000 x 3,659,060 ops/sec ±0.47% (65 runs sampled)'
+'DW-Cache simulation 1,000 x 3,111,354 ops/sec ±3.63% (58 runs sampled)'
 
-'LRUCache simulation 10,000 x 4,309,322 ops/sec ±1.62% (62 runs sampled)'
+'LRUCache simulation 10,000 x 4,603,830 ops/sec ±2.30% (61 runs sampled)'
 
-'DW-Cache simulation 10,000 x 2,682,612 ops/sec ±3.44% (62 runs sampled)'
+'DW-Cache simulation 10,000 x 2,754,571 ops/sec ±3.38% (55 runs sampled)'
 
-'LRUCache simulation 100,000 x 3,083,105 ops/sec ±1.11% (62 runs sampled)'
+'LRUCache simulation 100,000 x 3,059,272 ops/sec ±1.63% (59 runs sampled)'
 
-'DW-Cache simulation 100,000 x 1,646,118 ops/sec ±6.21% (55 runs sampled)'
+'DW-Cache simulation 100,000 x 1,625,055 ops/sec ±7.78% (49 runs sampled)'
 
-'LRUCache simulation 1,000,000 x 1,519,991 ops/sec ±5.31% (50 runs sampled)'
+'LRUCache simulation 1,000,000 x 1,700,876 ops/sec ±5.18% (51 runs sampled)'
 
-'DW-Cache simulation 1,000,000 x 798,439 ops/sec ±6.88% (54 runs sampled)'
+'DW-Cache simulation 1,000,000 x 836,083 ops/sec ±8.45% (53 runs sampled)'
 ```
 
-https://github.com/falsandtru/spica/runs/6743280573
+https://github.com/falsandtru/spica/runs/6751777283
 
@@ -121,2 +123,3 @@ ## API
     readonly age?: number;
+    readonly earlyExpiring?: boolean;
     readonly limit?: number;
@@ -133,6 +136,6 @@ readonly disposer?: (value: V, key: K) => void;
   constructor(opts: Cache.Options<K, V>);
-  put(key: K, value: V, size?: number, age?: number): boolean;
-  put(this: Cache<K, undefined>, key: K, value?: V, size?: number, age?: number): boolean;
-  set(key: K, value: V, size?: number, age?: number): this;
-  set(this: Cache<K, undefined>, key: K, value?: V, size?: number, age?: number): this;
+  put(key: K, value: V, opts?: { size?: number; age?: number; }): boolean;
+  put(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }): boolean;
+  set(key: K, value: V, opts?: { size?: number; age?: number; }): this;
+  set(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }): this;
   get(key: K): V | undefined;
@@ -139,0 +142,0 @@ has(key: K): boolean;

No alert changes

Improved metrics

Total package byte prevSize

71783

increased by4.6%

Lines of code

1217

increased by9.54%

Number of lines in readme file

144

increased by2.13%

No dependency changes