diff options
author | HampusM <hampus@hampusmat.com> | 2025-03-29 16:25:32 +0100 |
---|---|---|
committer | HampusM <hampus@hampusmat.com> | 2025-03-29 16:25:52 +0100 |
commit | ac07eee0fe8a5c18207ef6dc4eb42cc616af6164 (patch) | |
tree | fc395ca71ba0ef6200fa92844b81fe33087a52b0 | |
parent | 24c8b35725a1bb4faf511c992c0e4a6346cb75f7 (diff) |
perf: store metadata in the allocated buffer
-rw-r--r-- | src/lib.rs | 417 |
1 files changed, 313 insertions, 104 deletions
@@ -9,6 +9,11 @@ use crate::util::MaybeUninitByteSlice; mod util; +const FIELD_COUNT_SIZE: usize = size_of::<usize>(); + +const FIELD_COUNT_OFFSET: usize = 0; +const FIELD_METADATA_ARRAY_OFFSET: usize = FIELD_COUNT_SIZE; + pub struct OwnedAnyPtr { ptr: *mut dyn Any, @@ -96,8 +101,6 @@ impl Drop for OwnedAnyPtr pub struct MultiVec { ptr: NonNull<MaybeUninit<u8>>, - field_arr_byte_offsets: Vec<usize>, - field_metadata: Vec<FieldMetadata>, length: usize, capacity: usize, layout: Option<Layout>, @@ -133,8 +136,6 @@ impl MultiVec { Self { ptr: NonNull::dangling(), - field_arr_byte_offsets: Vec::new(), - field_metadata: Vec::new(), length: 0, capacity: 0, layout: None, @@ -172,7 +173,7 @@ impl MultiVec ) { if self.capacity != 0 { - assert_eq!(fields.as_ref().len(), self.field_arr_byte_offsets.len()); + assert_eq!(fields.as_ref().len(), self.field_cnt()); if self.capacity == self.length { self.grow_amortized(1, &fields); @@ -185,16 +186,6 @@ impl MultiVec return; } - self.field_metadata = fields - .as_ref() - .iter() - .map(|field| FieldMetadata { - size: field.size(), - type_id: field.id(), - drop_in_place: field.drop_in_place, - }) - .collect(); - self.do_first_alloc(1, &fields); self.write_item(0, fields); @@ -230,13 +221,11 @@ impl MultiVec /// Returns a slice containing the specified field of all items. #[must_use] - pub fn get_field_slice(&self, field_index: usize) -> FieldSlice<'_> + pub fn get_field_slice(&self, field_index: usize) -> Option<FieldSlice<'_>> { - let field_arr_byte_offset = self.field_arr_byte_offsets[field_index]; - - let field_metadata = &self.field_metadata[field_index]; + let field_metadata = &self.get_field_metadata()?.get(field_index)?; - let field_arr_ptr = unsafe { self.ptr.byte_add(field_arr_byte_offset) }; + let field_arr_ptr = unsafe { self.ptr.byte_add(field_metadata.array_offset) }; let bytes = unsafe { std::slice::from_raw_parts( @@ -245,22 +234,21 @@ impl MultiVec ) }; - FieldSlice { + Some(FieldSlice { bytes, len: self.len(), field_metadata, - } + }) } /// Returns a slice containing the specified field of all items. #[must_use] - pub fn get_field_slice_mut(&mut self, field_index: usize) -> FieldSliceMut<'_> + pub fn get_field_slice_mut(&mut self, field_index: usize) + -> Option<FieldSliceMut<'_>> { - let field_arr_byte_offset = self.field_arr_byte_offsets[field_index]; + let field_metadata = &self.get_field_metadata()?.get(field_index)?; - let field_metadata = &self.field_metadata[field_index]; - - let field_arr_ptr = unsafe { self.ptr.byte_add(field_arr_byte_offset) }; + let field_arr_ptr = unsafe { self.ptr.byte_add(field_metadata.array_offset) }; let bytes = unsafe { std::slice::from_raw_parts_mut( @@ -269,11 +257,11 @@ impl MultiVec ) }; - FieldSliceMut { + Some(FieldSliceMut { bytes, len: self.len(), field_metadata, - } + }) } /// Returns the number of items stored in this `MultiVec`. @@ -286,7 +274,11 @@ impl MultiVec /// Returns how many fields each item in this `MultiVec` has. pub fn field_cnt(&self) -> usize { - self.field_arr_byte_offsets.len() + if self.capacity() == 0 { + return 0; + } + + unsafe { self.ptr.byte_add(FIELD_COUNT_OFFSET).cast::<usize>().read() } } /// Returns how many items this `MultiVec` has capacity for. @@ -312,21 +304,37 @@ impl MultiVec let new_capacity = max(self.capacity * 2, required_cap); let new_capacity = max(Self::get_min_non_zero_cap(&fields), new_capacity); - let layout = &self.layout.unwrap(); - let (new_layout, new_field_arr_byte_offsets) = Self::create_layout(new_capacity, &fields); - let Some(new_ptr) = NonNull::new(if layout.size() == 0 { - std::ptr::dangling_mut() - } else { - unsafe { alloc(new_layout) } - }) else { + assert_ne!(new_layout.size(), 0); + + let Some(new_ptr) = NonNull::new(unsafe { alloc(new_layout) }) else { handle_alloc_error(new_layout); }; + unsafe { + new_ptr + .byte_add(FIELD_COUNT_OFFSET) + .cast::<usize>() + .write(self.field_cnt()); + } + + unsafe { + std::ptr::copy_nonoverlapping( + self.get_field_metadata() + .expect("Missing field metadata") + .as_ptr(), + new_ptr + .byte_add(FIELD_METADATA_ARRAY_OFFSET) + .cast::<FieldMetadata>() + .as_ptr(), + self.field_cnt(), + ); + } + for field_index in 0..self.field_cnt() { - let field_slice = self.get_field_slice(field_index); + let field_slice = self.get_field_slice(field_index).unwrap(); let new_byte_offset = new_field_arr_byte_offsets[field_index]; @@ -349,25 +357,49 @@ impl MultiVec self.ptr = new_ptr.cast::<MaybeUninit<u8>>(); self.layout = Some(new_layout); self.capacity = new_capacity; - self.field_arr_byte_offsets = new_field_arr_byte_offsets; + + for (field_metadata, new_field_array_offset) in self + .get_maybe_uninit_field_metadata_mut() + .iter_mut() + .zip(new_field_arr_byte_offsets) + { + let field_metadata = unsafe { field_metadata.assume_init_mut() }; + + field_metadata.array_offset = new_field_array_offset; + } } - fn do_first_alloc(&mut self, capacity: usize, fields: impl AsRef<[OwnedAnyPtr]>) + fn do_first_alloc(&mut self, capacity: usize, item_fields: impl AsRef<[OwnedAnyPtr]>) { - let (layout, field_arr_byte_offsets) = Self::create_layout(capacity, fields); + let (layout, field_arr_byte_offsets) = + Self::create_layout(capacity, item_fields.as_ref()); - let Some(ptr) = NonNull::new(if layout.size() == 0 { - std::ptr::dangling_mut() - } else { - unsafe { alloc(layout) } - }) else { + assert_ne!(layout.size(), 0); + + let Some(ptr) = NonNull::new(unsafe { alloc(layout) }) else { handle_alloc_error(layout); }; self.ptr = ptr.cast::<MaybeUninit<u8>>(); self.capacity = capacity; - self.field_arr_byte_offsets = field_arr_byte_offsets; self.layout = Some(layout); + + self.set_field_cnt(item_fields.as_ref().len()); + + for (field_index, uninit_field_metadata) in self + .get_maybe_uninit_field_metadata_mut() + .iter_mut() + .enumerate() + { + let item_field = &item_fields.as_ref()[field_index]; + + uninit_field_metadata.write(FieldMetadata { + size: item_field.size(), + type_id: item_field.id(), + array_offset: field_arr_byte_offsets[field_index], + drop_in_place: item_field.drop_in_place, + }); + } } fn create_layout( @@ -375,18 +407,26 @@ impl MultiVec fields: impl AsRef<[OwnedAnyPtr]>, ) -> (Layout, Vec<usize>) { - let mut field_iter = fields.as_ref().iter(); + let layout = Layout::from_size_align(0, 1).expect("Failed to create base layout"); - let first_field = field_iter.next().unwrap(); + let (layout, field_cnt_offset) = layout + .extend(Layout::new::<usize>()) + .expect("Failed to extend layout with field count layout"); - let mut layout = - array_layout(first_field.size(), first_field.alignment(), length).unwrap(); + assert_eq!(field_cnt_offset, FIELD_COUNT_OFFSET); - let mut field_arr_byte_offsets = Vec::with_capacity(fields.as_ref().len()); + let (mut layout, field_metadata_array_offset) = layout + .extend( + Layout::array::<FieldMetadata>(fields.as_ref().len()) + .expect("Failed to create field metadata array layout"), + ) + .expect("Failed to extend layout with field metadata array layout"); + + assert_eq!(field_metadata_array_offset, FIELD_METADATA_ARRAY_OFFSET); - field_arr_byte_offsets.push(0); + let mut field_arr_byte_offsets = Vec::with_capacity(fields.as_ref().len()); - for field in field_iter { + for field in fields.as_ref().iter() { let (new_layout, array_byte_offset) = layout .extend(array_layout(field.size(), field.alignment(), length).unwrap()) .unwrap(); @@ -401,12 +441,12 @@ impl MultiVec fn write_item(&mut self, index: usize, fields: impl IntoIterator<Item = OwnedAnyPtr>) { - for (field_index, item_field) in fields.into_iter().enumerate() { + for (item_field, field_metadata) in + fields.into_iter().zip(self.get_field_metadata().unwrap()) + { let field_size = item_field.size(); - let field_arr_byte_offset = self.field_arr_byte_offsets[field_index]; - - let field_arr_ptr = unsafe { self.ptr.byte_add(field_arr_byte_offset) }; + let field_arr_ptr = unsafe { self.ptr.byte_add(field_metadata.array_offset) }; let field_dst_ptr = unsafe { field_arr_ptr.add(field_size * index) }; @@ -436,6 +476,47 @@ impl MultiVec std::alloc::dealloc(self.ptr.as_ptr().cast::<u8>(), layout); } } + + fn get_field_metadata(&self) -> Option<&[FieldMetadata]> + { + if self.capacity == 0 { + return None; + } + + Some(unsafe { + std::slice::from_raw_parts( + self.ptr + .as_ptr() + .byte_add(FIELD_METADATA_ARRAY_OFFSET) + .cast::<FieldMetadata>(), + self.field_cnt(), + ) + }) + } + + fn get_maybe_uninit_field_metadata_mut(&mut self) + -> &mut [MaybeUninit<FieldMetadata>] + { + unsafe { + std::slice::from_raw_parts_mut( + self.ptr + .as_ptr() + .byte_add(FIELD_METADATA_ARRAY_OFFSET) + .cast::<MaybeUninit<FieldMetadata>>(), + self.field_cnt(), + ) + } + } + + fn set_field_cnt(&mut self, field_cnt: usize) + { + unsafe { + self.ptr + .byte_add(FIELD_COUNT_OFFSET) + .cast::<usize>() + .write(field_cnt); + } + } } //impl<ItemT> FromIterator<ItemT> for MultiVec<ItemT> @@ -477,10 +558,12 @@ impl Drop for MultiVec { fn drop(&mut self) { - assert_eq!(self.field_metadata.len(), self.field_arr_byte_offsets.len()); - - for field_index in 0..self.field_arr_byte_offsets.len() { - for field in self.get_field_slice_mut(field_index).iter_mut() { + for field_index in 0..self.field_cnt() { + for field in self + .get_field_slice_mut(field_index) + .expect("Not possible") + .iter_mut() + { let field_ptr = field.bytes.as_mut_ptr(); unsafe { @@ -638,7 +721,6 @@ impl<'mv> Iterator for FieldSliceIterMut<'mv> let field_bytes = unsafe { std::slice::from_raw_parts_mut( field_bytes_a.as_mut_ptr(), - //self.bytes.as_mut_ptr().byte_add(start_off), self.field_metadata.size, ) }; @@ -673,6 +755,7 @@ struct FieldMetadata { size: usize, type_id: TypeId, + array_offset: usize, drop_in_place: unsafe fn(NonNull<MaybeUninit<u8>>), } @@ -737,7 +820,25 @@ mod tests use std::ptr::NonNull; use std::sync::atomic::{AtomicUsize, Ordering}; - use crate::{FieldMetadata, MultiVec, OwnedAnyPtr}; + use crate::{ + FieldMetadata, + MultiVec, + OwnedAnyPtr, + FIELD_COUNT_OFFSET, + FIELD_METADATA_ARRAY_OFFSET, + }; + + macro_rules! replace { + ($tt: tt, $replacement: tt) => { + $replacement + }; + } + + macro_rules! count_rep { + ($($tt: tt,)*) => { + 0 $( + replace!($tt, 1))* + }; + } macro_rules! multi_vec_with_data { ( @@ -750,10 +851,26 @@ mod tests #[repr(C)] struct Data { + field_cnt: usize, + field_metadata: [FieldMetadata; count_rep!($($field_name,)*)], $($field_name: [$field_type; $length],)* } + assert_eq!(offset_of!(Data, field_cnt), FIELD_COUNT_OFFSET); + assert_eq!(offset_of!(Data, field_metadata), FIELD_METADATA_ARRAY_OFFSET); + $data = Data { + field_cnt: count_rep!($($field_name,)*), + field_metadata: [$( + FieldMetadata { + size: size_of::<$field_type>(), + type_id: TypeId::of::<$field_type>(), + array_offset: offset_of!(Data, $field_name), + drop_in_place: |ptr| unsafe { + std::ptr::drop_in_place(ptr.cast::<$field_type>().as_ptr()); + }, + }, + )*], $($field_name: $field_values.map(|val| val.into()),)* }; @@ -763,19 +880,6 @@ mod tests std::mem::forget($data); - multi_vec.field_arr_byte_offsets = - vec![$(offset_of!(Data, $field_name),)*]; - - multi_vec.field_metadata = vec![$( - FieldMetadata { - size: size_of::<$field_type>(), - type_id: TypeId::of::<$field_type>(), - drop_in_place: |ptr| unsafe { - std::ptr::drop_in_place(ptr.cast::<$field_type>().as_ptr()); - }, - }, - )*]; - multi_vec.length = $length; multi_vec.capacity = multi_vec.length; @@ -788,16 +892,38 @@ mod tests { let mut multi_vec = MultiVec::new(); - multi_vec.push([OwnedAnyPtr::new(123), OwnedAnyPtr::new(654)]); + multi_vec.push([OwnedAnyPtr::new(123u32), OwnedAnyPtr::new(654u16)]); assert_eq!(multi_vec.capacity, 1); assert_eq!(multi_vec.length, 1); + assert_eq!(multi_vec.field_cnt(), 2); + + let field_metadata_arr_size = FIELD_METADATA_ARRAY_OFFSET + + size_of::<FieldMetadata>() * multi_vec.field_cnt(); + + let field_metadata = multi_vec.get_field_metadata().expect("Should be Some"); + + assert_eq!(field_metadata[0].size, size_of::<u32>()); + assert_eq!(field_metadata[0].type_id, TypeId::of::<u32>()); + assert_eq!(field_metadata[0].array_offset, field_metadata_arr_size + 0); - assert_eq!(multi_vec.field_arr_byte_offsets, [0, size_of::<u32>()]); + assert_eq!(field_metadata[1].size, size_of::<u16>()); + assert_eq!(field_metadata[1].type_id, TypeId::of::<u16>()); + assert_eq!( + field_metadata[1].array_offset, + field_metadata_arr_size + size_of::<u32>() + ); assert_eq!( unsafe { - std::slice::from_raw_parts::<u32>(multi_vec.ptr.as_ptr().cast(), 1) + std::slice::from_raw_parts::<u32>( + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[0].array_offset) + .cast(), + 1, + ) }, [123] ); @@ -805,7 +931,11 @@ mod tests assert_eq!( unsafe { std::slice::from_raw_parts::<u16>( - multi_vec.ptr.as_ptr().byte_add(size_of::<u32>()).cast(), + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[1].array_offset) + .cast(), 1, ) }, @@ -818,18 +948,49 @@ mod tests { let mut multi_vec = MultiVec::new(); - multi_vec.push([OwnedAnyPtr::new(u32::MAX / 2), OwnedAnyPtr::new::<u16>(654)]); - multi_vec.push([OwnedAnyPtr::new(765), OwnedAnyPtr::new::<u16>(u16::MAX / 3)]); - multi_vec.push([OwnedAnyPtr::new(u32::MAX / 5), OwnedAnyPtr::new::<u16>(337)]); + multi_vec.push([ + OwnedAnyPtr::new::<u32>(u32::MAX / 2), + OwnedAnyPtr::new::<u16>(654), + ]); + multi_vec.push([ + OwnedAnyPtr::new::<u32>(765), + OwnedAnyPtr::new::<u16>(u16::MAX / 3), + ]); + multi_vec.push([ + OwnedAnyPtr::new::<u32>(u32::MAX / 5), + OwnedAnyPtr::new::<u16>(337), + ]); assert_eq!(multi_vec.capacity, 4); assert_eq!(multi_vec.length, 3); + assert_eq!(multi_vec.field_cnt(), 2); + + let field_metadata_arr_size = FIELD_METADATA_ARRAY_OFFSET + + size_of::<FieldMetadata>() * multi_vec.field_cnt(); + + let field_metadata = multi_vec.get_field_metadata().expect("Should be Some"); - assert_eq!(multi_vec.field_arr_byte_offsets, [0, size_of::<u32>() * 4]); + assert_eq!(field_metadata[0].size, size_of::<u32>()); + assert_eq!(field_metadata[0].type_id, TypeId::of::<u32>()); + assert_eq!(field_metadata[0].array_offset, field_metadata_arr_size + 0); + + assert_eq!(field_metadata[1].size, size_of::<u16>()); + assert_eq!(field_metadata[1].type_id, TypeId::of::<u16>()); + assert_eq!( + field_metadata[1].array_offset, + field_metadata_arr_size + size_of::<u32>() * multi_vec.capacity + ); assert_eq!( unsafe { - std::slice::from_raw_parts::<u32>(multi_vec.ptr.as_ptr().cast(), 3) + std::slice::from_raw_parts::<u32>( + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[0].array_offset) + .cast(), + multi_vec.length, + ) }, [u32::MAX / 2, 765, u32::MAX / 5] ); @@ -837,8 +998,12 @@ mod tests assert_eq!( unsafe { std::slice::from_raw_parts::<u16>( - multi_vec.ptr.as_ptr().byte_add(size_of::<u32>() * 4).cast(), - 3, + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[1].array_offset) + .cast(), + multi_vec.length, ) }, [654, u16::MAX / 3, 337] @@ -855,7 +1020,18 @@ mod tests multi_vec.push([OwnedAnyPtr::new(()), OwnedAnyPtr::new(UnsizedThing)]); multi_vec.push([OwnedAnyPtr::new(()), OwnedAnyPtr::new(UnsizedThing)]); - assert_eq!(multi_vec.field_arr_byte_offsets, [0, 0]); + let field_metadata_arr_size = FIELD_METADATA_ARRAY_OFFSET + + size_of::<FieldMetadata>() * multi_vec.field_cnt(); + + let field_metadata = multi_vec.get_field_metadata().expect("Should be Some"); + + assert_eq!(field_metadata[0].size, size_of::<()>()); + assert_eq!(field_metadata[0].type_id, TypeId::of::<()>()); + assert_eq!(field_metadata[0].array_offset, field_metadata_arr_size + 0); + + assert_eq!(field_metadata[1].size, size_of::<UnsizedThing>()); + assert_eq!(field_metadata[1].type_id, TypeId::of::<UnsizedThing>()); + assert_eq!(field_metadata[1].array_offset, field_metadata_arr_size + 0); } #[test] @@ -892,20 +1068,38 @@ mod tests assert_eq!(multi_vec.capacity, 4); assert_eq!(multi_vec.length, 2); + let field_metadata_arr_size = FIELD_METADATA_ARRAY_OFFSET + + size_of::<FieldMetadata>() * multi_vec.field_cnt(); + + let field_metadata = multi_vec.get_field_metadata().expect("Should be Some"); + + assert_eq!(field_metadata[0].size, size_of::<CustomerName>()); + assert_eq!(field_metadata[0].type_id, TypeId::of::<CustomerName>()); + assert_eq!(field_metadata[0].array_offset, field_metadata_arr_size + 0); + + assert_eq!(field_metadata[1].size, size_of::<UnsizedThing>()); + assert_eq!(field_metadata[1].type_id, TypeId::of::<UnsizedThing>()); assert_eq!( - multi_vec.field_arr_byte_offsets, - [ - 0, - size_of::<CustomerName>() * multi_vec.capacity, - size_of::<CustomerName>() * multi_vec.capacity, - ] + field_metadata[1].array_offset, + field_metadata_arr_size + size_of::<CustomerName>() * multi_vec.capacity + ); + + assert_eq!(field_metadata[2].size, size_of::<CustomerAge>()); + assert_eq!(field_metadata[2].type_id, TypeId::of::<CustomerAge>()); + assert_eq!( + field_metadata[2].array_offset, + field_metadata_arr_size + size_of::<CustomerName>() * multi_vec.capacity ); assert_eq!( unsafe { std::slice::from_raw_parts::<CustomerName>( - multi_vec.ptr.as_ptr().cast(), - 2, + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[0].array_offset) + .cast(), + multi_vec.length, ) }, [ @@ -920,9 +1114,9 @@ mod tests multi_vec .ptr .as_ptr() - .byte_add(multi_vec.field_arr_byte_offsets[2]) + .byte_add(field_metadata[2].array_offset) .cast(), - 2, + multi_vec.length, ) }, [CustomerAge { age: 54 }, CustomerAge { age: 40 }] @@ -1043,12 +1237,18 @@ mod tests ); assert_eq!( - multi_vec.get_field_slice(0).as_slice::<u32>(), + multi_vec + .get_field_slice(0) + .expect("Should be Some") + .as_slice::<u32>(), [u32::MAX - 3000, 901, 5560000] ); assert_eq!( - multi_vec.get_field_slice(1).as_slice::<u16>(), + multi_vec + .get_field_slice(1) + .expect("Should be Some") + .as_slice::<u16>(), [20210, 7120, 1010] ); } @@ -1068,17 +1268,26 @@ mod tests ); assert_eq!( - multi_vec.get_field_slice(0).as_slice::<u32>(), + multi_vec + .get_field_slice(0) + .expect("Should be Some") + .as_slice::<u32>(), [123, 888, 1910, 11144, 770077] ); assert_eq!( - multi_vec.get_field_slice(1).as_slice::<String>(), + multi_vec + .get_field_slice(1) + .expect("Should be Some") + .as_slice::<String>(), ["No,", "I", "am", "your", "father",] ); assert_eq!( - multi_vec.get_field_slice(2).as_slice::<u8>(), + multi_vec + .get_field_slice(2) + .expect("Should be Some") + .as_slice::<u8>(), [120, 88, 54, 3, 7] ); } |