Skip to main content

bench/
bench.rs

1//! Quick timing of common operations. Run with `cargo run --release --example bench`.
2
3use finger_vec::FingerVec;
4use std::time::Instant;
5
6fn time(name: &str, f: impl FnOnce()) {
7  let start = Instant::now();
8  f();
9  println!("{name:<36} {:>9.2} ms", start.elapsed().as_secs_f64() * 1e3);
10}
11
12fn main() {
13  let n = 100_000usize;
14  let mut sink = 0usize;
15  let mut v = FingerVec::new();
16  time("push_right 100k", || {
17    for i in 0..n {
18      v = v.push_right(i);
19    }
20  });
21  let mut p = FingerVec::new();
22  time("push_left 100k", || {
23    for i in 0..n {
24      p = p.push_left(i);
25    }
26  });
27  let source: Vec<usize> = (0..n).collect();
28  let mut b = FingerVec::new();
29  time("from Vec 100k", || b = FingerVec::from(source.clone()));
30  let mut x = 1u64;
31  let idx: Vec<usize> = (0..n)
32    .map(|_| {
33      x ^= x << 13;
34      x ^= x >> 7;
35      x ^= x << 17;
36      (x as usize) % n
37    })
38    .collect();
39  time("get 100k random", || {
40    for &i in &idx {
41      sink += *b.get(i).unwrap();
42    }
43  });
44  time("iterate 100k", || {
45    for y in v.iter() {
46      sink += *y;
47    }
48  });
49  let mut r = v.clone();
50  time("drop_left until empty 100k", || {
51    while !r.is_empty() {
52      r = r.drop_left();
53    }
54  });
55  let mut u = b.clone();
56  time("assoc 100k random", || {
57    for &i in &idx {
58      u = u.assoc(i, i).unwrap();
59    }
60  });
61  let mut c = FingerVec::new();
62  time("concat acc+[x] 20k", || {
63    for i in 0..20_000 {
64      c = c.concat_with(&FingerVec::from(vec![i]));
65    }
66  });
67  let mut m = b.clone();
68  time("insert middle 20k", || {
69    for i in 0..20_000 {
70      let l = m.len();
71      m = m.insert(l / 2, i, false).unwrap();
72    }
73  });
74  println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75  println!("sink {sink}");
76}