feat: improve shift() performance by using a linked list.

[neverendingqs]

Array.prototype.shift() runs in O(n) time. By using a linked list instead, both enqueue and dequeue are O(1) operations. In practice, I started hitting long delays at about 1,000,000 Promises in the queue.

yallist appears to be the most popular linked list implementation (implementation of push() and shift() for your convenience). Please let me know if you prefer another implementation.

I ran the following on my computer (100,000 Promises in the queue):

const limit = plimit(10000000);
const start = Date.now();
await Promise.all([...Array(100000)].map(_ => limit(async () => Promise.resolve())));
console.log(Date.now() - start, 'plimit');

Without this change: ~4300 ms With this change: ~300 ms

All unit tests pass locally.

[sindresorhus]

This is a great improvement. The downside is that it adds 4.8 kB to the bundled size. Which I normally don't care about, but p-limit is often used in the browser. I tried to find a tiny queue implementation that I liked on npm, but they were either bloated or badly made, so I decided to make one. Mine is only 300b.

Could you check out https://github.com/sindresorhus/p-limit/pull/47?

[neverendingqs]

Sounds good to me!