embed_btree/
lib.rs

1#![allow(rustdoc::redundant_explicit_links)]
2#![cfg_attr(docsrs, feature(doc_cfg))]
3#![cfg_attr(docsrs, allow(unused_attributes))]
4#![cfg_attr(not(feature = "std"), no_std)]
5//! ### embed-btree
6//!
7//! We provide a `BTreeMap` for single-threaded long-term in-memory storage.
8//! It's a cache aware b+tree:
9//!
10//! - Nodes are filled up in 4 cache lines (256 bytes on x86_64).
11//!   - Capacity in compile-time determined according to the size of Key, Value.
12//!   - Reduce memory fragmentation by alignment.
13//! - **Optimised for numeric key**
14//!   - Respecting numeric space for sequential insertion.
15//!   - Reduce latency for sequential insertion.
16//! - Faster iteration and teardown
17//! - **Limitation**:
18//!   - K should have clone (for propagate into the InterNode during split)
19//!   - K & V should <= CACHE_LINE_SIZE - 16
20//!     - It make sure InterNode can hold  at least two children.
21//!     - If K & V is large you should put into `Box`, for room saving, and for the speed to move value
22//! - **Special API**:
23//!   - Peak and move to previous/next `Entry` (for modification).
24//!   - Alter key of an OccupiedEntry.
25//!   - Batch remove with range.
26//!   - Movable `Cursor` (for readonly)
27//!
28//! Compared to std::collections::btree (as of rust 1.94):
29//! - The std impl is pure btree (not b+tree) without horizontal links. Each key store only once at either leaf and inter nodes.
30//! - The std impl is optimised for point lookup.
31//! - The std impl has fixed Cap=11, node size varies according to T. (For T=U64, size is 288B for InterNode and 192B for LeafNode)
32//! - The std cursor API is still unstable (as of 1.94) and relatively complex to use.
33//!
34//! **benchmark**
35//!
36//! platform: intel i7-8550U, key: u32, value: u32, rust 1.92.
37//!
38//! Measured in million ops for different size of dataset:
39//!
40//! insert_seq |btree|std
41//! -|-|-
42//! 1k|**88.956**|20.001
43//! 10k|**75.291**|16.04
44//! 100k|**45.959**|11.207
45//!
46//! insert_rand|btree|std|avl(box)|avl(arc)
47//! -|-|-|-|-
48//! 1k|**21.311**|17.792|11.172|9.5397
49//! 10k|**14.268**|11.587|6.3669|5.651
50//! 100k|**5.4814**|3.0691|0.78|0.732
51//!
52//! get_seq|btree|std
53//! -|-|-
54//! 1k|**59.448**|34.248
55//! 10k|**37.225**|27.571
56//! 100k|**30.77**|19.907
57//!
58//! get_rand|btree|std|avl(box)|avl(arc)
59//! -|-|-|-|-
60//! 1k|**47.33**|27.651|24.254|23.466
61//! 10k|**19.358**|16.868|11.771|10.806
62//! 100k|**5.2584**|3.2569|1.4423|1.2712
63//!
64//! remove_rand |btree|std
65//! -|-|-
66//! 1k|**20.965**|15.968
67//! 10k|**16.073**|11.701
68//! 100k|**5.0214**|3.0724
69//!
70//! iter|btree|std
71//! -|-|-
72//! 1k|1342.8|346.8
73//! 10k|1209.4|303.83
74//! 100k|**152.57**|51.147
75//!
76//! into_iter|btree|std
77//! -|-|-
78//! 1k|396.07|143.81
79//! 10k|397.05|81.389
80//! 100k|**360.18**|56.742
81
82extern crate alloc;
83#[cfg(any(feature = "std", test))]
84extern crate std;
85
86#[allow(private_interfaces)]
87pub mod various_map;
88pub use various_map::VariousMap;
89pub mod btree;
90pub use btree::BTreeMap;
91pub use embed_collections::CACHE_LINE_SIZE;
92
93/// logging macro for development
94#[macro_export(local_inner_macros)]
95macro_rules! trace_log {
96    ($($arg:tt)+)=>{
97        #[cfg(feature="trace_log")]
98        {
99            log::debug!($($arg)+);
100        }
101    };
102}
103
104/// logging macro for development
105#[macro_export(local_inner_macros)]
106macro_rules! print_log {
107    ($($arg:tt)+)=>{
108        #[cfg(feature="trace_log")]
109        {
110            log::debug!($($arg)+);
111        }
112        #[cfg(not(feature="trace_log"))]
113        {
114            std::println!($($arg)+);
115        }
116    };
117}
embed_btree/lib.rs

embed_btree/
lib.rs
