From 4f9327bf63123fa94e86b027ad1ab9b0a22c3500 Mon Sep 17 00:00:00 2001
From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= <jerome.benoit@sap.com>
Date: Mon, 29 May 2023 15:33:14 +0200
Subject: [PATCH] perf: use O(1) queue implementation in async locking code
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

Signed-off-by: Jérôme Benoit <jerome.benoit@sap.com>
---
 src/utils/AsyncLock.ts  | 14 ++++++---
 src/utils/Queue.ts      | 70 +++++++++++++++++++++++++++++++++++++++++
 test/utils/QueueTest.ts | 53 +++++++++++++++++++++++++++++++
 3 files changed, 132 insertions(+), 5 deletions(-)
 create mode 100644 src/utils/Queue.ts
 create mode 100644 test/utils/QueueTest.ts

diff --git a/src/utils/AsyncLock.ts b/src/utils/AsyncLock.ts
index cf0443b2..f00ee568 100644
--- a/src/utils/AsyncLock.ts
+++ b/src/utils/AsyncLock.ts
@@ -1,18 +1,22 @@
 // Partial Copyright Jerome Benoit. 2021-2023. All Rights Reserved.
 
+import { Queue } from './Queue';
+
 export enum AsyncLockType {
   configuration = 'configuration',
   performance = 'performance',
 }
 
+type ResolveType = (value: void | PromiseLike<void>) => void;
+
 export class AsyncLock {
   private static readonly asyncLocks = new Map<AsyncLockType, AsyncLock>();
   private acquired: boolean;
-  private readonly resolveQueue: ((value: void | PromiseLike<void>) => void)[];
+  private readonly resolveQueue: Queue<ResolveType>;
 
   private constructor() {
     this.acquired = false;
-    this.resolveQueue = [];
+    this.resolveQueue = new Queue<ResolveType>();
   }
 
   public static async acquire(type: AsyncLockType): Promise<void> {
@@ -22,17 +26,17 @@ export class AsyncLock {
       return;
     }
     return new Promise((resolve) => {
-      asyncLock.resolveQueue.push(resolve);
+      asyncLock.resolveQueue.enqueue(resolve);
     });
   }
 
   public static async release(type: AsyncLockType): Promise<void> {
     const asyncLock = AsyncLock.getAsyncLock(type);
-    if (asyncLock.resolveQueue.length === 0 && asyncLock.acquired) {
+    if (asyncLock.resolveQueue.size === 0 && asyncLock.acquired) {
       asyncLock.acquired = false;
       return;
     }
-    const queuedResolve = asyncLock.resolveQueue.shift();
+    const queuedResolve = asyncLock.resolveQueue.dequeue();
     return new Promise((resolve) => {
       queuedResolve();
       resolve();
diff --git a/src/utils/Queue.ts b/src/utils/Queue.ts
new file mode 100644
index 00000000..c13a7bda
--- /dev/null
+++ b/src/utils/Queue.ts
@@ -0,0 +1,70 @@
+// Copyright Jerome Benoit. 2021-2023. All Rights Reserved.
+
+/**
+ * Queue
+ *
+ * @typeParam T - Type of queue items.
+ */
+export class Queue<T> {
+  private items: Record<number, T>;
+  private head: number;
+  private tail: number;
+
+  public constructor() {
+    this.items = {};
+    this.head = 0;
+    this.tail = 0;
+  }
+
+  /**
+   * Get the size of the queue.
+   *
+   * @returns The size of the queue.
+   * @readonly
+   */
+  public get size(): number {
+    return this.tail - this.head;
+  }
+
+  /**
+   * Enqueue an item.
+   *
+   * @param item - Item to enqueue.
+   * @returns The new size of the queue.
+   */
+  public enqueue(item: T): number {
+    this.items[this.tail] = item;
+    this.tail++;
+    return this.size;
+  }
+
+  /**
+   * Dequeue an item.
+   *
+   * @returns The dequeued item or `undefined` if the queue is empty.
+   */
+  public dequeue(): T | undefined {
+    if (this.size <= 0) {
+      return undefined;
+    }
+    const item = this.items[this.head];
+    // eslint-disable-next-line @typescript-eslint/no-dynamic-delete
+    delete this.items[this.head];
+    this.head++;
+    if (this.head === this.tail) {
+      this.head = 0;
+      this.tail = 0;
+    }
+    return item;
+  }
+
+  /**
+   * Peek at the first item.
+   */
+  public peek(): T | undefined {
+    if (this.size <= 0) {
+      return undefined;
+    }
+    return this.items[this.head];
+  }
+}
diff --git a/test/utils/QueueTest.ts b/test/utils/QueueTest.ts
new file mode 100644
index 00000000..babce1ed
--- /dev/null
+++ b/test/utils/QueueTest.ts
@@ -0,0 +1,53 @@
+/* eslint-disable @typescript-eslint/no-unsafe-member-access */
+import { expect } from 'expect';
+
+import { Queue } from '../../src/utils/Queue';
+
+describe('Queue test suite', () => {
+  it('Verify enqueue() behavior', () => {
+    const queue = new Queue();
+    let rtSize = queue.enqueue(1);
+    expect(queue.size).toBe(1);
+    expect(rtSize).toBe(queue.size);
+    expect((queue as any).head).toBe(0);
+    expect((queue as any).tail).toBe(1);
+    expect((queue as any).items).toStrictEqual({ 0: 1 });
+    rtSize = queue.enqueue(2);
+    expect(queue.size).toBe(2);
+    expect(rtSize).toBe(queue.size);
+    expect((queue as any).head).toBe(0);
+    expect((queue as any).tail).toBe(2);
+    expect((queue as any).items).toStrictEqual({ 0: 1, 1: 2 });
+    rtSize = queue.enqueue(3);
+    expect(queue.size).toBe(3);
+    expect(rtSize).toBe(queue.size);
+    expect((queue as any).head).toBe(0);
+    expect((queue as any).tail).toBe(3);
+    expect((queue as any).items).toStrictEqual({ 0: 1, 1: 2, 2: 3 });
+  });
+
+  it('Verify dequeue() behavior', () => {
+    const queue = new Queue();
+    queue.enqueue(1);
+    queue.enqueue(2);
+    queue.enqueue(3);
+    let rtItem = queue.dequeue();
+    expect(queue.size).toBe(2);
+    expect(rtItem).toBe(1);
+    expect((queue as any).head).toBe(1);
+    expect((queue as any).tail).toBe(3);
+    expect((queue as any).items).toStrictEqual({ 1: 2, 2: 3 });
+    rtItem = queue.dequeue();
+    expect(queue.size).toBe(1);
+    expect(rtItem).toBe(2);
+    expect((queue as any).head).toBe(2);
+    expect((queue as any).tail).toBe(3);
+    expect((queue as any).items).toStrictEqual({ 2: 3 });
+    rtItem = queue.dequeue();
+    expect(queue.size).toBe(0);
+    expect(rtItem).toBe(3);
+    expect((queue as any).head).toBe(0);
+    expect((queue as any).tail).toBe(0);
+    expect((queue as any).items).toStrictEqual({});
+  });
+});
-- 
2.34.1