search

tikv / raft-engine

A persistent storage engine for Multi-Raft log
Apache License 2.0
565 stars 88 forks source link

Use BTreeMap for memtable put #171

Closed tabokie closed 2 years ago

tabokie commented 2 years ago

BTreeMap has better cache locality (and possibly fewer instructions involved) for single key put scenario. Micro benchmarks shows 6% improvement:

vanilla:
test memtable::tests::bench_memtable_single_put             ... bench:         101 ns/iter (+/- 39)
test memtable::tests::bench_memtable_single_put             ... bench:          99 ns/iter (+/- 31)
test memtable::tests::bench_memtable_triple_puts            ... bench:         317 ns/iter (+/- 15)
test memtable::tests::bench_memtable_triple_puts            ... bench:         317 ns/iter (+/- 19)

btreemap:
test memtable::tests::bench_memtable_single_put             ... bench:          93 ns/iter (+/- 9)
test memtable::tests::bench_memtable_single_put             ... bench:          94 ns/iter (+/- 13)
test memtable::tests::bench_memtable_triple_puts            ... bench:         311 ns/iter (+/- 56)
test memtable::tests::bench_memtable_triple_puts            ... bench:         313 ns/iter (+/- 41)
codecov[bot] commented 2 years ago

Codecov Report

Merging #171 (c2819fa) into master (e32e3e7) will increase coverage by 0.04%. The diff coverage is 100.00%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master     #171      +/-   ##
==========================================
+ Coverage   96.98%   97.02%   +0.04%     
==========================================
  Files          26       26              
  Lines        6592     6619      +27     
==========================================
+ Hits         6393     6422      +29     
+ Misses        199      197       -2
Impacted Files Coverage Δ
src/lib.rs 100.00% <ø> (ø)
src/config.rs 94.28% <100.00%> (+0.28%) :arrow_up:
src/memtable.rs 99.51% <100.00%> (+<0.01%) :arrow_up:
src/codec.rs 98.67% <0.00%> (+0.33%) :arrow_up:
src/consistency.rs 93.33% <0.00%> (+2.22%) :arrow_up:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update e59cb35...c2819fa. Read the comment docs.