Skip to content

Add fastpriorityqueue and replace O(n) array insertion in WorkerPool with a heap-based priority queue #13

@tapava

Description

@tapava

Background

  • The WorkerPool currently performs priority scheduling by inserting tasks into an array at the correct index. See current implementation:
  private enqueue<T>(task: QueuedTask<T>): void {
    // Insert based on priority (higher priority first)
    let inserted = false;
    for (let i = 0; i < this.taskQueue.length; i++) {
      if (task.priority > this.taskQueue[i].priority) {
        this.taskQueue.splice(i, 0, task as QueuedTask);
        inserted = true;
        break;
      }
    }
    if (!inserted) {
      this.taskQueue.push(task as QueuedTask);
    }
  }
  • This keeps higher-priority tasks earlier in the queue, but insertion uses Array.splice which is O(n) (in worst cases) per enqueue. For small queues this is fine, but with large queues or high enqueue rates it becomes a performance concern.

Problem: Current enqueue is O(n) and can be slow / cause GC churn under high task volumes.

Solution: Add FastPriorityQueue (or heapify) dependency and use a heap-backed priority queue for scheduling, with a comparator that orders by numeric priority and preserves FIFO for ties. Handle cancellation by skipping removed tasks when polling.

Purpose: Improve enqueue performance, reduce latency spikes, and provide a deterministic, reusable scheduling primitive.

Acceptance:

  • FastPriorityQueue (or heapify) added and used for task scheduling
  • Priority semantics preserved (higher numeric = higher priority; FIFO ties)
  • Cancellation handled safely
  • Tests added for ordering and cancellation

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or requesthelp wantedExtra attention is needed

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions