From 2fa2ad59958d0028c856fb68359edb9a7bd9cab8 Mon Sep 17 00:00:00 2001 From: Patrick Walton Date: Mon, 4 Mar 2013 19:43:14 -0800 Subject: 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` 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` 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 --- src/libcore/str.rs | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'src/libcore/str.rs') diff --git a/src/libcore/str.rs b/src/libcore/str.rs index 471e1ae5396..24b2d8b5813 100644 --- a/src/libcore/str.rs +++ b/src/libcore/str.rs @@ -20,7 +20,7 @@ use at_vec; use cast; use char; -use cmp::{TotalOrd, Ordering, Less, Equal, Greater}; +use cmp::{Equiv, TotalOrd, Ordering, Less, Equal, Greater}; use libc; use option::{None, Option, Some}; use ptr; @@ -898,6 +898,12 @@ impl Ord for @str { pure fn gt(&self, other: &@str) -> bool { gt((*self), (*other)) } } +#[cfg(notest)] +impl Equiv<~str> for &str { + #[inline(always)] + pure fn equiv(&self, other: &~str) -> bool { eq_slice(*self, *other) } +} + /* Section: Iterating through strings */ -- cgit 1.4.1-3-g733a5