auto merge of #10678 : alexcrichton/rust/issue-4877, r=pcwalton

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

1 files changed, 0 insertions, 75 deletions

diff --git a/src/libstd/rt/work_queue.rs b/src/libstd/rt/work_queue.rs
deleted file mode 100644
index 02ea8ab4f50..00000000000
--- a/src/libstd/rt/work_queue.rs
+++ /dev/null
@@ -1,75 +0,0 @@
-// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-use container::Container;
-use option::*;
-use vec::OwnedVector;
-use unstable::sync::Exclusive;
-use cell::Cell;
-use kinds::Send;
-use clone::Clone;
-
-pub struct WorkQueue<T> {
-    // XXX: Another mystery bug fixed by boxing this lock
-    priv queue: ~Exclusive<~[T]>
-}
-
-impl<T: Send> WorkQueue<T> {
-    pub fn new() -> WorkQueue<T> {
-        WorkQueue {
-            queue: ~Exclusive::new(~[])
-        }
-    }
-
-    pub fn push(&mut self, value: T) {
-        unsafe {
-            let value = Cell::new(value);
-            self.queue.with(|q| q.unshift(value.take()) );
-        }
-    }
-
-    pub fn pop(&mut self) -> Option<T> {
-        unsafe {
-            self.queue.with(|q| {
-                if !q.is_empty() {
-                    Some(q.shift())
-                } else {
-                    None
-                }
-            })
-        }
-    }
-
-    pub fn steal(&mut self) -> Option<T> {
-        unsafe {
-            self.queue.with(|q| {
-                if !q.is_empty() {
-                    Some(q.pop())
-                } else {
-                    None
-                }
-            })
-        }
-    }
-
-    pub fn is_empty(&self) -> bool {
-        unsafe {
-            self.queue.with_imm(|q| q.is_empty() )
-        }
-    }
-}
-
-impl<T> Clone for WorkQueue<T> {
-    fn clone(&self) -> WorkQueue<T> {
-        WorkQueue {
-            queue: self.queue.clone()
-        }
-    }
-}