foo.rs

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

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,
    }

    loop {
        let v = thread_rng().next_u64() as usize;
        if v == 0 { continue }
        let prev = KEY.compare_and_swap(0, v, Ordering::SeqCst);
        return if prev == 0 {v} 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::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)
        }
    }

    mod sip {
        use std::hash::{SipHasher, Hasher, Writer};
        use super::{Hash3, Hasher3};

        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);
    }

    mod u64 {
        use super::{Hash3, Hasher3};

        impl Hasher3 for u64 {
            type Output = u64;
            fn write(&mut self, bytes: &[u8]) {
                for b in bytes.iter() { self.write_u8(*b); }
            }
            fn finish(&self) -> u64 { *self }

            fn write_u8(&mut self, b: u8) { *self = ::combine(*self, b as u64); }
            fn write_u64(&mut self, b: u64) { *self = ::combine(*self, b); }
        }

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

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

results

$ rustc foo.rs --test -Clto -C opt-level=3 && ./foo --bench

running 20 tests
test hash1::str_long           ... bench:      7122 ns/iter (+/- 199)
test hash1::str_medium         ... bench:       376 ns/iter (+/- 8)
test hash1::str_small          ... bench:        19 ns/iter (+/- 0)
test hash1::u64                ... bench:        19 ns/iter (+/- 0)
test hash2::str_long           ... bench:      7113 ns/iter (+/- 577)
test hash2::str_medium         ... bench:       368 ns/iter (+/- 5)
test hash2::str_small          ... bench:        15 ns/iter (+/- 0)
test hash2::u64                ... bench:         2 ns/iter (+/- 0)
test hash2_combine::str_long   ... bench:     13202 ns/iter (+/- 390)
test hash2_combine::str_medium ... bench:       657 ns/iter (+/- 19)
test hash2_combine::str_small  ... bench:         0 ns/iter (+/- 0)
test hash2_combine::u64        ... bench:         2 ns/iter (+/- 0)
test hash3::sip::str_long      ... bench:      7113 ns/iter (+/- 95)
test hash3::sip::str_medium    ... bench:       370 ns/iter (+/- 6)
test hash3::sip::str_small     ... bench:        19 ns/iter (+/- 0)
test hash3::sip::u64           ... bench:        19 ns/iter (+/- 0)
test hash3::u64::str_long      ... bench:     13678 ns/iter (+/- 729)
test hash3::u64::str_medium    ... bench:       673 ns/iter (+/- 23)
test hash3::u64::str_small     ... bench:         3 ns/iter (+/- 0)
test hash3::u64::u64           ... bench:         2 ns/iter (+/- 0)

test result: ok. 0 passed; 0 failed; 0 ignored; 20 measured