Benchmark of rpds 0.5.0 against im `f59f24b` (slightly after 10.0.0)

benchmark-rpds-0.5.0-against-im-f59f24b-10.0.0.md

Benchmark of rpds 0.5.0 against im f59f24b (slightly after 10.0.0)

Results

im::ConsList vs rpds::List

Benchmark	im::ConsList (ns/iter)	rpds::List (ns/iter)	~Speedup
push_front	7,247,468	7,878,105	0.919
push_front_mut	-	5,598,963	-
drop_first	1,063,735	3,979,965	0.267
drop_first_mut	-	1,526,600	-
iterate	4,503,889	561,385	8.022

im::Vector vs rpds::Vector

Benchmark	im::Vector (ns/iter)	rpds::Vector (ns/iter)	~Speedup
push_back	30,716,343	90,416,977	0.339
push_back_mut	7,076,187	9,424,101	0.750
drop_last	25,538,357	79,242,154	0.322
drop_last_mut	6,732,801	5,513,976	1.221
get	1,977,921	2,434,592	0.812
iterate	1,682,513	750,157	2.242

im::HashMap vs rpds::HashTrieMap

Benchmark	im::HashMap (ns/iter)	rpds::HashTrieMap (ns/iter)	~Speedup
insert	205,060,198	220,708,446	0.929
insert_mut	28,031,419	21,575,286	1.299
remove	217,480,871	226,557,028	0.959
remove_mut	30,475,150	26,372,807	1.155
get	18,860,915	11,785,882	1.600
iterate	10,042,752	5,596,434	1.794

im::OrdMap vs rpds::RedBlackTreeMap

Benchmark	im::OrdMap (ns/iter)	rpds::RedBlackTreeMap (ns/iter)	~Speedup
insert	253,381,156	193,149,263	1.311
insert_mut	37,761,074	55,562,923	0.679
remove	234,548,211	150,821,893	1.555
remove_mut	21,676,435	47,156,266	0.459
get	7,833,185	6,541,685	1.197
iterate	5,861,675	1,229,430	4.767

Methodology

Compiled with rustc 1.27.0-nightly (4b9b70c39 2018-04-09).

Benchmark Code

This is the output of

for f in $(find benches -type f); do
    echo "========================== BEGIN $f"
    cat $f
    echo "========================== END $f"
done

is

========================== BEGIN benches/btree_map.rs
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

#![cfg_attr(feature = "fatal-warnings", deny(warnings))]

#![feature(test)]

extern crate test;
extern crate im;

mod utils;

use test::{black_box, Bencher};
use im::*;
use utils::iterations;
use utils::BencherNoDrop;

type RedBlackTreeMap<K, V> = OrdMap<K, V>;

#[bench]
fn red_black_tree_map_insert(bench: &mut Bencher) {
    let limit = iterations(100_000);

    bench.iter_no_drop(|| {
        let mut map = RedBlackTreeMap::new();

        for i in 0..limit {
            map = map.insert(i, -(i as isize));
        }

        map
    });
}

#[bench]
fn red_black_tree_map_insert_mut(bench: &mut Bencher) {
    let limit = iterations(100_000);

    bench.iter_no_drop(|| {
        let mut map = RedBlackTreeMap::new();

        for i in 0..limit {
            map.insert_mut(i, -(i as isize));
        }

        map
    });
}

#[bench]
fn red_black_tree_map_remove(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut full_map = RedBlackTreeMap::new();

    for i in 0..limit {
        full_map = full_map.insert(i, -(i as isize));
    }

    bench.iter_no_drop(|| {
        let mut map = full_map.clone();

        for i in 0..limit {
            map = map.remove(&i);
        }

        map
    });
}

#[bench]
fn red_black_tree_map_remove_mut(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut full_map = RedBlackTreeMap::new();

    for i in 0..limit {
        full_map = full_map.insert(i, -(i as isize));
    }

    bench.iter_no_drop(|| {
        let mut map = full_map.clone();

        for i in 0..limit {
            map.remove_mut(&i);
        }

        map
    });
}

#[bench]
fn red_black_tree_map_get(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut map = RedBlackTreeMap::new();

    for i in 0..limit {
        map = map.insert(i, -(i as isize));
    }

    bench.iter(|| {
        for i in 0..limit {
            black_box(map.get(&i));
        }
    });
}

#[bench]
fn red_black_tree_map_iterate(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut map = RedBlackTreeMap::new();

    for i in 0..limit {
        map = map.insert(i, -(i as isize));
    }

    bench.iter(|| {
        for kv in map.iter() {
            black_box(kv);
        }
    });
}
========================== END benches/btree_map.rs
========================== BEGIN benches/hash_trie_map.rs
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

#![cfg_attr(feature = "fatal-warnings", deny(warnings))]

#![feature(test)]

extern crate test;
extern crate im;

mod utils;

use test::{black_box, Bencher};
use im::*;
use utils::iterations;
use utils::BencherNoDrop;

type HashTrieMap<K, V> = HashMap<K, V>;

#[bench]
fn hash_trie_map_insert(bench: &mut Bencher) {
    let limit = iterations(100_000);

    bench.iter_no_drop(|| {
        let mut map = HashTrieMap::new();

        for i in 0..limit {
            map = map.insert(i, -(i as isize));
        }

        map
    });
}

#[bench]
fn hash_trie_map_insert_mut(bench: &mut Bencher) {
    let limit = iterations(100_000);

    bench.iter_no_drop(|| {
        let mut map = HashTrieMap::new();

        for i in 0..limit {
            map.insert_mut(i, -(i as isize));
        }

        map
    });
}

#[bench]
fn hash_trie_map_remove(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut full_map = HashTrieMap::new();

    for i in 0..limit {
        full_map = full_map.insert(i, -(i as isize));
    }

    bench.iter_no_drop(|| {
        let mut map = full_map.clone();

        for i in 0..limit {
            map = map.remove(&i);
        }

        map
    });
}

#[bench]
fn hash_trie_map_remove_mut(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut full_map = HashTrieMap::new();

    for i in 0..limit {
        full_map = full_map.insert(i, -(i as isize));
    }

    bench.iter_no_drop(|| {
        let mut map = full_map.clone();

        for i in 0..limit {
            map.remove_mut(&i);
        }

        map
    });
}

#[bench]
fn hash_trie_map_get(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut map = HashTrieMap::new();

    for i in 0..limit {
        map = map.insert(i, -(i as isize));
    }

    bench.iter(|| {
        for i in 0..limit {
            black_box(map.get(&i));
        }
    });
}

#[bench]
fn hash_trie_map_iterate(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut map = HashTrieMap::new();

    for i in 0..limit {
        map = map.insert(i, -(i as isize));
    }

    bench.iter(|| {
        for kv in map.iter() {
            black_box(kv);
        }
    });
}
========================== END benches/hash_trie_map.rs
========================== BEGIN benches/vector.rs
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

#![cfg_attr(feature = "fatal-warnings", deny(warnings))]
#![feature(test)]

extern crate test;
extern crate im;

mod utils;

use test::{black_box, Bencher};
use im::Vector;
use utils::iterations;
use utils::BencherNoDrop;

#[bench]
fn vector_push_back(bench: &mut Bencher) {
    let limit = iterations(100_000);

    bench.iter_no_drop(|| {
        let mut vector: Vector<usize> = Vector::new();

        for i in 0..limit {
            vector = vector.push_back(i);
        }

        vector
    });
}

#[bench]
fn vector_push_back_mut(bench: &mut Bencher) {
    let limit = iterations(100_000);

    bench.iter_no_drop(|| {
        let mut vector: Vector<usize> = Vector::new();

        for i in 0..limit {
            vector.push_back_mut(i);
        }

        vector
    });
}

#[bench]
fn vector_drop_last(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut full_vector: Vector<usize> = Vector::new();

    for i in 0..limit {
        full_vector = full_vector.push_back(i);
    }

    bench.iter_no_drop(|| {
        let mut vector: Vector<usize> = full_vector.clone();

        for _ in 0..limit {
            vector = vector.init().unwrap();
        }

        vector
    });
}

#[bench]
fn vector_drop_last_mut(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut full_vector: Vector<usize> = Vector::new();

    for i in 0..limit {
        full_vector.push_back_mut(i);
    }

    bench.iter_no_drop(|| {
        let mut vector: Vector<usize> = full_vector.clone();

        for _ in 0..limit {
            vector.pop_back_mut();
        }

        vector
    });
}

#[bench]
fn vector_get(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut vector: Vector<usize> = Vector::new();

    for i in 0..limit {
        vector = vector.push_back(i);
    }

    bench.iter(|| {
        for i in 0..limit {
            black_box(vector.get(i));
        }
    });
}

#[bench]
fn vector_iterate(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut vector: Vector<usize> = Vector::new();

    for i in 0..limit {
        vector = vector.push_back(i);
    }

    bench.iter(|| {
        for i in vector.iter() {
            black_box(i);
        }
    });
}
========================== END benches/vector.rs
========================== BEGIN benches/utils/mod.rs
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

use test::Bencher;

pub trait BencherNoDrop {
    /// Runs the given benchmark function.  The return values of the function will be dropped
    /// outside of the benchmark iteration and therefore the drop time will not be counted.
    fn iter_no_drop<T, F>(&mut self, inner: F)
    where
        F: FnMut() -> T;
}

impl BencherNoDrop for Bencher {
    fn iter_no_drop<T, F>(&mut self, mut inner: F)
    where
        F: FnMut() -> T,
    {
        let mut to_drop = Vec::with_capacity(1_000_000);
        let initial_capacity = to_drop.capacity();

        self.iter(|| {
            to_drop.push(inner());
        });

        assert_eq!(initial_capacity, to_drop.capacity(),
                   "Vector of to-be-dropped values was resized.  This might have impacted the benchmark measurement.");
    }
}

/// To avoid long benchmarks running with `QUICK_BENCH`.
/// This is used to test that the benchmarks are correctly defined without taking a lot of time,
/// which is what we want in the CI environment.
pub fn iterations(n: usize) -> usize {
    match ::std::env::var("QUICK_BENCH") {
        Ok(ref v) if v == "true" => 2,
        _ => n,
    }
}
========================== END benches/utils/mod.rs
========================== BEGIN benches/list.rs
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

#![feature(test)]

extern crate test;
extern crate im;

mod utils;

use test::{black_box, Bencher};
use im::conslist::ConsList;
use utils::iterations;
use utils::BencherNoDrop;

type List<T> = ConsList<T>;

#[bench]
fn list_push_front(bench: &mut Bencher) {
    let limit = iterations(100_000);

    bench.iter_no_drop(|| {
        let mut list: List<usize> = List::new();

        for i in 0..limit {
            list = list.cons(i);
        }

        list
    });
}

#[bench]
fn list_drop_first(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut full_list: List<usize> = List::new();

    for i in 0..limit {
        full_list = full_list.cons(i);
    }

    bench.iter_no_drop(|| {
        let mut list: List<usize> = full_list.clone();

        for _ in 0..limit {
            list = list.tail().unwrap();
        }

        list
    });
}

#[bench]
fn list_iterate(bench: &mut Bencher) {
    let limit = iterations(100_000);
    let mut list: List<usize> = List::new();

    for i in 0..limit {
        list = list.cons(i);
    }

    bench.iter(|| {
        for i in list.iter() {
            black_box(i);
        }
    });
}
========================== END benches/list.rs

Note that the btree test is incorrectly called refered to "red black tree".

Raw output from cargo +nightly bench

im

running 6 tests
test red_black_tree_map_get        ... bench:   7,833,185 ns/iter (+/- 363,352)
test red_black_tree_map_insert     ... bench: 253,381,156 ns/iter (+/- 5,715,503)
test red_black_tree_map_insert_mut ... bench:  37,761,074 ns/iter (+/- 851,187)
test red_black_tree_map_iterate    ... bench:   5,861,675 ns/iter (+/- 304,108)
test red_black_tree_map_remove     ... bench: 234,548,211 ns/iter (+/- 16,440,808)
test red_black_tree_map_remove_mut ... bench:  21,676,435 ns/iter (+/- 624,278)

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


running 6 tests
test hash_trie_map_get        ... bench:  18,860,915 ns/iter (+/- 1,423,342)
test hash_trie_map_insert     ... bench: 205,060,198 ns/iter (+/- 18,223,666)
test hash_trie_map_insert_mut ... bench:  28,031,419 ns/iter (+/- 4,293,722)
test hash_trie_map_iterate    ... bench:  10,042,752 ns/iter (+/- 869,204)
test hash_trie_map_remove     ... bench: 217,480,871 ns/iter (+/- 1,979,430)
test hash_trie_map_remove_mut ... bench:  30,475,150 ns/iter (+/- 1,031,259)

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


running 3 tests
test list_drop_first ... bench:   1,063,735 ns/iter (+/- 60,560)
test list_iterate    ... bench:   4,503,889 ns/iter (+/- 240,052)
test list_push_front ... bench:   7,247,468 ns/iter (+/- 258,636)

test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured; 0 filtered out


running 6 tests
test vector_drop_last     ... bench:  25,538,357 ns/iter (+/- 2,499,796)
test vector_drop_last_mut ... bench:   6,732,801 ns/iter (+/- 284,314)
test vector_get           ... bench:   1,977,921 ns/iter (+/- 104,114)
test vector_iterate       ... bench:   1,682,513 ns/iter (+/- 63,649)
test vector_push_back     ... bench:  30,716,343 ns/iter (+/- 641,538)
test vector_push_back_mut ... bench:   7,076,187 ns/iter (+/- 300,636)

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

rpds

running 6 tests
test rpds_hash_trie_map_get        ... bench:  11,785,882 ns/iter (+/- 681,004)
test rpds_hash_trie_map_insert     ... bench: 220,708,446 ns/iter (+/- 18,709,932)
test rpds_hash_trie_map_insert_mut ... bench:  21,575,286 ns/iter (+/- 2,771,799)
test rpds_hash_trie_map_iterate    ... bench:   5,596,434 ns/iter (+/- 458,425)
test rpds_hash_trie_map_remove     ... bench: 226,557,028 ns/iter (+/- 17,192,335)
test rpds_hash_trie_map_remove_mut ... bench:  26,372,807 ns/iter (+/- 2,552,610)

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


running 5 tests
test rpds_list_drop_first     ... bench:   3,979,965 ns/iter (+/- 110,785)
test rpds_list_drop_first_mut ... bench:   1,526,600 ns/iter (+/- 62,953)
test rpds_list_iterate        ... bench:     561,385 ns/iter (+/- 74,433)
test rpds_list_push_front     ... bench:   7,878,105 ns/iter (+/- 133,194)
test rpds_list_push_front_mut ... bench:   5,598,963 ns/iter (+/- 635,719)

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


running 6 tests
test rpds_red_black_tree_map_get        ... bench:   6,541,685 ns/iter (+/- 609,433)
test rpds_red_black_tree_map_insert     ... bench: 193,149,263 ns/iter (+/- 15,409,606)
test rpds_red_black_tree_map_insert_mut ... bench:  55,562,923 ns/iter (+/- 830,768)
test rpds_red_black_tree_map_iterate    ... bench:   1,229,430 ns/iter (+/- 105,755)
test rpds_red_black_tree_map_remove     ... bench: 150,821,893 ns/iter (+/- 11,829,882)
test rpds_red_black_tree_map_remove_mut ... bench:  47,156,266 ns/iter (+/- 4,172,621)

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


running 6 tests
test rpds_vector_drop_last     ... bench:  79,242,154 ns/iter (+/- 6,414,413)
test rpds_vector_drop_last_mut ... bench:   5,513,976 ns/iter (+/- 227,696)
test rpds_vector_get           ... bench:   2,434,592 ns/iter (+/- 60,699)
test rpds_vector_iterate       ... bench:     750,157 ns/iter (+/- 21,280)
test rpds_vector_push_back     ... bench:  90,416,977 ns/iter (+/- 1,311,010)
test rpds_vector_push_back_mut ... bench:   9,424,101 ns/iter (+/- 907,974)