foo.rs

#![feature(test, hash, rand)]

extern crate test;

macro_rules! benches {
    ($f:expr, $var:ident) => {
        use std::iter::repeat;
        #[bench]
        fn str_small(b: &mut ::test::Bencher) {
            let $var = "foo";
            b.iter(|| $f);
        }

        #[bench]
        fn str_medium(b: &mut ::test::Bencher) {
            let s = repeat('a').take(500).collect::<String>();
            let $var = &*s;
            b.iter(|| $f);
        }

        #[bench]
        fn str_long(b: &mut ::test::Bencher) {
            let s = repeat('a').take(10000).collect::<String>();
            let $var = &*s;
            b.iter(|| $f);
        }

        #[bench]
        fn u64(b: &mut ::test::Bencher) {
            let $var = &1u64;
            b.iter(|| $f);
        }
    }
}

#[allow(deprecated)]
fn global_key() -> u64 {
    use std::sync::atomic::{ATOMIC_USIZE_INIT, AtomicUsize, Ordering};
    use std::rand::{thread_rng, Rng};
    static KEY: AtomicUsize = ATOMIC_USIZE_INIT;
    match KEY.load(Ordering::Relaxed) {
        0 => {}
        n => return n as u64,
    }

    let v = thread_rng().next_u64() as usize;
    let prev = KEY.compare_and_swap(0, v, Ordering::SeqCst);
    if prev == 0 {v as u64} else {prev as u64}
}

fn combine(a: u64, b: u64) -> u64 {
    a ^ (b + 0x9e3779b9 + (a << 6) + (a >> 2))
}

mod hash1 {
    use std::hash::{hash, SipHasher};
    benches!(hash::<_, SipHasher>(&foo), foo);
}

mod hash2 {
    use std::hash::{Hasher, Writer, SipHasher};

    trait Hash2 {
        fn hash(&self) -> u64;
    }

    impl Hash2 for str {
        fn hash(&self) -> u64 {
            let mut s = SipHasher::new_with_keys(0, 0);
            s.write(self.as_bytes());
            s.finish()
        }
    }

    impl Hash2 for u64 {
        fn hash(&self) -> u64 {
            ::combine(::global_key(), *self)
        }
    }

    benches!(foo.hash(), foo);
}

mod hash2_combine {
    trait Hash2 {
        fn hash(&self) -> u64;
    }

    impl Hash2 for str {
        fn hash(&self) -> u64 {
            self.bytes().fold(0, |a, b| ::combine(a, b as u64))
        }
    }

    impl Hash2 for u64 {
        fn hash(&self) -> u64 {
            ::combine(::global_key(), *self)
        }
    }

    benches!(foo.hash(), foo);
}

mod hash3 {
    use std::hash::{Hasher, Writer, SipHasher};
    use std::mem;

    trait Hash3 {
        fn hash<H: Hasher3>(&self, h: &mut H);
    }

    pub trait Hasher3 {
        type Output;
        fn write(&mut self, bytes: &[u8]);
        fn finish(&self) -> Self::Output;

        fn write_u8(&mut self, i: u8) { self.write(&[i]) }
        fn write_u64(&mut self, i: u64) {
            self.write(&unsafe { mem::transmute::<_, [u8; 8]>(i) })
        }
    }

    impl Hash3 for str {
        fn hash<H: Hasher3>(&self, h: &mut H) {
            h.write(self.as_bytes());
            h.write_u8(0xff);
        }
    }

    impl Hash3 for u64 {
        fn hash<H: Hasher3>(&self, h: &mut H) {
            h.write_u64(*self)
        }
    }

    impl Hasher3 for SipHasher {
        type Output = u64;
        fn write(&mut self, bytes: &[u8]) { Writer::write(self, bytes) }
        fn finish(&self) -> u64 { Hasher::finish(self) }
    }

    fn sip<T: Hash3 + ?Sized>(t: &T) -> u64 {
        let mut s = SipHasher::new();
        Hash3::hash(t, &mut s);
        Hasher3::finish(&mut s)
    }

    benches!(sip(foo), foo);
}