From 9df282a07ef35012409d7d08207e6df983a7e905 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Tue, 28 May 2024 18:32:06 +0200 Subject: [PATCH] perf: optimize tasks queue implementation MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- src/fixed-priority-queue.ts | 31 ++- src/pools/abstract-pool.ts | 4 +- src/pools/worker-node.ts | 2 +- src/priority-queue.ts | 175 ++++++------- tests/fixed-priority-queue.test.mjs | 378 +++++++++++++++------------- tests/pools/abstract-pool.test.mjs | 6 +- tests/priority-queue.test.mjs | 231 ++++++++--------- 7 files changed, 399 insertions(+), 428 deletions(-) diff --git a/src/fixed-priority-queue.ts b/src/fixed-priority-queue.ts index 78ba2aff..53ef6edb 100644 --- a/src/fixed-priority-queue.ts +++ b/src/fixed-priority-queue.ts @@ -9,7 +9,7 @@ export const defaultQueueSize = 2048 * @typeParam T - Type of priority queue node data. * @internal */ -export interface PriorityQueueNode { +interface PriorityQueueNode { data: T priority: number } @@ -23,12 +23,20 @@ export interface PriorityQueueNode { export class FixedPriorityQueue { private start!: number private readonly nodeArray: Array> + public readonly capacity: number public size!: number public maxSize!: number + /** + * Constructs a fixed priority queue. + * + * @param size - Fixed priority queue size. @defaultValue defaultQueueSize + * @returns FixedPriorityQueue. + */ constructor (size: number = defaultQueueSize) { this.checkSize(size) - this.nodeArray = new Array>(size) + this.capacity = size + this.nodeArray = new Array>(this.capacity) this.clear() } @@ -37,7 +45,7 @@ export class FixedPriorityQueue { } public full (): boolean { - return this.size === this.nodeArray.length + return this.size === this.capacity } public enqueue (data: T, priority?: number): number { @@ -45,7 +53,6 @@ export class FixedPriorityQueue { throw new Error('Priority queue is full') } priority = priority ?? 0 - const nodeArrayLength = this.nodeArray.length let index = this.start let inserted = false for (let i = 0; i < this.size; i++) { @@ -55,16 +62,16 @@ export class FixedPriorityQueue { break } ++index - if (index === nodeArrayLength) { + if (index === this.capacity) { index = 0 } } - this.nodeArray.length !== nodeArrayLength && - (this.nodeArray.length = nodeArrayLength) + this.nodeArray.length !== this.capacity && + (this.nodeArray.length = this.capacity) if (!inserted) { let index = this.start + this.size - if (index >= nodeArrayLength) { - index -= nodeArrayLength + if (index >= this.capacity) { + index -= this.capacity } this.nodeArray[index] = { data, priority } } @@ -78,7 +85,7 @@ export class FixedPriorityQueue { const index = this.start --this.size ++this.start - if (this.start === this.nodeArray.length) { + if (this.start === this.capacity) { this.start = 0 } return this.nodeArray[index].data @@ -99,7 +106,7 @@ export class FixedPriorityQueue { * @returns An iterator for the fixed priority queue. * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols */ - [Symbol.iterator] (): Iterator { + public [Symbol.iterator] (): Iterator { let index = this.start let i = 0 return { @@ -113,7 +120,7 @@ export class FixedPriorityQueue { const value = this.nodeArray[index].data ++index ++i - if (index === this.nodeArray.length) { + if (index === this.capacity) { index = 0 } return { diff --git a/src/pools/abstract-pool.ts b/src/pools/abstract-pool.ts index ebdb0dd8..2c4fdf5a 100644 --- a/src/pools/abstract-pool.ts +++ b/src/pools/abstract-pool.ts @@ -4,6 +4,7 @@ import { EventEmitterAsyncResource } from 'node:events' import { performance } from 'node:perf_hooks' import type { TransferListItem } from 'node:worker_threads' +import { defaultBucketSize } from '../priority-queue.js' import type { MessageValue, PromiseResponseWrapper, @@ -2170,8 +2171,7 @@ export abstract class AbstractPool< getDefaultTasksQueueOptions( this.maximumNumberOfWorkers ?? this.minimumNumberOfWorkers ).size, - tasksQueueBucketSize: - (this.maximumNumberOfWorkers ?? this.minimumNumberOfWorkers) * 2 + tasksQueueBucketSize: defaultBucketSize } ) // Flag the worker node as ready at pool startup. diff --git a/src/pools/worker-node.ts b/src/pools/worker-node.ts index 07955701..7ea617fb 100644 --- a/src/pools/worker-node.ts +++ b/src/pools/worker-node.ts @@ -114,7 +114,7 @@ export class WorkerNode /** @inheritdoc */ public dequeueLastPrioritizedTask (): Task | undefined { // Start from the last empty or partially filled bucket - return this.dequeueTask(this.tasksQueue.buckets + 1) + return this.dequeueTask() } /** @inheritdoc */ diff --git a/src/priority-queue.ts b/src/priority-queue.ts index b4d70b5e..d1d93078 100644 --- a/src/priority-queue.ts +++ b/src/priority-queue.ts @@ -1,14 +1,20 @@ // Copyright Jerome Benoit. 2024. All Rights Reserved. +import { FixedPriorityQueue } from './fixed-priority-queue.js' + +/** + * Default bucket size. + */ +export const defaultBucketSize = 2048 + /** * Priority queue node. * * @typeParam T - Type of priority queue node data. * @internal */ -export interface PriorityQueueNode { - data: T - priority: number +export interface PriorityQueueNode extends FixedPriorityQueue { + next?: FixedPriorityQueue } /** @@ -18,42 +24,33 @@ export interface PriorityQueueNode { * @internal */ export class PriorityQueue { - private nodeArray!: Array> - /** Prioritized bucket size. */ + private head!: PriorityQueueNode + private tail!: PriorityQueueNode private readonly bucketSize: number - /** The size of the priority queue. */ - public size!: number - /** The maximum size of the priority queue. */ public maxSize!: number - /** - * The number of filled prioritized buckets. - */ - public get buckets (): number { - return this.bucketSize === Number.POSITIVE_INFINITY - ? 1 - : Math.trunc(this.nodeArray.length / this.bucketSize) - } - /** * Constructs a priority queue. * - * @param bucketSize - Prioritized bucket size. @defaultValue Number.POSITIVE_INFINITY + * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize + * @returns PriorityQueue. */ - public constructor (bucketSize = Number.POSITIVE_INFINITY) { - if ( - bucketSize !== Number.POSITIVE_INFINITY && - !Number.isSafeInteger(bucketSize) - ) { - throw new TypeError('bucketSize must be an integer') - } - if (bucketSize < 1) { - throw new RangeError('bucketSize must be greater than or equal to 1') - } + public constructor (bucketSize: number = defaultBucketSize) { this.bucketSize = bucketSize this.clear() } + /** The size of the priority queue. */ + public get size (): number { + let node: PriorityQueueNode | undefined = this.tail + let size = 0 + while (node != null) { + size += node.size + node = node.next + } + return size + } + /** * Enqueue data into the priority queue. * @@ -62,69 +59,63 @@ export class PriorityQueue { * @returns The new size of the priority queue. */ public enqueue (data: T, priority?: number): number { - priority = priority ?? 0 - const startIndex = - this.bucketSize === Number.POSITIVE_INFINITY - ? 0 - : this.buckets * this.bucketSize - let inserted = false - for (let index = startIndex; index < this.nodeArray.length; index++) { - if (this.nodeArray[index].priority > priority) { - this.nodeArray.splice(index, 0, { data, priority }) - inserted = true - break - } + if (this.head.full()) { + this.head = this.head.next = new FixedPriorityQueue(this.bucketSize) } - if (!inserted) { - this.nodeArray.push({ data, priority }) + this.head.enqueue(data, priority) + const size = this.size + if (size > this.maxSize) { + this.maxSize = size } - return this.incrementSize() + return size } /** * Dequeue data from the priority queue. * - * @param bucket - The prioritized bucket to dequeue from. @defaultValue 0 + * @param bucket - The prioritized bucket to dequeue from. * @returns The dequeued data or `undefined` if the priority queue is empty. */ - public dequeue (bucket = 0): T | undefined { - if (this.bucketSize !== Number.POSITIVE_INFINITY && bucket > 0) { - while (bucket > 0) { - const index = bucket * this.bucketSize - // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition - if (this.nodeArray[index] != null) { - --this.size - return this.nodeArray.splice(index, 1)[0].data + public dequeue (bucket?: number): T | undefined { + let tail: PriorityQueueNode | undefined = this.tail + if (bucket != null) { + let currentBucket = 0 + while (tail != null) { + ++currentBucket + if (currentBucket === bucket) { + break } - --bucket + tail = tail.next } } - this.decrementSize() - return this.nodeArray.shift()?.data - } - - /** - * Peeks at the first data. - * @returns The first data or `undefined` if the priority queue is empty. - */ - public peekFirst (): T | undefined { - return this.nodeArray[0]?.data - } - - /** - * Peeks at the last data. - * @returns The last data or `undefined` if the priority queue is empty. - */ - public peekLast (): T | undefined { - return this.nodeArray[this.nodeArray.length - 1]?.data + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + const data = tail!.dequeue() + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + if (tail!.empty() && tail!.next != null) { + if (tail === this.tail) { + this.tail = tail.next + } else { + let node: PriorityQueueNode | undefined = this.tail + while (node != null) { + if (node.next === tail) { + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + node.next = tail!.next + break + } + node = node.next + } + } + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + delete tail!.next + } + return data } /** * Clears the priority queue. */ public clear (): void { - this.nodeArray = [] - this.size = 0 + this.head = this.tail = new FixedPriorityQueue(this.bucketSize) this.maxSize = 0 } @@ -134,18 +125,23 @@ export class PriorityQueue { * @returns An iterator for the priority queue. * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols */ - [Symbol.iterator] (): Iterator { + public [Symbol.iterator] (): Iterator { let i = 0 + let node = this.tail return { next: () => { - if (i >= this.nodeArray.length) { + if (node.empty() || (i >= node.capacity && node.next == null)) { return { value: undefined, done: true } } - const value = this.nodeArray[i].data - i++ + const value = node.dequeue() as T + ++i + if (i === node.capacity && node.next != null) { + node = node.next + i = 0 + } return { value, done: false @@ -153,29 +149,4 @@ export class PriorityQueue { } } } - - /** - * Increments the size of the priority queue. - * - * @returns The new size of the priority queue. - */ - private incrementSize (): number { - ++this.size - if (this.size > this.maxSize) { - this.maxSize = this.size - } - return this.size - } - - /** - * Decrements the size of the priority queue. - * - * @returns The new size of the priority queue. - */ - private decrementSize (): number { - if (this.size > 0) { - --this.size - } - return this.size - } } diff --git a/tests/fixed-priority-queue.test.mjs b/tests/fixed-priority-queue.test.mjs index ef238aef..ddf002f0 100644 --- a/tests/fixed-priority-queue.test.mjs +++ b/tests/fixed-priority-queue.test.mjs @@ -1,185 +1,205 @@ -// import { expect } from 'expect' +import { expect } from 'expect' -// import { -// defaultQueueSize, -// FixedPriorityQueue -// } from '../lib/fixed-priority-queue.cjs' +import { + defaultQueueSize, + FixedPriorityQueue +} from '../lib/fixed-priority-queue.cjs' -// describe('Fixed priority queue test suite', () => { -// it('Verify constructor() behavior', () => { -// expect(() => new FixedPriorityQueue('')).toThrow( -// new TypeError("Invalid fixed priority queue size: '' is not an integer") -// ) -// expect(() => new FixedPriorityQueue(-1)).toThrow( -// new RangeError('Invalid fixed priority queue size: -1 < 0') -// ) -// let fixedPriorityQueue = new FixedPriorityQueue() -// expect(fixedPriorityQueue.start).toBe(0) -// expect(fixedPriorityQueue.size).toBe(0) -// expect(fixedPriorityQueue.maxSize).toBe(0) -// expect(fixedPriorityQueue.nodeArray).toBeInstanceOf(Array) -// expect(fixedPriorityQueue.nodeArray.length).toBe(defaultQueueSize) -// fixedPriorityQueue = new FixedPriorityQueue(2) -// expect(fixedPriorityQueue.start).toBe(0) -// expect(fixedPriorityQueue.size).toBe(0) -// expect(fixedPriorityQueue.maxSize).toBe(0) -// expect(fixedPriorityQueue.nodeArray).toBeInstanceOf(Array) -// expect(fixedPriorityQueue.nodeArray.length).toBe(2) -// }) +describe('Fixed priority queue test suite', () => { + it('Verify constructor() behavior', () => { + expect(() => new FixedPriorityQueue('')).toThrow( + new TypeError("Invalid fixed priority queue size: '' is not an integer") + ) + expect(() => new FixedPriorityQueue(-1)).toThrow( + new RangeError('Invalid fixed priority queue size: -1 < 0') + ) + let fixedPriorityQueue = new FixedPriorityQueue() + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(0) + expect(fixedPriorityQueue.maxSize).toBe(0) + expect(fixedPriorityQueue.nodeArray).toBeInstanceOf(Array) + expect(fixedPriorityQueue.capacity).toBe(defaultQueueSize) + fixedPriorityQueue = new FixedPriorityQueue(2) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(0) + expect(fixedPriorityQueue.maxSize).toBe(0) + expect(fixedPriorityQueue.nodeArray).toBeInstanceOf(Array) + expect(fixedPriorityQueue.capacity).toBe(2) + }) -// it('Verify enqueue() behavior', () => { -// const queueSize = 5 -// const fixedPriorityQueue = new FixedPriorityQueue(queueSize) -// let rtSize = fixedPriorityQueue.enqueue(1) -// expect(fixedPriorityQueue.start).toBe(0) -// expect(fixedPriorityQueue.size).toBe(1) -// expect(fixedPriorityQueue.maxSize).toBe(1) -// expect(rtSize).toBe(fixedPriorityQueue.size) -// expect(fixedPriorityQueue.nodeArray).toMatchObject([ -// { data: 1, priority: 0 } -// ]) -// expect(fixedPriorityQueue.nodeArray.length).toBe(queueSize) -// rtSize = fixedPriorityQueue.enqueue(2) -// expect(fixedPriorityQueue.start).toBe(0) -// expect(fixedPriorityQueue.size).toBe(2) -// expect(fixedPriorityQueue.maxSize).toBe(2) -// expect(rtSize).toBe(fixedPriorityQueue.size) -// expect(fixedPriorityQueue.nodeArray).toMatchObject([ -// { data: 1, priority: 0 }, -// { data: 2, priority: 0 } -// ]) -// expect(fixedPriorityQueue.nodeArray.length).toBe(queueSize) -// rtSize = fixedPriorityQueue.enqueue(3) -// expect(fixedPriorityQueue.start).toBe(0) -// expect(fixedPriorityQueue.size).toBe(3) -// expect(fixedPriorityQueue.maxSize).toBe(3) -// expect(rtSize).toBe(fixedPriorityQueue.size) -// expect(fixedPriorityQueue.nodeArray).toMatchObject([ -// { data: 1, priority: 0 }, -// { data: 2, priority: 0 }, -// { data: 3, priority: 0 } -// ]) -// expect(fixedPriorityQueue.nodeArray.length).toBe(queueSize) -// rtSize = fixedPriorityQueue.enqueue(3, -1) -// expect(fixedPriorityQueue.start).toBe(0) -// expect(fixedPriorityQueue.size).toBe(4) -// expect(fixedPriorityQueue.maxSize).toBe(4) -// expect(rtSize).toBe(fixedPriorityQueue.size) -// expect(fixedPriorityQueue.nodeArray).toMatchObject([ -// { data: 3, priority: -1 }, -// { data: 1, priority: 0 }, -// { data: 2, priority: 0 }, -// { data: 3, priority: 0 } -// ]) -// expect(fixedPriorityQueue.nodeArray.length).toBe(queueSize) -// rtSize = fixedPriorityQueue.enqueue(1, 1) -// expect(fixedPriorityQueue.start).toBe(0) -// expect(fixedPriorityQueue.size).toBe(5) -// expect(fixedPriorityQueue.maxSize).toBe(5) -// expect(rtSize).toBe(fixedPriorityQueue.size) -// expect(fixedPriorityQueue.nodeArray).toMatchObject([ -// { data: 3, priority: -1 }, -// { data: 1, priority: 0 }, -// { data: 2, priority: 0 }, -// { data: 3, priority: 0 }, -// { data: 1, priority: 1 } -// ]) -// expect(fixedPriorityQueue.nodeArray.length).toBe(queueSize) -// expect(() => fixedPriorityQueue.enqueue(4)).toThrow( -// new Error('Priority queue is full') -// ) -// }) + it('Verify enqueue() behavior', () => { + const queueSize = 5 + const fixedPriorityQueue = new FixedPriorityQueue(queueSize) + let rtSize = fixedPriorityQueue.enqueue(1) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(1) + expect(fixedPriorityQueue.maxSize).toBe(1) + expect(rtSize).toBe(fixedPriorityQueue.size) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 } + ]) + expect(fixedPriorityQueue.capacity).toBe(queueSize) + rtSize = fixedPriorityQueue.enqueue(2) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(2) + expect(fixedPriorityQueue.maxSize).toBe(2) + expect(rtSize).toBe(fixedPriorityQueue.size) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 } + ]) + expect(fixedPriorityQueue.capacity).toBe(queueSize) + rtSize = fixedPriorityQueue.enqueue(3) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(3) + expect(fixedPriorityQueue.maxSize).toBe(3) + expect(rtSize).toBe(fixedPriorityQueue.size) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ]) + expect(fixedPriorityQueue.capacity).toBe(queueSize) + rtSize = fixedPriorityQueue.enqueue(3, -1) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(4) + expect(fixedPriorityQueue.maxSize).toBe(4) + expect(rtSize).toBe(fixedPriorityQueue.size) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 3, priority: -1 }, + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ]) + expect(fixedPriorityQueue.capacity).toBe(queueSize) + rtSize = fixedPriorityQueue.enqueue(1, 1) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(5) + expect(fixedPriorityQueue.maxSize).toBe(5) + expect(rtSize).toBe(fixedPriorityQueue.size) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 3, priority: -1 }, + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 }, + { data: 1, priority: 1 } + ]) + expect(fixedPriorityQueue.capacity).toBe(queueSize) + expect(() => fixedPriorityQueue.enqueue(4)).toThrow( + new Error('Priority queue is full') + ) + }) -// it('Verify dequeue() behavior', () => { -// const queueSize = 5 -// const fixedPriorityQueue = new FixedPriorityQueue(queueSize) -// fixedPriorityQueue.enqueue(1) -// fixedPriorityQueue.enqueue(2, -1) -// fixedPriorityQueue.enqueue(3) -// expect(fixedPriorityQueue.start).toBe(0) -// expect(fixedPriorityQueue.size).toBe(3) -// expect(fixedPriorityQueue.maxSize).toBe(3) -// expect(fixedPriorityQueue.nodeArray.length).toBe(queueSize) -// let rtItem = fixedPriorityQueue.dequeue() -// expect(fixedPriorityQueue.start).toBe(1) -// expect(fixedPriorityQueue.size).toBe(2) -// expect(fixedPriorityQueue.maxSize).toBe(3) -// expect(rtItem).toBe(2) -// expect(fixedPriorityQueue.nodeArray).toMatchObject([ -// { data: 2, priority: -1 }, -// { data: 1, priority: 0 }, -// { data: 3, priority: 0 } -// ]) -// expect(fixedPriorityQueue.nodeArray.length).toBe(queueSize) -// rtItem = fixedPriorityQueue.dequeue() -// expect(fixedPriorityQueue.start).toBe(2) -// expect(fixedPriorityQueue.size).toBe(1) -// expect(fixedPriorityQueue.maxSize).toBe(3) -// expect(rtItem).toBe(1) -// expect(fixedPriorityQueue.nodeArray).toMatchObject([ -// { data: 2, priority: -1 }, -// { data: 1, priority: 0 }, -// { data: 3, priority: 0 } -// ]) -// expect(fixedPriorityQueue.nodeArray.length).toBe(queueSize) -// rtItem = fixedPriorityQueue.dequeue() -// expect(fixedPriorityQueue.start).toBe(3) -// expect(fixedPriorityQueue.size).toBe(0) -// expect(fixedPriorityQueue.maxSize).toBe(3) -// expect(rtItem).toBe(3) -// expect(fixedPriorityQueue.nodeArray).toMatchObject([ -// { data: 2, priority: -1 }, -// { data: 1, priority: 0 }, -// { data: 3, priority: 0 } -// ]) -// expect(fixedPriorityQueue.nodeArray.length).toBe(queueSize) -// rtItem = fixedPriorityQueue.dequeue() -// expect(fixedPriorityQueue.start).toBe(3) -// expect(fixedPriorityQueue.size).toBe(0) -// expect(fixedPriorityQueue.maxSize).toBe(3) -// expect(rtItem).toBe(undefined) -// expect(fixedPriorityQueue.nodeArray).toMatchObject([ -// { data: 2, priority: -1 }, -// { data: 1, priority: 0 }, -// { data: 3, priority: 0 } -// ]) -// expect(fixedPriorityQueue.nodeArray.length).toBe(queueSize) -// }) + it('Verify dequeue() behavior', () => { + const queueSize = 5 + const fixedPriorityQueue = new FixedPriorityQueue(queueSize) + fixedPriorityQueue.enqueue(1) + fixedPriorityQueue.enqueue(2, -1) + fixedPriorityQueue.enqueue(3) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(3) + expect(fixedPriorityQueue.maxSize).toBe(3) + expect(fixedPriorityQueue.capacity).toBe(queueSize) + let rtItem = fixedPriorityQueue.dequeue() + expect(fixedPriorityQueue.start).toBe(1) + expect(fixedPriorityQueue.size).toBe(2) + expect(fixedPriorityQueue.maxSize).toBe(3) + expect(rtItem).toBe(2) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 2, priority: -1 }, + { data: 1, priority: 0 }, + { data: 3, priority: 0 } + ]) + expect(fixedPriorityQueue.capacity).toBe(queueSize) + rtItem = fixedPriorityQueue.dequeue() + expect(fixedPriorityQueue.start).toBe(2) + expect(fixedPriorityQueue.size).toBe(1) + expect(fixedPriorityQueue.maxSize).toBe(3) + expect(rtItem).toBe(1) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 2, priority: -1 }, + { data: 1, priority: 0 }, + { data: 3, priority: 0 } + ]) + expect(fixedPriorityQueue.capacity).toBe(queueSize) + rtItem = fixedPriorityQueue.dequeue() + expect(fixedPriorityQueue.start).toBe(3) + expect(fixedPriorityQueue.size).toBe(0) + expect(fixedPriorityQueue.maxSize).toBe(3) + expect(rtItem).toBe(3) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 2, priority: -1 }, + { data: 1, priority: 0 }, + { data: 3, priority: 0 } + ]) + expect(fixedPriorityQueue.capacity).toBe(queueSize) + rtItem = fixedPriorityQueue.dequeue() + expect(fixedPriorityQueue.start).toBe(3) + expect(fixedPriorityQueue.size).toBe(0) + expect(fixedPriorityQueue.maxSize).toBe(3) + expect(rtItem).toBe(undefined) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 2, priority: -1 }, + { data: 1, priority: 0 }, + { data: 3, priority: 0 } + ]) + expect(fixedPriorityQueue.capacity).toBe(queueSize) + }) -// it('Verify iterator behavior', () => { -// const fixedPriorityQueue = new FixedPriorityQueue() -// fixedPriorityQueue.enqueue(1) -// fixedPriorityQueue.enqueue(2) -// fixedPriorityQueue.enqueue(3) -// let i = fixedPriorityQueue.start + 1 -// for (const value of fixedPriorityQueue) { -// expect(value).toBe(i) -// ++i -// } -// fixedPriorityQueue.dequeue() -// i = fixedPriorityQueue.start + 1 -// for (const value of fixedPriorityQueue) { -// expect(value).toBe(i) -// ++i -// } -// }) + it('Verify iterator behavior', () => { + const fixedPriorityQueue = new FixedPriorityQueue() + fixedPriorityQueue.enqueue(1) + fixedPriorityQueue.enqueue(2) + fixedPriorityQueue.enqueue(3) + let i = fixedPriorityQueue.start + 1 + for (const value of fixedPriorityQueue) { + expect(value).toBe(i) + ++i + } + fixedPriorityQueue.dequeue() + i = fixedPriorityQueue.start + 1 + for (const value of fixedPriorityQueue) { + expect(value).toBe(i) + ++i + } + }) -// it('Verify clear() behavior', () => { -// const fixedPriorityQueue = new FixedPriorityQueue() -// fixedPriorityQueue.start = 1 -// fixedPriorityQueue.size = 2 -// fixedPriorityQueue.maxSize = 2 -// fixedPriorityQueue.nodeArray = [ -// { data: 2, priority: 0 }, -// { data: 3, priority: 0 } -// ] -// fixedPriorityQueue.clear() -// expect(fixedPriorityQueue.start).toBe(0) -// expect(fixedPriorityQueue.size).toBe(0) -// expect(fixedPriorityQueue.maxSize).toBe(0) -// expect(fixedPriorityQueue.nodeArray).toMatchObject([ -// { data: 2, priority: 0 }, -// { data: 3, priority: 0 } -// ]) -// }) -// }) + it('Verify empty() behavior', () => { + const fixedPriorityQueue = new FixedPriorityQueue() + expect(fixedPriorityQueue.empty()).toBe(true) + fixedPriorityQueue.enqueue(1) + expect(fixedPriorityQueue.empty()).toBe(false) + fixedPriorityQueue.dequeue() + expect(fixedPriorityQueue.empty()).toBe(true) + }) + + it('Verify full() behavior', () => { + const fixedPriorityQueue = new FixedPriorityQueue(2) + expect(fixedPriorityQueue.full()).toBe(false) + fixedPriorityQueue.enqueue(1) + expect(fixedPriorityQueue.full()).toBe(false) + fixedPriorityQueue.enqueue(2) + expect(fixedPriorityQueue.full()).toBe(true) + fixedPriorityQueue.dequeue() + expect(fixedPriorityQueue.full()).toBe(false) + }) + + it('Verify clear() behavior', () => { + const fixedPriorityQueue = new FixedPriorityQueue() + fixedPriorityQueue.start = 1 + fixedPriorityQueue.size = 2 + fixedPriorityQueue.maxSize = 2 + fixedPriorityQueue.nodeArray = [ + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ] + fixedPriorityQueue.clear() + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(0) + expect(fixedPriorityQueue.maxSize).toBe(0) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ]) + }) +}) diff --git a/tests/pools/abstract-pool.test.mjs b/tests/pools/abstract-pool.test.mjs index 0c913497..62df26e3 100644 --- a/tests/pools/abstract-pool.test.mjs +++ b/tests/pools/abstract-pool.test.mjs @@ -20,7 +20,7 @@ import { WorkerTypes } from '../../lib/index.cjs' import { WorkerNode } from '../../lib/pools/worker-node.cjs' -import { PriorityQueue } from '../../lib/priority-queue.cjs' +import { defaultBucketSize, PriorityQueue } from '../../lib/priority-queue.cjs' import { DEFAULT_TASK_NAME } from '../../lib/utils.cjs' import { waitPoolEvents } from '../test-utils.cjs' @@ -789,7 +789,7 @@ describe('Abstract pool test suite', () => { expect(workerNode.tasksQueue).toBeInstanceOf(PriorityQueue) expect(workerNode.tasksQueue.size).toBe(0) expect(workerNode.tasksQueue.maxSize).toBe(0) - expect(workerNode.tasksQueue.bucketSize).toBe(numberOfWorkers * 2) + expect(workerNode.tasksQueue.bucketSize).toBe(defaultBucketSize) } await pool.destroy() pool = new DynamicThreadPool( @@ -802,7 +802,7 @@ describe('Abstract pool test suite', () => { expect(workerNode.tasksQueue).toBeInstanceOf(PriorityQueue) expect(workerNode.tasksQueue.size).toBe(0) expect(workerNode.tasksQueue.maxSize).toBe(0) - expect(workerNode.tasksQueue.bucketSize).toBe(numberOfWorkers * 2) + expect(workerNode.tasksQueue.bucketSize).toBe(defaultBucketSize) } await pool.destroy() }) diff --git a/tests/priority-queue.test.mjs b/tests/priority-queue.test.mjs index 00ecb33f..f366dc0f 100644 --- a/tests/priority-queue.test.mjs +++ b/tests/priority-queue.test.mjs @@ -1,178 +1,191 @@ import { expect } from 'expect' -import { PriorityQueue } from '../lib/priority-queue.cjs' +import { FixedPriorityQueue } from '../lib/fixed-priority-queue.cjs' +import { defaultBucketSize, PriorityQueue } from '../lib/priority-queue.cjs' describe('Priority queue test suite', () => { it('Verify constructor() behavior', () => { - expect(() => new PriorityQueue('')).toThrow( - new TypeError('bucketSize must be an integer') - ) - expect(() => new PriorityQueue(-1)).toThrow( - new RangeError('bucketSize must be greater than or equal to 1') - ) - expect(() => new PriorityQueue(0)).toThrow( - new RangeError('bucketSize must be greater than or equal to 1') - ) - let priorityQueue = new PriorityQueue() - expect(priorityQueue.bucketSize).toBe(Number.POSITIVE_INFINITY) - expect(priorityQueue.buckets).toBe(1) - expect(priorityQueue.size).toBe(0) - expect(priorityQueue.maxSize).toBe(0) - expect(priorityQueue.nodeArray).toStrictEqual([]) - priorityQueue = new PriorityQueue(2) - expect(priorityQueue.bucketSize).toBe(2) - expect(priorityQueue.buckets).toBe(0) + const priorityQueue = new PriorityQueue() expect(priorityQueue.size).toBe(0) expect(priorityQueue.maxSize).toBe(0) - expect(priorityQueue.nodeArray).toStrictEqual([]) + expect(priorityQueue.head).toBeInstanceOf(FixedPriorityQueue) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.head.capacity).toBe(defaultBucketSize) + expect(priorityQueue.tail).toBeInstanceOf(FixedPriorityQueue) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) }) - it('Verify default bucketSize enqueue() behavior', () => { + it('Verify default bucket size enqueue() behavior', () => { const priorityQueue = new PriorityQueue() let rtSize = priorityQueue.enqueue(1) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(1) expect(priorityQueue.maxSize).toBe(1) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }]) + expect(priorityQueue.head.nodeArray).toMatchObject([ + { data: 1, priority: 0 } + ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(2) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(2) expect(priorityQueue.maxSize).toBe(2) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([ + expect(priorityQueue.head.nodeArray).toMatchObject([ { data: 1, priority: 0 }, { data: 2, priority: 0 } ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(3) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(3) expect(priorityQueue.maxSize).toBe(3) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([ + expect(priorityQueue.head.nodeArray).toMatchObject([ { data: 1, priority: 0 }, { data: 2, priority: 0 }, { data: 3, priority: 0 } ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(3, -1) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(4) expect(priorityQueue.maxSize).toBe(4) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([ + expect(priorityQueue.head.nodeArray).toMatchObject([ { data: 3, priority: -1 }, { data: 1, priority: 0 }, { data: 2, priority: 0 }, { data: 3, priority: 0 } ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(1, 1) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(5) expect(priorityQueue.maxSize).toBe(5) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([ + expect(priorityQueue.head.nodeArray).toMatchObject([ { data: 3, priority: -1 }, { data: 1, priority: 0 }, { data: 2, priority: 0 }, { data: 3, priority: 0 }, { data: 1, priority: 1 } ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) }) it('Verify bucketSize=2 enqueue() behavior', () => { const priorityQueue = new PriorityQueue(2) let rtSize = priorityQueue.enqueue(1) - expect(priorityQueue.buckets).toBe(0) expect(priorityQueue.size).toBe(1) expect(priorityQueue.maxSize).toBe(1) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }]) + expect(priorityQueue.head.nodeArray).toMatchObject([ + { data: 1, priority: 0 } + ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(2) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(2) expect(priorityQueue.maxSize).toBe(2) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([ + expect(priorityQueue.head.nodeArray).toMatchObject([ { data: 1, priority: 0 }, { data: 2, priority: 0 } ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(3) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(3) expect(priorityQueue.maxSize).toBe(3) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, + expect(priorityQueue.head.nodeArray).toMatchObject([ { data: 3, priority: 0 } ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 } + ]) + expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(3, -1) - expect(priorityQueue.buckets).toBe(2) expect(priorityQueue.size).toBe(4) expect(priorityQueue.maxSize).toBe(4) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, + expect(priorityQueue.head.nodeArray).toMatchObject([ { data: 3, priority: -1 }, { data: 3, priority: 0 } ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 } + ]) + expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(1, 1) - expect(priorityQueue.buckets).toBe(2) expect(priorityQueue.size).toBe(5) expect(priorityQueue.maxSize).toBe(5) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([ + expect(priorityQueue.head.nodeArray).toMatchObject([ + { data: 1, priority: 1 } + ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail.nodeArray).toMatchObject([ { data: 1, priority: 0 }, - { data: 2, priority: 0 }, + { data: 2, priority: 0 } + ]) + expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head) + expect(priorityQueue.tail.next.nodeArray).toMatchObject([ { data: 3, priority: -1 }, - { data: 3, priority: 0 }, - { data: 1, priority: 1 } + { data: 3, priority: 0 } ]) rtSize = priorityQueue.enqueue(3, -2) - expect(priorityQueue.buckets).toBe(3) expect(priorityQueue.size).toBe(6) expect(priorityQueue.maxSize).toBe(6) expect(rtSize).toBe(priorityQueue.size) - expect(priorityQueue.nodeArray).toStrictEqual([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, - { data: 3, priority: -1 }, - { data: 3, priority: 0 }, + expect(priorityQueue.head.nodeArray).toMatchObject([ { data: 3, priority: -2 }, { data: 1, priority: 1 } ]) + expect(priorityQueue.head.next).toBe(undefined) + expect(priorityQueue.tail.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 } + ]) + expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head) + expect(priorityQueue.tail.next.nodeArray).toMatchObject([ + { data: 3, priority: -1 }, + { data: 3, priority: 0 } + ]) }) - it('Verify default bucketSize dequeue() behavior', () => { + it('Verify default bucket size dequeue() behavior', () => { const priorityQueue = new PriorityQueue() priorityQueue.enqueue(1) priorityQueue.enqueue(2, -1) priorityQueue.enqueue(3) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(3) expect(priorityQueue.maxSize).toBe(3) + expect(priorityQueue.tail.empty()).toBe(false) + expect(priorityQueue.tail.next).toBe(undefined) let rtItem = priorityQueue.dequeue() - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(2) expect(priorityQueue.maxSize).toBe(3) expect(rtItem).toBe(2) - expect(priorityQueue.nodeArray).toStrictEqual([ - { data: 1, priority: 0 }, - { data: 3, priority: 0 } - ]) + expect(priorityQueue.tail.empty()).toBe(false) + expect(priorityQueue.tail.next).toBe(undefined) rtItem = priorityQueue.dequeue() - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(1) expect(priorityQueue.maxSize).toBe(3) expect(rtItem).toBe(1) - expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: 0 }]) + expect(priorityQueue.tail.empty()).toBe(false) + expect(priorityQueue.tail.next).toBe(undefined) rtItem = priorityQueue.dequeue() - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(0) expect(priorityQueue.maxSize).toBe(3) expect(rtItem).toBe(3) - expect(priorityQueue.nodeArray).toStrictEqual([]) + expect(priorityQueue.tail.empty()).toBe(true) + expect(priorityQueue.tail.next).toBe(undefined) }) it('Verify bucketSize=2 dequeue() behavior', () => { @@ -183,87 +196,50 @@ describe('Priority queue test suite', () => { priorityQueue.enqueue(3, -1) priorityQueue.enqueue(1, 1) priorityQueue.enqueue(3, -2) - expect(priorityQueue.buckets).toBe(3) expect(priorityQueue.size).toBe(6) expect(priorityQueue.maxSize).toBe(6) + expect(priorityQueue.tail.empty()).toBe(false) + expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue) let rtItem = priorityQueue.dequeue(3) - expect(priorityQueue.buckets).toBe(2) expect(priorityQueue.size).toBe(5) expect(priorityQueue.maxSize).toBe(6) expect(rtItem).toBe(3) - expect(priorityQueue.nodeArray).toStrictEqual([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, - { data: 3, priority: -1 }, - { data: 3, priority: 0 }, - { data: 1, priority: 1 } - ]) + expect(priorityQueue.tail.empty()).toBe(false) + expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue) rtItem = priorityQueue.dequeue() - expect(priorityQueue.buckets).toBe(2) expect(priorityQueue.size).toBe(4) expect(priorityQueue.maxSize).toBe(6) expect(rtItem).toBe(1) - expect(priorityQueue.nodeArray).toStrictEqual([ - { data: 2, priority: 0 }, - { data: 3, priority: -1 }, - { data: 3, priority: 0 }, - { data: 1, priority: 1 } - ]) + expect(priorityQueue.tail.empty()).toBe(false) + expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue) rtItem = priorityQueue.dequeue(2) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(3) expect(priorityQueue.maxSize).toBe(6) expect(rtItem).toBe(3) - expect(priorityQueue.nodeArray).toStrictEqual([ - { data: 2, priority: 0 }, - { data: 3, priority: -1 }, - { data: 1, priority: 1 } - ]) + expect(priorityQueue.tail.empty()).toBe(false) + expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue) rtItem = priorityQueue.dequeue(2) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(2) expect(priorityQueue.maxSize).toBe(6) - expect(rtItem).toBe(1) - expect(priorityQueue.nodeArray).toStrictEqual([ - { data: 2, priority: 0 }, - { data: 3, priority: -1 } - ]) + expect(rtItem).toBe(3) + expect(priorityQueue.tail.empty()).toBe(false) + expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue) rtItem = priorityQueue.dequeue(2) - expect(priorityQueue.buckets).toBe(0) expect(priorityQueue.size).toBe(1) expect(priorityQueue.maxSize).toBe(6) - expect(rtItem).toBe(2) - expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: -1 }]) + expect(rtItem).toBe(1) + expect(priorityQueue.tail.empty()).toBe(false) + expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue) rtItem = priorityQueue.dequeue() - expect(priorityQueue.buckets).toBe(0) expect(priorityQueue.size).toBe(0) expect(priorityQueue.maxSize).toBe(6) - expect(rtItem).toBe(3) - expect(priorityQueue.nodeArray).toStrictEqual([]) - }) - - it('Verify peekFirst() behavior', () => { - const priorityQueue = new PriorityQueue() - priorityQueue.enqueue(1) - priorityQueue.enqueue(2) - priorityQueue.enqueue(3) - expect(priorityQueue.size).toBe(3) - expect(priorityQueue.peekFirst()).toBe(1) - expect(priorityQueue.size).toBe(3) - }) - - it('Verify peekLast() behavior', () => { - const priorityQueue = new PriorityQueue() - priorityQueue.enqueue(1) - priorityQueue.enqueue(2) - priorityQueue.enqueue(3) - expect(priorityQueue.size).toBe(3) - expect(priorityQueue.peekLast()).toBe(3) - expect(priorityQueue.size).toBe(3) + expect(rtItem).toBe(2) + expect(priorityQueue.tail.empty()).toBe(true) + expect(priorityQueue.tail.next).toBe(undefined) }) it('Verify iterator behavior', () => { - const priorityQueue = new PriorityQueue() + const priorityQueue = new PriorityQueue(2) priorityQueue.enqueue(1) priorityQueue.enqueue(2) priorityQueue.enqueue(3) @@ -275,22 +251,19 @@ describe('Priority queue test suite', () => { }) it('Verify clear() behavior', () => { - const priorityQueue = new PriorityQueue() + const priorityQueue = new PriorityQueue(2) priorityQueue.enqueue(1) priorityQueue.enqueue(2) priorityQueue.enqueue(3) - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(3) expect(priorityQueue.maxSize).toBe(3) - expect(priorityQueue.nodeArray).toStrictEqual([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, - { data: 3, priority: 0 } - ]) + expect(priorityQueue.head.empty()).toBe(false) + expect(priorityQueue.tail.empty()).toBe(false) + expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head) priorityQueue.clear() - expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(0) expect(priorityQueue.maxSize).toBe(0) - expect(priorityQueue.nodeArray).toStrictEqual([]) + expect(priorityQueue.head.empty()).toBe(true) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) }) }) -- 2.34.1