ts_bart/node/
child_storage.rs

1use alloc::boxed::Box;
2
3/// Generic data storage mechanism.
4///
5/// Currently an abstraction over [`Box`] storage (much more memory-efficient)
6/// and inlined structs (sometimes faster).
7///
8/// The particular structure of the trait (GAT for container type) is needed to
9/// enable the storage type to not carry a parameter, e.g. `Node<T,
10/// InlineStorage>` (rather than `Node<T, InlineStorage<T>>`). This is desirable
11/// to make type inference and trait derivation much more straightforward.
12pub trait Storage {
13    /// The container type used to hold the value type.
14    type Container<T>;
15
16    /// Construct a new container.
17    fn new<T>(t: T) -> Self::Container<T>;
18    /// Destruct the container to retrieve the contained value.
19    fn into_inner<T>(container: Self::Container<T>) -> T;
20    /// Retrieve a reference to the contained value.
21    fn as_ref<T>(container: &Self::Container<T>) -> &T;
22    /// Retrieve a mutable reference to the contained value.
23    fn as_mut<T>(container: &mut Self::Container<T>) -> &mut T;
24    /// Clone the container.
25    fn clone<T>(container: &Self::Container<T>) -> Self::Container<T>
26    where
27        T: Clone;
28}
29
30/// [`Storage`] that stores values inline.
31#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
32pub enum InlineStorage {}
33
34/// [`Storage`] that stores values in boxes.
35///
36/// # Memory Efficiency
37///
38/// Vastly more memory-efficient than inline storage: `heaptrack` suggests on the order of 5x
39/// better.
40///
41/// Notably, `size_of::<Box<T>>()` is always a single `usize`, while an inline `Node` is 2
42/// `Array256`es, which are comparatively large (256-bit bitset + vec -> ~7x larger up to alignment
43/// on a 64-bit arch). Suspect the large overhead for inline storage is mostly due to the
44/// powers-of-two oversizing of the `Node::children` Vec storage: this is going to be costly in
45/// direct proportion to the size of the contained value.
46#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
47pub enum BoxStorage {}
48
49impl Storage for InlineStorage {
50    type Container<T> = T;
51
52    #[inline]
53    fn new<T>(t: T) -> Self::Container<T> {
54        t
55    }
56
57    #[inline]
58    fn into_inner<T>(container: Self::Container<T>) -> T {
59        container
60    }
61
62    #[inline]
63    fn as_ref<T>(container: &Self::Container<T>) -> &T {
64        container
65    }
66
67    #[inline]
68    fn as_mut<T>(container: &mut Self::Container<T>) -> &mut T {
69        container
70    }
71
72    #[inline]
73    fn clone<T>(container: &Self::Container<T>) -> Self::Container<T>
74    where
75        T: Clone,
76    {
77        container.clone()
78    }
79}
80
81impl Storage for BoxStorage {
82    type Container<T> = Box<T>;
83
84    #[inline]
85    fn new<T>(t: T) -> Self::Container<T> {
86        Box::new(t)
87    }
88
89    #[inline]
90    fn into_inner<T>(container: Self::Container<T>) -> T {
91        *container
92    }
93
94    #[inline]
95    fn as_ref<T>(container: &Self::Container<T>) -> &T {
96        container.as_ref()
97    }
98
99    #[inline]
100    fn as_mut<T>(container: &mut Self::Container<T>) -> &mut T {
101        container.as_mut()
102    }
103
104    #[inline]
105    fn clone<T>(container: &Self::Container<T>) -> Self::Container<T>
106    where
107        T: Clone,
108    {
109        container.clone()
110    }
111}
ts_bart/node/child_storage.rs

ts_bart/node/
child_storage.rs
