Questions about using binary search in scheduler.ts to ensure queue order

[lyf534631748]

I have an idea, can we use sparse array to store tasks, with jobID as array index and job as array element, so that all queue insertion operations have O(1) time complexity.
Although doing so may cause the queue to be traversed many times during execution, modern js engines have optimized for for loops. On my M3 Pro + chrome 137, one million array traversals only take 2ms.

In addition, if it has been demonstrated that using binary search is better, I think binary search can take advantage of component id clustering optimization, because the component tree generation process is from parent to child, and the tree traversal update process also has this feature, then the next id inserted into the queue is likely to have a strong correlation with the previous ID inserted into the queue.

[skirtles-code]

As far as I'm aware, no-one has attempted implementing it the way you've suggested. Then again, if someone did attempt it but it didn't work then they likely wouldn't have shared it.

I believe the most recent performance tweaks to the scheduler were made in preparation for Vapor mode, which creates a lot more effects and put much more pressure on the scheduler.

While I haven't attempted the specific change you mentioned, I have attempted similar ideas elsewhere in the codebase and there are a few other considerations that often scupper these kinds of changes:

1. Using more complex data structures can lead to more memory use, or perhaps more importantly more GC activity. The latter can cause spikes in performance.
2. Build size. While the binary search looks like a lot of code, it minifies down pretty well. If an alternative adds an extra 1KB to the build (for example) then it has to be a really significant performance improvement. As far as I'm aware, the scheduler isn't currently a major bottleneck, so it may be difficult to justify changes unless the build stays roughly the same size.

A couple of other considerations:

1. Scheduler jobs can be added while the queue is running. This is an important reason why things are implemented the way they are, as it rules out a lot of simpler approaches. While I imagine your proposal can be implemented to handle that, that may add a lot of complexity to the implementation.
2. There is already a 'fast path' to handle jobs being added to the end of the queue, which skips the binary search. As you mentioned, rendering jobs are likely to be triggered in tree order, and in that case it should be able to use the fast path.

I think it's also worth keeping in mind that the queue size can never be particularly big. Each job represents some kind of reactive effect and those take time to run. If the queue grows to some crazy length then just running the effects will take an impractical length of time, the inefficiency of the scheduler likely won't be a major contributor. O(logn) is likely fast enough for the sizes of n we can actually encounter.

But don't let me discourage you from trying to implement your idea. Sometimes these kinds of ideas work out, sometimes they don't. If nothing else you'll likely learn a lot just attempting it.