benchmark.md

Intro

Migrated Benchmark data into this doc.

Benchmark

Data collected on macbook pro m1. The Key type is Point { x: f64, y: f64}

# try it
cargo bench

# generate the table
critcmp > benchmark_data 
python3 render_table.py

Advantages

• bptree ordered_get is way faster than random_get, also way faster(1.2ms vs 4.7ms) than btree's ordered_get.
• bptree iter's faster than btree(86us vs 220us).
• bptree bulk_insert is the most fast way to build a tree(938µs vs normal bptree insert 2ms vs btree insert 8ms).
• For unsorted data, sort then bulk_load is the fastest(9ms vs normal bptree 18.ms vs normal btree insert 13.9ms).

Disadvantages

• bptree random_get is slower(13ms vs 9ms) than btree.
• random_remove(17ms vs 12ms).

Point benchmark data

Point is a struct with 2 f64 fields, with very cheap clone and cmp cost.

name	size	btree	bptree	speed factor
clone	1000	12.3±0.08µs	5.6±0.21µs	2.20
clone	10000	133.2±1.60µs	60.3±0.53µs	2.21
clone	100000	2.5±0.03ms	1073.9±93.60µs	2.33
cursor	1000	-	4.6±0.03µs	-
cursor	10000	-	46.8±0.18µs	-
cursor	100000	-	470.0±2.39µs	-
drop	1000	7.9±0.10µs	1093.1±17.60ns	7.23
drop	10000	84.7±1.08µs	12.1±0.32µs	7.00
drop	100000	1799.9±23.56µs	295.2±11.19µs	6.10
into_iter	1000	8.1±0.58µs	1134.7±13.43ns	7.14
into_iter	10000	84.9±0.71µs	12.1±0.10µs	7.02
into_iter	100000	1825.7±79.25µs	254.9±7.95µs	7.16
iter	1000	844.2±8.44ns	416.8±5.02ns	2.03
iter	10000	11.9±0.29µs	4.7±0.03µs	2.53
iter	100000	216.5±0.80µs	54.8±0.13µs	3.95
ordered_get	1000	26.8±1.08µs	10.0±0.10µs	2.68
ordered_get	10000	418.7±2.83µs	107.5±0.53µs	3.89
ordered_get	100000	4.7±0.01ms	1126.8±4.21µs	4.17
ordered_remove	1000	32.5±0.84µs	84.1±0.80µs	0.39
ordered_remove	10000	344.9±3.55µs	873.5±0.72µs	0.39
ordered_remove	100000	4.5±0.47ms	9.6±0.20ms	0.47
random_get	1000	25.1±1.45µs	18.6±1.77µs	1.35
random_get	10000	664.3±50.24µs	956.8±6.58µs	0.69
random_get	100000	9.3±0.01ms	13.4±0.02ms	0.69
random_remove	1000	61.6±4.01µs	89.6±1.39µs	0.69
random_remove	10000	912.4±0.84µs	1411.6±2.83µs	0.65
random_remove	100000	12.8±0.90ms	18.7±0.04ms	0.68

Point benchmark data with bulk_load

name	size	type	time
ordered_insert	1000	bptree	26.9±0.23µs
		bptree_bulk	6.1±0.08µs
		btree	50.8±1.80µs
ordered_insert	10000	bptree	358.3±10.02µs
		bptree_bulk	66.0±0.61µs
		btree	778.5±13.34µs
ordered_insert	100000	bptree	4.7±0.02ms
		bptree_bulk	916.1±20.79µs
		btree	8.8±0.04ms
random_insert	1000	bptree	81.3±1.15µs
		bptree_sort_load	43.2±0.29µs
		btree	55.5±1.36µs
random_insert	10000	bptree	1381.6±16.30µs
		bptree_sort_load	698.6±7.84µs
		btree	962.6±9.49µs
random_insert	100000	bptree	18.3±0.06ms
		bptree_sort_load	9.5±0.01ms
		btree	14.0±0.08ms

String benchmark data

String type is relative heavy for clone, cmp and drop.

For clone and drop, bptree actually needs to do more work, but still faster. For random_get and random_remove, bptree still slower, but the margin is smaller.

name	size	btree	bptree	speed factor
clone	1000	34.4±0.41µs	27.6±0.55µs	1.25
clone	10000	431.6±10.88µs	307.0±8.21µs	1.41
clone	100000	7.2±0.07ms	5.2±0.02ms	1.38
cursor	1000	-	30.2±0.16µs	-
cursor	10000	-	306.2±0.89µs	-
cursor	100000	-	3.5±0.64ms	-
drop	1000	21.5±1.03µs	14.7±0.06µs	1.46
drop	10000	234.5±2.83µs	146.6±2.22µs	1.60
drop	100000	4.5±0.06ms	2.3±0.02ms	1.96
into_iter	1000	20.5±0.19µs	13.2±0.82µs	1.55
into_iter	10000	235.2±7.75µs	147.2±1.07µs	1.60
into_iter	100000	4.4±0.07ms	2.3±0.02ms	1.91
iter	1000	848.8±6.17ns	405.1±5.59ns	2.10
iter	10000	18.3±0.42µs	5.1±0.03µs	3.59
iter	100000	235.7±6.59µs	55.1±0.40µs	4.28
ordered_get	1000	221.5±2.02µs	213.1±1.81µs	1.04
ordered_get	10000	2.4±0.00ms	2.1±0.02ms	1.14
ordered_get	100000	25.8±0.07ms	22.2±0.02ms	1.16
ordered_remove	1000	231.5±2.46µs	311.2±4.56µs	0.74
ordered_remove	10000	2.4±0.00ms	3.2±0.02ms	0.75
ordered_remove	100000	26.2±0.67ms	34.5±0.92ms	0.76
random_get	1000	63.8±0.84µs	71.2±1.82µs	0.90
random_get	10000	1156.2±5.75µs	1464.0±11.94µs	0.79
random_get	100000	23.0±0.68ms	26.0±0.32ms	0.88
random_remove	1000	126.1±0.93µs	152.2±2.01µs	0.83
random_remove	10000	1764.6±30.54µs	2.2±0.00ms	0.80
random_remove	100000	30.7±0.11ms	37.2±0.19ms	0.83

String benchmark data with bulk_load

name	size	type	time
ordered_insert	1000	bptree	220.3±2.30µs
		bptree_bulk	173.1±2.14µs
		btree	268.3±11.22µs
ordered_insert	10000	bptree	2.4±0.07ms
		bptree_bulk	1736.9±16.15µs
		btree	3.0±0.00ms
ordered_insert	100000	bptree	25.5±0.11ms
		bptree_bulk	17.8±0.13ms
		btree	33.0±0.11ms
random_insert	1000	bptree	135.6±1.39µs
		bptree_sort_load	75.4±1.55µs
		btree	122.8±1.82µs
random_insert	10000	bptree	2.2±0.00ms
		bptree_sort_load	1449.7±14.30µs
		btree	1807.4±18.02µs
random_insert	100000	bptree	36.5±0.53ms
		bptree_sort_load	20.8±0.46ms
		btree	30.9±0.82ms