Mutex is accidentally quadratic

[nathdobson]

Locking a Mutex concurrently from N tasks takes O(N^2) time. This test reproduces the issue. The problem is the use of Slab::iter_mut in Mutex::unlock. Slab::iter_mut takes linear time because it must scan through all the vacant entries at the beginning of the Slab. I've started one possible solution which creates a separate VecDeque of wait keys so that scanning for a valid waker takes amortized constant time.

There are a number of other possible implementations (e.g. tokio's stack-allocated linked list). Before diving too deeply into a fix, do we have any clear design constraints for this implementation (e.g. avoiding unsafe code, avoiding synchronous waiting, optimizing throughput with LIFO scheduling, or optimizing latency with FIFO scheduling)?

[taiki-e]

Thanks for finding this.

do we have any clear design constraints for this implementation (e.g. avoiding unsafe code, avoiding synchronous waiting, optimizing throughput with LIFO scheduling, or optimizing latency with FIFO scheduling)?

There are no specific constraints, but reviews of large patches and patches with a lot of unsafe things tend to be delayed.

[EFanZh]

How about replacing Slab with HopSlotMap? It claims to have fast iteration speed.