Priority Queue Option

[sebmarkbage]

We find ourselves often having multiple pieces of work at different priority levels. E.g. React implements a priority queue and a central requestIdleCallback. Then it picks the highest priority to work on at any given point.

The problem is that different frameworks don't share the same priority queue. So low priority work in one system can get prioritized over high priority work in another framework.

That sounds like a perfect reason for why a standardized priority queue is needed.

I propose adding another option to IdleRequestOptions called priority. This would hold a number. The user agent would then call the callbacks of the highest priority before the lowest priority, unless a timeout elapsed, in which case they take priority just like today.

[RReverser]

Can't think of a good alternative, but wouldn't numbers for priority API lead us into z-index:9999 situation where developers will prioritize things with abitrary high numbers and there would be still no guarantee which one is highest in the codebase?

[mbrevda]

wouldn't numbers for priority API lead us into z-index:9999 situation where developers will prioritize things with abitrary high numbers

Currently a colocated framework/library can tie up the thread by simply not using requestIdleCallback, causing all their code to run even before requestIdleCallback. It doesn't seem this proposal is worse than the current situation.

[motiz88]

To @RReverser's point, it is probably far less trivial to standardise a semantic taxonomy of work priorities (e.g. "animation" | "user" | "network" | ...) than to provide a simple numeric API, but maybe it's worth a shot? For extensibility & long-term interoperability in the face of priority: 9999 etc.

That, or at least a bounded scale of integers e.g. one to ten, or however many discrete steps are deemed necessary for current needs. That would at least have an interoperability story (with eventual consensus brought on by the limited range), but less of an extensibility story. (Unless, perhaps, the API is complicated further, e.g. with a scheduler option that explicitly opts into a version/specific queue?)

[rmcilroy]

One of the other advantages of a standardised taxonomy of work priorities is that the user-agent can explicitly remap the relative priorities of different work types depending on the phase of execution (loading / animating / idle etc.). We do exactly this in Chrome's internal scheduler for exactly this reason.

@skyostil who might also have thoughts on this.

[sebmarkbage]

Yea I agree standardizing this is tough but we might also see some different conventions fall out of it.

In React we actually just use the absolute timeout time as the priority (the lower time, the higher priority). That way things that risk timing out soon automatically gets higher priority.

[skyostil]

I agree that a semantic labeling of tasks has historically worked better for us in Chrome vs. letting everyone set their own priorities. However defining meaningful semantics might be difficult -- maybe we could look at task sources for inspiration. Note that we already have some of that -- e.g., to schedule an animation task you call requestAnimationFrame().

The higher level question I'm wondering is whether requestIdleCallback is the right API for this or should we come up with something more general.

[sebmarkbage]

Thinking about this some more, I think that semantic labeling would not be sufficient for us to get rid of our own implementation. We sometimes have up to 63 different levels and prefer to do the work in that order. Every relative priority between them probably doesn't matter that much but it is much more granular than a few simple priority levels.

For example, we would use this to determine which part of the Facebook home page to compute first, second etc. during load. If we only have a couple of levels, we would still have to keep our own priority queue on top. Which would be unfortunate but might be fine. Maybe the role of the standard one is more about coarse grained priorities.

[farre]

I think adding priorities at the requestIdleCallback level is a bad idea precisely because of the max priority issue. If callers of requestIdleCallback are allowed to set an arbitrarily high priority, one part of the code base could starve another, effectively degenerating requestIdleCallback to setTimeout for the lower priority ones. This is worse than the situation today, since the intent of requestIdleCallback is there to help scripts co-operate with the UA to run callbacks when they wouldn't cause jank. Arbitrary priorities would instead encourage competition, albeit amongst callbacks at first, but in the end with the UA by increasing the amount of callbacks timing out.

This could of course be solved by making the default priority be the max priority, and only allow lowering the priority. This would make setting a priority a co-operative action, instead of a competitive, but I'm not sure if that's enough. It could still mean that more callbacks time out.

[sebmarkbage]

If the priority increases over time you don't risk timing out as much because eventually newer priorities will have less priority than the previous ones. E.g. if the priority is set to "current time + some offset".

[RReverser]

I wonder if combining two approaches and allowing only named, but user-defined, states, could take the best of both worlds or it's going to be too verbose? Something like:

App-level or framework-level queue:

const queue = new PriorityQueue([
  // can define as many states as needed in increasing priority order
  'low',
  'medium',
  'high'
]);

Somewhere in code:

let task = queue.schedule('medium', () => { ... }); // adds to the "medium" queue
let other = queue.schedule('high', () => { ... }); // adds to the high-priority queue
let yetAnother = queue.schedule('xxx', () => { ... }); // Error: unknown priority "xxx"

At least this would solve

1. Issue with non-descriptive numbers.
2. Discoverability issue - all the possible priorities are defined in one place so you don't need to wonder if 1000 is highest priority within the app or there is 9999 somewhere else.
3. Would allow not to define categories for browser-level tasks yet while still providing a primitive that could be used for them in future.

[clelland]

@shaseley -- this may introduce significant complexity, but can you weigh in as editor on whether it's worth adding something like this? (Or is this something that the WG should discuss?)

[shaseley]

Short answer: yes I think it's worth adding, but probably not as part of requestIdleCallback.

I believe this issue helped motivate exploring the broader scheduling space, which we've been doing in Prioritized Task Scheduling (with OP's help). IMO that's probably a better place to be exploring this, given the broader scope (outside of just idle priority).

As others have mentioned, there are two separate notions of priority:

1. Event loop priority: what the browser uses to schedule tasks in a turn of the event loop
2. App-specific priority: How a page or framework's tasks are prioritized locally

"idle" priority, as supported by requestIdleCallback(), is included in (1). scheduler.postTask() expands this and includes 3 semantic priorities (which can be expanded, although we want to keep this small).

I think (2) is useful independent of (1): from what we've seen from userland schedulers, prioritizing app-specific tasks within the same event loop priority is still useful/desirable. But I think this also applies to task scheduling in general[^1], not just requestIdleCallback. There are certainly challenges here, e.g. different parts of the page have different notions of priority, but overall I think it would be worth adding if event loop priorities aren't sufficient. While exploring postTask, I wrote about what one option might look like.

[^1]: I can see an argument for eventually merging these efforts, depending on WG support.