dw-cache - npm Package Compare versions

Comparing version 0.0.75 to 0.0.76

dist/index.js

@@ -1,2 +0,2 @@
-/*! dw-cache v0.0.75 https://github.com/falsandtru/dw-cache | (c) 2021, falsandtru | (Apache-2.0 AND MPL-2.0) License */
+/*! dw-cache v0.0.76 https://github.com/falsandtru/dw-cache | (c) 2021, falsandtru | (Apache-2.0 AND MPL-2.0) License */
 (function webpackUniversalModuleDefinition(root, factory) {
@@ -301,2 +301,97 @@ if(typeof exports === 'object' && typeof module === 'object')
 const assign_1 = __webpack_require__(401);
+// Dual Window Cache
+/*
+LFU論理寿命：
+小容量で小効果のみにつきLRU下限で代替し廃止。
+
+LRU下限：
+小容量で大効果につき採用。
+
+LFUヒット率変化率：
+S3での逆効果のみ確認につきオプション化。
+
+統計解像度：
+効果ないが検証用に残置。
+
+サイクリックスウィープ：
+大効果につき採用。
+LRU汚染対策。
+
+加重エージング：
+LFU解放とLRU拡大による高参照間隔アクセス対応に必要。
+リストによる実装ではランダムメモリアクセスを追加するためオーバーヘッドが大きい。
+LFU汚染対策。
+
+*/
+/*
+比較検討
+
+LRU/CLOCK:
+性能が低い。
+
+CAR/CDW(CLOCK+DWC)/CLOCK-Pro:
+最悪計算量がO(n)であるため汎用的でない。
+CLOCK-ProはCAR同様合計2倍の履歴を持つ。
+
+ARC:
+キャッシュサイズの2倍のキーを保持する。
+すでにARCに近いヒット率を達成しているためわずかなヒット率向上のために
+2倍のキーサイズとリスト操作による空間効率悪化と速度低下を正当化できるワークロードでのみ優位性がある。
+Loop耐性が欠如しておりGLIやDS1などLoop耐性を要するワークロードではDWCが大幅に優れている。
+
+DWC:
+時間空間ともに定数計算量かつすべての基本的耐性を持つ。
+それゆえ履歴が必要となる高参照間隔または耐性が逆効果となる刷新を要するアクセスパターンでは
+原理的に性能低下を免れない。
+適正サイズより大幅に小さいキャッシュサイズではおそらく統計精度の悪化により性能低下しやすい。
+
+LIRS:
+キャッシュサイズの3倍以上のキーを保持する。
+LIRS論文全著者を共著者とするLIRS2論文筆頭著者の実装によると最大2500倍、事実上無制限。
+にもかかわらずARCより安定して十分に性能が高いとは言えないうえ大幅に性能の劣るケースも散見される。
+履歴に現実的な上限を与えた場合の実際の性能が不明でありまともな比較資料がない。
+キーを無制限に走査するGC的処理があるためキャッシュサイズに比例して大きな遅延が入る可能性が上がり
+遅延が許容できない水準に達する可能性がある。
+まともなアルゴリズムではない。
+
+TinyLFU:
+TinyLFUはキーのポインタのアドレスでブルームフィルタを生成するためJavaScriptでは
+文字列やオブジェクトなどからアドレスを取得または代替値を高速に割り当てる方法がなく汎用的に使用できない。
+乱数を代用する方法は強引で低速だがリモートアクセスなど低速な処理では償却可能と思われる。
+オーバーヘッドが大きくメモ化など同期処理に耐える速度を要件とする用途には適さないと思われる。
+ブルームフィルタが削除操作不可であるためキャッシュを削除操作数に比例して性能が低下する。
+キャッシュサイズ分の挿入ごとにブルームフィルタがリセットのため全走査されるため
+キャッシュサイズに比例した大きさの遅延が入る。
+W-TinyLFUの性能は非常に高いがTinyLFUの性能は大幅に低くDWCと一長一短かより悪いうえ
+バーストアクセスに脆弱となるためあらかじめワークロードが検証されている場合以外はDWCのほうが優れている。
+エヴィクションポリシーにLRUを使用しているためこれをDWCに置換できる可能性がある。
+
+https://github.com/ben-manes/caffeine/wiki/Efficiency
+
+*/
+/*
+# lru-cacheの最適化分析
+
+最適化前(@6)よりオブジェクト値において50-10%ほど高速化している。
+
+## Map値の数値化
+
+Mapは値が数値の場合setが2倍高速化される。
+getは変わらないため読み取り主体の場合効果が低い。
+
+## インデクスアクセス化
+
+個別の状態を個別のオブジェクトのプロパティに持たせると最適化されていないプロパティアクセスにより
+低速化するためすべての状態を状態別の配列に格納しインデクスアクセスに変換することで高速化している。
+DWCはこの最適化を行っても状態数の多さに比例して増加したオーバーヘッドに相殺され効果を得られない。
+状態をオブジェクトの代わりに配列に入れても最適化されずプロパティ・インデクスとも二段のアクセスは
+最適化されないと思われる。
+
+## TypedArray
+
+インデクスアクセス化にTypedArrayを使うことで配列の書き込みが2倍高速化される。
+これによりリスト操作が高速化されるがもともと高速なため全体的な寄与は小さいと思われる。
+
+*/
+const RESOLUTION = 1000;
 class Cache {
@@ -322,2 +417,6 @@ constructor(capacity, opts = {}) {
       },
+      life: {
+        LRU: 1,
+        LFU: 4
+      },
       test: false
@@ -337,5 +436,14 @@ };
     }
+    if (opts.test) {
+      // @ts-expect-error
+      this.settings.sweep.threshold = 0;
+      // @ts-expect-error
+      this.settings.life.LRU = 16;
+      // @ts-expect-error
+      this.settings.life.LFU = 16;
+    }
     const settings = (0, assign_1.extend)(this.settings, opts, {
       capacity
     });
+    if (settings.window >= 0.1 === false) throw new Error(`Spica: Cache: Window must be 0.1% or more of capacity.`);
     this.capacity = capacity = settings.capacity;
@@ -345,5 +453,4 @@ if (capacity >>> 0 !== capacity) throw new Error(`Spica: Cache: Capacity must be integer.`);
     this.window = settings.window * capacity / 100 >>> 0;
-    if (this.window * 1000 >= capacity === false) throw new Error(`Spica: Cache: Window must be 0.1% or more of capacity.`);
-    this.unit = 1000 / capacity | 0 || 1;
-    this.limit = 1000 - settings.entrance * 10;
+    this.unit = RESOLUTION / capacity | 0 || 1;
+    this.limit = RESOLUTION - settings.entrance * RESOLUTION / 100;
     this.resource = settings.resource ?? capacity;
@@ -356,2 +463,3 @@ this.age = settings.age;
     this.sweeper = new Sweeper(this.indexes.LRU, settings.sweep.threshold, capacity, settings.sweep.window, settings.sweep.range, settings.sweep.shift);
+    this.life = settings.life;
     this.disposer = settings.disposer;
@@ -370,4 +478,17 @@ this.test = settings.test;
   }
+  escapeHand(node) {
+    if (node !== this.hand) return;
+    this.hand = node.prev === node ? undefined : node.prev;
+  }
+  advanceHand() {
+    const node = this.hand ??= this.indexes.LFU.last;
+    if (node === undefined) return;
+    this.escapeHand(node);
+    if (--node.value.age !== 0) return;
+    this.indexes.LRU.unshiftNode(node);
+    ++this.overlap;
+  }
   evict(node, callback) {
     //assert(this.memory.size <= this.capacity);
+    this.escapeHand(node);
     const entry = node.value;
@@ -396,7 +517,8 @@ entry.region === 'LFU' && node.list === this.indexes.LRU && --this.overlap;
       } else {
-        if (this.sweeper.isAvailable() && !this.test) {
+        if (this.sweeper.isAvailable()) {
           this.sweeper.sweep();
-        } else if (LFU.length > this.capacity * (this.ratio ?? this.limit) / 1000) {
+        } else if (LFU.length * RESOLUTION > this.capacity * (this.ratio ?? this.limit)) {
           const node = LFU.last !== skip ? LFU.last : LFU.length !== 1 ? LFU.last.prev : undefined;
           if (node !== undefined) {
+            this.escapeHand(node);
             LRU.unshiftNode(node);
@@ -428,4 +550,6 @@ ++this.overlap;
     }
+    this.advanceHand();
     const {
-      LRU
+      LRU,
+      LFU
     } = this.indexes;
@@ -459,3 +583,7 @@ age === Infinity ? age = 0 : this.expiration ||= true;
       }
+      this.escapeHand(node);
       node.moveToHead();
+      if (node.list === LFU) {
+        entry.age = (this.capacity - LFU.length + 1) * this.life.LFU;
+      }
       this.disposer?.(value$, key$);
@@ -470,3 +598,4 @@ return match;
       expiration,
-      region: 'LRU'
+      region: 'LRU',
+      age: 0
     }));
@@ -537,6 +666,5 @@ if (this.expirations && age) {
     const window = this.settings.window * capacity / 100 >>> 0;
-    if (window * 1000 >= capacity === false) throw new Error(`Spica: Cache: Window must be 0.1% or more of capacity.`);
     this.capacity = capacity;
     this.window = window;
-    this.unit = 1000 / capacity | 0 || 1;
+    this.unit = RESOLUTION / capacity | 0 || 1;
     this.resource = resource;
@@ -569,2 +697,3 @@ this.stats.resize(window);
     } = this.indexes;
+    let life = 0;
     this.sweeper.hit();
@@ -575,5 +704,7 @@ if (node.list === LRU) {
       if (region === 'LFU') {
+        life = this.life.LFU;
         this.stats.hitLFU();
         --this.overlap;
       } else {
+        life = this.life.LRU;
         this.stats.hitLRU();
@@ -586,5 +717,9 @@ entry.region = 'LFU';
       if (node === LFU.head && !this.test) return;
+      life = this.life.LFU;
       this.stats.hitLFU();
+      this.escapeHand(node);
       node.moveToHead();
     }
+    entry.age = (this.capacity - LFU.length + 1) * life;
+    this.advanceHand();
     this.coordinate();
@@ -598,4 +733,4 @@ }
     } = this;
-    if (stats.subtotal() * 1000 % capacity !== 0 || !stats.isReady()) return;
-    this.ratio ??= (0, alias_1.min)(indexes.LFU.length / capacity * 1000 | 0, this.limit);
+    if (stats.subtotal() * RESOLUTION % capacity !== 0 || !stats.isReady()) return;
+    this.ratio ??= (0, alias_1.min)(indexes.LFU.length * RESOLUTION / capacity | 0, this.limit);
     const lenR = indexes.LRU.length;
@@ -612,10 +747,10 @@ const lenF = indexes.LFU.length;
     // LRUの下限設定ではLRU拡大の要否を迅速に判定できないためLFUのヒット率低下の検出で代替する
-    if (this.ratio > 0 && (rateR0 > rateF0 || stats.offset && rateF0 * 100 < rateF1 * (100 - stats.offset))) {
+    if (this.ratio > 0 && (rateR0 > rateF0 || stats.offset !== 0 && rateF0 * 100 < rateF1 * (100 - stats.offset))) {
       //rateR0 <= rateF0 && rateF0 * 100 < rateF1 * (100 - stats.offset) && console.debug(0);
-      if (lenR >= capacity * (1000 - this.ratio) / 1000) {
-        //this.ratio % 100 || this.ratio === 1000 || console.debug('-', this.ratio, LRU, LFU);
+      if (lenR * RESOLUTION >= capacity * (RESOLUTION - this.ratio)) {
+        //this.ratio % 100 || this.ratio === RESOLUTION || console.debug('-', this.ratio, LRU, LFU);
         this.ratio = (0, alias_1.max)(this.ratio - this.unit, 0);
       }
     } else if (this.ratio < this.limit && rateF0 > rateR0) {
-      if (lenF >= capacity * this.ratio / 1000) {
+      if (lenF * RESOLUTION >= capacity * this.ratio) {
         //this.ratio % 100 || this.ratio === 0 || console.debug('+', this.ratio, LRU, LFU);
@@ -622,0 +757,0 @@ this.ratio = (0, alias_1.min)(this.ratio + this.unit, this.limit);

package.json

 {
   "name": "dw-cache",
-  "version": "0.0.75",
+  "version": "0.0.76",
   "description": "The highest performance constant complexity cache algorithm.",
@@ -53,3 +53,3 @@ "private": false,
     "npm-check-updates": "^16.4.1",
-    "spica": "0.0.679",
+    "spica": "0.0.680",
     "ts-loader": "^9.4.1",
@@ -56,0 +56,0 @@ "typescript": "4.9.3",

README.md

@@ -22,2 +22,5 @@ # Dual Window Cache
 - Transitive wide MRU with cyclic replacement
+  - Not required if loop resistance is unnecessary.
+- Weighted aging
+  - Not required if low inter-reference accesses are present.
 
@@ -430,5 +433,5 @@ ## Properties
 LRU hit ratio 16.47%
-DWC hit ratio 17.47%
-DWC - LRU hit ratio delta 1.00%
-DWC / LRU hit ratio rate  106%
+DWC hit ratio 18.12%
+DWC - LRU hit ratio delta 1.65%
+DWC / LRU hit ratio rate  110%
 
@@ -482,2 +485,4 @@ OLTP 500
 
+- DWC is significantly better than ARC.
+
 <!--
@@ -503,3 +508,3 @@ const data = {
       label: 'DWC',
-      data: [16, 31, 42, 50, 52, 54, 55, 57],
+      data: [16, 32, 42, 50, 52, 54, 55, 57],
       borderColor: Utils.color(2),
@@ -526,3 +531,3 @@ },
 
-![image](https://user-images.githubusercontent.com/3143368/201696229-b6f34a7c-cd7a-4d60-8c67-4888a33217f0.png)
+![image](https://user-images.githubusercontent.com/3143368/202870810-b8b4c1c6-8b1b-4368-a1d1-018e0b85f0fb.png)
 
@@ -532,11 +537,11 @@ ```
 LRU hit ratio 0.93%
-DWC hit ratio 15.77%
-DWC - LRU hit ratio delta 14.84%
-DWC / LRU hit ratio rate  1694%
+DWC hit ratio 15.89%
+DWC - LRU hit ratio delta 14.96%
+DWC / LRU hit ratio rate  1707%
 
 GLI 500
 LRU hit ratio 0.96%
-DWC hit ratio 31.43%
-DWC - LRU hit ratio delta 30.46%
-DWC / LRU hit ratio rate  3260%
+DWC hit ratio 31.48%
+DWC - LRU hit ratio delta 30.51%
+DWC / LRU hit ratio rate  3265%
 
@@ -622,3 +627,3 @@ GLI 750
 
-75-95% of [lru-cache](https://www.npmjs.com/package/lru-cache).
+70-85% of [lru-cache](https://www.npmjs.com/package/lru-cache).
 
@@ -639,29 +644,29 @@ Note that the number of trials per capacity for simulation 1,000,000 is insufficient.
 ```
-'LRUCache new x 10,395 ops/sec ±3.03% (111 runs sampled)'
+'LRUCache new x 10,919 ops/sec ±1.67% (114 runs sampled)'
 
-'DW-Cache new x 4,576,566 ops/sec ±3.38% (122 runs sampled)'
+'DW-Cache new x 5,907,995 ops/sec ±0.69% (123 runs sampled)'
 
-'LRUCache simulation 10 x 7,793,225 ops/sec ±2.05% (118 runs sampled)'
+'LRUCache simulation 10 x 8,589,630 ops/sec ±1.08% (123 runs sampled)'
 
-'DW-Cache simulation 10 x 7,191,135 ops/sec ±1.93% (120 runs sampled)'
+'DW-Cache simulation 10 x 7,088,696 ops/sec ±0.31% (122 runs sampled)'
 
-'LRUCache simulation 100 x 8,039,009 ops/sec ±2.14% (119 runs sampled)'
+'LRUCache simulation 100 x 8,974,195 ops/sec ±0.56% (122 runs sampled)'
 
-'DW-Cache simulation 100 x 6,079,217 ops/sec ±2.06% (120 runs sampled)'
+'DW-Cache simulation 100 x 6,261,227 ops/sec ±1.15% (121 runs sampled)'
 
-'LRUCache simulation 1,000 x 7,089,730 ops/sec ±2.06% (118 runs sampled)'
+'LRUCache simulation 1,000 x 7,942,931 ops/sec ±0.69% (123 runs sampled)'
 
-'DW-Cache simulation 1,000 x 6,239,714 ops/sec ±2.32% (120 runs sampled)'
+'DW-Cache simulation 1,000 x 5,982,914 ops/sec ±1.35% (122 runs sampled)'
 
-'LRUCache simulation 10,000 x 6,075,071 ops/sec ±2.05% (119 runs sampled)'
+'LRUCache simulation 10,000 x 7,018,158 ops/sec ±1.29% (121 runs sampled)'
 
-'DW-Cache simulation 10,000 x 5,000,182 ops/sec ±1.76% (121 runs sampled)'
+'DW-Cache simulation 10,000 x 5,269,636 ops/sec ±1.59% (121 runs sampled)'
 
-'LRUCache simulation 100,000 x 2,398,306 ops/sec ±1.55% (113 runs sampled)'
+'LRUCache simulation 100,000 x 4,001,962 ops/sec ±1.41% (114 runs sampled)'
 
-'DW-Cache simulation 100,000 x 2,119,292 ops/sec ±2.87% (108 runs sampled)'
+'DW-Cache simulation 100,000 x 3,486,851 ops/sec ±1.71% (114 runs sampled)'
 
-'LRUCache simulation 1,000,000 x 1,226,698 ops/sec ±3.70% (103 runs sampled)'
+'LRUCache simulation 1,000,000 x 2,036,892 ops/sec ±2.66% (102 runs sampled)'
 
-'DW-Cache simulation 1,000,000 x 1,118,352 ops/sec ±2.45% (113 runs sampled)'
+'DW-Cache simulation 1,000,000 x 1,442,923 ops/sec ±1.82% (111 runs sampled)'
 ```
@@ -755,2 +760,6 @@
     };
+    readonly life?: {
+      readonly LRU: number;
+      readonly LFU: number;
+    };
   }
@@ -757,0 +766,0 @@ }

No alert changes

Improved metrics

Total package byte prevSize

112418

increased by5.9%

Lines of code

2135

increased by5.59%

Number of lines in readme file

775

increased by1.17%

No dependency changes