Default TaskQueue implementation is slow for a large number of queued tasks

[robhogan]

I'm writing this not as an ask from the maintainers but as a note for users and an opportunity for contributors.

While benchmarking piscina against jest-worker for a (very) large number of small tasks, I saw jest-worker was several times faster out of the box, using worker threads. After digging in a bit, it turns out that for a large enough number of tasks, ArrayTaskQueue.prototype.shift(), within the default FIFO queue , whose implementation is just an O(n) Array shift, dominates on the host thread. For me this became apparent at around 100,000 queued tasks.

A lightweight linked list implementation would speed this up algorithmically without much extra complexity in implementation - indeed using a custom taskQueue I was able to get parity with jest-worker for queues around 500k.

PR to follow (hopefully!), but I wanted to note this anyway for the benefit of anyone seeing (maybe without realising) this issue.

[metcoder95]

Hey @robhogan, thanks for your notes; they are in fact very useful.
Overall, it is somehow expected that a common FIFO algorithm for balancing tasks will face some limitations with big tasks numbers, the goal is not make it a one-size-fits-all solution. That's why CustomTaskQueue exists.

We have #347 to enhance and have some out-of-the-box algorithms that can fulfills other needs, aside of the CustomTaskQueue one.

I'm seeing this one as somehow duplicated of #347, I'll link your comment there for reference.

[ronag]

Use nodes fixed_queue implementation?

[metcoder95]

As default Task Queue?

[JaoodxD]

@ronag @metcoder95 I would like to enhance piscina with node's fixed_queue.
Should I firstly create separate issue or straightly go to work and then make a PR?

[metcoder95]

Let's continue on the PR 👍