concinnity_memory/
inline_vec.rs

1// concinnity-memory/src/inline_vec.rs
2//
3// A sequence that keeps its first element inline.
4//
5// Some populations hold exactly one item almost everywhere: an entity's draw
6// slots (one per mesh, and most props are one mesh), a parent's children. A
7// `Vec` charges each of those a heap block -- twenty thousand entities, twenty
8// thousand blocks of four bytes -- and a pointer chase to reach it on every
9// frame that walks them. Holding the first element inline removes both for the
10// common case while keeping the heap for the rest, so a caller does not have to
11// know which case it is in.
12//
13// Capacity one rather than a general N: one is expressible as an enum, which is
14// why this file contains no `unsafe`. A general inline capacity needs
15// `MaybeUninit` and a hand-written drop, and nothing has asked for it.
16//
17// Equality and ordering read the contents, never the representation: a
18// one-element inline value equals a one-element spilled one.
19
20use alloc::vec::Vec;
21use core::fmt;
22use core::ops::{Deref, DerefMut};
23
24/// A sequence holding its first element inline and spilling to the heap beyond
25/// that.
26///
27/// Derefs to `[T]`, so slice methods (`iter`, `len`, `contains`, indexing) are
28/// available directly.
29///
30/// Spilled storage is kept once acquired: removing elements does not move the
31/// remainder back inline, so a value that has grown never silently reallocates
32/// when it shrinks.
33pub struct InlineVec<T>(Repr<T>);
34
35#[derive(Clone)]
36enum Repr<T> {
37    Empty,
38    One(T),
39    Spilled(Vec<T>),
40}
41
42impl<T> InlineVec<T> {
43    /// An empty sequence, holding no allocation.
44    pub const fn new() -> Self {
45        Self(Repr::Empty)
46    }
47
48    /// A sequence holding exactly `value`, inline.
49    pub const fn one(value: T) -> Self {
50        Self(Repr::One(value))
51    }
52
53    // Whether the contents live on the heap rather than inline.
54    #[cfg(test)]
55    pub(crate) fn spilled(&self) -> bool {
56        matches!(self.0, Repr::Spilled(_))
57    }
58
59    /// The contents as a slice.
60    pub fn as_slice(&self) -> &[T] {
61        match &self.0 {
62            Repr::Empty => &[],
63            Repr::One(value) => core::slice::from_ref(value),
64            Repr::Spilled(values) => values,
65        }
66    }
67
68    /// The contents as a mutable slice.
69    pub fn as_mut_slice(&mut self) -> &mut [T] {
70        match &mut self.0 {
71            Repr::Empty => &mut [],
72            Repr::One(value) => core::slice::from_mut(value),
73            Repr::Spilled(values) => values,
74        }
75    }
76
77    /// Append `value`, spilling to the heap if this is the second element.
78    pub fn push(&mut self, value: T) {
79        match &mut self.0 {
80            Repr::Empty => self.0 = Repr::One(value),
81            Repr::Spilled(values) => values.push(value),
82            Repr::One(_) => {
83                let Repr::One(first) = core::mem::replace(&mut self.0, Repr::Empty) else {
84                    unreachable!("the arm above matched One")
85                };
86                self.0 = Repr::Spilled(alloc::vec![first, value]);
87            }
88        }
89    }
90
91    /// Remove and return the last element, or `None` when empty.
92    pub fn pop(&mut self) -> Option<T> {
93        match &mut self.0 {
94            Repr::Empty => None,
95            Repr::Spilled(values) => values.pop(),
96            Repr::One(_) => match core::mem::replace(&mut self.0, Repr::Empty) {
97                Repr::One(value) => Some(value),
98                _ => unreachable!("the arm above matched One"),
99            },
100        }
101    }
102
103    /// Drop every element for which `keep` returns false.
104    pub fn retain(&mut self, mut keep: impl FnMut(&T) -> bool) {
105        match &mut self.0 {
106            Repr::Empty => {}
107            Repr::Spilled(values) => values.retain(|value| keep(value)),
108            Repr::One(value) => {
109                if !keep(value) {
110                    self.0 = Repr::Empty;
111                }
112            }
113        }
114    }
115
116    /// Drop every element and release any heap storage.
117    pub fn clear(&mut self) {
118        self.0 = Repr::Empty;
119    }
120
121    // The contents as an owned `Vec`, allocating when they were held inline.
122    pub(crate) fn into_vec(self) -> Vec<T> {
123        match self.0 {
124            Repr::Empty => Vec::new(),
125            Repr::One(value) => alloc::vec![value],
126            Repr::Spilled(values) => values,
127        }
128    }
129}
130
131impl<T> Default for InlineVec<T> {
132    fn default() -> Self {
133        Self::new()
134    }
135}
136
137impl<T: Clone> Clone for InlineVec<T> {
138    fn clone(&self) -> Self {
139        Self(self.0.clone())
140    }
141}
142
143impl<T> Deref for InlineVec<T> {
144    type Target = [T];
145
146    fn deref(&self) -> &[T] {
147        self.as_slice()
148    }
149}
150
151impl<T> DerefMut for InlineVec<T> {
152    fn deref_mut(&mut self) -> &mut [T] {
153        self.as_mut_slice()
154    }
155}
156
157// Contents, not representation: `One(x)` and `Spilled(vec![x])` hold the same
158// sequence and must not be distinguishable.
159impl<T: PartialEq> PartialEq for InlineVec<T> {
160    fn eq(&self, other: &Self) -> bool {
161        self.as_slice() == other.as_slice()
162    }
163}
164
165impl<T: Eq> Eq for InlineVec<T> {}
166
167impl<T: PartialEq<U>, U, const N: usize> PartialEq<[U; N]> for InlineVec<T> {
168    fn eq(&self, other: &[U; N]) -> bool {
169        self.as_slice() == other.as_slice()
170    }
171}
172
173impl<T: PartialEq<U>, U> PartialEq<[U]> for InlineVec<T> {
174    fn eq(&self, other: &[U]) -> bool {
175        self.as_slice() == other
176    }
177}
178
179impl<T: PartialEq<U>, U> PartialEq<Vec<U>> for InlineVec<T> {
180    fn eq(&self, other: &Vec<U>) -> bool {
181        self.as_slice() == other.as_slice()
182    }
183}
184
185impl<T: fmt::Debug> fmt::Debug for InlineVec<T> {
186    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
187        self.as_slice().fmt(f)
188    }
189}
190
191impl<T> From<Vec<T>> for InlineVec<T> {
192    // Normalizes: a `Vec` of at most one element gives up its allocation.
193    fn from(values: Vec<T>) -> Self {
194        let mut values = values;
195        match values.len() {
196            0 => Self::new(),
197            1 => Self(Repr::One(values.pop().expect("length is one"))),
198            _ => Self(Repr::Spilled(values)),
199        }
200    }
201}
202
203impl<T, const N: usize> From<[T; N]> for InlineVec<T> {
204    fn from(values: [T; N]) -> Self {
205        values.into_iter().collect()
206    }
207}
208
209impl<T> From<InlineVec<T>> for Vec<T> {
210    fn from(inline: InlineVec<T>) -> Self {
211        inline.into_vec()
212    }
213}
214
215impl<T> FromIterator<T> for InlineVec<T> {
216    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
217        let mut iter = iter.into_iter();
218        let Some(first) = iter.next() else {
219            return Self::new();
220        };
221        let Some(second) = iter.next() else {
222            return Self(Repr::One(first));
223        };
224        let mut values = Vec::with_capacity(iter.size_hint().0 + 2);
225        values.push(first);
226        values.push(second);
227        values.extend(iter);
228        Self(Repr::Spilled(values))
229    }
230}
231
232impl<T> Extend<T> for InlineVec<T> {
233    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
234        for value in iter {
235            self.push(value);
236        }
237    }
238}
239
240/// By-value iterator over an [`InlineVec`], produced by `into_iter`.
241pub enum IntoIter<T> {
242    #[doc(hidden)]
243    Inline(core::option::IntoIter<T>),
244    #[doc(hidden)]
245    Spilled(alloc::vec::IntoIter<T>),
246}
247
248impl<T> Iterator for IntoIter<T> {
249    type Item = T;
250
251    fn next(&mut self) -> Option<T> {
252        match self {
253            Self::Inline(iter) => iter.next(),
254            Self::Spilled(iter) => iter.next(),
255        }
256    }
257
258    fn size_hint(&self) -> (usize, Option<usize>) {
259        match self {
260            Self::Inline(iter) => iter.size_hint(),
261            Self::Spilled(iter) => iter.size_hint(),
262        }
263    }
264}
265
266impl<T> ExactSizeIterator for IntoIter<T> {}
267
268impl<T> IntoIterator for InlineVec<T> {
269    type Item = T;
270    type IntoIter = IntoIter<T>;
271
272    fn into_iter(self) -> IntoIter<T> {
273        match self.0 {
274            Repr::Empty => IntoIter::Inline(None.into_iter()),
275            Repr::One(value) => IntoIter::Inline(Some(value).into_iter()),
276            Repr::Spilled(values) => IntoIter::Spilled(values.into_iter()),
277        }
278    }
279}
280
281impl<'a, T> IntoIterator for &'a InlineVec<T> {
282    type Item = &'a T;
283    type IntoIter = core::slice::Iter<'a, T>;
284
285    fn into_iter(self) -> core::slice::Iter<'a, T> {
286        self.as_slice().iter()
287    }
288}
289
290impl<'a, T> IntoIterator for &'a mut InlineVec<T> {
291    type Item = &'a mut T;
292    type IntoIter = core::slice::IterMut<'a, T>;
293
294    fn into_iter(self) -> core::slice::IterMut<'a, T> {
295        self.as_mut_slice().iter_mut()
296    }
297}
298
299#[cfg(test)]
300mod tests {
301    use super::*;
302    use alloc::vec;
303
304    #[test]
305    fn an_empty_value_holds_nothing_inline() {
306        let empty = InlineVec::<u32>::new();
307        assert!(empty.is_empty());
308        assert_eq!(empty.len(), 0);
309        assert!(!empty.spilled());
310        assert_eq!(empty.as_slice(), &[] as &[u32]);
311    }
312
313    // The whole point: the common case must not reach the heap.
314    #[test]
315    fn a_single_element_stays_inline() {
316        let mut one = InlineVec::new();
317        one.push(7u32);
318        assert!(!one.spilled(), "one element must not allocate");
319        assert_eq!(one.as_slice(), [7]);
320        assert_eq!(InlineVec::one(7u32).as_slice(), [7]);
321    }
322
323    #[test]
324    fn a_second_element_spills_to_the_heap_in_order() {
325        let mut many = InlineVec::new();
326        many.push(1u32);
327        many.push(2);
328        many.push(3);
329        assert!(many.spilled());
330        assert_eq!(many.as_slice(), [1, 2, 3]);
331    }
332
333    #[test]
334    fn collecting_picks_the_representation_from_the_length() {
335        let none: InlineVec<u32> = core::iter::empty().collect();
336        assert!(none.is_empty() && !none.spilled());
337
338        let one: InlineVec<u32> = core::iter::once(5).collect();
339        assert!(!one.spilled());
340        assert_eq!(one.as_slice(), [5]);
341
342        let many: InlineVec<u32> = (0..4).collect();
343        assert!(many.spilled());
344        assert_eq!(many.as_slice(), [0, 1, 2, 3]);
345    }
346
347    // A `Vec` handed in gives up an allocation it no longer needs, so a caller
348    // building through `Vec` is not stuck with the block forever.
349    #[test]
350    fn a_short_vec_gives_up_its_allocation() {
351        assert!(!InlineVec::from(vec![9u32]).spilled());
352        assert!(InlineVec::from(vec![9u32, 10]).spilled());
353        assert!(!InlineVec::<u32>::from(vec![]).spilled());
354        assert_eq!(InlineVec::from(vec![9u32, 10]).as_slice(), [9, 10]);
355    }
356
357    // Equality is over contents. Both representations can hold one element, and
358    // a caller must never be able to tell which it got.
359    #[test]
360    fn the_two_representations_compare_equal_on_equal_contents() {
361        let inline = InlineVec::one(4u32);
362        let mut spilled = InlineVec::new();
363        spilled.push(4u32);
364        spilled.push(5);
365        spilled.pop();
366
367        assert!(spilled.spilled() && !inline.spilled());
368        assert_eq!(inline, spilled);
369        assert_eq!(
370            alloc::format!("{inline:?}"),
371            alloc::format!("{spilled:?}"),
372            "the representation must not show in Debug"
373        );
374    }
375
376    #[test]
377    fn retain_drops_the_inline_element_and_filters_the_spilled_one() {
378        let mut one = InlineVec::one(1u32);
379        one.retain(|&v| v != 1);
380        assert!(one.is_empty());
381
382        let mut many: InlineVec<u32> = (0..6).collect();
383        many.retain(|v| v % 2 == 0);
384        assert_eq!(many.as_slice(), [0, 2, 4]);
385    }
386
387    // Documented behaviour: shrinking keeps the block rather than reallocating.
388    #[test]
389    fn a_shrunk_value_keeps_its_heap_storage_until_cleared() {
390        let mut many: InlineVec<u32> = (0..3).collect();
391        many.retain(|&v| v == 0);
392        assert!(many.spilled());
393        assert_eq!(many.as_slice(), [0]);
394
395        many.clear();
396        assert!(!many.spilled());
397        assert!(many.is_empty());
398    }
399
400    #[test]
401    fn pop_returns_elements_from_the_end_of_both_representations() {
402        let mut one = InlineVec::one(1u32);
403        assert_eq!(one.pop(), Some(1));
404        assert_eq!(one.pop(), None);
405
406        let mut many: InlineVec<u32> = (0..3).collect();
407        assert_eq!(many.pop(), Some(2));
408        assert_eq!(many.pop(), Some(1));
409        assert_eq!(many.pop(), Some(0));
410        assert_eq!(many.pop(), None);
411    }
412
413    #[test]
414    fn iteration_covers_every_representation() {
415        let cases = [
416            InlineVec::<u32>::new(),
417            InlineVec::one(1),
418            (1..4).collect::<InlineVec<u32>>(),
419        ];
420        let expected: [&[u32]; 3] = [&[], &[1], &[1, 2, 3]];
421
422        for (case, want) in cases.into_iter().zip(expected) {
423            assert_eq!(case.iter().copied().collect::<Vec<_>>(), want);
424            assert_eq!((&case).into_iter().copied().collect::<Vec<_>>(), want);
425            assert_eq!(case.clone().into_vec(), want);
426            assert_eq!(case.into_iter().collect::<Vec<_>>(), want);
427        }
428    }
429
430    #[test]
431    fn mutable_access_reaches_both_representations() {
432        let mut one = InlineVec::one(1u32);
433        for value in &mut one {
434            *value += 1;
435        }
436        assert_eq!(one.as_slice(), [2]);
437
438        let mut many: InlineVec<u32> = (0..3).collect();
439        many.as_mut_slice()[1] = 9;
440        assert_eq!(many.as_slice(), [0, 9, 2]);
441    }
442
443    #[test]
444    fn extend_grows_through_the_same_spill_rule() {
445        let mut values = InlineVec::new();
446        values.extend([1u32]);
447        assert!(!values.spilled());
448        values.extend([2u32, 3]);
449        assert_eq!(values.as_slice(), [1, 2, 3]);
450    }
451
452    // The inline element rides in the `Vec` pointer's niche, so a column of
453    // these is no wider than a column of `Vec`s and the saved heap block is not
454    // paid for in inline bytes. A representation change that broke the niche
455    // would grow every component column that holds one, silently.
456    #[test]
457    fn the_inline_element_costs_no_more_than_the_vec_it_replaces() {
458        assert_eq!(
459            size_of::<InlineVec<u32>>(),
460            size_of::<Vec<u32>>(),
461            "the inline case must ride in the Vec's niche"
462        );
463        assert_eq!(size_of::<InlineVec<u64>>(), size_of::<Vec<u64>>());
464        assert_eq!(
465            size_of::<InlineVec<(u32, u32)>>(),
466            size_of::<Vec<(u32, u32)>>()
467        );
468    }
469
470    // Comparing against a literal is what call sites and their tests do, so it
471    // reads the same whether the value spilled or not.
472    #[test]
473    fn arrays_and_vecs_convert_and_compare_across_both_representations() {
474        let one: InlineVec<u32> = [1].into();
475        let many: InlineVec<u32> = [1, 2].into();
476        assert!(!one.spilled() && many.spilled());
477
478        assert_eq!(one, [1]);
479        assert_eq!(many, [1, 2]);
480        assert_eq!(many, vec![1u32, 2]);
481        assert_eq!(many, *[1u32, 2].as_slice());
482        assert_ne!(one, [2]);
483        assert_ne!(one, [1, 2]);
484    }
485
486    // Slice methods arrive through `Deref`, so call sites that held a `Vec`
487    // keep reading the same way.
488    #[test]
489    fn slice_methods_are_available_through_deref() {
490        let values: InlineVec<u32> = (10..13).collect();
491        assert!(values.contains(&11));
492        assert_eq!(values[2], 12);
493        assert_eq!(values.first(), Some(&10));
494        assert_eq!(values.to_vec(), vec![10, 11, 12]);
495    }
496
497    // Ownership is real on both paths: dropping must run element destructors
498    // exactly once whether or not the value spilled.
499    #[test]
500    fn dropping_runs_element_destructors_once() {
501        use alloc::rc::Rc;
502
503        let witness = Rc::new(());
504        let mut values = InlineVec::new();
505        values.push(Rc::clone(&witness));
506        assert_eq!(Rc::strong_count(&witness), 2);
507
508        values.push(Rc::clone(&witness));
509        assert_eq!(Rc::strong_count(&witness), 3, "the spill must not leak");
510
511        drop(values);
512        assert_eq!(Rc::strong_count(&witness), 1);
513    }
514}
concinnity_memory/inline_vec.rs

concinnity_memory/
inline_vec.rs
