add mutable concurrent containers (queues, priority queues, non-contiguous vector, hashmap)

[steveklabnik]

Issue by thestinger
Wednesday Nov 20, 2013 at 19:34 GMT

For earlier discussion, see rust-lang/rust#10580

This issue was labelled with: A-libs, metabug in the Rust repository

---

I'm not sure how to handle concurrent containers in the standard library. In a 1:1 threading situation, it's best to use the native mutex and condition variable types because they're highly optimized. On Linux, they only actually need to do a system call when there's contention or consumer exhaustion because they spin a bit before waiting on futex.

The standard library has a form of M:N queues already, but they block on the scheduler so they aren't going to work well for 1:1 threading.

https://github.com/thestinger/rust-core/blob/master/core/concurrent.rs (blocking bounded/unbounded queues and priority queues with native synchronization primitives)

[Gankra]

Just a note: it's not clear that RobinHood Hashing (or any open addressing scheme) will reasonably translate to an effecient concurrent design. Having to walk along and shift elements in the table could lead to really nasty contention, or even dead-locks. Hashing with chaining might be a more reasonable design for concurrent access.

[ticki]

Relevant: https://github.com/aturon/crossbeam

[schets]

I've started working on this - I'll be pushing completed datastructures and updates to https://github.com/schets/crossbeam/tree/rust_concurrent_collections (and feature work in other branches) as well as making pull requests back to crossbeam. I'm not sure of the best way to actually integrate this into rust stdlib, so I'll keep stuff in crossbeam for for now.

The original proposal suggests using locks, but I don't really agree with that - locks may be faster in some cases, but only when there is no contention- with contention, mutexes fail hard. Also, lock-based operations have significantly worse latency properties than lock/wait free operations - imagine a hashtable read contending with a lock around a hashtable resize. It's trivial to wrap a datastructure with a mutex for the low contention case so I don't think that's needed in the stdlib.

I think a base goal would be to maintain feature/performance parity with the collections in Java concurrent collections, with a more ambitious goal of beating Java concurrent collections in throughput and latency. The crossbeam queues seem to be significantly better than the Java queues, so I think it's definitely possible.

[ticki]

I've implemented a concurrent query here: https://github.com/redox-os/redox/blob/master/libstd/src/sync/mpsc/mpsc_queue.rs

[sanxiyn]

Crossbeam people are working on concurrent hash table: crossbeam-rs/rfcs#32

[polarker]

@sanxiyn Is there any performance benchmark available against C++/Java for crossbeam?

[sanxiyn]

There is a benchmark of crossbeam-channel against Go channel. I am not aware of one for concurrent collections.

[Gankra]

I think this can pretty safely be closed as out of scope for the standard library. These kinds of collections are super specific to a usecase, and being able to build these kinds of opinionated things on crates.io is what really makes rust powerful in this area.

If we ever end up introducing concurrent queues and stuff it would presumably be part of some larger effort to build a blessed concurrency framework like apple's Grand Central Dispatch.