embed-btree 0.3.0

Cpu-cache aware b+tree with extened cursor/entry API
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

#![allow(rustdoc::redundant_explicit_links)]
#![cfg_attr(docsrs, feature(doc_cfg))]
#![cfg_attr(docsrs, allow(unused_attributes))]
#![cfg_attr(not(feature = "std"), no_std)]
//! ### embed-btree
//!
//! We provide a `BTreeMap` for single-threaded long-term in-memory storage.
//! It's a cache aware b+tree:
//!
//! - Being B+Tree, the leaves are linked, provide faster iteration and teardown.
//! - Nodes are filled up in 4 cache lines (256 bytes on x86_64).
//!   - Capacity in compile-time determined according to the size of Key, Value.
//!   - Reduce memory fragmentation by alignment.
//! - **Optimised for numeric key**
//!   - Respecting numeric space for sequential insertion.
//!   - Reduce latency for sequential insertion.
//! - Bytes keys on the heap are supported, but we will not do prefix compress.
//! - Support unbalanced size K / V, and 0-size V, will fill the space (to increase fanout) as much as it could.
//! - **Limitation**:
//!   - K should have clone (for propagate into the InterNode during split)
//!   - K & V should <= CACHE_LINE_SIZE - 16
//!     - It make sure InterNode can hold at least two children.
//!     - If K & V is large you should put into `Box`, for room saving, and for the speed to move value
//! - **Special API**:
//!   - Peak and move to previous/next `Entry` (for modification).
//!   - Alter key of an OccupiedEntry.
//!   - Batch remove with range.
//!   - Movable `Cursor` (for readonly)
//!
//! Compared to std::collections::btree (as of rust 1.94):
//! - The std impl is pure btree (not b+tree) without horizontal links. Each key store only once at either leaf and inter nodes.
//! - The std impl is optimised for point lookup.
//! - 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)
//! - The std cursor API is still unstable (as of 1.94) and relatively complex to use.
//!
//! **benchmark**
//!
//! platform: intel i7-8550U, key: u32, value: u32, rust 1.97.
//!
//! Measured in million ops for different size of dataset:
//!
//! insert_seq |btree|std
//! -|-|-
//! 1k|**104.68**|20.001
//! 10k|**90.206**|16.04
//! 1m|**50.454**|11.207
//!
//! insert_rand|btree|std|avl(box)|avl(arc)
//! -|-|-|-|-
//! 1k|**23.325**|17.792|11.172|9.5397
//! 10k|**14.949**|11.587|6.3669|5.651
//! 1M|**6.1205**|3.0691|0.78|0.732
//!
//! get_seq|btree|std
//! -|-|-
//! 1k|**56.462**|34.248
//! 10k|**40.265**|27.571
//! 1M|**31.384**|19.907
//!
//! get_rand|btree|std|avl(box)|avl(arc)
//! -|-|-|-|-
//! 1k|**49.961**|27.651|24.254|23.466
//! 10k|**20.223**|16.868|11.771|10.806
//! 1M|**6.0508**|3.2569|1.4423|1.2712
//!
//! remove_rand |btree|std
//! -|-|-
//! 1k|**19.963**|15.968
//! 10k|**15.462**|11.701
//! 1M|**5.4713**|3.0724
//!
//! iter|btree|std
//! -|-|-
//! 1k|1443.2|346.8
//! 10k|1286.9|303.83
//! 1M|**215.95**|51.147
//!
//! into_iter|btree|std
//! -|-|-
//! 1k|396.07|143.81
//! 10k|410.32|81.389
//! 1M|**360.18**|56.742

extern crate alloc;
#[cfg(any(feature = "std", test))]
extern crate std;

#[allow(private_interfaces)]
pub mod various_map;
pub use various_map::VariousMap;
pub mod btree;
pub use btree::BTreeMap;
pub use embed_collections::CACHE_LINE_SIZE;

/// logging macro for development
#[macro_export(local_inner_macros)]
macro_rules! trace_log {
    ($($arg:tt)+)=>{
        #[cfg(feature="trace_log")]
        {
            log::debug!($($arg)+);
        }
    };
}

/// logging macro for development
#[macro_export(local_inner_macros)]
macro_rules! print_log {
    ($($arg:tt)+)=>{
        #[cfg(feature="trace_log")]
        {
            log::debug!($($arg)+);
        }
        #[cfg(not(feature="trace_log"))]
        {
            std::println!($($arg)+);
        }
    };
}