Priority queue which works as a channel?

What I need is a combination of crossbeam-channel and priority-queue. Something where I put things on the queue with various priorities, then work threads take them off the queue, highest priority first. Is there a standard crate to do that? There are enough crates in both categories that it seems likely someone has done this. Suggestions?

If you have small(~100) and fixed amount of priority levels you can make a channel per level and select() them, but ignore the index and always .try_recv() channels in order.

If you have variable number of levels or just too many of them, I don't think it can be implemented efficiently with lock-free structure like crossbeam channel. You can use Arc<Mutex<BinaryHeap<T>>> as a queue though.

2 Likes

Another option would be to have a thread whose only job is to keep a small, bounded crossbeam-channel full by pulling items out of the priority queue. Items will then be processed after no more than N lower-priority items, where N is the size of the distribution queue.

3 Likes

Now that would work. Because there's quite a bit of work per queue entry (file loading, decompression, 3D mesh assembly) the overhead of that will be tiny vs. work per queue entry.

I've implemented a channel that preserves a strict order, but it could easily be repurposed to perform prioritization:

1 Like

Did that. It uses a zero-length bounded channel for output. Reading from the channel then causes the queuing thread to start. That's a nice solution.

Here it is in Playground: Rust Playground

But it won't run there, because Playground does not have priority_queue.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.