Support coroutine priorities

[dovchinnikov]

Use case

There are different activities in IJ:

• those which are run on their own: startup activities, heavy sync which are triggered by external file change, timeout activities, e.g. toolbar update every 500ms;
• those which are run as an indirect response to user action: re-highlighting after user typed something in the editor, tasks with background progress bar which are initiated by a user-invoked action;
• those which are run as a direct response to user action: pressing a shortcut triggers computation of applicable actions, we'd like to parallelise that on Dispatchers.Default while blocking the Event Dispatch Thread (UI thread), or actions which trigger modal progress bar.

We can tolerate 1st and 2nd categories to co-exist together in Dispatchers.Default, but for the last category of actions the latency should be minimized (as opposed to maximising throughput), they should run be ASAP regardless of whatever is queued by Dispatchers.Default for execution.

The Shape of the API

Option 0. Support coroutine priorities in the library.

Option 1. Support fixed set of coroutine priorities (1, 0, -1) in the library (this allows to maintain several queues instead of a proper priority queue). This should be pretty simple to implement. Defaulting to NORMAL will also would allow to implement a dispatcher view with proper priority queue on the client side to support custom priorities if needed.

Option 2. Provide an ability to supplement own kotlinx.coroutines.scheduling.CoroutineScheduler implementation via SPI. Multiple implementation should trigger an error like in Dispatchers.Main.

[fvasco]

Are you considered to use your own dispatcher with a proper thread pool? Threads already own priority support.

Moreover, suspending function can switch the dispatcher at any time, so priorities should be applied to other dispatchers, too.

Finally, should Semaphore and Mutex support priority?

[dovchinnikov]

Are you considered to use your own dispatcher with a proper thread pool?

We considered own dispatcher with proper priority queue, but we cannot forbid everybody else to use Dispatchers.Default, which will provide an escape from the priority model.

Threads already own priority support.

Thread-based priority support contradicts coroutine approach, it can be unreliable on different platforms, it will lead to existence of a separate physical high priority pool, which will be underutilised most of the time, and which will force excessive thread-switching from normal-priority pool.

suspending function can switch the dispatcher at any time, so priorities should be applied to other dispatchers

In IJ we don't recommend using custom physical thread pools and dispatchers on top of them as per single-pool-per-app approach. Also, switching to another dispatcher is explicit, so another dispatchers may or may not support priorities as they wish, and we don't really care about that. We care only about tasks which are already submitted to Dispatchers.Default by other clients at the moment when the platform needs full Dispatchers.Default speed to handle the user input.

should Semaphore and Mutex support priority?

This is a really good question. I don't expect Semaphore/Mutex to support priorities, at least not on the first iteration.

[fvasco]

If I understood well, you want the ability to define high-priority tasks, that might be executed in the next loop of the Dispatcher, and low-priority tasks, that are subject to idle for an undefined amount of time. Your rationale assumes that higher-priority tasks are not enough to utilize the Default dispatcher all the time, so other tasks should be executed in a reasonable future. At the same time, you are assuming that higher-priority tasks are not waiting for a Mutex or Semaphore locked by a lower-priority task, to avoid any kind of deadlock due to priority.

---

but we cannot forbid everybody else to use Dispatchers.Default, which will provide an escape from the priority model.

This proposal does not forbid everybody to submit tasks without a proper priority, so the issue remains.

Thread-based priority support contradicts coroutine approach, it can be unreliable on different platforms

Can you provide a reference? Thread-based priority can perform differently on different platforms, but it looks more reliable and battle-tested than any coroutine-based proposal, IMHO.

and which will force excessive thread-switching from normal-priority pool

You wrote "we'd like to parallelise that on Dispatchers.Default while blocking the Event Dispatch Thread (UI thread)", this already implies a context switch, how does this proposal avoid this?

We care only about tasks which are already submitted to Dispatchers.Default by other clients at the moment when the platform needs full Dispatchers.Default speed to handle the user input.

This proposal does not guarantee that you can use the full speed of the Default dispatcher, another client may have a good, different reason to execute a task quickly (video render or heartbeat response, for example).

---

The Default dispatcher is the default one and exposes a default behavior, changing this makes it harder to use (everyone should always use the right priority) and can harm the overall performance (handling priority requires code).

[francescotescari]

If I understood well, you want the ability to define high-priority tasks, that might be executed in the next loop of the Dispatcher, and low-priority tasks, that are subject to idle for an undefined amount of time. Your rationale assumes that higher-priority tasks are not enough to utilize the Default dispatcher all the time, so other tasks should be executed in a reasonable future. At the same time, you are assuming that higher-priority tasks are not waiting for a Mutex or Semaphore locked by a lower-priority task, to avoid any kind of deadlock due to priority.

Many of the arguments for/against priorities are not much different from the threading world IMHO (except that coroutines don't have preemption). With your rationale, even high-priorities threads could use all the CPUs all the time, (if the thread scheduler was written poorly I'd say), and low-priority threads would be subject to idle for an undefined amount of time. But that's not how it is in reality, schedulers are smart enough to prevent these extreme starvation issues and make the threads cooperate decently. Also, it's not like anyone using Dispatchers.Default can expect low or predictable latency today: since it's shared by everyone, you don't know if your lanched task will take 0, 200, or even 1000ms to actually be executed. From this point of view I don't see a huge problem adding priorities: tasks with high-priority will have the same amount of latency or less (most of the times), tasks with low or default priority (or no priority) are not interested in latency and thus will have a slightly higher latency on average. This, at high-level, is no different from threads. Again, assuming that the scheduler is smart and is not delaying low-priority tasks from the 10-200ms to 1-10s or even forever... There must be some calibration I guess 🤔

makes it harder to use (everyone should always use the right priority)

This is also not much different from threads. Threads support priorities but it's not like everyone using threads must fine-tune the priority of each thread. Also, the inherited coroutine context and potentially inherited coroutine priority would require people to specify priority only when creating root CoroutineScope or when an explicit change is necessary (and again, there could be a default value).

Swift tasks do support priorities AFAIS (even adapting ones, where priorities of awaited tasks are increased to match the ones of awaiter tasks), so it's not impossible.

[fvasco]

This proposal's primary enhancement is for platforms that miss multithread support, like JS or WASM.

[bubenheimer]

Related to #3178, which links further issues.

[kevincianfarini]

Moreover, suspending function can switch the dispatcher at any time, so priorities should be applied to other dispatchers, too.

We might be able to support dispatcher portability with a new CoroutineContext element. Dispatchers have access to this context element for the coroutine already, so portability between dispatchers should be a matter of looking for the appropriate context element within a Dispatcher's implementation.

An API like the following could be nice:

data class CoroutinePriority(val level: Int) : AbstractCoroutineContextElement(CoroutinePriority) {

    /**
     * Key for [CoroutinePriority] instance in the coroutine context.
     */
    public companion object Key : CoroutineContext.Key<CoroutinePriority>
}

fun main() = runBlocking {
  launch { 
    println("This is low priority")
  }
  launch(context = CoroutinePriority(level = Int.MAX_VALUE) {
    println("This is high priorty")
    launch { 
      println("This is also high priority")
    }
  }
}