| 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 |
| 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 |
| 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 |
| 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 |
Compiled with rustc 1.27.0-nightly (4b9b70c39 2018-04-09).
This is the output of
for f in $(find benches -type f); do
echo "========================== BEGIN $f"
cat $f
echo "========================== END $f"
doneis
========================== 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".
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
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)