You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
I've had https://github.com/Thiez/rust/blob/ll-message-queue/src/libstd/rt/message_queue.rs lying around for a while now. It is a Michael-Scott lockless queue as described here http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf . However, since Rust does not (at this time) have an intrinsic for double-word compare-and-swap, my version is considerably more vulnerable to the ABA-problem and thus I am hesitant to declare this queue complete.
Adding a DWCAS intrinsic is not a good option as it is not supported on all the architectures we target. I think the best option would be to have a ABA-safe atomic pointer type defined in the library (it would help with the implementation of other datastructures as well). I suspect such a thing could be implemented for each target architecture with some #[cfg(target_arch = <sometarget>)] annotations; using LLVM would be tricky as it has no IR instruction that captures the semantics of of LL/SC (on architectures such as ARM).
I have no MIPS or multicore ARM devices lying around so I would not be able to test such a pointer.
To summarize, the basic algorithm is implemented and appears to work (without leaking memory, or so valgrind tells me) but it's going to fail randomly (but rarely) when at least two threads are writing and one thread is reading.
Currently there's manual malloc/free in the code but now that ~ has lost the headers the malloc could be replaced by a normal ~ followed by a transmute (and transmute back to ~ to delete).
The biggest place where we need to reduce lock contention is the global sleeper list #6838. Its lock is just getting hammered constantly. There are lots of ways we might fix this but an obvious one to replace it with a lock-free queue.
Activity
brson commentedon Jun 5, 2013
@Thiez is working on this
msullivan commentedon Jul 26, 2013
How's this going?
Thiez commentedon Jul 28, 2013
I've had https://github.com/Thiez/rust/blob/ll-message-queue/src/libstd/rt/message_queue.rs lying around for a while now. It is a Michael-Scott lockless queue as described here http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf . However, since Rust does not (at this time) have an intrinsic for double-word compare-and-swap, my version is considerably more vulnerable to the ABA-problem and thus I am hesitant to declare this queue complete.
Adding a DWCAS intrinsic is not a good option as it is not supported on all the architectures we target. I think the best option would be to have a ABA-safe atomic pointer type defined in the library (it would help with the implementation of other datastructures as well). I suspect such a thing could be implemented for each target architecture with some
#[cfg(target_arch = <sometarget>)]annotations; using LLVM would be tricky as it has no IR instruction that captures the semantics of of LL/SC (on architectures such as ARM).I have no MIPS or multicore ARM devices lying around so I would not be able to test such a pointer.
To summarize, the basic algorithm is implemented and appears to work (without leaking memory, or so valgrind tells me) but it's going to fail randomly (but rarely) when at least two threads are writing and one thread is reading.
Currently there's manual malloc/free in the code but now that ~ has lost the headers the malloc could be replaced by a normal ~ followed by a transmute (and transmute back to ~ to delete).
Suggestions are welcome.
plokhotnyuk commentedon Aug 7, 2013
I used lock-free MPSC queue that was described by Dmitriy Vyukov (http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue) to implement one of fastest and lightweight actor for JVM: https://github.com/plokhotnyuk/actors/blob/master/src/test/scala/com/github/plokhotnyuk/actors/Actor2.scala
brson commentedon Aug 17, 2013
The biggest place where we need to reduce lock contention is the global sleeper list #6838. Its lock is just getting hammered constantly. There are lots of ways we might fix this but an obvious one to replace it with a lock-free queue.
Thiez commentedon Sep 2, 2013
@plokhotnyuk thanks for that link, implementing it in rust was incredibly easy https://github.com/Thiez/rust/blob/better-message-queue/src/libstd/rt/message_queue.rs
@brson did you have a good benchmark for message-passing lying around?
alexcrichton commentedon Oct 29, 2013
Closed by #9710
Auto merge of rust-lang#6865 - Jarcho:explicit_deref_methods, r=llogiq
Auto merge of rust-lang#7930 - lengyijun:needless_deref_new, r=Jarcho