std btreeset bench

This bench is to compare with AvlTree and assess the need to implement a BTreeSet of our own.

Condition

platform: intel i7-8550U, rust 1.97.

Measured in million ops for different dataset sizes.

A boxed item is put into BTreeSet, comparable to an intrusive AvlTree.

#[derive(Default, Debug, PartialEq, PartialOrd, Ord, Eq)]
struct IntNode {
    pub value: u32,
}

impl Borrow<u32> for Box<IntNode> {
    #[inline]
    fn borrow(&self) -> &u32 {
        &self.value
    }
}

fn new_intnode_box(i: u32) -> Box<IntNode> {
    Box::new(IntNode { value: i})
}

Result

insert_seq	std
1k	14.832
10k	10.839
1m	7.5195

insert_rand	std
1k	12.544
10k	7.09
1M	0.951

get_seq	std
1K	31.705
10K	24.485
1M	15.593

get_rand	std
1K	24.640
10K	11.684
1M	1.5484

remove_seq	std
1K	31.684
10K	25.341
1M	16.882

remove_rand	std
1K	12.496
10K	8.6591
1M	1.5484

iter	std
1K	297.86
10K	253.95
1M	38.607

into_iter_box	std
1K	49.565
10K	50.956
1M	5.9180

drop	std
1K	31.622
10K	54.522
1M	5.9725

Conclusion

We can see insert_seq, insert_rand is slightly better, remove_seq, remove_rand. get_rand is the same,
get_seq is better, iter is significantly better.