Concurrency/queue with specific, dynamic execution order

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() {

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

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?

Is it possible to solve this with an extra level of indirection?

Right now, each task = actual work to be done.

Extra indirection:
each task = closure with Arc to multi threaded heap
when 'task' is executed, it pops 'real task' from the multi threaded heap and executes it

Thus, each thread is pushed a bunch of 'lazy tasks', that when executed, pops the 'real task' off the multi threaded heap.


This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.