spica - npm Package Compare versions

Comparing version 0.0.781 to 0.0.782

cache.test.ts

@@ -661,3 +661,3 @@ import { Cache } from './cache';
       assert(dwc['partition'] === capacity - dwc['window']);
-      assert(dwc['sweeper'].isActive());
+      assert(dwc['sweeper']?.isActive());
       assert(dwc['declination'] === 8);
@@ -664,0 +664,0 @@ dwc['injection'] = 0;

cache.ts

@@ -158,2 +158,3 @@ import { max, min, round } from './alias';
 export class Cache<K, V> implements IterableDict<K, V> {
+  constructor(capacity: number, sweep?: boolean);
   constructor(capacity: number, opts?: Cache.Options<K, V>);
@@ -163,4 +164,16 @@ constructor(opts: Cache.Options<K, V>);
     capacity: number | Cache.Options<K, V>,
-    opts: Cache.Options<K, V> = {},
+    opts: boolean | Cache.Options<K, V> = {},
   ) {
+    switch (opts) {
+      case true:
+        opts = {};
+        break;
+      case false:
+        opts = {
+          sweep: {
+            threshold: 0,
+          },
+        };
+        break;
+    }
     if (typeof capacity === 'object') {
@@ -184,11 +197,13 @@ opts = capacity;
     }
-    this.sweeper = new Sweeper(
-      this.LRU,
-      capacity,
-      settings.sweep!.window!,
-      settings.sweep!.room!,
-      settings.sweep!.threshold!,
-      settings.sweep!.ratio!,
-      settings.sweep!.range!,
-      settings.sweep!.shift!);
+    this.sweeper = settings.sweep?.threshold! > 0
+      ? new Sweeper(
+          this.LRU,
+          capacity,
+          settings.sweep!.window!,
+          settings.sweep!.room!,
+          settings.sweep!.threshold!,
+          settings.sweep!.ratio!,
+          settings.sweep!.range!,
+          settings.sweep!.shift!)
+      : undefined;
     this.disposer = settings.disposer!;
@@ -245,3 +260,3 @@ assert(settings.resource === opts.resource);
     this.resource = resource ?? settings.resource ?? capacity;
-    this.sweeper.resize(
+    this.sweeper?.resize(
       capacity,
@@ -266,4 +281,4 @@ settings.sweep!.window!,
     this.expirations?.clear();
-    this.sweeper.clear();
-    this.sweeper.replace(this.LRU);
+    this.sweeper?.clear();
+    this.sweeper?.replace(this.LRU);
     if (!this.disposer || !this.settings.capture!.clear) return;
@@ -330,3 +345,3 @@ for (const { key, value } of LRU) {
   }
-  private readonly sweeper: Sweeper<List<Entry<K, V>>>;
+  private readonly sweeper?: Sweeper<List<Entry<K, V>>>;
   private injection = 100;
@@ -366,3 +381,3 @@ private declination = 1;
         }
-        if (this.sweeper.isActive()) {
+        if (this.sweeper?.isActive()) {
           this.sweeper.sweep();
@@ -581,11 +596,11 @@ }
     if (entry === undefined) {
-      this.sweeper.miss();
+      this.sweeper?.miss();
       return;
     }
     if (this.expiration && entry.expiration !== Infinity && entry.expiration < now()) {
-      this.sweeper.miss();
+      this.sweeper?.miss();
       this.evict$(entry, true);
       return;
     }
-    this.sweeper.hit();
+    this.sweeper?.hit();
     this.replace(entry);
@@ -696,3 +711,2 @@ return entry.value;
   private update(): void {
-    if (this.threshold === 0) return;
     const ratio = this.ratioWindow();
@@ -847,3 +861,3 @@ this.active =
   constructor(
-    private readonly step: number = 1,
+    private readonly step: number = 2,
     private readonly window: number = 0,
@@ -874,9 +888,7 @@ private readonly retrial: boolean = true,
     const { list } = this;
-    if (this.count !== -1 &&
-        this.handV !== undefined &&
-        this.handG !== list.last && this.handG !== undefined) {
+    if (this.count !== -1 && this.handV === this.handG && this.handG !== undefined) {
       if (this.count >= 0) {
-        //this.count = -max(max(list.length - this.count, 0) * this.step / 100 | 0, 1) - 1;
         this.count = -max(
-          list.length * this.step / 100 | 0,
+          //list.length * this.step / 100 / max(this.count / list.length * this.step, 1) | 0,
+          (list.length - this.count) * this.step / 100 | 0,
           list.length * this.window / 100 - this.count | 0,
@@ -886,13 +898,4 @@ 1) - 1;
       }
-      else {
-        this.handG = this.handG.prev;
-      }
     }
     else {
-      if (this.handV === list.head) {
-        this.handG = undefined;
-      }
-      if (this.handG === list.last) {
-        this.handG = this.handG?.prev;
-      }
       this.handV = list.last;
@@ -915,3 +918,4 @@ this.count = 0;
     const { list } = this;
-    if (this.handV === this.handG || this.handV === list.last) {
+    this.handV ??= list.last;
+    if (this.handV === this.handG || this.count === 0) {
       this.return();
@@ -921,3 +925,2 @@ }
     if (this.count >= 0 || !this.retrial) {
-      this.handV ??= list.last;
       list.insert(entry, this.handV?.next);
@@ -937,9 +940,19 @@ this.handV ??= list.last!;
       this.handV = entry;
-      this.handG = entry.prev;
+      this.handG = entry;
     }
-    if(this.handV !== this.handG){
+    if (this.count < 0 && this.handV === this.handG) {
+      this.handG = this.handG !== list.head
+        ? this.handG.prev
+        : undefined;
+    }
+    if (this.handV !== this.handG) {
       this.handV = this.handV.prev;
     }
+    if (this.handV !== list.last) {
+      ++this.count;
+    }
+    else {
+      this.count = 0;
+    }
     assert(this.count >= 0 || this.handV === this.handG);
-    ++this.count;
     return true;
@@ -957,10 +970,6 @@ }
     if (entry === this.handV) {
-      this.handV = this.handV !== list.head
-        ? this.handV.prev
-        : this.handV.next;
+      this.handV = this.handV.prev;
     }
     if (entry === this.handG) {
-      this.handG = this.handG !== list.head
-        ? this.handG.prev
-        : this.handG.next;
+      this.handG = this.handG.prev;
     }
@@ -967,0 +976,0 @@ }

lru.test.ts

@@ -8,2 +8,16 @@ import { LRU } from './lru';
   describe('LRU', () => {
+    it('order', function () {
+      const capacity = 4;
+      const cache = new LRU<number, 1>(capacity);
+      for (let i = 0; i < capacity; ++i) {
+        cache.add(~i, 1);
+      }
+      for (const i of [1, 2, 3, 3, 2, 4]) {
+        cache.get(i) ?? cache.add(i, 1);
+      }
+      assert.deepStrictEqual(
+        [...cache].map(t => t[0]),
+        [4, 2, 3, 1]);
+    });
+
     for (let i = 0; i < 10; ++i) it(`verify ${i}`, function () {
@@ -29,16 +43,2 @@ this.timeout(10 * 1e3);
 
-    it('order', function () {
-      const capacity = 4;
-      const cache = new LRU<number, 1>(capacity);
-      for (let i = 0; i < capacity; ++i) {
-        cache.add(~i, 1);
-      }
-      for (const i of [1, 2, 3, 3, 2, 4]) {
-        cache.get(i) ?? cache.add(i, 1);
-      }
-      assert.deepStrictEqual(
-        [...cache].map(t => t[0]),
-        [4, 2, 3, 1]);
-    });
-
     class Stats {
@@ -45,0 +45,0 @@ lru = 0;

package.json

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

tlru.clock.test.ts

@@ -8,2 +8,145 @@ import { TLRU } from './tlru.clock';
   describe('TLRU-Clock', () => {
+    it('basic', function () {
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, true);
+        for (const i of [0, 1, 2, 3, 4, 5, 6, 7]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [7, 6, 5, 4]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, false);
+        for (const i of [0, 1, 2, 3, 4, 5, 6, 7]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [7, 6, 5, 4]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, true);
+        for (const i of [0, 0, 1, 2, 3, 4, 5, 6, 7]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [3, 7, 2, 6]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, false);
+        for (const i of [0, 0, 1, 2, 3, 4, 5, 6, 7]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [3, 2, 6, 7]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, true);
+        for (const i of [0, 1, 2, 3, 3, 4, 5, 6, 7, 8]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [7, 3, 6, 8]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, false);
+        for (const i of [0, 1, 2, 3, 3, 4, 5, 6, 7, 8]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [7, 6, 5, 8]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, true);
+        for (const i of [0, 1, 2, 3, 4, 4, 5, 6, 7, 8]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [8, 4, 7, 6]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, false);
+        for (const i of [0, 1, 2, 3, 4, 4, 5, 6, 7, 8]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [8, 7, 6, 5]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, true);
+        for (const i of [0, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [8, 6, 7, 9]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, false);
+        for (const i of [0, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [8, 7, 5, 9]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, true);
+        for (const i of [0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [7, 6, 9, 8]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 1, 0, false);
+        for (const i of [0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [7, 6, 9, 8]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 100, 0, true);
+        for (const i of [0, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [7, 3, 9, 8]);
+      }
+      {
+        const cache = new TLRU<number, 1>(4, 100, 0, false);
+        for (const i of [0, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9]) {
+          cache.get(i) ?? cache.add(i, 1);
+        }
+        assert.deepStrictEqual(
+          [...cache].map(t => t[0]),
+          [7, 6, 9, 8]);
+      }
+    });
+
+    it('order', function () {
+      const capacity = 4;
+      const cache = new TLRU<number, 1>(capacity);
+      for (let i = 0; i < capacity; ++i) {
+        cache.add(~i, 1);
+      }
+      for (const i of [1, 2, 3, 3, 2, 4]) {
+        cache.get(i) ?? cache.add(i, 1);
+      }
+      assert.deepStrictEqual(
+        [...cache].map(t => t[0]),
+        [2, 3, 4, 1]);
+    });
+
     for (let i = 0; i < 1000; ++i) it(`verify ${i}`, function () {
@@ -13,3 +156,3 @@ this.timeout(10 * 1e3);
       const capacity = 4;
-      const cache = new TLRU<number, number>(capacity, i % 3, (i % 4 + 99) % 100);
+      const cache = new TLRU<number, number>(capacity, i % 3, (i % 4 + 99) % 100, i % 2 === 0);
 
@@ -30,16 +173,2 @@ const trials = capacity * 1000;
 
-    it('order', function () {
-      const capacity = 4;
-      const cache = new TLRU<number, 1>(capacity);
-      for (let i = 0; i < capacity; ++i) {
-        cache.add(~i, 1);
-      }
-      for (const i of [1, 2, 3, 3, 2, 4]) {
-        cache.get(i) ?? cache.add(i, 1);
-      }
-      assert.deepStrictEqual(
-        [...cache].map(t => t[0]),
-        [2, 3, 4, 1]);
-    });
-
     class Stats {
@@ -113,3 +242,3 @@ trc = 0;
       console.debug('TRC / LRU hit ratio', `${stats.trc / stats.lru * 100 | 0}%`);
-      assert(stats.trc / stats.lru * 100 >>> 0 === 129);
+      assert(stats.trc / stats.lru * 100 >>> 0 === 145);
     });
@@ -116,0 +245,0 @@

tlru.clock.ts

@@ -18,3 +18,3 @@ import { max } from './alias';
     private readonly capacity: number,
-    private readonly step: number = 1,
+    private readonly step: number = 2,
     private readonly window: number = 0,
@@ -37,11 +37,10 @@ private readonly retrial: boolean = true,
     const { list } = this;
-    if (this.count !== -1 &&
-        this.handV !== undefined &&
-        this.handG !== list.last && this.handG !== undefined) {
+    assert(this.handV = this.handV!);
+    if (this.count !== -1 && this.handV === this.handG) {
       if (this.count >= 0) {
         // 1周できる
         assert(this.count <= this.capacity);
-        //this.count = -max(max(list.length - this.count, 0) * this.step / 100 | 0, 1) - 1;
         this.count = -max(
-          list.length * this.step / 100 | 0,
+          //list.length * this.step / 100 / max(this.count / list.length * this.step, 1) | 0,
+          (list.length - this.count) * this.step / 100 | 0,
           list.length * this.window / 100 - this.count | 0,
@@ -51,13 +50,4 @@ 1) - 1;
       }
-      else {
-        this.handG = this.handG.prev;
-      }
     }
     else {
-      if (this.handV === list.head) {
-        this.handG = undefined;
-      }
-      if (this.handG === list.last!) {
-        this.handG = this.handG.prev;
-      }
       this.handV = list.last;
@@ -69,3 +59,4 @@ this.count = 0;
     const { dict, list } = this;
-    if (this.handV === this.handG || this.handV === list.last) {
+    this.handV ??= list.last!;
+    if (this.handV === this.handG || this.count === 0) {
       this.return();
@@ -75,3 +66,3 @@ }
     if (this.count >= 0 || !this.retrial) {
-      const entry = this.handV ??= list.last!;
+      const entry = this.handV;
       dict.delete(entry.key);
@@ -100,9 +91,19 @@ dict.set(key, entry);
       this.handV = entry;
-      this.handG = entry.prev;
+      this.handG = entry;
     }
-    if(this.handV !== this.handG){
+    if (this.count < 0 && this.handV === this.handG) {
+      this.handG = this.handG !== list.head
+        ? this.handG.prev
+        : undefined;
+    }
+    if (this.handV !== this.handG) {
       this.handV = this.handV.prev;
     }
+    if (this.handV !== list.last) {
+      ++this.count;
+    }
+    else {
+      this.count = 0;
+    }
     assert(this.count >= 0 || this.handV === this.handG);
-    ++this.count;
   }
@@ -157,10 +158,6 @@ public evict(): [K, V] | undefined {
     if (entry === this.handV) {
-      this.handV = this.handV !== list.head
-        ? this.handV.prev
-        : this.handV.next;
+      this.handV = this.handV.prev;
     }
     if (entry === this.handG) {
-      this.handG = this.handG !== list.head
-        ? this.handG.prev
-        : this.handG.next;
+      this.handG = this.handG.prev;
     }
@@ -167,0 +164,0 @@ }

tlru.lru.test.ts

@@ -8,2 +8,16 @@ import { TLRU } from './tlru.lru';
   describe('TLRU-LRU', () => {
+    it('order', function () {
+      const capacity = 4;
+      const cache = new TLRU<number, 1>(capacity);
+      for (let i = 0; i < capacity; ++i) {
+        cache.add(~i, 1);
+      }
+      for (const i of [1, 2, 3, 3, 2, 4]) {
+        cache.get(i) ?? cache.add(i, 1);
+      }
+      assert.deepStrictEqual(
+        [...cache].map(t => t[0]),
+        [2, 3, 4, 1]);
+    });
+
     for (let i = 0; i < 1000; ++i) it(`verify ${i}`, function () {
@@ -13,3 +27,3 @@ this.timeout(10 * 1e3);
       const capacity = 4;
-      const cache = new TLRU<number, number>(capacity, i % 3, (i % 4 + 99) % 100);
+      const cache = new TLRU<number, number>(capacity, i % 3, (i % 4 + 99) % 100, i % 2 === 0);
 
@@ -30,16 +44,2 @@ const trials = capacity * 1000;
 
-    it('order', function () {
-      const capacity = 4;
-      const cache = new TLRU<number, 1>(capacity);
-      for (let i = 0; i < capacity; ++i) {
-        cache.add(~i, 1);
-      }
-      for (const i of [1, 2, 3, 3, 2, 4]) {
-        cache.get(i) ?? cache.add(i, 1);
-      }
-      assert.deepStrictEqual(
-        [...cache].map(t => t[0]),
-        [2, 3, 4, 1]);
-    });
-
     class Stats {
@@ -113,3 +113,3 @@ trc = 0;
       console.debug('TRC / LRU hit ratio', `${stats.trc / stats.lru * 100 | 0}%`);
-      assert(stats.trc / stats.lru * 100 >>> 0 === 141);
+      assert(stats.trc / stats.lru * 100 >>> 0 === 145);
     });
@@ -116,0 +116,0 @@

tlru.lru.ts

@@ -18,3 +18,3 @@ import { max } from './alias';
     private readonly capacity: number,
-    private readonly step: number = 1,
+    private readonly step: number = 2,
     private readonly window: number = 0,
@@ -44,5 +44,5 @@ private readonly retrial: boolean = true,
         assert(this.count < this.capacity);
-        //this.count = -max(max(list.length - this.count, 0) * this.step / 100 | 0, 1) - 1;
         this.count = -max(
-          list.length * this.step / 100 | 0,
+          //list.length * this.step / 100 / max(this.count / list.length * this.step, 1) | 0,
+          (list.length - this.count) * this.step / 100 | 0,
           list.length * this.window / 100 - this.count | 0,
@@ -49,0 +49,0 @@ 1) - 1;

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

842011

increased by0.48%

Lines of code

27498

increased by0.49%

No dependency changes