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//! - Being B+Tree, the leaves are linked, provide faster iteration and teardown.
11//! - Nodes are filled up in 4 cache lines (256 bytes on x86_64).
12//!   - Capacity in compile-time determined according to the size of Key, Value.
13//!   - Reduce memory fragmentation by alignment.
14//! - **Optimised for numeric key**
15//!   - Respecting numeric space for sequential insertion.
16//!   - Reduce latency for sequential insertion.
17//! - Bytes keys on the heap are supported, but we will not do prefix compress.
18//! - Support unbalanced size K / V, and 0-size V, will fill the space (to increase fanout) as much as it could.
19//! - **Limitation**:
20//!   - K should have clone (for propagate into the InterNode during split)
21//!   - K & V should <= CACHE_LINE_SIZE - 16
22//!     - It make sure InterNode can hold at least two children.
23//!     - If K & V is large you should put into `Box`, for room saving, and for the speed to move value
24//! - **Special API**:
25//!   - Peak and move to previous/next `Entry` (for modification).
26//!   - Alter key of an OccupiedEntry.
27//!   - Batch remove with range.
28//!   - Movable `Cursor` (for readonly)
29//!
30//! Compared to std::collections::btree (as of rust 1.94):
31//! - The std impl is pure btree (not b+tree) without horizontal links. Each key store only once at either leaf and inter nodes.
32//! - The std impl is optimised for point lookup.
33//! - 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)
34//! - The std cursor API is still unstable (as of 1.94) and relatively complex to use.
35//!
36//! **benchmark**
37//!
38//! platform: intel i7-8550U, key: u32, value: u32, rust 1.97.
39//!
40//! Measured in million ops for different size of dataset:
41//!
42//! insert_seq |btree|std
43//! -|-|-
44//! 1k|**104.68**|20.001
45//! 10k|**90.206**|16.04
46//! 1m|**50.454**|11.207
47//!
48//! insert_rand|btree|std|avl(box)|avl(arc)
49//! -|-|-|-|-
50//! 1k|**23.325**|17.792|11.172|9.5397
51//! 10k|**14.949**|11.587|6.3669|5.651
52//! 1M|**6.1205**|3.0691|0.78|0.732
53//!
54//! get_seq|btree|std
55//! -|-|-
56//! 1k|**56.462**|34.248
57//! 10k|**40.265**|27.571
58//! 1M|**31.384**|19.907
59//!
60//! get_rand|btree|std|avl(box)|avl(arc)
61//! -|-|-|-|-
62//! 1k|**49.961**|27.651|24.254|23.466
63//! 10k|**20.223**|16.868|11.771|10.806
64//! 1M|**6.0508**|3.2569|1.4423|1.2712
65//!
66//! remove_rand |btree|std
67//! -|-|-
68//! 1k|**19.963**|15.968
69//! 10k|**15.462**|11.701
70//! 1M|**5.4713**|3.0724
71//!
72//! iter|btree|std
73//! -|-|-
74//! 1k|1443.2|346.8
75//! 10k|1286.9|303.83
76//! 1M|**215.95**|51.147
77//!
78//! into_iter|btree|std
79//! -|-|-
80//! 1k|396.07|143.81
81//! 10k|410.32|81.389
82//! 1M|**360.18**|56.742
83
84extern crate alloc;
85#[cfg(any(feature = "std", test))]
86extern crate std;
87
88#[allow(private_interfaces)]
89pub mod various_map;
90pub use various_map::VariousMap;
91pub mod btree;
92pub use btree::BTreeMap;
93pub use embed_collections::CACHE_LINE_SIZE;
94
95/// logging macro for development
96#[macro_export(local_inner_macros)]
97macro_rules! trace_log {
98    ($($arg:tt)+)=>{
99        #[cfg(feature="trace_log")]
100        {
101            log::debug!($($arg)+);
102        }
103    };
104}
105
106/// logging macro for development
107#[macro_export(local_inner_macros)]
108macro_rules! print_log {
109    ($($arg:tt)+)=>{
110        #[cfg(feature="trace_log")]
111        {
112            log::debug!($($arg)+);
113        }
114        #[cfg(not(feature="trace_log"))]
115        {
116            std::println!($($arg)+);
117        }
118    };
119}
embed_btree/lib.rs

embed_btree/
lib.rs
