spica - npm Package Compare versions

Comparing version 0.0.784 to 0.0.785

cache.ts

@@ -188,4 +188,4 @@ import { max, min, round } from './alias';
     this.partition = capacity - this.window;
+    this.resource = settings.resource! ?? capacity;
     this.sample = settings.sample!;
-    this.resource = settings.resource! ?? capacity;
     this.age = settings.age!;
@@ -192,0 +192,0 @@ if (settings.eagerExpiration) {

colistener.ts

@@ -30,3 +30,3 @@ import { AtomicFuture } from './future';
         notifiable = true;
-        while (queue.length > 0) {
+        while (!queue.isEmpty()) {
           yield queue.pop()!;
@@ -33,0 +33,0 @@ }

package.json

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

queue.test.ts

@@ -59,8 +59,8 @@ import { Queue } from './queue';
       for (const size of [
-        16 - 1 + (2048 - 1) * 0,
-        16 - 1 + (2048 - 1) * 1,
-        16 - 1 + (2048 - 1) * 2,
-        16 - 1 + (2048 - 1) * 3,
-      ]) for (const permanent of [false, true]) {
-        const queue = new Queue(permanent);
+        16 + 2048 * 0,
+        16 + 2048 * 1,
+        16 + 2048 * 2,
+        16 + 2048 * 3,
+      ]) {
+        const queue = new Queue();
         for (let i = -3; i < 4; ++i) {
@@ -67,0 +67,0 @@ const len = size + i;

queue.ts

@@ -9,6 +9,2 @@ import { Heap } from './heap';
 export class Queue<T> {
-  constructor(
-    private readonly permanent: boolean = false,
-  ) {
-  }
   private head = new FixedQueue<T>(initsize);
@@ -21,4 +17,5 @@ private tail = this.head;
       ? this.head.length
-      : this.head.length + this.tail.length + (size - 1) * (this.count - 2) + (this.irregular || size) - 1;
+      : this.head.length + this.tail.length + size * (this.count - 2) + (this.irregular || size);
   }
+  // Faster than queue.length > 0.
   public isEmpty(): boolean {
@@ -38,9 +35,6 @@ return this.head.isEmpty();
       }
-      else if (!this.permanent) {
-        this.tail = tail.next = new FixedQueue(size);
-        assert(this.tail.next !== this.head);
-      }
       else {
         this.tail = tail.next = new FixedQueue(size, tail.next);
       }
+      assert(this.tail.isEmpty());
       ++this.count;
@@ -54,2 +48,3 @@ if (tail.size !== size && tail !== this.head) {
   }
+  private prev?: FixedQueue<T> = undefined;
   public pop(): T | undefined {
@@ -59,7 +54,12 @@ const head = this.head;
     if (head.isEmpty() && !head.next.isEmpty()) {
-      --this.count;
-      this.head = head.next;
-      if (!this.permanent) {
+      if (this.prev?.isEmpty()) {
+        this.head = this.prev.next = head.next;
         head.next = head;
       }
+      else {
+        this.head = head.next;
+        this.prev = head;
+      }
+      assert(this.prev.next === this.head);
+      --this.count;
       if (this.head.size === this.irregular) {
@@ -84,3 +84,2 @@ assert(this.irregular === initsize);
 
-// capacity = size - 1
 class FixedQueue<T> {
@@ -98,13 +97,15 @@ constructor(
   private tail = 0;
+  // 1要素無駄にしフラグを使用しない場合と有意差がないため可読性とテスト性を優先しフラグを使用。
+  private empty = true;
   public next: FixedQueue<T>;
   public get length(): number {
     return this.tail >= this.head
-      ? this.tail - this.head
+      ? this.empty ? 0 : this.tail - this.head || this.size
       : this.array.length - this.head + this.tail;
   }
   public isEmpty(): boolean {
-    return this.tail === this.head;
+    return this.empty;
   }
   public isFull(): boolean {
-    return (this.tail + 1 & this.mask) === this.head;
+    return this.tail === this.head && !this.empty;
   }
@@ -119,8 +120,11 @@ public peek(index: 0 | -1 = 0): T | undefined {
     this.tail = this.tail + 1 & this.mask;
+    this.empty = false;
   }
   public pop(): T | undefined {
-    if (this.isEmpty()) return;
+    if (this.empty) return;
     const value = this.array[this.head];
     this.array[this.head] = undefined;
     this.head = this.head + 1 & this.mask;
+    // isEmptyの前倒し
+    this.empty = this.tail === this.head;
     return value;
@@ -127,0 +131,0 @@ }

s3-fifo.ts

@@ -24,5 +24,5 @@ // https://jasony.me/publication/sosp23-s3fifo.pdf
   private readonly dict = new Map<K, Node<K, V>>();
-  private readonly fifoS = new Queue<Node<K, V>>(true);
-  private readonly fifoM = new Queue<Node<K, V>>(true);
-  private readonly fifoG = new Queue<Node<K, undefined>>(true);
+  private readonly fifoS = new Queue<Node<K, V>>();
+  private readonly fifoM = new Queue<Node<K, V>>();
+  private readonly fifoG = new Queue<Node<K, undefined>>();
   public get length(): number {
@@ -65,3 +65,3 @@ return this.fifoS.length + this.fifoM.length;
   private evictS(): void {
-    while (this.fifoS.length > 0) {
+    while (!this.fifoS.isEmpty()) {
       const t = this.fifoS.pop()!;
@@ -87,3 +87,3 @@ if (t.freq > 1) {
   private evictM(): void {
-    while (this.fifoM.length > 0) {
+    while (!this.fifoM.isEmpty()) {
       const t = this.fifoM.pop()!;
@@ -101,3 +101,3 @@ if (t.freq > 0) {
   private evictG(): void {
-    while (this.fifoG.length > 0) {
+    while (!this.fifoG.isEmpty()) {
       const t = this.fifoG.pop()!;
@@ -104,0 +104,0 @@ if (!t.resident) {

tlru.ts

@@ -12,3 +12,4 @@ // TLRU: True LRU
 step=100で重み付けと保護なしの純粋なTLRUを設定できる。
-windowパラメータでSLRU同様捕捉可能最小再利用距離を保証できる。
+windowパラメータでSLRU同様捕捉可能最小再利用距離を設定できるが
+降格区間内では捕捉可能再利用距離が半減しSLRUより短くなる。
 DWCより高速かつ堅牢でアプリケーションのインメモリキャッシュなどの
@@ -15,0 +16,0 @@ 極端に変化の大きいアクセスパターンにも適応する。

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

842209

increased by0.03%

Lines of code

27493

increased by0.02%

No dependency changes