DEV Community: Jin.Park

Introducing elegant-queue: An Efficient Queue Implementation in JavaScript/TypeScript

Jin.Park — Thu, 22 Aug 2024 07:12:30 +0000

elegant-queue

Overview

In JavaScript and TypeScript, arrays are often used to implement queues. The built-in shift() method removes the element at the zeroth index and shifts the remaining elements down, which has O(n) time complexity due to the re-indexing required.

Why Circular Buffers?

To optimize queue operations, especially with large datasets, a circular buffer is a highly effective solution. It allows both enqueue and dequeue operations to be performed in O(1) time complexity by managing elements in a fixed-size array with wrapping pointers.

Key Benefits:

Memory Efficiency: A circular buffer uses a fixed-size array and wraps around, eliminating the need for continuous resizing and minimizing memory overhead.
Consistent O(1) Performance: Operations remain constant time, avoiding the performance pitfalls of array resizing and shifting.
Avoids Memory Fragmentation: Efficient memory use and reduced risk of fragmentation, even with dynamic queue sizes.

📚 Getting Started

elegant-queue supports both CommonJS and ES Modules.

CommonJS

const { Queue } = require("elegant-queue");

ES Modules

import { Queue } from "elegant-queue";

🔎 Explore features

`constructor(array: T[])`

The constructor initializes a new queue with the elements from the provided array.

`enqueue(value: T)`

This method adds a new element to the end of the queue.

`dequeue()`

This method removes and returns the element at the front of the queue. If the queue is empty, it throws a EmptyQueueException.

`peek()`

This method returns the element at the front of the queue without removing it. If the queue is empty, it throws a EmptyQueueException.

`clear()`

This method clears all elements from the queue.(effectively resetting the queue to its initial state.)

`size()`

This method returns the number of elements currently in the queue.

`isEmpty()`

This method checks if the queue is empty. It returns true if _head is equal to _tail (indicating no elements are present), and false otherwise.

🌈 Examples

Usage Example

import { Queue } from "elegant-queue";

const queue = new Queue([1, 2, 3, 4, 5]);
queue.enqueue(6); // [1, 2, 3, 4, 5, 6]

const item = queue.dequeue();
console.log(item); // 1 

console.log(queue); // [2, 3, 4, 5, 6]

Exception Handling Example

import { Queue, EmptyQueueException } from "elegant-queue";

try {
    const item = queue.dequeue(); // Attempt to remove the item from the queue.
    console.log('Dequeued item:', item);
} catch (error) {
    if (error instanceof EmptyQueueException) {
        console.error('Queue is empty. Cannot dequeue an item.');
    } else {
        console.error('An unexpected error occurred:', error);
    }
}

⚡️ Performance (1 million numbers)

The following benchmarks compare elegant-queue with a standard array-based queue.

Array Queue performance:

console.time('ArrayQueue Enqueue Time');
const numbers: Array<number> = [];

for (let i = 0; i < LARGE_DATA_SIZE; i++) {
  arrayQueue.push(i);
}
console.timeEnd('ArrayQueue Enqueue Time');

console.time('ArrayQueue Dequeue Time');
while (arrayQueue.length > 0) {
  arrayQueue.shift();
}
console.timeEnd('ArrayQueue Dequeue Time');

Array Queue performance result:

  console.time
    ArrayQueue Dequeue Time: 109907 ms

Elegant Queue performance:

console.time('ElegantQueue Enqueue Time');
const numbers = new Array<number>();

for (let i = 0; i < LARGE_DATA_SIZE; i++) {
    numbers.push(i);
}

const elegantQueue = new Queue(numbers);
console.timeEnd('ElegantQueue Enqueue Time');

console.time('ElegantQueue Dequeue Time');
while (elegantQueue.size() > 0) {
  elegantQueue.dequeue();
}
console.timeEnd('ElegantQueue Dequeue Time');

Elegant Queue performance result:

  console.time
    ElegantQueue Dequeue Time: 5 ms

Note: The shift() method in arrays has O(n) time complexity due to the need to re-index elements after removal. In contrast, elegant-queue provides O(1) time complexity for both enqueue and dequeue operations by utilizing a circular buffer design, making it significantly faster for large datasets.

Efficient batch processing for event-driven chunking

Jin.Park — Sun, 03 Mar 2024 09:28:06 +0000

🏛️ Arehs

The arehs ensures the best possible large batch processing, which is oriented towards event-driven chunk
processing.

It does this by immediately allocating the next asynchronous task call for dense packing, rather than waiting for the
first asynchronous task call to complete.

Also, if your database has a pool of 50 connections and you need to run 1,000 queries, you might need to create a Promise array of 50 or fewer chunks and do Promise.all on those chunks, which is typical.
However, Promise.all might not be enough, so you might want to consider Arehs, which is a good option for chunk processing.

In that way we can achieve multiple things:

Control the throughput of our service by setting the concurrency of the Promise Pool.
Manage load on the downstream services by setting the concurrency of the Promise Pool.
Increase the performance of our application
Reduced CPU idle time, etc.

📚 Getting Started

arehs supports both CommonJS and ES Modules.

CommonJS

const { Arehs } = require("arehs");

ES Modules

import { Arehs } from "arehs";

Example

create: The purpose of the create method is to create an Arehs instance from a specific array of data.
withConcurrency: Methods that set the value for parallelism and return the current instance.(default: 10)
timeoutLimit: The default value is 0. If it's greater than 0, the option works, and an error is thrown if the operation takes longer than the timeout time(ms).
stopOnFailure: If the stopOnFailure option is set to true, the function stops processing and emits appropriate events.
retryLimit: Set a limit on the number of retries on failure.
mapAsync: Calling the mapAsync function starts the process of asynchronously processing the input data and returning the results. If the stopOnFailure option is set to true, the function stops processing and emits appropriate events. This can be useful for handling transient errors or ensuring data processing resilience. Also, if the retryLimit option is greater than 0, you can set a limit on the number of retries on failure.

import { Arehs } from "arehs";

const dataArr = [
  { id: 1, name: "John" },
  { id: 2, name: "Alice" },
  { id: 3, name: "Bob" }
];

const result = await Arehs.create(dataArr)
  .withConcurrency(10)
  .mapAsync(async data => {
    return await someAsyncFunction(data);
  });

⚡️ Performance

Tests have shown that Arehs can be improved by about 30% over Promise.all.

import { Arehs } from "arehs";

const delay = (i) => {
  return new Promise((res, rej) => {
    setTimeout(() => {
      res(i);
    }, 150 + Math.random() * 1000);
  });
};

(async () => {
  const tasks = Array.from({ length: 1000 }).map((d, i) => i);

  const startArehs = performance.now();
  await Arehs.create(tasks).withConcurrency(50).mapAsync(delay);
  const endArehs = performance.now();

  console.log(`Arehs: ${endArehs - startArehs}ms`);

  const startPromiseAll = performance.now();
  while (tasks.length > 0) {
    const chunkedTasks = tasks.splice(0, 50);
    await Promise.all(chunkedTasks.map(delay));
  }
  const endPromiseAll = performance.now();

  console.log(`Promise.all: ${endPromiseAll - startPromiseAll}ms`);
})();

    promiseAllTime: 19.859867874979972(s)
    promisePoolTime: 13.55725229203701(s)

Promise.all

As you can see, Promise.all runs as long as the slowest promise in the batch.

So your main thread is basically “doing nothing” and is waiting for the slowest request to finish.

The longest promise in the Promise array, number 4, will be the chunk's execution time.

This creates an inefficient problem where the next promises don't do any work until the longest promise is finished.

Arehs

Arehs is all about making the most of Node.js's main thread by running the Promise Pool Pattern.

To achieve better utilization we need densely pack the API calls (or any other async task) so that we do not wait while
the most extended call completes, rather we schedule the next call as soon as the first one finishes.

🙋‍♀️FAQ

Is this always better than Promise.all?

No, there is No silver bullet.

This can increase your application's performance when you're making a lot of API calls and asynchronous operations.

Also, it may not make much difference in situations where each promise has roughly the same work time.

If you can't get any further performance improvement with Promise.all in your environment,

you can give it a try, but if you can get by with Promise.all, you don't have to.

Therefore, you should try to use Arehs in your projects that need performance improvements only after thoroughly
testing it.

It will help you. Thank you.