dw-cache - npm Package Compare versions

Comparing version 0.0.70 to 0.0.71

dist/index.js

@@ -1,2 +0,2 @@
-/*! dw-cache v0.0.70 https://github.com/falsandtru/dw-cache | (c) 2021, falsandtru | (Apache-2.0 AND MPL-2.0) License */
+/*! dw-cache v0.0.71 https://github.com/falsandtru/dw-cache | (c) 2021, falsandtru | (Apache-2.0 AND MPL-2.0) License */
 (function webpackUniversalModuleDefinition(root, factory) {
@@ -315,7 +315,6 @@ if(typeof exports === 'object' && typeof module === 'object')
       entrance: 5,
-      // 15のほうがベンチマークの全体的なスコアが上がるが低容量でのループ耐性が上がる代わりに
-      // それ以外の性能が下がっているため実用的には20のほうがよいと思われる。
-      threshold: 20,
       sweep: {
-        interval: 10,
+        threshold: 1,
+        window: 5,
+        interval: 4,
         shift: 1
@@ -333,3 +332,2 @@ },
     this.$size = 0;
-    this.misses = 0;
     if (typeof capacity === 'object') {
@@ -355,4 +353,3 @@ opts = capacity;
     this.stats = opts.resolution || opts.offset ? new StatsExperimental(this.window, settings.resolution, settings.offset) : new Stats(this.window);
-    this.threshold = settings.threshold;
-    this.sweeper = new Sweeper(this.indexes.LRU, settings.sweep.interval, settings.sweep.shift);
+    this.sweeper = new Sweeper(this.indexes.LRU, settings.sweep.threshold, capacity, capacity * settings.sweep.window / 100 | 0 || 1, settings.sweep.interval, settings.sweep.shift);
     this.disposer = settings.disposer;
@@ -396,3 +393,3 @@ this.test = settings.test;
       } else {
-        if (this.misses > LRU.length * this.threshold / 100 && !this.test) {
+        if (this.sweeper.isAvailable() && !this.test) {
           this.sweeper.sweep();
@@ -435,3 +432,3 @@ } else if (LFU.length > this.capacity * (this.ratio ?? this.limit) / 1000) {
     const match = node !== undefined;
-    !match && ++this.misses;
+    !match && this.sweeper.miss();
     node = this.ensure(size, node, true);
@@ -516,3 +513,2 @@ if (node !== undefined) {
     this.stats.clear();
-    this.misses = 0;
     this.sweeper.clear();
@@ -543,2 +539,3 @@ if (!this.disposer || !this.settings.capture.clear) return void this.memory.clear();
     this.stats.resize(window);
+    this.sweeper.resize(capacity, capacity * this.settings.sweep.window / 100 | 0 || 1);
     this.ensure(0);
@@ -568,11 +565,11 @@ }
     } = this.indexes;
-    this.misses &&= 0;
-    this.sweeper.clear();
+    this.sweeper.hit();
     if (node.list === LRU) {
       // For memoize.
       if (node === LRU.head && !this.test) return;
-      ++this.stats[region][0];
       if (region === 'LFU') {
+        this.stats.hitLFU();
         --this.overlap;
       } else {
+        this.stats.hitLRU();
         entry.region = 'LFU';
@@ -584,3 +581,3 @@ }
       if (node === LFU.head && !this.test) return;
-      ++this.stats[region][0];
+      this.stats.hitLFU();
       node.moveToHead();
@@ -629,11 +626,12 @@ }
     this.offset = 0;
-    this.max = 2;
-    this.LRU = [0];
-    this.LFU = [0];
+    this.currLRUHits = 0;
+    this.prevLRUHits = 0;
+    this.currLFUHits = 0;
+    this.prevLFUHits = 0;
   }
-  static rate(window, hits1, hits2, offset) {
-    const currHits = hits1[0];
-    const prevHits = hits1[1];
-    const currTotal = currHits + hits2[0];
-    const prevTotal = prevHits + hits2[1];
+  static rate(window, targets, remains, offset) {
+    const currHits = targets[0];
+    const prevHits = targets[1];
+    const currTotal = currHits + remains[0];
+    const prevTotal = prevHits + remains[1];
     const prevRate = prevHits && prevHits * 100 / prevTotal;
@@ -646,43 +644,33 @@ const currRatio = currTotal * 100 / window - offset;
   }
-  get length() {
-    return this.LRU.length;
-  }
   isFull() {
-    return this.length === this.max;
+    return this.prevLRUHits !== 0 || this.prevLFUHits !== 0;
   }
+  hitLRU() {
+    ++this.currLRUHits;
+  }
+  hitLFU() {
+    ++this.currLFUHits;
+  }
   rateLRU(offset = false) {
-    return Stats.rate(this.window, this.LRU, this.LFU, +offset & 0);
+    return Stats.rate(this.window, [this.currLRUHits, this.prevLRUHits], [this.currLFUHits, this.prevLFUHits], +offset & 0);
   }
   rateLFU(offset = false) {
-    return Stats.rate(this.window, this.LFU, this.LRU, +offset & 0);
+    return Stats.rate(this.window, [this.currLFUHits, this.prevLFUHits], [this.currLRUHits, this.prevLRUHits], +offset & 0);
   }
   subtotal() {
-    const {
-      LRU,
-      LFU,
-      window
-    } = this;
-    const subtotal = LRU[0] + LFU[0];
-    subtotal >= window && this.slide();
+    const subtotal = this.currLRUHits + this.currLFUHits;
+    subtotal >= this.window && this.slide();
     return subtotal;
   }
   slide() {
-    const {
-      LRU,
-      LFU,
-      max
-    } = this;
-    if (LRU.length === max) {
-      LRU[1] = LRU[0];
-      LFU[1] = LFU[0];
-      LRU[0] = 0;
-      LFU[0] = 0;
-    } else {
-      LRU.unshift(0);
-      LFU.unshift(0);
-    }
+    this.prevLRUHits = this.currLRUHits;
+    this.prevLFUHits = this.currLFUHits;
+    this.currLRUHits = 0;
+    this.currLFUHits = 0;
   }
   clear() {
-    this.LRU = [0];
-    this.LFU = [0];
+    this.currLRUHits = 0;
+    this.currLFUHits = 0;
+    this.prevLRUHits = 0;
+    this.prevLFUHits = 0;
   }
@@ -699,9 +687,11 @@ resize(window) {
     this.max = (0, alias_1.ceil)(this.resolution * (100 + this.offset) / 100) + 1;
+    this.LRU = [0];
+    this.LFU = [0];
   }
-  static rate(window, hits1, hits2, offset) {
+  static rate(window, targets, remains, offset) {
     let total = 0;
     let hits = 0;
     let ratio = 100;
-    for (let len = hits1.length, i = 0; i < len; ++i) {
-      const subtotal = hits1[i] + hits2[i];
+    for (let len = targets.length, i = 0; i < len; ++i) {
+      const subtotal = targets[i] + remains[i];
       if (subtotal === 0) continue;
@@ -714,3 +704,3 @@ offset = i + 1 === len ? 0 : offset;
       total += subtotal * rate;
-      hits += hits1[i] * rate;
+      hits += targets[i] * rate;
       ratio -= subratio;
@@ -721,2 +711,14 @@ if (ratio <= 0) break;
   }
+  get length() {
+    return this.LRU.length;
+  }
+  isFull() {
+    return this.length === this.max;
+  }
+  hitLRU() {
+    ++this.LRU[0];
+  }
+  hitLFU() {
+    ++this.LFU[0];
+  }
   rateLRU(offset = false) {
@@ -763,15 +765,45 @@ return StatsExperimental.rate(this.window, this.LRU, this.LFU, +offset && this.offset);
   }
+  clear() {
+    this.LRU = [0];
+    this.LFU = [0];
+  }
 }
 // Transitive Wide MRU with Round Replacement
 class Sweeper {
-  constructor(target, interval, shift) {
+  constructor(target, threshold, capacity, window, interval, shift) {
     this.target = target;
+    this.threshold = threshold;
+    this.capacity = capacity;
+    this.window = window;
     this.interval = interval;
     this.shift = shift;
+    this.currHits = 0;
+    this.currMisses = 0;
+    this.prevHits = 0;
+    this.prevMisses = 0;
+    this.active = false;
+    this.direction = true;
     this.initial = true;
-    this.direction = true;
     this.back = 0;
     this.advance = 0;
   }
+  slide() {
+    this.prevHits = this.currHits;
+    this.prevMisses = this.currMisses;
+    this.currHits = 0;
+    this.currMisses = 0;
+  }
+  hit() {
+    ++this.currHits + this.currMisses === this.window && this.slide();
+    this.active && !this.isAvailable() && this.clear();
+  }
+  miss() {
+    this.currHits + ++this.currMisses === this.window && this.slide();
+  }
+  isAvailable() {
+    const rate = Stats.rate(this.window, [this.currHits, this.prevHits], [this.currMisses, this.prevMisses], 0);
+    return rate / 100 < this.threshold;
+  }
   sweep() {
+    this.active ||= true;
     const {
@@ -782,7 +814,7 @@ target
       if (this.back < 1) {
-        this.back += target.length * this.interval / 100;
+        this.back += this.capacity * this.interval / 100;
       }
     } else {
       if (this.advance < 1) {
-        this.advance += target.length * this.interval / 100 * (100 - this.shift) / 100;
+        this.advance += this.capacity * this.interval / 100 * (100 - this.shift) / 100;
       }
@@ -809,8 +841,13 @@ }
   clear() {
-    if (this.initial && this.back === 0) return;
+    if (!this.active) return;
+    this.active = false;
+    this.direction = true;
     this.initial = true;
-    this.direction = true;
     this.back = 0;
     this.advance = 0;
   }
+  resize(capacity, window) {
+    this.capacity = capacity;
+    this.window = window;
+  }
 }
@@ -817,0 +854,0 @@

package.json

 {
   "name": "dw-cache",
-  "version": "0.0.70",
+  "version": "0.0.71",
   "description": "The highest performance constant complexity cache algorithm.",
@@ -52,7 +52,7 @@ "private": false,
     "mocha": "^10.1.0",
-    "npm-check-updates": "^16.3.16",
-    "spica": "0.0.672",
+    "npm-check-updates": "^16.3.25",
+    "spica": "0.0.673",
     "ts-loader": "^9.4.1",
     "typescript": "4.8.4",
-    "webpack": "^5.74.0",
+    "webpack": "^5.75.0",
     "webpack-cli": "^4.10.0",
@@ -59,0 +59,0 @@ "webpack-merge": "^5.8.0"

README.md

@@ -130,3 +130,3 @@ # Dual Window Cache
     - Bloom filters don't support delete operation.
-    - *Frequent delete operation degrades performance.*
+    - *Frequent delete operations degrade performance.*
   - Spike latency
@@ -139,3 +139,3 @@ - **Whole reset of Bloom filters takes linear time.**
     - Bloom filters don't support delete operation.
-    - *Frequent delete operation degrades performance.*
+    - *Frequent delete operations degrade performance.*
   - Spike latency
@@ -210,3 +210,3 @@ - **Whole reset of Bloom filters takes linear time.**
       label: 'DWC',
-      data: [6, 23, 37, 39, 41, 46, 52, 60],
+      data: [11, 26, 37, 40, 47, 56, 53, 62],
       borderColor: Utils.color(2),
@@ -233,3 +233,3 @@ },
 
-![image](https://user-images.githubusercontent.com/3143368/200041495-e8941ed5-b6dc-430c-8a03-c2654b9ac776.png)
+![image](https://user-images.githubusercontent.com/3143368/201507692-7b1fcb9e-ad9e-49bf-ac95-713333ae0ea0.png)
 
@@ -239,47 +239,47 @@ ```
 LRU hit ratio 3.08%
-DWC hit ratio 6.37%
-DWC - LRU hit ratio delta 3.29%
-DWC / LRU hit ratio rate  206%
+DWC hit ratio 10.94%
+DWC - LRU hit ratio delta 7.85%
+DWC / LRU hit ratio rate  354%
 
 DS1 2,000,000
 LRU hit ratio 10.74%
-DWC hit ratio 23.25%
-DWC - LRU hit ratio delta 12.50%
-DWC / LRU hit ratio rate  216%
+DWC hit ratio 25.82%
+DWC - LRU hit ratio delta 15.08%
+DWC / LRU hit ratio rate  240%
 
 DS1 3,000,000
 LRU hit ratio 18.59%
-DWC hit ratio 36.90%
-DWC - LRU hit ratio delta 18.31%
-DWC / LRU hit ratio rate  198%
+DWC hit ratio 37.19%
+DWC - LRU hit ratio delta 18.60%
+DWC / LRU hit ratio rate  200%
 
 DS1 4,000,000
 LRU hit ratio 20.24%
-DWC hit ratio 39.13%
-DWC - LRU hit ratio delta 18.88%
-DWC / LRU hit ratio rate  193%
+DWC hit ratio 40.02%
+DWC - LRU hit ratio delta 19.77%
+DWC / LRU hit ratio rate  197%
 
 DS1 5,000,000
 LRU hit ratio 21.03%
-DWC hit ratio 40.62%
-DWC - LRU hit ratio delta 19.58%
-DWC / LRU hit ratio rate  193%
+DWC hit ratio 47.36%
+DWC - LRU hit ratio delta 26.32%
+DWC / LRU hit ratio rate  225%
 
 DS1 6,000,000
 LRU hit ratio 33.95%
-DWC hit ratio 45.67%
-DWC - LRU hit ratio delta 11.72%
-DWC / LRU hit ratio rate  134%
+DWC hit ratio 55.73%
+DWC - LRU hit ratio delta 21.78%
+DWC / LRU hit ratio rate  164%
 
 DS1 7,000,000
 LRU hit ratio 38.89%
-DWC hit ratio 51.52%
-DWC - LRU hit ratio delta 12.63%
-DWC / LRU hit ratio rate  132%
+DWC hit ratio 52.48%
+DWC - LRU hit ratio delta 13.58%
+DWC / LRU hit ratio rate  134%
 
 DS1 8,000,000
 LRU hit ratio 43.03%
-DWC hit ratio 59.92%
-DWC - LRU hit ratio delta 16.89%
-DWC / LRU hit ratio rate  139%
+DWC hit ratio 62.35%
+DWC - LRU hit ratio delta 19.31%
+DWC / LRU hit ratio rate  144%
 ```
@@ -340,4 +340,4 @@
 LRU hit ratio 2.32%
-DWC hit ratio 10.15%
-DWC - LRU hit ratio delta 7.82%
+DWC hit ratio 10.16%
+DWC - LRU hit ratio delta 7.83%
 DWC / LRU hit ratio rate  436%
@@ -436,3 +436,3 @@
 
-![image](https://user-images.githubusercontent.com/3143368/200042285-0e42a9a5-daac-40c9-9e6e-39e355f3755d.png)
+![image](https://user-images.githubusercontent.com/3143368/200601395-55e379b1-d423-4fcb-9a04-29d2b4d7c3fc.png)
 
@@ -442,10 +442,10 @@ ```
 LRU hit ratio 16.47%
-DWC hit ratio 18.05%
-DWC - LRU hit ratio delta 1.58%
-DWC / LRU hit ratio rate  109%
+DWC hit ratio 17.51%
+DWC - LRU hit ratio delta 1.03%
+DWC / LRU hit ratio rate  106%
 
 OLTP 500
 LRU hit ratio 23.44%
-DWC hit ratio 29.01%
-DWC - LRU hit ratio delta 5.56%
+DWC hit ratio 28.95%
+DWC - LRU hit ratio delta 5.51%
 DWC / LRU hit ratio rate  123%
@@ -455,4 +455,4 @@
 LRU hit ratio 28.28%
-DWC hit ratio 34.71%
-DWC - LRU hit ratio delta 6.43%
+DWC hit ratio 34.72%
+DWC - LRU hit ratio delta 6.44%
 DWC / LRU hit ratio rate  122%
@@ -462,4 +462,4 @@
 LRU hit ratio 32.83%
-DWC hit ratio 37.99%
-DWC - LRU hit ratio delta 5.16%
+DWC hit ratio 38.03%
+DWC - LRU hit ratio delta 5.20%
 DWC / LRU hit ratio rate  115%
@@ -518,3 +518,3 @@
       label: 'DWC',
-      data: [16, 27, 42, 47, 52, 54, 55, 57],
+      data: [15, 30, 42, 48, 52, 54, 55, 57],
       borderColor: Utils.color(2),
@@ -541,3 +541,3 @@ },
 
-![image](https://user-images.githubusercontent.com/3143368/200044553-1a0c442c-64cb-40b9-8359-8f2d1a92c9c0.png)
+![image](https://user-images.githubusercontent.com/3143368/201507793-1bbe8f23-0676-4c17-bc48-53d9cd37797c.png)
 
@@ -547,34 +547,34 @@ ```
 LRU hit ratio 0.93%
-DWC hit ratio 15.54%
-DWC - LRU hit ratio delta 14.61%
-DWC / LRU hit ratio rate  1669%
+DWC hit ratio 15.39%
+DWC - LRU hit ratio delta 14.46%
+DWC / LRU hit ratio rate  1653%
 
 GLI 500
 LRU hit ratio 0.96%
-DWC hit ratio 27.02%
-DWC - LRU hit ratio delta 26.06%
-DWC / LRU hit ratio rate  2803%
+DWC hit ratio 30.03%
+DWC - LRU hit ratio delta 29.07%
+DWC / LRU hit ratio rate  3115%
 
 GLI 750
 LRU hit ratio 1.16%
-DWC hit ratio 42.25%
-DWC - LRU hit ratio delta 41.09%
-DWC / LRU hit ratio rate  3631%
+DWC hit ratio 41.78%
+DWC - LRU hit ratio delta 40.62%
+DWC / LRU hit ratio rate  3591%
 
 GLI 1,000
 LRU hit ratio 11.22%
-DWC hit ratio 47.35%
-DWC - LRU hit ratio delta 36.13%
-DWC / LRU hit ratio rate  422%
+DWC hit ratio 48.25%
+DWC - LRU hit ratio delta 37.03%
+DWC / LRU hit ratio rate  430%
 
 GLI 1,250
 LRU hit ratio 21.25%
-DWC hit ratio 52.12%
-DWC - LRU hit ratio delta 30.86%
-DWC / LRU hit ratio rate  245%
+DWC hit ratio 51.61%
+DWC - LRU hit ratio delta 30.35%
+DWC / LRU hit ratio rate  242%
 
 GLI 1,500
 LRU hit ratio 36.56%
-DWC hit ratio 54.50%
-DWC - LRU hit ratio delta 17.93%
+DWC hit ratio 54.63%
+DWC - LRU hit ratio delta 18.06%
 DWC / LRU hit ratio rate  149%
@@ -584,4 +584,4 @@
 LRU hit ratio 45.04%
-DWC hit ratio 54.70%
-DWC - LRU hit ratio delta 9.65%
+DWC hit ratio 54.85%
+DWC - LRU hit ratio delta 9.80%
 DWC / LRU hit ratio rate  121%
@@ -601,4 +601,4 @@
 LRU hit ratio 0.00%
-DWC hit ratio 9.37%
-DWC - LRU hit ratio delta 9.37%
+DWC hit ratio 9.08%
+DWC - LRU hit ratio delta 9.08%
 DWC / LRU hit ratio rate  Infinity%
@@ -608,4 +608,4 @@
 LRU hit ratio 0.00%
-DWC hit ratio 23.09%
-DWC - LRU hit ratio delta 23.09%
+DWC hit ratio 23.29%
+DWC - LRU hit ratio delta 23.29%
 DWC / LRU hit ratio rate  Infinity%
@@ -615,4 +615,4 @@
 LRU hit ratio 0.00%
-DWC hit ratio 48.84%
-DWC - LRU hit ratio delta 48.84%
+DWC hit ratio 46.92%
+DWC - LRU hit ratio delta 46.92%
 DWC / LRU hit ratio rate  Infinity%
@@ -622,4 +622,4 @@
 LRU hit ratio 0.00%
-DWC hit ratio 73.83%
-DWC - LRU hit ratio delta 73.83%
+DWC hit ratio 70.34%
+DWC - LRU hit ratio delta 70.34%
 DWC / LRU hit ratio rate  Infinity%
@@ -629,4 +629,4 @@
 LRU hit ratio 0.00%
-DWC hit ratio 98.61%
-DWC - LRU hit ratio delta 98.61%
+DWC hit ratio 94.34%
+DWC - LRU hit ratio delta 94.34%
 DWC / LRU hit ratio rate  Infinity%
@@ -643,4 +643,6 @@
 
-100-80% of [lru-cache](https://www.npmjs.com/package/lru-cache).
+80-100% of [lru-cache](https://www.npmjs.com/package/lru-cache).
 
+Note that the number of trials per capacity for simulation 1,000,000 is insufficient.
+
 No result with 10,000,000 because lru-cache crushes with the next error on the next machine of GitHub Actions.
@@ -658,25 +660,29 @@ It is verified that the error was thrown also when benchmarking only lru-cache.
 ```
-'LRUCache new x 85,202 ops/sec ±1.52% (122 runs sampled)'
+'LRUCache new x 10,892 ops/sec ±1.67% (114 runs sampled)'
 
-'DW-Cache new x 6,352,805 ops/sec ±1.10% (123 runs sampled)'
+'DW-Cache new x 6,180,273 ops/sec ±0.89% (123 runs sampled)'
 
-'LRUCache simulation 100 x 7,559,408 ops/sec ±2.33% (118 runs sampled)'
+'LRUCache simulation 10 x 8,625,515 ops/sec ±1.05% (123 runs sampled)'
 
-'DW-Cache simulation 100 x 7,228,836 ops/sec ±2.48% (119 runs sampled)'
+'DW-Cache simulation 10 x 7,665,021 ops/sec ±1.35% (122 runs sampled)'
 
-'LRUCache simulation 1,000 x 6,886,150 ops/sec ±2.44% (115 runs sampled)'
+'LRUCache simulation 100 x 8,939,202 ops/sec ±0.88% (123 runs sampled)'
 
-'DW-Cache simulation 1,000 x 6,853,913 ops/sec ±2.63% (116 runs sampled)'
+'DW-Cache simulation 100 x 7,280,351 ops/sec ±0.78% (123 runs sampled)'
 
-'LRUCache simulation 10,000 x 6,381,916 ops/sec ±2.34% (118 runs sampled)'
+'LRUCache simulation 1,000 x 7,964,882 ops/sec ±0.44% (124 runs sampled)'
 
-'DW-Cache simulation 10,000 x 6,302,861 ops/sec ±2.32% (119 runs sampled)'
+'DW-Cache simulation 1,000 x 7,436,336 ops/sec ±1.30% (123 runs sampled)'
 
-'LRUCache simulation 100,000 x 3,680,483 ops/sec ±1.95% (114 runs sampled)'
+'LRUCache simulation 10,000 x 6,896,531 ops/sec ±1.77% (121 runs sampled)'
 
-'DW-Cache simulation 100,000 x 3,693,721 ops/sec ±3.15% (113 runs sampled)'
+'DW-Cache simulation 10,000 x 6,568,404 ops/sec ±1.64% (121 runs sampled)'
 
-'LRUCache simulation 1,000,000 x 1,703,083 ops/sec ±5.16% (98 runs sampled)'
+'LRUCache simulation 100,000 x 3,841,058 ops/sec ±1.38% (112 runs sampled)'
 
-'DW-Cache simulation 1,000,000 x 1,389,332 ops/sec ±5.59% (109 runs sampled)'
+'DW-Cache simulation 100,000 x 3,778,800 ops/sec ±2.25% (110 runs sampled)'
+
+'LRUCache simulation 1,000,000 x 1,921,274 ops/sec ±3.02% (103 runs sampled)'
+
+'DW-Cache simulation 1,000,000 x 1,572,905 ops/sec ±2.17% (111 runs sampled)'
 ```
@@ -764,4 +770,5 @@
     readonly entrance?: number;
-    readonly threshold?: number;
     readonly sweep?: {
+      readonly threshold?: number;
+      readonly window?: number;
       readonly interval?: number;
@@ -768,0 +775,0 @@ readonly shift?: number;

No alert changes

Improved metrics

Total package byte prevSize

105325

increased by1.4%

Lines of code

1984

increased by1.9%

Number of lines in readme file

774

increased by0.91%

No dependency changes