Benchmark results

[TheAwesomeKoeniq]

I think it would be nice to show some benchmark results for people looking for the best hash table for their project.

With benchmarks like remove we have to clone the maps and that falsifies the result, which is why I didn't include them.

System

- CPU
Intel Core i5 11400 [6c - 12t]
- RAM
2x 8GB DDR4 - 2666MHz

Config

[package]
name = "maptest"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
hashbrown = "0.14.0"
indexmap = "2.0.0"
serde_json = { version = "1.0", features = ["preserve_order"] }

Source Code

#![feature(test)]

extern crate test;
use test::Bencher;

#[macro_use]
extern crate serde_json;

use std::collections::{BTreeMap, HashMap};

use hashbrown::HashMap as HashBrown;
use indexmap::IndexMap;

#[bench]
fn a_new_btreemap(b: &mut Bencher) {
    b.iter(|| BTreeMap::<String, String>::new());
}

#[bench]
fn a_new_indexmap(b: &mut Bencher) {
    b.iter(|| IndexMap::<String, String>::new());
}

#[bench]
fn a_new_hashmap(b: &mut Bencher) {
    b.iter(|| HashMap::<String, String>::new());
}

#[bench]
fn a_new_hashbrown(b: &mut Bencher) {
    b.iter(|| HashBrown::<String, String>::new());
}

/* ========== INSERT ========== */

#[bench]
fn b_insert_btreemap(b: &mut Bencher) {
    b.iter(|| {
        let mut map = BTreeMap::new();
        for i in 0..100_000 {
            map.insert(i.to_string(), json!({ "Name": "Nick" }));
        }
    });
}

#[bench]
fn b_insert_indexmap(b: &mut Bencher) {
    b.iter(|| {
        let mut map = IndexMap::new();
        for i in 0..100_000 {
            map.insert(i.to_string(), json!({ "Name": "Nick" }));
        }
    });
}

#[bench]
fn b_insert_hashmap(b: &mut Bencher) {
    b.iter(|| {
        let mut map = HashMap::new();
        for i in 0..100_000 {
            map.insert(i.to_string(), json!({ "Name": "Nick" }));
        }
    });
}

#[bench]
fn b_insert_hashbrown(b: &mut Bencher) {
    b.iter(|| {
        let mut map = HashBrown::new();
        for i in 0..100_000 {
            map.insert(i.to_string(), json!({ "Name": "Nick" }));
        }
    });
}

/* ========== CLONE ========== */

#[bench]
fn c_clone_btreemap(b: &mut Bencher) {
    let mut map = BTreeMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| map.clone());
}

#[bench]
fn c_clone_indexmap(b: &mut Bencher) {
    let mut map = IndexMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| map.clone());
}

#[bench]
fn c_clone_hashmap(b: &mut Bencher) {
    let mut map = HashMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| map.clone());
}

#[bench]
fn c_clone_hashbrown(b: &mut Bencher) {
    let mut map = HashBrown::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| map.clone());
}

/* ========== FOR_EACH ========== */

#[bench]
fn d_for_each_btreemap(b: &mut Bencher) {
    let mut map = BTreeMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| {
        map.iter().for_each(|(key, val)| {
            if *key == 100_000.to_string() {
                // DO NOTHING
            }

            if val["name"] == "Nick" {
                // DO NOTHING
            }
        })
    });
}

#[bench]
fn d_for_each_indexmap(b: &mut Bencher) {
    let mut map = IndexMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| {
        map.iter().for_each(|(key, val)| {
            if *key == 100_000.to_string() {
                // DO NOTHING
            }

            if val["name"] == "Nick" {
                // DO NOTHING
            }
        })
    });
}

#[bench]
fn d_for_each_hashmap(b: &mut Bencher) {
    let mut map = HashMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| {
        map.iter().for_each(|(key, val)| {
            if *key == 100_000.to_string() {
                // DO NOTHING
            }

            if val["name"] == "Nick" {
                // DO NOTHING
            }
        })
    });
}

#[bench]
fn d_for_each_hashbrown(b: &mut Bencher) {
    let mut map = HashBrown::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| {
        map.iter().for_each(|(key, val)| {
            if *key == 100_000.to_string() {
                // DO NOTHING
            }

            if val["name"] == "Nick" {
                // DO NOTHING
            }
        })
    });
}

/* ========== FIND ========== */

#[bench]
fn e_find_btreemap(b: &mut Bencher) {
    let mut map = BTreeMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| map.iter().find(|(key, val)| val["name"] != "Nick" || **key == 100_000.to_string()));
}

#[bench]
fn e_find_indexmap(b: &mut Bencher) {
    let mut map = IndexMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| map.iter().find(|(key, val)| val["name"] != "Nick" || **key == 100_000.to_string()));
}

#[bench]
fn e_find_hashmap(b: &mut Bencher) {
    let mut map = HashMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| map.iter().find(|(key, val)| val["name"] != "Nick" || **key == 100_000.to_string()));
}

#[bench]
fn e_find_hashbrown(b: &mut Bencher) {
    let mut map = HashBrown::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| map.iter().find(|(key, val)| val["name"] != "Nick" || **key == 100_000.to_string()));
}

/* ========== RFIND ========== */

#[bench]
fn f_rfind_btreemap(b: &mut Bencher) {
    let mut map = BTreeMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| map.iter().rfind(|(key, val)| val["name"] != "Nick" || **key == 0.to_string()));
}

#[bench]
fn f_rfind_indexmap(b: &mut Bencher) {
    let mut map = IndexMap::new();
    for i in 0..100_000 {
        map.insert(i.to_string(), json!({ "Name": "Nick" }));
    }
    b.iter(|| map.iter().rfind(|(key, val)| val["name"] != "Nick" || **key == 0.to_string()));
}

Benchmark Results (updated on 07/17/2023)

running 22 tests

test a_new_btreemap       ... bench:           1 ns/iter (+/- 0)
test a_new_hashbrown      ... bench:           0 ns/iter (+/- 0)
test a_new_hashmap        ... bench:           3 ns/iter (+/- 0)
test a_new_indexmap       ... bench:           3 ns/iter (+/- 0)

test b_insert_btreemap    ... bench:  60,621,040 ns/iter (+/- 15,248,541)
test b_insert_hashbrown   ... bench:  56,344,580 ns/iter (+/- 1,773,809)
test b_insert_hashmap     ... bench:  58,881,920 ns/iter (+/- 2,330,201)
test b_insert_indexmap    ... bench:  42,826,040 ns/iter (+/- 1,214,166)

test c_clone_btreemap     ... bench:  41,720,370 ns/iter (+/- 1,932,831)
test c_clone_hashbrown    ... bench:  60,450,380 ns/iter (+/- 1,895,384)
test c_clone_hashmap      ... bench:  60,734,640 ns/iter (+/- 1,530,737)
test c_clone_indexmap     ... bench:  39,500,870 ns/iter (+/- 1,026,400)

test d_for_each_btreemap  ... bench:   8,487,320 ns/iter (+/- 112,188)
test d_for_each_hashbrown ... bench:   9,733,745 ns/iter (+/- 344,671)
test d_for_each_hashmap   ... bench:   9,800,705 ns/iter (+/- 664,072)
test d_for_each_indexmap  ... bench:   7,427,390 ns/iter (+/- 177,412)

test e_find_btreemap      ... bench:          16 ns/iter (+/- 1)
test e_find_hashbrown     ... bench:          15 ns/iter (+/- 2)
test e_find_hashmap       ... bench:          15 ns/iter (+/- 0)
test e_find_indexmap      ... bench:          13 ns/iter (+/- 0)

test f_rfind_btreemap     ... bench:          23 ns/iter (+/- 1)
test f_rfind_indexmap     ... bench:          14 ns/iter (+/- 0)

test result: ok. 0 passed; 0 failed; 0 ignored; 22 measured; 0 filtered out; finished in 170.61s

🗣 How Do You Run This Benchmark?

Copy the Source Code into PATH_TO_PROJECT\benches\test.rs and replace PATH_TO_PROJECT\Cargo.toml with Config. Then run cargo bench in your console

[your-diary]

How about adding FxHashMap?