succinct/
space_usage.rs

1//! A trait for computing space usage.
2
3use std::mem;
4
5/// Computes the space usage of an object.
6///
7/// We calculate the space usage as split into two portions, the heap
8/// portion (returned by `heap_bytes` and the stack portion (returned by
9/// `stack_bytes`). The stack portion is the statically-known size for
10/// every object of its type as allocated on the stack; the dynamic
11/// portion is the additional heap allocation that may depend on
12/// run-time factors.
13///
14/// Examples:
15///
16///  - Primitive types like `u32` and `usize` are stack-only.
17///
18///  - A tuple or struct type is stack-only when all its components are.
19///    Its heap portion is the sum of their heap portions, but its stack
20///    portion may exceed the sum of their stack portions because of
21///    alignment and padding.
22///
23///  - The size of a vector includes a stack portion, the vector struct
24///    itself, and a heap portion, the array holding its elements. The
25///    heap portion of a vector includes the stack portions of its
26///    elements. (Should they be called something else for this reason? I
27///    considered static/dynamic, but `Box` shows why that doesn’t express
28///    exactly the right property.)
29
30pub trait SpaceUsage: Sized {
31    /// Computes the size of the receiver in bytes.
32    ///
33    /// This includes not just the immediate stack object, but any heap
34    /// memory that it owns.
35    ///
36    /// The default implementation returns
37    /// `Self::stack_bytes() + self.heap_bytes()`.
38    #[inline]
39    fn total_bytes(&self) -> usize {
40        Self::stack_bytes() + self.heap_bytes()
41    }
42
43    /// Is the size of this type known statically?
44    ///
45    /// If this method returns true then `heap_bytes` should always
46    /// return 0.
47    fn is_stack_only() -> bool;
48
49    /// Calculates the stack portion of the size of this type.
50    ///
51    /// This is the size of the immediate storage that all objects of
52    /// this type occupy; it excludes storage that objects of the
53    /// type might allocate dynamically.
54    ///
55    /// The default implementation returns `std::mem::size_of::<Self>()`.
56
57    #[inline]
58    fn stack_bytes() -> usize {
59        mem::size_of::<Self>()
60    }
61
62    /// Calculates the heap portion of the size of an object.
63    ///
64    /// This is the memory used by (or, rather, owned by) the object, not
65    /// including any portion of its size that is
66    /// included in `stack_bytes`. This is typically for containers
67    /// that heap allocate varying amounts of memory.
68    #[inline]
69    fn heap_bytes(&self) -> usize;
70}
71
72impl_stack_only_space_usage!(());
73impl_stack_only_space_usage!(u8);
74impl_stack_only_space_usage!(u16);
75impl_stack_only_space_usage!(u32);
76impl_stack_only_space_usage!(u64);
77impl_stack_only_space_usage!(usize);
78impl_stack_only_space_usage!(i8);
79impl_stack_only_space_usage!(i16);
80impl_stack_only_space_usage!(i32);
81impl_stack_only_space_usage!(i64);
82impl_stack_only_space_usage!(isize);
83impl_stack_only_space_usage!(f32);
84impl_stack_only_space_usage!(f64);
85
86impl<'a, T> SpaceUsage for &'a T {
87    fn is_stack_only() -> bool { true }
88    fn heap_bytes(&self) -> usize { 0 }
89}
90
91impl<'a, T> SpaceUsage for &'a [T] {
92    fn is_stack_only() -> bool { true }
93    fn heap_bytes(&self) -> usize { 0 }
94}
95
96macro_rules! impl_tuple_space_usage {
97    ( $( $tv:ident ),+ ) =>
98    {
99        impl<$( $tv: SpaceUsage ),+> SpaceUsage for ($( $tv, )+) {
100            #[allow(non_snake_case)]
101            fn heap_bytes(&self) -> usize {
102                let &($( ref $tv, )+) = self;
103                0 $( + $tv.heap_bytes() )+
104            }
105
106            #[inline]
107            fn is_stack_only() -> bool {
108                $( $tv::is_stack_only() )&*
109            }
110        }
111    }
112}
113
114impl_tuple_space_usage!(A);
115impl_tuple_space_usage!(A, B);
116impl_tuple_space_usage!(A, B, C);
117impl_tuple_space_usage!(A, B, C, D);
118impl_tuple_space_usage!(A, B, C, D, E);
119impl_tuple_space_usage!(A, B, C, D, E, F);
120impl_tuple_space_usage!(A, B, C, D, E, F, G);
121impl_tuple_space_usage!(A, B, C, D, E, F, G, H);
122impl_tuple_space_usage!(A, B, C, D, E, F, G, H, I);
123impl_tuple_space_usage!(A, B, C, D, E, F, G, H, I, J);
124impl_tuple_space_usage!(A, B, C, D, E, F, G, H, I, J, K);
125impl_tuple_space_usage!(A, B, C, D, E, F, G, H, I, J, K, L);
126
127impl<A: SpaceUsage + ::std::fmt::Debug> SpaceUsage for Vec<A> {
128    #[inline]
129    fn is_stack_only() -> bool { false }
130
131    fn heap_bytes(&self) -> usize {
132        let mut result = self.capacity() * A::stack_bytes();
133
134        if ! A::is_stack_only() {
135            for each in self {
136                result += each.heap_bytes();
137            }
138        }
139
140        result
141    }
142}
143
144impl<A: SpaceUsage> SpaceUsage for Box<A> {
145    #[inline]
146    fn is_stack_only() -> bool { false }
147
148    fn stack_bytes() -> usize {
149        mem::size_of::<Self>()
150    }
151
152    fn heap_bytes(&self) -> usize {
153        use std::ops::Deref;
154        self.deref().total_bytes()
155    }
156}
157
158#[cfg(test)]
159mod test {
160    use super::*;
161    use std::mem::size_of;
162
163    #[test]
164    fn is_stack_only() {
165        assert!(  u32::is_stack_only());
166        assert!(  isize::is_stack_only());
167        assert!(! Vec::<u64>::is_stack_only());
168        assert!(! Vec::<Vec<u64>>::is_stack_only());
169        assert!(  <(u32, u32, u32)>::is_stack_only());
170        assert!(! <(u32, Vec<u32>, u32)>::is_stack_only());
171    }
172
173    #[test]
174    fn int_size() {
175        assert_eq!(2, 0u16.total_bytes());
176        assert_eq!(4, 0u32.total_bytes());
177        assert_eq!(8, 0i64.total_bytes());
178    }
179
180    #[test]
181    fn tuple_size() {
182        assert_eq!(8, (0u32, 0u32).total_bytes());
183        // This isn’t guaranteed to work, but it does for now:
184        assert_eq!(12, (0u32, 0u8, 0u32).total_bytes());
185    }
186
187    #[test]
188    fn vec_size() {
189        let v = Vec::<u64>::with_capacity(8);
190        assert_eq!(8, v.capacity());
191        assert_eq!(64, v.heap_bytes());
192        assert_eq!(64 + size_of::<Vec<u64>>(),
193                   v.total_bytes());
194    }
195
196    #[test]
197    fn vec_vec_size() {
198        let v1 = Vec::<u64>::with_capacity(8);
199        let v2 = Vec::<u64>::with_capacity(8);
200        let w = vec![v1, v2];
201        assert_eq!(2, w.capacity());
202        assert_eq!(128 + 2 * size_of::<Vec<u64>>() +
203                      size_of::<Vec<Vec<u64>>>(),
204                   w.total_bytes());
205    }
206}
succinct/space_usage.rs

succinct/
space_usage.rs
