Merge remote-tracking branch 'rust-lang/master'

Conflicts:
	mk/tests.mk
	src/liballoc/arc.rs
	src/liballoc/boxed.rs
	src/liballoc/rc.rs
	src/libcollections/bit.rs
	src/libcollections/btree/map.rs
	src/libcollections/btree/set.rs
	src/libcollections/dlist.rs
	src/libcollections/ring_buf.rs
	src/libcollections/slice.rs
	src/libcollections/str.rs
	src/libcollections/string.rs
	src/libcollections/vec.rs
	src/libcollections/vec_map.rs
	src/libcore/any.rs
	src/libcore/array.rs
	src/libcore/borrow.rs
	src/libcore/error.rs
	src/libcore/fmt/mod.rs
	src/libcore/iter.rs
	src/libcore/marker.rs
	src/libcore/ops.rs
	src/libcore/result.rs
	src/libcore/slice.rs
	src/libcore/str/mod.rs
	src/libregex/lib.rs
	src/libregex/re.rs
	src/librustc/lint/builtin.rs
	src/libstd/collections/hash/map.rs
	src/libstd/collections/hash/set.rs
	src/libstd/sync/mpsc/mod.rs
	src/libstd/sync/mutex.rs
	src/libstd/sync/poison.rs
	src/libstd/sync/rwlock.rs
	src/libsyntax/feature_gate.rs
	src/libsyntax/test.rs

1 files changed, 52 insertions, 2 deletions

diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index 1b8780120b1..0c55850b32a 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -49,8 +49,8 @@
 //! * You want a double-ended queue (deque).
 //!
 //! ### Use a `DList` when:
-//! * You want a `Vec` or `RingBuf` of unknown size, and can't tolerate inconsistent
-//! performance during insertions.
+//! * You want a `Vec` or `RingBuf` of unknown size, and can't tolerate amortization.
+//! * You want to efficiently split and append lists.
 //! * You are *absolutely* certain you *really*, *truly*, want a doubly linked list.
 //!
 //! ### Use a `HashMap` when:
@@ -85,6 +85,56 @@
 //! or "most important" one at any given time.
 //! * You want a priority queue.
 //!
+//! # Performance
+//!
+//! Choosing the right collection for the job requires an understanding of what each collection
+//! is good at. Here we briefly summarize the performance of different collections for certain
+//! important operations. For further details, see each type's documentation.
+//!
+//! Throughout the documentation, we will follow a few conventions. For all operations,
+//! the collection's size is denoted by n. If another collection is involved in the operation, it
+//! contains m elements. Operations which have an *amortized* cost are suffixed with a `*`.
+//! Operations with an *expected* cost are suffixed with a `~`.
+//!
+//! All amortized costs are for the potential need to resize when capacity is exhausted.
+//! If a resize occurs it will take O(n) time. Our collections never automatically shrink,
+//! so removal operations aren't amortized. Over a sufficiently large series of
+//! operations, the average cost per operation will deterministically equal the given cost.
+//!
+//! Only HashMap has expected costs, due to the probabilistic nature of hashing. It is
+//! theoretically possible, though very unlikely, for HashMap to experience worse performance.
+//!
+//! ## Sequences
+//!
+//! |         | get(i)         | insert(i)       | remove(i)      | append | split_off(i)   |
+//! |---------|----------------|-----------------|----------------|--------|----------------|
+//! | Vec     | O(1)           | O(n-i)*         | O(n-i)         | O(m)*  | O(n-i)         |
+//! | RingBuf | O(1)           | O(min(i, n-i))* | O(min(i, n-i)) | O(m)*  | O(min(i, n-i)) |
+//! | DList   | O(min(i, n-i)) | O(min(i, n-i))  | O(min(i, n-i)) | O(1)   | O(min(i, n-i)) |
+//! | Bitv    | O(1)           | O(n-i)*         | O(n-i)         | O(m)*  | O(n-i)         |
+//!
+//! Note that where ties occur, Vec is generally going to be faster than RingBuf, and RingBuf
+//! is generally going to be faster than DList. Bitv is not a general purpose collection, and
+//! therefore cannot reasonably be compared.
+//!
+//! ## Maps
+//!
+//! For Sets, all operations have the cost of the equivalent Map operation. For BitvSet,
+//! refer to VecMap.
+//!
+//! |          | get       | insert   | remove   | predecessor |
+//! |----------|-----------|----------|----------|-------------|
+//! | HashMap  | O(1)~     | O(1)~*   | O(1)~    | N/A         |
+//! | BTreeMap | O(log n)  | O(log n) | O(log n) | O(log n)    |
+//! | VecMap   | O(1)      | O(1)?    | O(1)     | O(n)        |
+//!
+//! Note that VecMap is *incredibly* inefficient in terms of space. The O(1) insertion time
+//! assumes space for the element is already allocated. Otherwise, a large key may require a
+//! massive reallocation, with no direct relation to the number of elements in the collection.
+//! VecMap should only be seriously considered for small keys.
+//!
+//! Note also that BTreeMap's precise preformance depends on the value of B.
+//!
 //! # Correct and Efficient Usage of Collections
 //!
 //! Of course, knowing which collection is the right one for the job doesn't instantly