libcore: Implement an `Equiv` trait and use it on hashmaps.

7.3x speedup in string map search speed on a microbenchmark of pure hashmap
searching against a constant string, due to the lack of allocations.

I ran into a few snags.

1. The way the coherence check is set up, I can't implement `Equiv<@str>` and
   `Equiv<~str>` for `&str` simultaneously.

2. I wanted to implement `Equiv<T>` for all `T:Eq` (i.e. every type can be
   compared to itself if it implements `Eq`), but the coherence check didn't
   like that either.

3. I couldn't add this to the `Map` trait because `LinearMap` needs special
   handling for its `Q` type parameter: it must not only implement `Equiv<T>`
   but also `Hash` and `Eq`.

4. `find_equiv(&&"foo")` doesn't parse, because of the double ampersand. It has
   to be written `find_equiv(& &"foo")`. We can probably just fix this.

Nevertheless, this is a huge win; it should address a major source of
performance problems, including the one here:

http://maniagnosis.crsr.net/2013/02/creating-letterpress-cheating-program.html

1 files changed, 7 insertions, 1 deletions

diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index f7676bd211e..ab5f04ace79 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -14,7 +14,7 @@
 
 use container::{Container, Mutable};
 use cast;
-use cmp::{Eq, Ord, TotalOrd, Ordering, Less, Equal, Greater};
+use cmp::{Eq, Equiv, Ord, TotalOrd, Ordering, Less, Equal, Greater};
 use iter::BaseIter;
 use iter;
 use kinds::Copy;
@@ -1572,6 +1572,12 @@ impl<T:Eq> Eq for @[T] {
     pure fn ne(&self, other: &@[T]) -> bool { !(*self).eq(other) }
 }
 
+#[cfg(notest)]
+impl<T:Eq> Equiv<~[T]> for &[T] {
+    #[inline(always)]
+    pure fn equiv(&self, other: &~[T]) -> bool { eq(*self, *other) }
+}
+
 // Lexicographical comparison
 
 pure fn cmp<T: TotalOrd>(a: &[T], b: &[T]) -> Ordering {