dw-cache - npm Package Compare versions

Comparing version 0.0.21 to 0.0.22

dist/dw-cache.js

@@ -1,2 +0,2 @@
-/*! dw-cache v0.0.21 https://github.com/falsandtru/dw-cache | (c) 2021, falsandtru | (Apache-2.0 AND MPL-2.0) License */
+/*! dw-cache v0.0.22 https://github.com/falsandtru/dw-cache | (c) 2021, falsandtru | (Apache-2.0 AND MPL-2.0) License */
 require = function () {
@@ -349,4 +349,5 @@ function r(e, n, t) {
                 constructor(capacity, opts = {}) {
-                    this.capacity = capacity;
+                    var _a;
                     this.settings = {
+                        capacity: 0,
                         space: global_1.Infinity,
@@ -367,3 +368,4 @@ age: global_1.Infinity,
                         LRU: new invlist_1.List(),
-                        LFU: new invlist_1.List()
+                        LFU: new invlist_1.List(),
+                        OVF: new invlist_1.List()
                     };
@@ -387,9 +389,14 @@ this.stats = {
                     this.ratio = 50;
+                    if (typeof capacity === 'object') {
+                        opts = capacity;
+                        capacity = (_a = opts.capacity) !== null && _a !== void 0 ? _a : 0;
+                    }
+                    const settings = (0, assign_1.extend)(this.settings, opts, { capacity });
+                    this.capacity = settings.capacity;
+                    if (this.capacity >= 1 === false)
+                        throw new Error(`Spica: Cache: Capacity must be 1 or more.`);
                     this.frequency = (0, alias_1.max)(this.capacity / 100 | 0, 1);
-                    if (capacity >= 1 === false)
-                        throw new Error(`Spica: Cache: Capacity must be 1 or more.`);
-                    (0, assign_1.extend)(this.settings, opts);
-                    this.space = this.settings.space;
-                    this.life = this.capacity * this.settings.life;
-                    this.limit = this.settings.limit;
+                    this.space = settings.space;
+                    this.life = this.capacity * settings.life;
+                    this.limit = settings.limit;
                 }
@@ -403,3 +410,3 @@ get length() {
                 dispose(node, record, callback) {
-                    var _a, _b;
+                    var _a, _b, _c;
                     const index = node.value;
@@ -409,38 +416,38 @@ callback && (callback = !!this.settings.disposer);
                     node.delete();
+                    (_a = node.value.overflow) === null || _a === void 0 ? void 0 : _a.delete();
                     this.memory.delete(index.key);
                     this.SIZE -= index.size;
-                    callback && ((_b = (_a = this.settings).disposer) === null || _b === void 0 ? void 0 : _b.call(_a, record.value, index.key));
+                    callback && ((_c = (_b = this.settings).disposer) === null || _c === void 0 ? void 0 : _c.call(_b, record.value, index.key));
                 }
                 ensure(margin, skip) {
-                    var _a, _b;
+                    var _a, _b, _c;
                     let size = (_a = skip === null || skip === void 0 ? void 0 : skip.value.size) !== null && _a !== void 0 ? _a : 0;
                     if (margin - size <= 0)
                         return;
-                    const {LRU, LFU} = this.indexes;
+                    const {LRU, LFU, OVF} = this.indexes;
                     while (this.length === this.capacity || this.size + margin - size > this.space) {
-                        let record;
+                        const lastNode = (_b = OVF.last) !== null && _b !== void 0 ? _b : LFU.last;
+                        const lastIndex = lastNode === null || lastNode === void 0 ? void 0 : lastNode.value;
+                        let target;
                         switch (true) {
-                        case !LFU.last:
+                        case LRU.length === 0:
+                        case LRU.length === 1 && LRU.last === skip:
+                            target = LFU.last;
                             break;
-                        case LRU.length === 0:
-                        case LRU.length === +(LRU.last === skip):
-                        case LFU.last.value.clock < this.clock - this.life:
-                        case LFU.last.value.expiry !== global_1.Infinity && LFU.last.value.expiry < (0, clock_1.now)(): {
-                                const index = LFU.pop();
-                                record = this.memory.get(index.key);
-                                record.index = LRU.push(index);
-                                break;
-                            }
-                        case LFU.length > this.capacity * this.ratio / 100: {
-                                const index = LFU.pop();
-                                index.clock = index.clock - this.clock + ++this.clockR;
-                                record = this.memory.get(index.key);
-                                record.index = LRU.unshift(index);
-                                break;
-                            }
+                        case lastIndex && lastIndex.clock < this.clock - this.life:
+                        case lastIndex && lastIndex.expiry !== global_1.Infinity && lastIndex.expiry < (0, clock_1.now)():
+                            target = lastNode;
+                            break;
+                        case LFU.length > this.capacity * this.ratio / 100:
+                            const lastLFU = LFU.last;
+                            LRU.unshiftNode(lastLFU);
+                            lastLFU.value.overflow = OVF.unshift(lastLFU.value);
+                        default:
+                            const lastLRU = LRU.last;
+                            target = lastLRU === skip ? lastLRU.prev : lastLRU;
+                            break;
                         }
-                        const node = LRU.last === skip ? LRU.last.prev : LRU.last;
-                        this.dispose(node, record, true);
+                        this.dispose(target, void 0, true);
                         skip = (skip === null || skip === void 0 ? void 0 : skip.list) ? skip : void 0;
-                        size = (_b = skip === null || skip === void 0 ? void 0 : skip.value.size) !== null && _b !== void 0 ? _b : 0;
+                        size = (_c = skip === null || skip === void 0 ? void 0 : skip.value.size) !== null && _c !== void 0 ? _c : 0;
                     }
@@ -497,3 +504,3 @@ }
                     const expiry = node.value.expiry;
-                    if (expiry !== global_1.Infinity && expiry <= (0, clock_1.now)()) {
+                    if (expiry !== global_1.Infinity && expiry < (0, clock_1.now)()) {
                         this.dispose(node, record, true);
@@ -504,3 +511,3 @@ return;
                         return record.value;
-                    this.access(record);
+                    this.access(node);
                     this.slide();
@@ -514,3 +521,3 @@ return record.value;
                     const expiry = record.index.value.expiry;
-                    if (expiry !== global_1.Infinity && expiry <= (0, clock_1.now)()) {
+                    if (expiry !== global_1.Infinity && expiry < (0, clock_1.now)()) {
                         this.dispose(record.index, record, true);
@@ -534,2 +541,3 @@ return false;
                     this.indexes.LFU.clear();
+                    this.indexes.OVF.clear();
                     if (!this.settings.disposer || !this.settings.capture.clear)
@@ -571,25 +579,22 @@ return void this.memory.clear();
                 }
-                access(record) {
-                    return this.accessLFU(record) || this.accessLRU(record);
+                access(node) {
+                    return this.accessLFU(node) || this.accessLRU(node);
                 }
-                accessLRU(record) {
-                    const node = record.index;
+                accessLRU(node) {
+                    var _a;
                     const index = node.value;
                     const {LRU, LFU} = this.indexes;
                     ++index.stat[0];
-                    ++this.clock;
-                    ++this.clockR;
-                    if (index.clock > this.clockR - LRU.length / 3 && index.stat === this.stats.LRU) {
-                        index.clock = this.clockR;
+                    if (!index.overflow && index.clock >= this.clockR - LRU.length / 3 && this.capacity > 3) {
+                        index.clock = ++this.clockR;
                         node.moveToHead();
                         return true;
                     }
-                    node.delete();
-                    index.clock = this.clock;
+                    index.clock = ++this.clock;
                     index.stat = this.stats.LFU;
-                    record.index = LFU.unshift(index);
+                    (_a = index.overflow) === null || _a === void 0 ? void 0 : _a.delete();
+                    LFU.unshiftNode(node);
                     return true;
                 }
-                accessLFU(record) {
-                    const node = record.index;
+                accessLFU(node) {
                     const index = node.value;
@@ -600,4 +605,3 @@ const {LFU} = this.indexes;
                     ++index.stat[0];
-                    ++this.clock;
-                    index.clock = this.clock;
+                    index.clock = ++this.clock;
                     node.moveToHead();
@@ -734,3 +738,3 @@ return true;
             Object.defineProperty(exports, '__esModule', { value: true });
-            exports.Node = exports.List = void 0;
+            exports.List = void 0;
             const undefined = void 0;
@@ -761,2 +765,5 @@ const LENGTH = Symbol('length');
                 }
+                unshiftNode(node) {
+                    return this.head = this.pushNode(node);
+                }
                 unshiftRotationally(value) {
@@ -778,2 +785,5 @@ const node = this.last;
                 }
+                pushNode(node) {
+                    return this.insert(node, this.head);
+                }
                 pushRotationally(value) {
@@ -791,2 +801,15 @@ const node = this.head;
                 }
+                insert(node, before = this.head) {
+                    var _b, _c;
+                    if (node.list === this)
+                        return before && node.move(before), node;
+                    node.delete();
+                    ++this[LENGTH];
+                    (_b = this.head) !== null && _b !== void 0 ? _b : this.head = node;
+                    node.list = this;
+                    const next = node.next = before !== null && before !== void 0 ? before : node;
+                    const prev = node.prev = (_c = next.prev) !== null && _c !== void 0 ? _c : node;
+                    next.prev = prev.next = node;
+                    return node;
+                }
                 *[(_a = LENGTH, Symbol.iterator)]() {
@@ -803,4 +826,7 @@ for (let node = this.head; node;) {
             class Node {
-                constructor(value, next, prev, list = next ? next.list : new List()) {
-                    var _b;
+                constructor(value, next, prev, list) {
+                    var _b, _c;
+                    if (list === void 0) {
+                        list = (_b = next === null || next === void 0 ? void 0 : next.list) !== null && _b !== void 0 ? _b : new List();
+                    }
                     this.value = value;
@@ -811,8 +837,7 @@ this.next = next;
                     ++list[LENGTH];
-                    (_b = list.head) !== null && _b !== void 0 ? _b : list.head = this;
-                    next ? next.prev = this : this.next = this;
-                    prev ? prev.next = this : this.prev = this;
+                    (_c = list.head) !== null && _c !== void 0 ? _c : list.head = this;
+                    next && prev ? next.prev = prev.next = this : this.next = this.prev = this;
                 }
                 delete() {
-                    if (!this.next && !this.prev)
+                    if (!this.list)
                         return this.value;
@@ -844,5 +869,5 @@ --this.list[LENGTH];
                         return false;
+                    if (before.list !== this.list)
+                        return before.list.insert(this, before), true;
                     const a1 = this;
-                    if (!a1)
-                        return false;
                     const b1 = before;
@@ -877,2 +902,4 @@ if (!b1)
                     const node3 = node2.next;
+                    if (node1.list !== node2.list)
+                        throw new Error(`Spica: InvList: Cannot swap nodes across lists.`);
                     node2.move(node1);
@@ -891,3 +918,2 @@ node1.move(node3);
             }
-            exports.Node = Node;
         },
@@ -894,0 +920,0 @@ {}

package.json

 {
   "name": "dw-cache",
-  "version": "0.0.21",
+  "version": "0.0.22",
   "description": "Dual window cache adaptively coordinates the ratio of LRU to LFU using the two sliding windows.",
@@ -54,3 +54,3 @@ "private": false,
     "power-assert": "^1.6.1",
-    "spica": "0.0.503",
+    "spica": "0.0.504",
     "tsify": "^5.0.4",
@@ -57,0 +57,0 @@ "typescript": "4.5.5",

README.md

@@ -21,4 +21,4 @@ # Dual Window Cache
 'Cache even 100'
-'LRU hit rate', 10.49
-'DWC hit rate', 10.49
+'LRU hit rate', 9.57
+'DWC hit rate', 9.57
 'DWC ratio', 0, 0
@@ -28,4 +28,4 @@ 'DWC / LRU hit rate ratio', '100%'
 'Cache uneven 100'
-'LRU hit rate', 18.67
-'DWC hit rate', 36.62
+'LRU hit rate', 18.98
+'DWC hit rate', 37.27
 'DWC ratio', 95, 95
@@ -35,10 +35,10 @@ 'DWC / LRU hit rate ratio', '196%'
 'Cache uneven 100 transitive distribution'
-'LRU hit rate', 18.49
-'DWC hit rate', 37.03
+'LRU hit rate', 18.07
+'DWC hit rate', 35.74
 'DWC ratio', 95, 95
-'DWC / LRU hit rate ratio', '200%'
+'DWC / LRU hit rate ratio', '197%'
 
 'Cache uneven 100 transitive bias'
-'LRU hit rate', 11.37
-'DWC hit rate', 11.37
+'LRU hit rate', 11.21
+'DWC hit rate', 11.21
 'DWC ratio', 0, 0
@@ -48,15 +48,15 @@ 'DWC / LRU hit rate ratio', '100%'
 'Cache uneven 100 sequential'
-'LRU hit rate', 13.64
-'DWC hit rate', 37.76
+'LRU hit rate', 14.14
+'DWC hit rate', 38.24
 'DWC ratio', 95, 95
-'DWC / LRU hit rate ratio', '276%'
+'DWC / LRU hit rate ratio', '270%'
 
 'Cache uneven 100 adversarial'
-'LRU hit rate', 42.35
-'DWC hit rate', 50
-'DWC ratio', 95, 95
+'LRU hit rate', 41.78
+'DWC hit rate', 49.59
+'DWC ratio', 94, 93
 'DWC / LRU hit rate ratio', '118%'
 ```
 
-https://github.com/falsandtru/spica/runs/4975199942
+https://github.com/falsandtru/spica/runs/4991878619
 
@@ -68,20 +68,24 @@ ### Benchmark
 ```
-'LRUCache simulation 100 x 4,374,051 ops/sec ±0.29% (42 runs sampled)'
+'LRUCache simulation 100 x 3,492,847 ops/sec ±0.94% (65 runs sampled)'
 
-'DW-Cache simulation 100 x 4,266,032 ops/sec ±0.34% (40 runs sampled)'
+'DW-Cache simulation 100 x 3,415,062 ops/sec ±0.55% (66 runs sampled)'
 
-'LRUCache simulation 1,000 x 4,157,006 ops/sec ±0.84% (39 runs sampled)'
+'LRUCache simulation 1,000 x 3,304,101 ops/sec ±0.47% (67 runs sampled)'
 
-'DW-Cache simulation 1,000 x 4,040,645 ops/sec ±5.22% (32 runs sampled)'
+'DW-Cache simulation 1,000 x 2,767,648 ops/sec ±3.77% (55 runs sampled)'
 
-'LRUCache simulation 10,000 x 2,812,756 ops/sec ±2.48% (36 runs sampled)'
+'LRUCache simulation 10,000 x 2,257,419 ops/sec ±3.30% (59 runs sampled)'
 
-'DW-Cache simulation 10,000 x 3,123,457 ops/sec ±3.11% (39 runs sampled)'
+'DW-Cache simulation 10,000 x 2,455,625 ops/sec ±3.14% (63 runs sampled)'
 
-'LRUCache simulation 100,000 x 1,493,577 ops/sec ±2.45% (39 runs sampled)'
+'LRUCache simulation 100,000 x 1,235,246 ops/sec ±3.40% (55 runs sampled)'
 
-'DW-Cache simulation 100,000 x 1,610,209 ops/sec ±8.14% (30 runs sampled)'
+'DW-Cache simulation 100,000 x 1,194,966 ops/sec ±6.72% (53 runs sampled)'
+
+'LRUCache simulation 1,000,000 x 769,860 ops/sec ±7.67% (58 runs sampled)'
+
+'DW-Cache simulation 1,000,000 x 681,607 ops/sec ±7.97% (57 runs sampled)'
 ```
 
-https://github.com/falsandtru/spica/runs/4975213482
+https://github.com/falsandtru/spica/runs/4991888588
 
@@ -91,19 +95,5 @@ ## API
 ```ts
-export interface CacheOptions<K, V = undefined> {
-  readonly space?: number;
-  readonly age?: number;
-  readonly life?: number;
-  readonly limit?: number;
-  readonly disposer?: (value: V, key: K) => void;
-  readonly capture?: {
-    readonly delete?: boolean;
-    readonly clear?: boolean;
-  };
-}
-
 export class Cache<K, V = undefined> {
-  constructor(
-    capacity: number,
-    opts: CacheOptions<K, V> = {},
-  );
+  constructor(capacity: number, opts?: Cache.Options<K, V>);
+  constructor(opts: Cache.Options<K, V>);
   put(key: K, value: V, size?: number, age?: number): boolean;
@@ -119,2 +109,15 @@ set(key: K, value: V, size?: number, age?: number): this;
 }
+namespace Cache {
+  export interface Options<K, V = undefined> {
+    readonly space?: number;
+    readonly age?: number;
+    readonly life?: number;
+    readonly limit?: number;
+    readonly disposer?: (value: V, key: K) => void;
+    readonly capture?: {
+      readonly delete?: boolean;
+      readonly clear?: boolean;
+    };
+  }
+}
 ```

No alert changes

Improved metrics

Total package byte prevSize

484627

increased by0.37%

Lines of code

11836

increased by0.22%

Number of lines in readme file

117

increased by2.63%

No dependency changes