spica - npm Package Compare versions

Comparing version 0.0.790 to 0.0.791

cache.test.ts

@@ -409,2 +409,35 @@ import { Cache } from './cache';
 
+    it('ratio pzipf 100', function () {
+      this.timeout(10 * 1e3);
+
+      const capacity = 100;
+      const lru = new LRU<number, 1>(capacity);
+      const trc = new TLRU<number, 1>(capacity);
+      const dwc = new Cache<number, 1>(capacity);
+
+      const trials = capacity * 1000;
+      const random = xorshift.random(1);
+      const stats = new Stats();
+      const log = { 0: 0 };
+      for (let i = 0; i < trials; ++i) {
+        const key = Math.floor((random() * capacity) ** 2 / (10 * capacity / 100 | 0));
+        stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
+        stats.trc += trc.get(key) ?? +trc.set(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.set(key, 1) & 0;
+        stats.total += 1;
+        key in log ? ++log[key] : log[key] = 1;
+      }
+      //console.debug(Object.entries(log).sort((a, b) => b[1] - a[1]).map(e => [+e[0], e[1]]));
+      assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
+      assert(dwc['dict'].size <= capacity);
+      console.debug('Cache pzipf 100');
+      console.debug('LRU hit ratio', stats.lru * 100 / stats.total);
+      console.debug('TRC hit ratio', stats.trc * 100 / stats.total);
+      console.debug('DWC hit ratio', stats.dwc * 100 / stats.total);
+      console.debug('DWC / LRU hit ratio', `${stats.dwc / stats.lru * 100 | 0}%`);
+      console.debug('DWC ratio', dwc['partition']! * 100 / capacity | 0, dwc['LFU'].length * 100 / capacity | 0);
+      console.debug('DWC overlap', dwc['overlapLRU'], dwc['overlapLFU']);
+      assert(stats.dwc / stats.lru * 100 >>> 0 === 126);
+    });
+
     it('ratio zipf 100', function () {
@@ -807,3 +840,3 @@ this.timeout(10 * 1e3);
 
-    it('ratio uneven 1,000', function () {
+    it('ratio pzipf 1,000', function () {
       this.timeout(60 * 1e3);
@@ -819,6 +852,5 @@
       const stats = new Stats();
+      const log = { 0: 0 };
       for (let i = 0; i < trials; ++i) {
-        const key = random() < 0.4
-          ? random() * capacity * -1 | 0
-          : random() * capacity * 10 | 0;
+        const key = Math.floor((random() * capacity) ** 2 / (10 * capacity / 100 | 0));
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
@@ -828,6 +860,8 @@ stats.trc += trc.get(key) ?? +trc.set(key, 1) & 0;
         stats.total += 1;
+        key in log ? ++log[key] : log[key] = 1;
       }
+      //console.debug(Object.entries(log).sort((a, b) => b[1] - a[1]).map(e => [+e[0], e[1]]));
       assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
       assert(dwc['dict'].size <= capacity);
-      console.debug('Cache uneven 1,000');
+      console.debug('Cache pzipf 1,000');
       console.debug('LRU hit ratio', stats.lru * 100 / stats.total);
@@ -839,3 +873,3 @@ console.debug('TRC hit ratio', stats.trc * 100 / stats.total);
       console.debug('DWC overlap', dwc['overlapLRU'], dwc['overlapLFU']);
-      assert(stats.dwc / stats.lru * 100 >>> 0 === 162);
+      assert(stats.dwc / stats.lru * 100 >>> 0 === 130);
     });
@@ -842,0 +876,0 @@

cache.ts

@@ -82,3 +82,5 @@ import { max, min } from './alias';
 
-最適化前(@6)よりオブジェクト値において50-10%ほど高速化している。
+非常に高いヒット率では素朴な実装より高速化するがそれ以外の場合は低速化する。
+この最適化により素朴な実装より速くなる範囲が非常に狭く全体的には低速化している。
+巨大な配列を複数要するため空間オーバーヘッドも大きく消費メモリ基準では容量とヒット率が低下する。
 
@@ -92,7 +94,4 @@ ## Map値の数値化
 
-個別の状態を個別のオブジェクトのプロパティに持たせると最適化されていないプロパティアクセスにより
-低速化するためすべての状態を状態別の配列に格納しインデクスアクセスに変換することで高速化している。
-DWCはこの最適化を行っても状態数の多さに比例して増加したオーバーヘッドに相殺され効果を得られない。
-状態をオブジェクトの代わりに配列に入れても最適化されずプロパティ・インデクスとも二段のアクセスは
-最適化されないと思われる。
+すべての状態を状態別の配列に格納しインデクスアクセスに変換することで高速化している。
+DWCはこの高速化を行っても状態数の多さに比例して増加したオーバーヘッドに相殺され効果を得られない。
 
@@ -711,4 +710,6 @@ ## TypedArray
       this.window,
-      [this.currWindowHits, this.prevWindowHits],
-      [this.currWindowMisses, this.prevWindowMisses],
+      this.currWindowHits,
+      this.prevWindowHits,
+      this.currWindowMisses,
+      this.prevWindowMisses,
       0);
@@ -719,4 +720,6 @@ }
       this.room,
-      [this.currRoomHits, this.prevRoomHits],
-      [this.currRoomMisses, this.prevRoomMisses],
+      this.currRoomHits,
+      this.prevRoomHits,
+      this.currRoomMisses,
+      this.prevRoomMisses,
       0);
@@ -786,12 +789,10 @@ }
   window: number,
-  targets: readonly [number, number],
-  remains: readonly [number, number],
+  currHits: number,
+  prevHits: number,
+  currMisses: number,
+  prevMisses: number,
   offset: number,
 ): number {
-  assert(targets.length === 2);
-  assert(targets.length === remains.length);
-  const currHits = targets[0];
-  const prevHits = targets[1];
-  const currTotal = currHits + remains[0];
-  const prevTotal = prevHits + remains[1];
+  const currTotal = currHits + currMisses;
+  const prevTotal = prevHits + prevMisses;
   assert(currTotal <= window);
@@ -832,9 +833,9 @@ const prevRate = prevHits && prevHits * 100 / prevTotal;
 }
-assert(ratio(10, [4, 0], [6, 0], 0) === 4000);
-assert(ratio(10, [0, 4], [0, 6], 0) === 4000);
-assert(ratio(10, [1, 4], [4, 6], 0) === 3000);
-assert(ratio(10, [0, 4], [0, 6], 5) === 4000);
-assert(ratio(10, [1, 2], [4, 8], 5) === 2000);
-assert(ratio(10, [2, 2], [3, 8], 5) === 2900);
-assert(ratio(10, [2, 0], [3, 0], 0) === 4000);
+assert(ratio(10, 4, 0, 6, 0, 0) === 4000);
+assert(ratio(10, 0, 4, 0, 6, 0) === 4000);
+assert(ratio(10, 1, 4, 4, 6, 0) === 3000);
+assert(ratio(10, 0, 4, 0, 6, 5) === 4000);
+assert(ratio(10, 1, 2, 4, 8, 5) === 2000);
+assert(ratio(10, 2, 2, 3, 8, 5) === 2900);
+assert(ratio(10, 2, 0, 3, 0, 0) === 4000);
 assert(ratio2(10, [4, 0], [6, 0], 0) === 4000);
@@ -841,0 +842,0 @@ assert(ratio2(10, [0, 4], [0, 6], 0) === 4000);

package.json

 {
   "name": "spica",
-  "version": "0.0.790",
+  "version": "0.0.791",
   "description": "Supervisor, Coroutine, Channel, select, AtomicPromise, Cancellation, Cache, List, Queue, Stack, and some utils.",
@@ -5,0 +5,0 @@ "private": false,

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

843674

increased by0.18%

Lines of code

27522

increased by0.12%

No dependency changes