orx_split_vec/growth/recursive/
recursive_growth.rs

1use crate::{Doubling, Fragment, Growth, SplitVec};
2use alloc::string::String;
3use orx_pseudo_default::PseudoDefault;
4
5/// Equivalent to [`Doubling`] strategy except for the following:
6///
7/// * enables zero-cost (no-ops) `append` operation:
8///   * we can append standard vectors, vectors of vectors, split vectors, etc., any data that implements `IntoFragments` trait,
9///   * by simply accepting it as a whole fragment,
10///   * according to benchmarks documented in the crate definition:
11///     * `SplitVec<_, Recursive>` is infinitely faster than other growth strategies or standard vector :)
12///     * since its time complexity is independent of size of the data to be appended.
13/// * at the expense of providing slower random-access performance:
14///   * random access time complexity of `Doubling` strategy is constant time;
15///   * that of `Recursive` strategy is linear in the number of fragments;
16///   * according to benchmarks documented in the crate definition:
17///     * `SplitVec<_, Doubling>` or standard vector are around 4 to 7 times faster than `SplitVec<_, Recursive>`,
18///     * and 1.5 times faster when the elements get very large (16 x `u64`).
19///
20/// Note that other operations such as serial access are equivalent to `Doubling` strategy.
21///
22/// # Examples
23///
24/// ```
25/// use orx_split_vec::*;
26///
27/// // SplitVec<usize, Recursive>
28/// let mut vec = SplitVec::with_recursive_growth();
29///
30/// vec.push('a');
31/// assert_eq!(vec, &['a']);
32///
33/// vec.append(vec!['b', 'c']);
34/// assert_eq!(vec, &['a', 'b', 'c']);
35///
36/// vec.append(vec![vec!['d'], vec!['e', 'f']]);
37/// assert_eq!(vec, &['a', 'b', 'c', 'd', 'e', 'f']);
38///
39/// let other_split_vec: SplitVec<_> = vec!['g', 'h'].into();
40/// vec.append(other_split_vec);
41/// assert_eq!(vec, &['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']);
42/// ```
43#[derive(Debug, Default, Clone, PartialEq)]
44pub struct Recursive;
45
46impl PseudoDefault for Recursive {
47    fn pseudo_default() -> Self {
48        Default::default()
49    }
50}
51
52impl Growth for Recursive {
53    #[inline(always)]
54    fn new_fragment_capacity_from(
55        &self,
56        fragment_capacities: impl ExactSizeIterator<Item = usize>,
57    ) -> usize {
58        Doubling.new_fragment_capacity_from(fragment_capacities)
59    }
60
61    fn maximum_concurrent_capacity<T>(
62        &self,
63        fragments: &[Fragment<T>],
64        fragments_capacity: usize,
65    ) -> usize {
66        assert!(fragments_capacity >= fragments.len());
67
68        let current_capacity = fragments.iter().map(|x| x.capacity()).sum();
69        let mut last_capacity = fragments.last().map(|x| x.capacity()).unwrap_or(2);
70
71        let mut total_capacity = current_capacity;
72
73        for _ in fragments.len()..fragments_capacity {
74            last_capacity *= 2;
75            total_capacity += last_capacity;
76        }
77
78        total_capacity
79    }
80
81    fn required_fragments_len<T>(
82        &self,
83        fragments: &[Fragment<T>],
84        maximum_capacity: usize,
85    ) -> Result<usize, String> {
86        fn overflown_err() -> String {
87            alloc::format!(
88                "Maximum cumulative capacity that can be reached by the Recursive strategy is {}.",
89                usize::MAX
90            )
91        }
92
93        let current_capacity: usize = fragments.iter().map(|x| x.capacity()).sum();
94        let mut last_capacity = fragments.last().map(|x| x.capacity()).unwrap_or(2);
95
96        let mut total_capacity = current_capacity;
97        let mut f = fragments.len();
98
99        while total_capacity < maximum_capacity {
100            let (new_last_capacity, overflown) = last_capacity.overflowing_mul(2);
101            if overflown {
102                return Err(overflown_err());
103            }
104            last_capacity = new_last_capacity;
105
106            let (new_total_capacity, overflown) = total_capacity.overflowing_add(last_capacity);
107            if overflown {
108                return Err(overflown_err());
109            }
110
111            total_capacity = new_total_capacity;
112            f += 1;
113        }
114
115        Ok(f)
116    }
117
118    fn maximum_concurrent_capacity_bound<T>(
119        &self,
120        fragments: &[Fragment<T>],
121        fragments_capacity: usize,
122    ) -> usize {
123        Doubling.maximum_concurrent_capacity_bound(fragments, fragments_capacity)
124    }
125}
126
127impl<T> SplitVec<T, Recursive> {
128    /// Strategy which allows to create a fragment with double the capacity
129    /// of the prior fragment every time the split vector needs to expand.
130    ///
131    /// Notice that this is similar to the `Doubling` growth strategy.
132    /// However, `Recursive` and `Doubling` strategies have the two following important differences in terms of performance:
133    ///
134    /// * Random access by indices is much faster with `Doubling`.
135    /// * Recursive strategy enables copy-free `append` method which merges another vector to this vector in constant time.
136    ///
137    /// All other operations are expected to have similar complexity.
138    ///
139    /// ## Random Access
140    ///
141    /// * `Doubling` strategy provides a constant time access by random indices.
142    /// * `Recursive` strategy provides a random access time complexity that is linear in the number of fragments.
143    ///   Note that this is significantly faster than the linear-in-number-of-elements complexity of linked lists;
144    ///   however, significantly slower than the `Doubling` strategy's constant time.
145    ///
146    /// ## Append
147    ///
148    /// * `Recursive` strategy provides `append` operation which allows merging two vectors in constant time without copies.
149    ///
150    /// `SplitVec::append` method should not be confused with `std::vec::Vec::append` method:
151    /// * The split vector version consumes the vector to be appended.
152    ///   It takes advantage of its split nature and appends the other vector simply by owning its pointer.
153    ///   In other words, the other vector is appended to this vector with no cost and no copies.
154    /// * The standard vector version mutates the vector to be appended,
155    ///   moving all its element to the first vector leaving the latter empty.
156    ///   This operation is carried out by memory copies.
157    ///
158    /// # Examples
159    ///
160    /// ```
161    /// use orx_split_vec::*;
162    ///
163    /// // SplitVec<usize, Doubling>
164    /// let mut vec = SplitVec::with_recursive_growth();
165    ///
166    /// assert_eq!(1, vec.fragments().len());
167    /// assert_eq!(Some(4), vec.fragments().first().map(|f| f.capacity()));
168    /// assert_eq!(Some(0), vec.fragments().first().map(|f| f.len()));
169    ///
170    /// // fill the first 5 fragments
171    /// let expected_fragment_capacities = vec![4, 8, 16, 32];
172    /// let num_items: usize = expected_fragment_capacities.iter().sum();
173    /// for i in 0..num_items {
174    ///     vec.push(i);
175    /// }
176    ///
177    /// assert_eq!(
178    ///     expected_fragment_capacities,
179    ///     vec.fragments()
180    ///     .iter()
181    ///     .map(|f| f.capacity())
182    ///     .collect::<Vec<_>>()
183    /// );
184    /// assert_eq!(
185    ///     expected_fragment_capacities,
186    ///     vec.fragments().iter().map(|f| f.len()).collect::<Vec<_>>()
187    /// );
188    ///
189    /// // create the 6-th fragment doubling the capacity
190    /// vec.push(42);
191    /// assert_eq!(
192    ///     vec.fragments().len(),
193    ///     expected_fragment_capacities.len() + 1
194    /// );
195    ///
196    /// assert_eq!(vec.fragments().last().map(|f| f.capacity()), Some(32 * 2));
197    /// assert_eq!(vec.fragments().last().map(|f| f.len()), Some(1));
198    /// ```
199    pub fn with_recursive_growth() -> Self {
200        SplitVec::with_doubling_growth().into()
201    }
202
203    /// Creates a new split vector with `Recursive` growth and initial `fragments_capacity`.
204    ///
205    /// This method differs from [`SplitVec::with_recursive_growth`] only by the pre-allocation of fragments collection.
206    /// Note that this (only) important for concurrent programs:
207    /// * SplitVec already keeps all elements pinned to their locations;
208    /// * Creating a buffer for storing the meta information is important for keeping the meta information pinned as well.
209    ///   This is relevant and important for concurrent programs.
210    ///
211    /// # Panics
212    ///
213    /// Panics if `fragments_capacity == 0`.
214    pub fn with_recursive_growth_and_fragments_capacity(fragments_capacity: usize) -> Self {
215        SplitVec::with_doubling_growth_and_fragments_capacity(fragments_capacity).into()
216    }
217
218    /// Creates a new split vector with `Recursive` growth and maximum concurrent capacity which depends
219    /// on the pointer size of the target architecture.
220    ///
221    /// This method differs from [`SplitVec::with_recursive_growth`] only by the pre-allocation of fragments collection,
222    /// which never contains more elements than 33.
223    pub fn with_recursive_growth_and_max_concurrent_capacity() -> Self {
224        SplitVec::with_doubling_growth_and_max_concurrent_capacity().into()
225    }
226}
227
228#[cfg(test)]
229mod tests {
230    use crate::growth::doubling::constants::{CAPACITIES_LEN, FIRST_FRAGMENT_CAPACITY};
231
232    use super::*;
233    use alloc::vec::Vec;
234    use orx_pinned_vec::PinnedVec;
235
236    #[test]
237    fn get_fragment_and_inner_indices() {
238        let growth = Recursive;
239
240        let vecs = alloc::vec![
241            alloc::vec![0, 1, 2, 3],
242            alloc::vec![4, 5],
243            alloc::vec![6, 7, 8],
244            alloc::vec![9],
245            alloc::vec![10, 11, 12, 13, 14],
246        ];
247        let mut fragments: Vec<Fragment<_>> = vecs.clone().into_iter().map(|x| x.into()).collect();
248        let len = fragments.iter().map(|x| x.len()).sum();
249
250        let mut index = 0;
251        for (f, vec) in vecs.iter().enumerate() {
252            for (i, _) in vec.iter().enumerate() {
253                let maybe_fi = growth.get_fragment_and_inner_indices(len, &fragments, index);
254                assert_eq!(maybe_fi, Some((f, i)));
255
256                let ptr = growth.get_ptr_mut(&mut fragments, index).expect("is-some");
257                assert_eq!(unsafe { *ptr }, index);
258
259                unsafe { *ptr = 10 * index };
260                assert_eq!(unsafe { *ptr }, 10 * index);
261
262                index += 1;
263            }
264        }
265    }
266
267    #[test]
268    fn get_fragment_and_inner_indices_exhaustive() {
269        let growth = Recursive;
270
271        let mut fragments: Vec<Fragment<_>> = alloc::vec![];
272
273        #[cfg(not(miri))]
274        let lengths = [30, 1, 7, 3, 79, 147, 530];
275        #[cfg(miri)]
276        let lengths = [1, 7, 3, 30];
277
278        let mut index = 0;
279        for _ in 0..10 {
280            for &len in &lengths {
281                let mut vec = Vec::with_capacity(len);
282                for _ in 0..len {
283                    vec.push(index);
284                    index += 1;
285                }
286                fragments.push(vec.into());
287            }
288        }
289
290        let total_len = fragments.iter().map(|x| x.len()).sum();
291
292        let mut index = 0;
293        let mut f = 0;
294        for _ in 0..10 {
295            for &len in &lengths {
296                for i in 0..len {
297                    let maybe_fi =
298                        growth.get_fragment_and_inner_indices(total_len, &fragments, index);
299
300                    assert_eq!(maybe_fi, Some((f, i)));
301
302                    let ptr = growth.get_ptr_mut(&mut fragments, index).expect("is-some");
303                    assert_eq!(unsafe { *ptr }, index);
304
305                    unsafe { *ptr = 10 * index };
306                    assert_eq!(unsafe { *ptr }, 10 * index);
307
308                    index += 1;
309                }
310                f += 1;
311            }
312        }
313    }
314
315    #[test]
316    fn maximum_concurrent_capacity() {
317        fn max_cap<T>(vec: &SplitVec<T, Recursive>) -> usize {
318            vec.growth()
319                .maximum_concurrent_capacity(vec.fragments(), vec.fragments.capacity())
320        }
321
322        let mut vec: SplitVec<char, Recursive> = SplitVec::with_recursive_growth();
323        assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32);
324
325        let until = max_cap(&vec);
326        for _ in 0..until {
327            vec.push('x');
328            assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32);
329        }
330
331        // fragments allocate beyond max_cap
332        vec.push('x');
333        assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512);
334    }
335
336    #[test]
337    fn maximum_concurrent_capacity_when_appended() {
338        fn max_cap<T>(vec: &SplitVec<T, Recursive>) -> usize {
339            vec.growth()
340                .maximum_concurrent_capacity(vec.fragments(), vec.fragments.capacity())
341        }
342
343        let mut vec: SplitVec<char, Recursive> = SplitVec::with_recursive_growth();
344        assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32);
345
346        vec.append(alloc::vec!['x'; 10]);
347        assert_eq!(vec.fragments().len(), 2);
348        assert_eq!(vec.fragments()[1].capacity(), 10);
349        assert_eq!(vec.fragments()[1].len(), 10);
350
351        assert_eq!(max_cap(&vec), 4 + 10 + 20 + 40);
352    }
353
354    #[test]
355    fn with_recursive_growth_and_fragments_capacity_normal_growth() {
356        let mut vec: SplitVec<char, _> = SplitVec::with_recursive_growth_and_fragments_capacity(1);
357
358        assert_eq!(1, vec.fragments.capacity());
359
360        #[cfg(not(miri))]
361        let n = 100_000;
362        #[cfg(miri)]
363        let n = 55;
364
365        for _ in 0..n {
366            vec.push('x');
367        }
368
369        #[cfg(not(miri))]
370        assert!(vec.fragments.capacity() > 4);
371    }
372
373    #[test]
374    #[should_panic]
375    fn with_recursive_growth_and_fragments_capacity_zero() {
376        let _: SplitVec<char, _> = SplitVec::with_recursive_growth_and_fragments_capacity(0);
377    }
378
379    #[test]
380    #[should_panic]
381    fn with_recursive_growth_and_fragments_capacity_too_large_fragments_capacity() {
382        let vec: SplitVec<char, _> = SplitVec::with_recursive_growth_and_fragments_capacity(1000);
383        assert_eq!(
384            vec.maximum_concurrent_capacity(),
385            (1 << (CAPACITIES_LEN + 2)) - FIRST_FRAGMENT_CAPACITY
386        );
387    }
388
389    #[test]
390    fn with_recursive_growth_and_max_concurrent_capacity() {
391        let vec: SplitVec<char, _> = SplitVec::with_recursive_growth_and_max_concurrent_capacity();
392        assert_eq!(
393            vec.maximum_concurrent_capacity(),
394            (1 << (CAPACITIES_LEN + 2)) - FIRST_FRAGMENT_CAPACITY
395        );
396    }
397
398    #[test]
399    fn required_fragments_len() {
400        let vec: SplitVec<char, Recursive> = SplitVec::with_recursive_growth();
401        let num_fragments = |max_cap| {
402            vec.growth()
403                .required_fragments_len(vec.fragments(), max_cap)
404        };
405
406        // 4 - 12 - 28 - 60 - 124
407        assert_eq!(num_fragments(0), Ok(1));
408        assert_eq!(num_fragments(1), Ok(1));
409        assert_eq!(num_fragments(4), Ok(1));
410        assert_eq!(num_fragments(5), Ok(2));
411        assert_eq!(num_fragments(12), Ok(2));
412        assert_eq!(num_fragments(13), Ok(3));
413        assert_eq!(num_fragments(36), Ok(4));
414        assert_eq!(num_fragments(67), Ok(5));
415        assert_eq!(num_fragments(136), Ok(6));
416    }
417
418    #[test]
419    fn required_fragments_len_when_appended() {
420        let mut vec: SplitVec<char, Recursive> = SplitVec::with_recursive_growth();
421        for _ in 0..4 {
422            vec.push('x')
423        }
424        vec.append(alloc::vec!['x'; 10]);
425
426        let num_fragments = |max_cap| {
427            vec.growth()
428                .required_fragments_len(vec.fragments(), max_cap)
429        };
430
431        // 4 - 10 - 20 - 40 - 80
432        // 4 - 14 - 34 - 74 - 154
433        assert_eq!(num_fragments(0), Ok(2));
434        assert_eq!(num_fragments(1), Ok(2));
435        assert_eq!(num_fragments(14), Ok(2));
436        assert_eq!(num_fragments(15), Ok(3));
437        assert_eq!(num_fragments(21), Ok(3));
438        assert_eq!(num_fragments(34), Ok(3));
439        assert_eq!(num_fragments(35), Ok(4));
440        assert_eq!(num_fragments(74), Ok(4));
441        assert_eq!(num_fragments(75), Ok(5));
442        assert_eq!(num_fragments(154), Ok(5));
443        assert_eq!(num_fragments(155), Ok(6));
444    }
445}