perf(fifo-queue): use linked list structure for queue

[roggervalf]

No description provided.

[manast]

I did try a linked list implementation, but when I ran the benchmarks it was much slower than using the old implementation. Did you notice any performance improvements?

[manast]

I think the array implementation is so efficient in V8, that even an algorithmically better implementation may not give the expected results...

[roggervalf]

I did try a linked list implementation, but when I ran the benchmarks it was much slower than using the old implementation. Did you notice any performance improvements?

I executed this test for example in a loop of 100 iterations:

describe.only('test linked list and array', function () {
    it('print time diff', async function () {
      const numJobsArr = [
        100,
        1000,
        10000,
        15000,
        25000
      ];
      const arrays = numJobsArr.map((numJobs) =>(Array.from(Array(numJobs).keys())))
      const arrayAverage = Array.apply(null, Array(numJobsArr.length)).map(() => 0);
      const listAverage = Array.apply(null, Array(numJobsArr.length)).map(() => 0);
      const loops = 100;
      for(const index of Array.from(Array(loops).keys())){
        for(let i = 0; i<numJobsArr.length; i++){
          console.log('numJobs      :', numJobsArr[i]);

          const helper = arrays[i];
          const exampleArray:string[] = []
          const now = Date.now();
          const jobs = helper.map(() => {
            exampleArray.push('result of job');
          });
          jobs.forEach(() =>{
            exampleArray.shift()
          }
          )
          
          const diff1 = Date.now()-now;
          console.log('array ms diff:', diff1);
          arrayAverage[i]+=diff1;
    
          const exampleList:LinkedList<string> = new LinkedList();
          const now2 = Date.now();
    
          const jobs2 = helper.map(() => {
            exampleList.push('result of job');
          });
          jobs2.forEach(() =>{
            exampleList.shift()?.value
          }
          )
          const diff2 = Date.now()-now2;

          console.log('list ms diff :', diff2);
          listAverage[i]+=diff2;
    
          await delay(5);
        }
      }

      console.log('----- Average ------');

        for(let i = 0; i<numJobsArr.length; i++){
          console.log('numJobs         :', numJobsArr[i]);
          console.log('array ms average:', arrayAverage[i]/loops);
          console.log('list ms average :', listAverage[i]/loops);
        }
    });
  });

these are the results I'm getting:

----- Average ------
numJobs         : 100
array ms average: 0.02
list ms average : 0
numJobs         : 1000
array ms average: 0.32
list ms average : 0.03
numJobs         : 10000
array ms average: 2.27
list ms average : 0.74
numJobs         : 15000
array ms average: 2.73
list ms average : 1.04
numJobs         : 25000
array ms average: 123.47
list ms average : 1.6

[manast]

----- Average ------
numJobs : 100
array ms average: 0.02
list ms average : 0
numJobs : 1000
array ms average: 0.32
list ms average : 0.03
numJobs : 10000
array ms average: 2.27
list ms average : 0.74
numJobs : 15000
array ms average: 2.73
list ms average : 1.04
numJobs : 25000
array ms average: 123.47
list ms average : 1.6

These results are promising. I will benchmark with actual job processing to make sure it does not regress performance in real use.

[manast]

LGTM, I would just want to benchmark with real jobs for extra verification. Give me a couple of days.

[manast]

I run the tests in https://github.com/taskforcesh/bullmq-bench but I cannot find any noticeable improvement or decrease in performance. In my M2 using old implementation 43307 jobs/sec, using new 43651 jobs/sec. But this varies between runs, sometimes one is faster and the other is slower or viceversa.

[roggervalf]

As our internak conversación, there could be other bottlenecks that affects our benchmark. Merging this pr at least for a minimal improvement as previous tests isolate only array and list implementation