Add an mpmc concurrent queue

[RalfJung]

Proposal

Problem statement

The standard library currently provides no concurrent queue that permits multiple consumers. Given that we no have scoped threads, a multi-consumer concurrent queue is the last missing piece to be able to implement basic parallelism via "fill a queue with work to be done, then have N workers do the work".

The standard library already contains an implementation of an mpmc queue, ever since crossbeam's queue was ported over as the underlying implementation for our standard mpsc queue. However, so far this extra power is currently not exposed to users. If we're anyway spending the maintenance effort on such a queue, I think we should let our users benefit as well. :)

Motivating examples or use cases

For instance, the formatting in bootstrap is currently using a pretty complicated "poor man's async" scheme to run mutliple instances of rustfmt concurrently when formatting many files. However it anyway limits this to 2*available_parallelism many workers, so with an MPMC queue, a much simpler implementation with one thread per worker would be possible. In our pretty similar code for ./miri fmt we didn't bother with the manual async so formatting is just unnecessarily sequential.

The ui_test crate just imports crossbeam-channel for a similar situation (walking the file system and then processing things in parallel); that dependency could be entirely avoided if there was an MPMC queue in std.

Solution sketch

The intent of this ACP is to gauge whether there is interest for having an MPMC queue in the standard library at all. Figuring out the exact API could happen at a later stage.

Alternatives

We could do nothing, and ask people to depend on crossbeam when they need an mpmc queue.

Links and related work

Go's native channels are MPMC. (They also allow receiving on multiple channels at once, but that is very complicated to implement and not part of this proposal. It seems orthogonal to the single- vs multiple-consumer question: our MPSC queues don't allow a receiver to receive on multiple queues at once, and neither will our MPMC queues.)

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[BurntSushi]

I am personally in favor of this. I basically think that we should have added mpmc initially and not bothered at all with mpsc. On the other hand, I also think "don't offer a channel primitive at all" could have been defensible. But we kinda live in a tweener state right: we give you a channel, but not the most flexible one.

So I'm on board with this. While I think one libs-api member is enough to move this forward, I think this is a big enough proposal that I'd feel a lot more comfortable if we had at least one other libs-api member approve this before moving it forward.

And if anyone on libs-api is a hard no on this (which I think is reasonable), then that would be useful to know now as well!

[RalfJung]

Yeah, the point here was to "test the waters" and see whether anyone in t-libs-api is in favor (seems like yes, awesome :) and whether anyone is strictly against. I won't have time to do API design / implementation work here, but my hope is if the initial paperwork is done then it is easier for someone to pick that up and start some experiments on nightly.

[the8472]

We discussed this during today's libs-API meeting. We're ok with the general idea of exposing mpmc and the added bug surface it means, but we need a more detailed ACP because there several questions such as

• which API surfaces changes are we talking about exactly?
• is a new Receiver type that is Sync and Clone needed or can we extend the existing one? The API does say it does it can only exist in one thread, could anyone be relying on that?
• naming and deprecations, e.g. what do we do with the mpsc module

Yeah, the point here was to "test the waters" and see whether anyone in t-libs-api is in favor

So yeah, this has a chance, but please come back with a proper ACP showing how API surface will have to be remodeled.

[RalfJung]

Great, thanks! I opened https://github.com/rust-lang/rust/issues/125712 to track the next step. I won't have the time to draft a concrete API surface, hopefully someone can pick this up. :)