Rust Vec vs. HashMap lookup performance - note: see comments! test is flawed (test never adds more than 7 items to HashMap).

lib.rs

#![feature(test)]
extern crate test;
use std::borrow::Cow;
use std::collections::HashMap;

pub fn test_vec(x: &Vec<(Cow<'static, str>, i32)>, module: &str) -> Option<i32> {
    x.iter().find(|&&(ref test_module, _)| test_module == module).map(|&(_, level)| level)
}

pub fn test_map(x: &HashMap<Cow<'static, str>, i32>, module: &str) -> Option<i32> {
    x.get(module).cloned()
}

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    fn create_data<T: std::iter::FromIterator<(Cow<'static, str>, i32)>>(number_of_items: usize) -> T {
        vec!["fdsfsdfaasdf::fdsa", "def::fe", "ags::asdf", "asdffdsa", "fdwa84e9faw", "fjio8493", "fw2ioo0"]
            .into_iter()
            .cycle()
            .take(number_of_items)
            .collect::<Vec<_>>()
            .into_iter()
            .map(Into::into)
            .zip(100..)
            .collect()
    }

    #[bench]
    fn bench_10_item_vec(b: &mut Bencher) {
        let tests = test::black_box(create_data(10));

        b.iter(|| test_vec(&tests, test::black_box("q3428f9")))
    }
    #[bench]
    fn bench_10_item_hash_map(b: &mut Bencher) {
        let tests = test::black_box(create_data(10));

        b.iter(|| test_map(&tests, test::black_box("q3428f9")))
    }

    #[bench]
    fn bench_20_item_vec(b: &mut Bencher) {
        let tests = test::black_box(create_data(20));

        b.iter(|| test_vec(&tests, test::black_box("q3428f9")))
    }
    #[bench]
    fn bench_20_item_hash_map(b: &mut Bencher) {
        let tests = test::black_box(create_data(20));

        b.iter(|| test_map(&tests, test::black_box("q3428f9")))
    }

    #[bench]
    fn bench_50_item_vec(b: &mut Bencher) {
        let tests = test::black_box(create_data(50));

        b.iter(|| test_vec(&tests, test::black_box("q3428f9")))
    }
    #[bench]
    fn bench_50_item_hash_map(b: &mut Bencher) {
        let tests = test::black_box(create_data(50));

        b.iter(|| test_map(&tests, test::black_box("q3428f9")))
    }
}

results.md

Edit 2023-01-12: See comments! Test is flawed - it will never add more than 7 elements to the HashMap. I've left the original results here unedited.

Test results on an Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz CPU:

$ cargo bench
   Compiling bench_test v0.1.0 (file:///home/daboross/bench_test)
    Finished release [optimized] target(s) in 2.99 secs
     Running target/release/deps/bench_test-6b454ea06156805a

running 6 tests
test tests::bench_10_item_hash_map ... bench:          35 ns/iter (+/- 4)
test tests::bench_10_item_vec      ... bench:          29 ns/iter (+/- 2)
test tests::bench_20_item_hash_map ... bench:          33 ns/iter (+/- 1)
test tests::bench_20_item_vec      ... bench:          51 ns/iter (+/- 6)
test tests::bench_50_item_hash_map ... bench:          35 ns/iter (+/- 2)
test tests::bench_50_item_vec      ... bench:         129 ns/iter (+/- 1)

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

Conclusion: Vec is best when there are 15 or fewer items, HashMap is better when there are more than 15.

@Glitchy-Tozier Here is the benchmark with ahash.
run on a c5 ec2 instance

running 15 tests
test tests::bench_2_item_ahash_map ... bench:           8 ns/iter (+/- 0)
test tests::bench_2_item_hash_map  ... bench:          20 ns/iter (+/- 0)
test tests::bench_2_item_vec       ... bench:           5 ns/iter (+/- 0)

test tests::bench_5_item_ahash_map  ... bench:           8 ns/iter (+/- 0)
test tests::bench_5_item_hash_map   ... bench:          20 ns/iter (+/- 0)
test tests::bench_5_item_vec        ... bench:           6 ns/iter (+/- 0)

test tests::bench_10_item_ahash_map ... bench:           8 ns/iter (+/- 0)
test tests::bench_10_item_hash_map  ... bench:          20 ns/iter (+/- 0)
test tests::bench_10_item_vec       ... bench:          14 ns/iter (+/- 0)

test tests::bench_20_item_ahash_map ... bench:           8 ns/iter (+/- 0)
test tests::bench_20_item_hash_map  ... bench:          20 ns/iter (+/- 0)
test tests::bench_20_item_vec       ... bench:          24 ns/iter (+/- 0)

test tests::bench_50_item_ahash_map ... bench:           8 ns/iter (+/- 0)
test tests::bench_50_item_hash_map  ... bench:          20 ns/iter (+/- 0)
test tests::bench_50_item_vec       ... bench:          60 ns/iter (+/- 0)

@cgbur Amazing, thank you!

I just found this from google trying to answer a similar question, and I think this is not comparing what you think it is comparing. The way you are constructing the hashmaps they will never have more than 7 elements because keys in HashMaps are unique. Using iter().cycle() means you are overwriting the values for those keys continuously without increasing the actual capacity of the HashMap. you can see this with:

    #[test]
    fn create_data_from_vec() {
        let desired_len = 100;
        let hm: HashMap<Cow<'static, str>, i32> = create_data(desired_len);
        assert_eq!(hm.len(), desired_len);
    }

Which fails with:

thread 'create_data_from_vec' panicked at 'assertion failed: `(left == right)`
  left: `7`,
 right: `100`', src/lib.rs:61:5

A better create_data function that draws key values from random might look something like this

use rand::distributions::Alphanumeric;
use rand::{thread_rng, Rng};

fn create_data_new<T: std::iter::FromIterator<(Cow<'static, str>, i32)>>(
    number_of_items: usize,
) -> T {
    let base = 100;
    (0..number_of_items)
        .map(|x| {
            (
                thread_rng()
                    .sample_iter(&Alphanumeric)
                    .take(30)
                    .map(char::from)
                    .collect::<Cow<'static, str>>(),
                i32::try_from(base + x).unwrap(),
            )
        })
        .collect()
}

In order to test lookups you now need to insert a known element after creating the object during each test as there are no pre-determined values.

#[bench]
fn bench_10_item_vec(b: &mut Bencher) {
    let mut tests: Vec<(Cow<str>, i32)> = test::black_box(create_data(10));
    tests.push((Cow::from("q3428f9"), 1));

    b.iter(|| test_vec(&tests, test::black_box("q3428f9")))
}
#[bench]
fn bench_10_item_hash_map(b: &mut Bencher) {
    let mut tests: HashMap<Cow<'static, str>, i32> = test::black_box(create_data(10));
    tests.insert(Cow::from("q3428f9"), 1);

    b.iter(|| test_map(&tests, test::black_box("q3428f9")))
}

However, even with these changes the performance of hashmaps doesn't change much because Hashmaps are generally optimized for lookups.

test tests::bench_10_item_hash_map     ... bench:          27 ns/iter (+/- 1)
test tests::bench_10_item_vec          ... bench:           8 ns/iter (+/- 0)
test tests::bench_20_item_hash_map     ... bench:          27 ns/iter (+/- 1)
test tests::bench_20_item_vec          ... bench:          13 ns/iter (+/- 0)
test tests::bench_50_item_hash_map     ... bench:          27 ns/iter (+/- 0)
test tests::bench_50_item_vec          ... bench:          25 ns/iter (+/- 0)
test tests::bench_10_000_item_hash_map ... bench:          27 ns/iter (+/- 2)
test tests::bench_10_000_item_vec      ... bench:       8,472 ns/iter (+/- 297)

I just found this from google trying to answer a similar question, and I think this is not comparing what you think it is comparing. The way you are constructing the hashmaps they will never have more than 7 elements because keys in HashMaps are unique. Using iter().cycle() means you are overwriting the values for those keys continuously without increasing the actual capacity of the HashMap. you can see this with:

You're completely correct!

I can't believe I've come back to this gist so many times without noticing this error.

tests.push((Cow::from("q3428f9"), 1));

I don't know if I stated this in the original document, but for fern's use case, misses are expected to be much more common than hits, and thus this test does exclusively test misses. Even in the original test, the test string "q3428f9" doesn't appear in the preselected list of things to add to each.

---

I think the fact that the test resulted in roughly what I was expecting (vec better at smaller magnitudes, hashmap better at larger ones) helped me miss this.

If I were to recreate the test fully today, I think I'd probably want to include some real-world data on how many hits vs. misses are expected, and distribute the test string in a random place in the vec/hashmap to account for that as well.

---

Thanks for catching this!