From a70f9d7324a91058d31c1301c4351932880d57e8 Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Tue, 26 Nov 2013 09:40:24 -0800 Subject: Implement a lock-free work-stealing deque This adds an implementation of the Chase-Lev work-stealing deque to libstd under std::rt::deque. I've been unable to break the implementation of the deque itself, and it's not super highly optimized just yet (everything uses a SeqCst memory ordering). The major snag in implementing the chase-lev deque is that the buffers used to store data internally cannot get deallocated back to the OS. In the meantime, a shared buffer pool (synchronized by a normal mutex) is used to deallocate/allocate buffers from. This is done in hope of not overcommitting too much memory. It is in theory possible to eventually free the buffers, but one must be very careful in doing so. I was unable to get some good numbers from src/test/bench tests (I don't think many of them are slamming the work queue that much), but I was able to get some good numbers from one of my own tests. In a recent rewrite of select::select(), I found that my implementation was incredibly slow due to contention on the shared work queue. Upon switching to the parallel deque, I saw the contention drop to 0 and the runtime go from 1.6s to 0.9s with the most amount of time spent in libuv awakening the schedulers (plus allocations). Closes #4877 --- src/libstd/task/spawn.rs | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'src/libstd/task') diff --git a/src/libstd/task/spawn.rs b/src/libstd/task/spawn.rs index 198fe596a89..153b3e4ce25 100644 --- a/src/libstd/task/spawn.rs +++ b/src/libstd/task/spawn.rs @@ -84,7 +84,6 @@ use rt::sched::{Scheduler, Shutdown, TaskFromFriend}; use rt::task::{Task, Sched}; use rt::task::UnwindResult; use rt::thread::Thread; -use rt::work_queue::WorkQueue; use rt::{in_green_task_context, new_event_loop}; use task::SingleThreaded; use task::TaskOpts; @@ -111,11 +110,11 @@ pub fn spawn_raw(mut opts: TaskOpts, f: proc()) { // Since this is a 1:1 scheduler we create a queue not in // the stealee set. The run_anything flag is set false // which will disable stealing. - let work_queue = WorkQueue::new(); + let (worker, _stealer) = (*sched).work_queue.pool().deque(); // Create a new scheduler to hold the new task let mut new_sched = ~Scheduler::new_special(new_event_loop(), - work_queue, + worker, (*sched).work_queues.clone(), (*sched).sleeper_list.clone(), false, -- cgit 1.4.1-3-g733a5