From d41734115eee6af64d894b46f5a5e628ed127477 Mon Sep 17 00:00:00 2001 From: HampusM Date: Mon, 26 Aug 2024 20:06:36 +0200 Subject: feat: add amortization --- src/lib.rs | 45 +++++++++++++++++++++++++++++++++++++-------- 1 file changed, 37 insertions(+), 8 deletions(-) (limited to 'src') diff --git a/src/lib.rs b/src/lib.rs index 098d726..424b366 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1,4 +1,5 @@ use std::alloc::{alloc, handle_alloc_error, realloc, Layout}; +use std::cmp::max; use std::marker::PhantomData; use std::mem::{forget, needs_drop}; use std::ptr::NonNull; @@ -34,6 +35,7 @@ where ptr: NonNull, field_arr_byte_offsets: Vec, length: usize, + capacity: usize, layout: Option, } @@ -41,6 +43,20 @@ impl MultiVec where ItemT: Item, { + // The following is borrow from std's RawVec implementation: + // Skip to: + // - 8 if the element size is 1, because any heap allocators is likely to round up a + // request of less than 8 bytes to at least 8 bytes. + // - 4 if elements are moderate-sized (<= 1 KiB). + // - 1 otherwise, to avoid wasting too much space for very short Vecs. + const MIN_NON_ZERO_CAP: usize = if size_of::() == 1 { + 8 + } else if size_of::() <= 1024 { + 4 + } else { + 1 + }; + pub const fn new() -> Self { Self { @@ -48,22 +64,30 @@ where ptr: NonNull::dangling(), field_arr_byte_offsets: Vec::new(), length: 0, + capacity: 0, layout: None, } } pub fn push(&mut self, item: ItemT) { - if self.length != 0 { - self.reallocate_for_more(1); + if self.capacity != 0 { + if self.capacity == self.length { + self.grow_amortized(1); + } self.write_item(self.length - 1, item); + + self.length += 1; + return; } self.do_first_alloc(); self.write_item(0, item); + + self.length = 1; } pub fn get( @@ -91,13 +115,18 @@ where unsafe { field_ptr.cast().as_ref() } } - fn reallocate_for_more(&mut self, item_cnt_inc: usize) + fn grow_amortized(&mut self, additional: usize) { - let new_length = self.length + item_cnt_inc; + let required_cap = self.capacity.checked_add(additional).unwrap(); + + // This guarantees exponential growth. The doubling cannot overflow + // because `cap <= isize::MAX` and the type of `cap` is `usize`. + let new_capacity = max(self.capacity * 2, required_cap); + let new_capacity = max(Self::MIN_NON_ZERO_CAP, new_capacity); let layout = &self.layout.unwrap(); - let (new_layout, new_field_arr_byte_offsets) = Self::create_layout(new_length); + let (new_layout, new_field_arr_byte_offsets) = Self::create_layout(new_capacity); let Some(new_ptr) = NonNull::new(unsafe { realloc(self.ptr.as_ptr(), *layout, new_layout.size()) @@ -121,14 +150,14 @@ where std::ptr::copy( old_field_arr_ptr.as_ptr(), new_field_arr_ptr.as_ptr(), - field_metadata.size * self.length, + field_metadata.size * self.capacity, ); } } self.ptr = new_ptr; self.layout = Some(new_layout); - self.length = new_length; + self.capacity = new_capacity; self.field_arr_byte_offsets = new_field_arr_byte_offsets; } @@ -141,7 +170,7 @@ where }; self.ptr = ptr; - self.length = 1; + self.capacity = 1; self.field_arr_byte_offsets = field_arr_byte_offsets; self.layout = Some(layout); } -- cgit v1.2.3-18-g5258