dw-cache - npm Package Compare versions

Comparing version 0.0.93 to 0.0.94

dist/index.js

@@ -1,2 +0,2 @@
-/*! dw-cache v0.0.93 https://github.com/falsandtru/dw-cache | (c) 2021, falsandtru | (Apache-2.0 AND MPL-2.0) License */
+/*! dw-cache v0.0.94 https://github.com/falsandtru/dw-cache | (c) 2021, falsandtru | (Apache-2.0 AND MPL-2.0) License */
 (function webpackUniversalModuleDefinition(root, factory) {
@@ -55,5 +55,5 @@ if(typeof exports === 'object' && typeof module === 'object')
 }));
-exports.ObjectSetPrototypeOf = exports.ObjectGetPrototypeOf = exports.ObjectCreate = exports.ObjectAssign = exports.toString = exports.isEnumerable = exports.isPrototypeOf = exports.hasOwnProperty = exports.isArray = exports.sqrt = exports.log = exports.tan = exports.cos = exports.sign = exports.round = exports.random = exports.min = exports.max = exports.floor = exports.ceil = exports.abs = exports.PI = exports.parseInt = exports.parseFloat = exports.isSafeInteger = exports.isNaN = exports.isInteger = exports.isFinite = exports.EPSILON = exports.MIN_VALUE = exports.MIN_SAFE_INTEGER = exports.MAX_VALUE = exports.MAX_SAFE_INTEGER = void 0;
+exports.ObjectSetPrototypeOf = exports.ObjectGetPrototypeOf = exports.ObjectCreate = exports.ObjectAssign = exports.toString = exports.isEnumerable = exports.isPrototypeOf = exports.hasOwnProperty = exports.isArray = exports.sqrt = exports.log10 = exports.log2 = exports.log = exports.tan = exports.cos = exports.sign = exports.round = exports.random = exports.min = exports.max = exports.floor = exports.ceil = exports.abs = exports.PI = exports.parseInt = exports.parseFloat = exports.isSafeInteger = exports.isNaN = exports.isInteger = exports.isFinite = exports.EPSILON = exports.MIN_VALUE = exports.MIN_SAFE_INTEGER = exports.MAX_VALUE = exports.MAX_SAFE_INTEGER = void 0;
 exports.MAX_SAFE_INTEGER = Number.MAX_SAFE_INTEGER, exports.MAX_VALUE = Number.MAX_VALUE, exports.MIN_SAFE_INTEGER = Number.MIN_SAFE_INTEGER, exports.MIN_VALUE = Number.MIN_VALUE, exports.EPSILON = Number.EPSILON, exports.isFinite = Number.isFinite, exports.isInteger = Number.isInteger, exports.isNaN = Number.isNaN, exports.isSafeInteger = Number.isSafeInteger, exports.parseFloat = Number.parseFloat, exports.parseInt = Number.parseInt;
-exports.PI = Math.PI, exports.abs = Math.abs, exports.ceil = Math.ceil, exports.floor = Math.floor, exports.max = Math.max, exports.min = Math.min, exports.random = Math.random, exports.round = Math.round, exports.sign = Math.sign, exports.cos = Math.cos, exports.tan = Math.tan, exports.log = Math.log, exports.sqrt = Math.sqrt;
+exports.PI = Math.PI, exports.abs = Math.abs, exports.ceil = Math.ceil, exports.floor = Math.floor, exports.max = Math.max, exports.min = Math.min, exports.random = Math.random, exports.round = Math.round, exports.sign = Math.sign, exports.cos = Math.cos, exports.tan = Math.tan, exports.log = Math.log, exports.log2 = Math.log2, exports.log10 = Math.log10, exports.sqrt = Math.sqrt;
 exports.isArray = Array.isArray;
@@ -88,3 +88,3 @@ exports.hasOwnProperty = Object.prototype.hasOwnProperty.call.bind(Object.prototype.hasOwnProperty);
     if (as.length === 1) return bs.unshift(as[0]), bs;
-    if (Symbol.iterator in as) return bs.unshift(...as), bs;
+    if (Array.isArray(as)) return bs.unshift(...as), bs;
     for (let i = as.length; i--;) {
@@ -107,3 +107,3 @@ bs.unshift(as[i]);
     if (bs.length === 1) return as.push(bs[0]), as;
-    if (Symbol.iterator in bs && bs.length > 50) return as.push(...bs), as;
+    if (Array.isArray(bs) && bs.length > 100) return as.push(...bs), as;
     for (let len = bs.length, i = 0; i < len; ++i) {
@@ -300,3 +300,3 @@ as.push(bs[i]);
 const alias_1 = __webpack_require__(406);
-const clock_1 = __webpack_require__(681);
+const chrono_1 = __webpack_require__(393);
 const list_1 = __webpack_require__(667);
@@ -313,5 +313,2 @@ const heap_1 = __webpack_require__(818);
 
-LFUヒット率変化率：
-S3での逆効果のみ確認につきオプション化。
-
 統計解像度：
@@ -412,2 +409,5 @@ 効果ないが検証用に残置。
 }
+function segment(expiration) {
+  return (0, alias_1.floor)(expiration / 16);
+}
 class Cache {
@@ -427,3 +427,2 @@ constructor(capacity, opts = {}) {
       resolution: 1,
-      offset: 0,
       sweep: {
@@ -442,5 +441,4 @@ threshold: 10,
     this.overlapLFU = 0;
-    this.expiration = false;
     this.$size = 0;
-    this.acc = 0;
+    this.injection = 0;
     this.densityR = 0;
@@ -469,7 +467,10 @@ this.densityF = 0;
     this.resource = settings.resource ?? capacity;
+    this.expiration = opts.age !== undefined;
     this.age = settings.age;
     if (settings.eagerExpiration) {
-      this.expirations = new heap_1.Heap(heap_1.Heap.min);
+      this.expirations = new heap_1.Heap(heap_1.Heap.min, {
+        stable: false
+      });
     }
-    this.stats = opts.resolution || opts.offset ? new StatsExperimental(this.window, settings.resolution, settings.offset) : new Stats(this.window);
+    this.stats = opts.resolution ? new StatsExperimental(this.window, settings.resolution, 0) : new Stats(this.window);
     this.sweeper = new Sweeper(this.LRU, settings.sweep.threshold, capacity, settings.sweep.window, settings.sweep.range, settings.sweep.shift);
@@ -519,2 +520,3 @@ this.disposer = settings.disposer;
   }
+  // Update and deletion are reentrant but addition is not.
   ensure(margin, target, capture = false) {
@@ -527,4 +529,4 @@ let size = target?.size ?? 0;
     while (this.size + margin - size > this.resource) {
-      let victim = this.expirations?.peek();
-      if (victim !== undefined && victim !== target && victim.expiration < (0, clock_1.now)()) {} else if (LRU.length === 0) {
+      let victim = this.expirations?.peek()?.value;
+      if (victim !== undefined && victim !== target && victim.expiration < (0, chrono_1.now)()) {} else if (LRU.length === 0) {
         victim = LFU.head.prev;
@@ -542,9 +544,9 @@ victim = victim !== target ? victim : victim.prev;
         } else if (LRU.length >= this.capacity - this.limit && this.overlapLRU * 100 / (0, alias_1.min)(LFU.length, this.partition) < this.sample) {
-          this.acc = (0, alias_1.min)(this.acc + this.sample / 100, this.capacity);
+          this.injection = (0, alias_1.min)(this.injection + this.sample / 100, this.capacity);
           const entry = LRU.head.prev;
-          if (this.acc >= 1 && entry.region === 'LRU') {
+          if (this.injection >= 1 && entry.region === 'LRU') {
             LRU.delete(entry);
             LFU.unshift(this.overlap(entry));
             entry.partition = LFU;
-            --this.acc;
+            --this.injection;
           }
@@ -575,7 +577,26 @@ }
   }
-  put(key, value, {
+  update(entry, key, value, size, expiration) {
+    const key$ = entry.key;
+    const value$ = entry.value;
+    entry.key = key;
+    entry.value = value;
+    this.$size += size - entry.size;
+    entry.size = size;
+    entry.expiration = expiration;
+    if (this.expiration && this.expirations !== undefined && expiration !== Infinity) {
+      entry.enode !== undefined ? this.expirations.update(entry.enode, segment(expiration)) : entry.enode = this.expirations.insert(entry, segment(expiration));
+    } else if (entry.enode !== undefined) {
+      this.expirations.delete(entry.enode);
+      entry.enode = undefined;
+    }
+    this.disposer?.(value$, key$);
+  }
+  validate(size, age) {
+    return 1 <= size && size <= this.resource && 1 <= age;
+  }
+  add(key, value, {
     size = 1,
     age = this.age
-  } = {}) {
-    if (size < 1 || this.resource < size || age <= 0) {
+  } = {}, victim) {
+    if (!this.validate(size, age)) {
       this.disposer?.(value, key);
@@ -587,40 +608,44 @@ return false;
     } = this;
-    const expiration = age === Infinity ? Infinity : (0, clock_1.now)() + age;
-    if (!this.expiration && expiration !== Infinity) {
-      this.expiration = true;
+    const expiration = age === Infinity ? age : (0, chrono_1.now)() + age;
+    victim = this.ensure(size, victim, true);
+    // Note that the key will be duplicate if the key is evicted and added again in disposing.
+    if (victim !== undefined) {
+      victim.region === 'LFU' && --this.overlapLFU;
+      this.dict.delete(victim.key);
+      this.dict.set(key, victim);
+      victim.region = 'LRU';
+      LRU.head = victim;
+      this.update(victim, key, value, size, expiration);
+      return true;
     }
-    let entry = this.dict.get(key);
-    const match = entry !== undefined;
-    entry = this.ensure(size, entry, true);
-    if (entry === undefined) {
-      this.$size += size;
-      entry = new Entry(key, value, size, LRU, 'LRU', expiration);
-      LRU.unshift(entry);
-      this.dict.set(key, entry);
-      if (this.expiration && this.expirations !== undefined && expiration !== Infinity) {
-        entry.enode = this.expirations.insert(entry, expiration);
-      }
+    this.$size += size;
+    const entry = new Entry(key, value, size, LRU, 'LRU', expiration);
+    LRU.unshift(entry);
+    this.dict.set(key, entry);
+    if (this.expiration && this.expirations !== undefined && expiration !== Infinity) {
+      entry.enode = this.expirations.insert(entry, segment(expiration));
+    }
+    return true;
+  }
+  put(key, value, {
+    size = 1,
+    age = this.age
+  } = {}) {
+    if (!this.validate(size, age)) {
+      this.disposer?.(value, key);
       return false;
     }
-    const key$ = entry.key;
-    const value$ = entry.value;
-    if (!match) {
-      entry.region === 'LFU' && --this.overlapLFU;
-      this.dict.delete(key$);
-      this.dict.set(key, entry);
-      entry.key = key;
-      entry.region = 'LRU';
-      LRU.head = entry;
+    const entry = this.dict.get(key);
+    const match = entry !== undefined;
+    const victim = this.ensure(size, entry, true);
+    // Note that the key of entry or victim may be changed if the new key is set in disposing.
+    if (match && entry === victim) {
+      const expiration = age === Infinity ? age : (0, chrono_1.now)() + age;
+      this.update(entry, key, value, size, expiration);
+      return match;
     }
-    entry.value = value;
-    this.$size += size - entry.size;
-    entry.size = size;
-    entry.expiration = expiration;
-    if (this.expiration && this.expirations !== undefined && expiration !== Infinity) {
-      entry.enode !== undefined ? this.expirations.update(entry.enode, expiration) : entry.enode = this.expirations.insert(entry, expiration);
-    } else if (entry.enode !== undefined) {
-      this.expirations.delete(entry.enode);
-      entry.enode = undefined;
-    }
-    this.disposer?.(value$, key$);
+    this.add(key, value, {
+      size,
+      age
+    }, victim);
     return match;
@@ -638,3 +663,3 @@ }
     }
-    if (this.expiration && entry.expiration !== Infinity && entry.expiration < (0, clock_1.now)()) {
+    if (this.expiration && entry.expiration !== Infinity && entry.expiration < (0, chrono_1.now)()) {
       this.sweeper.miss();
@@ -644,3 +669,3 @@ this.evict(entry, true);
     }
-    this.update(entry);
+    this.replace(entry);
     return entry.value;
@@ -651,3 +676,3 @@ }
     if (entry === undefined) return false;
-    if (this.expiration && entry.expiration !== Infinity && entry.expiration < (0, clock_1.now)()) {
+    if (this.expiration && entry.expiration !== Infinity && entry.expiration < (0, chrono_1.now)()) {
       this.evict(entry, true);
@@ -669,3 +694,3 @@ return false;
     } = this;
-    this.acc = 0;
+    this.injection = 0;
     this.$size = 0;
@@ -680,3 +705,2 @@ this.partition = this.limit;
     this.overlapLFU = 0;
-    this.expiration = false;
     this.expirations?.clear();
@@ -729,3 +753,3 @@ this.stats.clear();
   }
-  update(entry) {
+  replace(entry) {
     const {
@@ -785,6 +809,4 @@ LRU,
     const densityF = this.densityF = ratioF * (1000 - leverage);
-    const densityFO = stats.offset && stats.ratioLFU(true) * (1000 - leverage);
     // 操作頻度を超えてキャッシュ比率を増減させても余剰比率の消化が追いつかず無駄
-    // LRUの下限設定ではLRU拡大の要否を迅速に判定できないためLFUのヒット率低下の検出で代替する
-    if (this.partition > 0 && (densityR > densityF || stats.offset !== 0 && densityF * 100 < densityFO * (100 - stats.offset))) {
+    if (this.partition > 0 && densityR > densityF) {
       if (lenR >= this.capacity - this.partition) {
@@ -1080,3 +1102,3 @@ const delta = ratioF > ratioR ? this.unit * ratioF / ratioR | 0 : this.unit;
 
-/***/ 681:
+/***/ 393:
 /***/ ((__unused_webpack_module, exports, __webpack_require__) => {
@@ -1215,3 +1237,3 @@
   peek() {
-    return this.array[0]?.[1];
+    return this.array[0];
   }
@@ -1223,3 +1245,7 @@ insert(value, order) {
     const array = this.array;
-    const node = array[this.$length] = [order, value, ++this.$length];
+    const node = array[this.$length] = {
+      index: ++this.$length,
+      order,
+      value
+    };
     upHeapify(this.cmp, array, this.$length);
@@ -1234,6 +1260,8 @@ return node;
     const array = this.array;
-    const old = array[0][1];
-    array[0] = [order, value, 1];
+    const node = array[0];
+    const val = node.value;
+    node.order = order;
+    node.value = value;
     downHeapify(this.cmp, array, 1, this.$length, this.stable);
-    return old;
+    return val;
   }
@@ -1244,7 +1272,7 @@ extract() {
     this.delete(node);
-    return node[1];
+    return node.value;
   }
   delete(node) {
     const array = this.array;
-    const index = node[2];
+    const index = node.index;
     if (array[index - 1] !== node) throw new Error('Invalid node');
@@ -1254,15 +1282,15 @@ swap(array, index, this.$length--);
     array[this.$length] = undefined;
-    return node[1];
+    return node.value;
   }
   update(node, order, value) {
     const array = this.array;
-    const index = node[2];
+    const index = node.index;
     if (array[index - 1] !== node) throw new Error('Invalid node');
     if (arguments.length === 1) {
-      order = node[0];
+      order = node.order;
     }
     if (arguments.length >= 3) {
-      node[1] = value;
+      node.value = value;
     }
-    if (this.cmp(node[0], node[0] = order) === 0) return;
+    if (this.cmp(node.order, node.order = order) === 0) return;
     sort(this.cmp, array, index, this.$length, this.stable);
@@ -1290,7 +1318,7 @@ }
 function upHeapify(cmp, array, index) {
-  const order = array[index - 1][0];
+  const order = array[index - 1].order;
   let changed = false;
   while (index > 1) {
     const parent = index / 2 | 0;
-    if (cmp(array[parent - 1][0], order) <= 0) break;
+    if (cmp(array[parent - 1].order, order) <= 0) break;
     swap(array, index, parent);
@@ -1309,3 +1337,3 @@ index = parent;
     if (left <= length) {
-      const result = cmp(array[left - 1][0], array[min - 1][0]);
+      const result = cmp(array[left - 1].order, array[min - 1].order);
       if (stable ? result <= 0 : result < 0) {
@@ -1316,3 +1344,3 @@ min = left;
     if (right <= length) {
-      const result = cmp(array[right - 1][0], array[min - 1][0]);
+      const result = cmp(array[right - 1].order, array[min - 1].order);
       if (stable ? result <= 0 : result < 0) {
@@ -1337,9 +1365,10 @@ min = right;
   array[pos2] = node1;
-  node1[2] = index2;
-  node2[2] = index1;
+  node1.index = index2;
+  node2.index = index1;
 }
 class MultiNode extends list_1.List.Node {
-  constructor(list, value) {
+  constructor(list, order, value) {
     super();
     this.list = list;
+    this.order = order;
     this.value = value;
@@ -1369,3 +1398,3 @@ }
   peek() {
-    return this.heap.peek()?.head.value;
+    return this.heap.peek()?.value.head;
   }
@@ -1377,3 +1406,3 @@ insert(value, order) {
     ++this.$length;
-    const node = new MultiNode(this.list(order), value);
+    const node = new MultiNode(this.list(order), order, value);
     node.list.push(node);
@@ -1385,3 +1414,3 @@ return node;
     --this.$length;
-    const list = this.heap.peek();
+    const list = this.heap.peek()?.value;
     const value = list.shift().value;
@@ -1593,9 +1622,9 @@ if (list.length === 0) {
 function memoizeArray(f, identify, memory) {
-  let nullish = false;
+  let nullable = false;
   return (...as) => {
     const b = identify(...as);
     let z = memory[b];
-    if (z !== undefined || nullish && memory[b] !== undefined) return z;
+    if (z !== undefined || nullable && memory[b] !== undefined) return z;
     z = f(...as);
-    nullish ||= z === undefined;
+    nullable ||= z === undefined;
     memory[b] = z;
@@ -1606,10 +1635,10 @@ return z;
 function memoizeObject(f, identify, memory) {
-  let nullish = false;
+  let nullable = false;
   return (...as) => {
     const b = identify(...as);
     let z = memory.get(b);
-    if (z !== undefined || nullish && memory.has(b)) return z;
+    if (z !== undefined || nullable && memory.has(b)) return z;
     z = f(...as);
-    nullish ||= z === undefined;
-    memory.set(b, z);
+    nullable ||= z === undefined;
+    memory.add?.(b, z) ?? memory.set(b, z);
     return z;
@@ -1756,3 +1785,3 @@ };
   peek(priority) {
-    return arguments.length === 0 ? this.heap.peek()?.peek() : this.dict.get(priority)?.peek();
+    return arguments.length === 0 ? this.heap.peek()?.value.peek() : this.dict.get(priority)?.peek();
   }
@@ -1766,3 +1795,3 @@ push(priority, value) {
     --this.$length;
-    const queue = arguments.length === 0 ? this.heap.peek() : this.dict.get(priority);
+    const queue = arguments.length === 0 ? this.heap.peek().value : this.dict.get(priority);
     const value = queue?.pop();
@@ -1894,3 +1923,3 @@ if (queue?.isEmpty()) {
     } = this;
-    return index === 0 ? array[(array.length || 1) - 1] : array[0];
+    return index === 0 ? array.at(-1) : array[0];
   }
@@ -1897,0 +1926,0 @@ push(value) {

package.json

 {
   "name": "dw-cache",
-  "version": "0.0.93",
+  "version": "0.0.94",
   "description": "The highest performance constant complexity cache algorithm.",
@@ -36,7 +36,7 @@ "private": false,
     "@types/power-assert": "1.5.8",
-    "@typescript-eslint/parser": "^5.45.0",
+    "@typescript-eslint/parser": "^5.45.1",
     "babel-loader": "^9.1.0",
     "babel-plugin-unassert": "^3.2.0",
     "concurrently": "^7.6.0",
-    "eslint": "^8.28.0",
+    "eslint": "^8.29.0",
     "eslint-plugin-redos": "^4.4.1",
@@ -54,7 +54,7 @@ "eslint-webpack-plugin": "^3.2.0",
     "npm-check-updates": "^16.4.3",
-    "spica": "0.0.701",
-    "ts-loader": "^9.4.1",
+    "spica": "0.0.707",
+    "ts-loader": "^9.4.2",
     "typescript": "4.9.3",
     "webpack": "^5.75.0",
-    "webpack-cli": "^5.0.0",
+    "webpack-cli": "^5.0.1",
     "webpack-merge": "^5.8.0"
@@ -61,0 +61,0 @@ },

README.md

@@ -22,3 +22,3 @@ # Dual Window Cache
 - Transitive wide MRU with cyclic replacement
-- Sampled history
+- Sampled history injection
 
@@ -757,2 +757,3 @@ ## Properties
     readonly eagerExpiration?: boolean;
+    // WARNING: Don't add any new key in disposing.
     readonly disposer?: (value: V, key: K) => void;
@@ -771,3 +772,2 @@ readonly capture?: {
     readonly resolution?: number;
-    readonly offset?: number;
     readonly sweep?: {
@@ -774,0 +774,0 @@ readonly threshold?: number;

No alert changes

Improved metrics

Total package byte prevSize

113987

increased by0.76%

Lines of code

2136

increased by1.42%

No dependency changes