I have a program that collects some tasks to execute, and each task has a priority. Higher-priority tasks should be executed first. More tasks may be discovered during program's execution, and they should jump the queue if needed.
In a single thread it's easy to do with a BinaryHeap
:
while let Some(task) = heap.pop() {
task();
heap.push(more_tasks());
}
However, how can I parallelize it without losing too much of the ordering?
Existing threadpools assume you push all tasks into their queue:
while let Some(task) = heap.pop() {
rayon::spawn(task); // or channel.send(task) or such
heap.push(more_tasks());
}
but then I'll immediately drain my heap into another queue, which won't give new tasks a chance to be sorted before the tasks that have already been sent to a threadpool.
Is there some library or design pattern that will "pull" tasks out of my binary heap lazily only immediately before spawning a new task?