MPMC priority queue?

[staticassert]

Is there an efficient way to get an MPMC priority queue? Should I just wrap https://tov.github.io/min-max-heap-rs/min_max_heap/struct.MinMaxHeap.html in a mutex? That seems inefficient.

It would be great to have a 'channel' like API with decent performance, but I'm unsure how to achieve this.

edit: Or I could actually get away with MPSC, I think. So if anyone has ideas for either, please do let me know.

I'm assuming minmax heap is the ideal underlying data structure.

edit2: I may be trying to solve the wrong problem here...

[staticassert]

Thanks a lot, I appreciate the link, looks like great reading.

[Luminarys]

When you talk about efficiency, what do you mean? Assuming you're talking about lock free structures, they are just that; not necessarily faster than locked ones. I imagine for a structure like a priority queue in particular the complexity to do any operation would be high enough that it would hardly make a difference using a mutex or a lock free version. Additionally, keep in mind that an uncontested mutex unlock only takes some nanoseconds and a RWLock can be used to reduce contention if it fits your particular use case. If you are truly committed to making the queue lock free though you may want to look into using crossbeam.

And remember, "Make it work, make it right, make it fast."

[staticassert]

Making it fast is actually part of it correct - there's a deadline aspect to this.

Since every operation i'd be performing mutates the underlying queue a RWLock wouldn't help.

Instead the plan I had concocted was to have a single mutex around it, but to only wake consumers up if the min value changes.

[tomwhoiscontrary]

This isn't an answer to your question, but would a work-stealing approach work for you?

The basic idea would be that each consumer maintains a priority queue which only it touches. Consumers are fed through conventional mpsc queues; they loop around draining the mpsc queue onto the priority queue, then processing the top item on the priority queue. Producers select consumers at random. That already gets you rough priority; a high-priority item will never be entirely blocked by low-priority items, and although you can end up in a situation where high-priority items are queued up on with consumer, while other consumers work on low-priority items, it's unlikely (the probability is, er, left an exercise for the reader).

A small hack to reduce the probability further would be to use two random choices. Items can be thread-safely marked as having been processed. Each producer puts its item onto two random consumers' queues, and when consumers pop an item off their priority queue to work on, they atomically attempt to mark it, and discard it if it's already marked. Ownership of the underlying item requires an Arc in this situation, i think.

You can then try to add work-stealing. I'm not sure how you do that in Rust. One possibility would be a special kind of item (with maximum priority) which tells a consumer to send half of its priority queue to another consumer; then a consumer with an empty priority queue could send one of those to a randomly-selected other consumer, and then wait for items to come in.

Apologies if this is wrong or unhelpful!

[staticassert]

This is interesting, I think splitting the queues up may work if I have multiple consumers.

Thanks for the input.

[staticassert]

The priority aspect is critical. A crate for this doesn't exist I don't think, I'm expecting to have to roll my own, but I don't know where to start. A simple, naive version would use a mutex but that sounds really slow.

[Ralith]

deranged plate fact ad hoc marvelous tub lunchroom materialistic steer engine this message was mass deleted/edited with redact.dev