# Embed Collections
docs.rs: <https://docs.rs/embed-collections/latest/embed_collections/>
## embed-collections
A collection of memory efficient data structures, for embedding environment and server applications that need tight memory management.
This repo consists some small crates.
**NOTE: There nothing in the main crate, all modules have moved to sub crates**.
### Cache efficient collections
- [embed-constvec](https://docs.rs/embed-constvec): Fixed capacity inline vec
- [embed-seglist](https://docs.rs/embed-seglist): A cache aware (short-live) list to store elements with adaptive size segments
- [embed-btree](https://docs.rs/embed-btree): A cache aware B+tree for lone-live and large dataset, optimized for numeric types, with special entry API allows peeking adjacent values.
### Intrusive collections:
We support all-types from the [pointers](https://docs.rs/pointers) crate,
with `Pointer` trait for intrusive collections:
- raw pointers (`NonNull<T>`, `*const T`, `*mut T`)
- std `Box` (owned),
- std `Arc`, `Rc` (multiple ownership)
- `Irc`: Highly customizable Intrusive Reference Counter.
- [WaitGroupZeroGuard](https://docs.rs/crossfire/latest/crossfire/waitgroup/struct.WaitGroupZeroGuard.html): see the doc in `crossfire` crate
Sub crates:
- [embed-dlist](https://docs.rs/embed-dlist): Intrusive Doubly Linked List (Queue / Stack).
- [embed-slist](https://docs.rs/embed-slist): Intrusive Singly Linked List ( Queue / stack).
- [embed-avl](https://docs.rs/embed-avl): Intrusive AVL Tree (Balanced Binary Search Tree), port to rust from ZFS
**Disclaimer**
Intrusive code is not recommended unless you are full aware of what you are doing.
Most traits are mark with `unsafe`. While we try to give you freedom, not letting the rules probibit
you build highly customized logic, this library still has regular scheduled Miri test routine.
But the disadvantages includes:
- Complex to write (This crate seal most boilderplates)
- Linking heap object to another is bad for cache hit (Use structure like `SegList` is preferable)
There're three usage scenarios:
1. Push smart pointer to the list, so that the list hold 1 ref count when the type is `Arc` /
`Rc`, but you have to use UnsafeCell for internal mutation.
2. Push `Box` to the list, the list own the items until they are popped, it's better than std
LinkedList because no additional allocation is needed. It will not move the item
in-and-out of hidden `Box` on every push / pop.
3. Push raw pointer (better use NonNull instead of *const T for smaller footprint) to the list,
for temporary usage. You must ensure the list item not dropped be other refcount
(for example, the item is holding by Arc in other structure).
#### Difference to `intrusive-collections` crate
This crate choose to use trait instead of c like `offset_of!`, mainly because:
- Mangling with offset conversion makes the code hard to read (for people not used to c style coding).
- You don't have to understand some complex macro style.
- It's dangerous to use pointer offset conversion when the embedded Node not perfectly aligned,
and using memtion to return the node ref is more safer approach.
For example, the default `repr(Rust)` might reorder the field, or you mistakenly use `repr(packed)`.
### SegList & Various
crate: [embed-seglist](https://docs.rs/embed-seglist)
`SegList` and `Various` is designed for parameter passing.
More CPU-cache friendly compared to `LinkedList`. And because it does not re-allocate, it's faster than `Vec::push()` when the number of elements is small.
It's nice to the memory allocator (always allocate with fixed size segment).
Benchmark: append + drain (x86_64, cache line 128 bytes):
(platform: intel i7-8550U)
| 10 | 40.5 ns | 147.0 ns | **3.6x faster** |
| 32 | 99.1 ns | 237.8 ns | **2.4x faster** |
| 100 | 471.1 ns | 464.0 ns | ~1.0x |
| 500 | 2.77 µs | 895.5 ns | 3.1x slower |
### embed-btree
crate: [embed-btree](https://docs.rs/embed-btree)
We provide a `BTreeMap` for single-threaded long-term in-memory storage.
It's a cache aware b+tree:
- 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.
- Faster iteration and teardown
- **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.92.
Measured in million ops for different size of dataset:
insert_seq |btree|std
10k|**75.291**|16.04
100k|**45.959**|11.207
insert_rand|btree|std|avl(box)|avl(arc)
10k|**14.268**|11.587|6.3669|5.651
100k|**5.4814**|3.0691|0.78|0.732
get_seq|btree|std
10k|**37.225**|27.571
100k|**30.77**|19.907
get_rand|btree|std|avl(box)|avl(arc)
10k|**19.358**|16.868|11.771|10.806
100k|**5.2584**|3.2569|1.4423|1.2712
remove_rand |btree|std
10k|**16.073**|11.701
100k|**5.0214**|3.0724
1k|1342.8|346.8
10k|1209.4|303.83
100k|**152.57**|51.147
into_iter|btree|std
10k|397.05|81.389
100k|**360.18**|56.742
#### instrusive link list example
```rust
use embed_dlist::{DLinkedList, DListItem, DListNode};
use pointers::Pointer;
use std::cell::UnsafeCell;
use std::sync::Arc;
// The tag structure only for labeling, distinguish two lists
struct CacheTag;
struct IOTag;
struct MyItem {
val: i32,
cache_link: UnsafeCell<DListNode<MyItem, CacheTag>>,
io_link: UnsafeCell<DListNode<MyItem, IOTag>>,
}
impl MyItem {
fn new(val: i32) -> Self {
Self {
val,
cache_link: UnsafeCell::new(DListNode::default()),
io_link: UnsafeCell::new(DListNode::default()),
}
}
}
unsafe impl DListItem<CacheTag> for MyItem {
fn get_node(&self) -> &mut DListNode<Self, CacheTag> {
unsafe { &mut *self.cache_link.get() }
}
}
unsafe impl DListItem<IOTag> for MyItem {
fn get_node(&self) -> &mut DListNode<Self, IOTag> {
unsafe { &mut *self.io_link.get() }
}
}
let mut cache_list = DLinkedList::<Arc<MyItem>, CacheTag>::new();
let mut io_list = DLinkedList::<Arc<MyItem>, IOTag>::new();
let item1 = Arc::new(MyItem::new(10));
let item2 = Arc::new(MyItem::new(20));
// Push the same item to both lists
cache_list.push_back(item1.clone());
io_list.push_back(item1.clone());
cache_list.push_back(item2.clone());
io_list.push_back(item2.clone());
assert_eq!(cache_list.pop_front().unwrap().val, 10);
assert_eq!(io_list.pop_front().unwrap().val, 10);
assert_eq!(cache_list.pop_front().unwrap().val, 20);
assert_eq!(io_list.pop_front().unwrap().val, 20);
```