oxc-project / oxc-project/backlog
Reduce size of `Vec` to 16
Nobody has claimed this yet.
- Dominant language
- No language data
- Stars
- 7
- Forks
- 0
- PR merge metrics
- No merged PRs in 30d
Description
Continuation of https://github.com/oxc-project/oxc/issues/9706. Much of content below is copied from that issue.
Vec is currently 24 bytes. It consists of:
- Pointer to
Vec's contents (NonNull<u8>) - Length (
u32) - Capacity (
u32) - Pointer to allocator (
&Allocator)
We could remove the &Allocator reference, reducing Vec to 16, if can accept:
- A lower limit on len/capacity of
Vec. - Extra overhead of 1 bitwise operation when getting capacity.
- Extra overhead of several operations when resizing
Vec.
As follows:
- Allocator allocates all chunks with same alignment as size of the chunk.
- Reserve top 5 bits of
capacityfield (5 bits can store a number 0 - 31). - Store the power of the chunk's alignment in those top 5 bits i.e. if chunk is aligned on 65536 (1 << 16), top 5 bits contain 16.
- Max capacity of
Vecis limited to 134 million (1 << 27). - Do not store pointer to
Allocatoras separate field, but deduce it from data pointer + the top 5 bits ofcapacity. - Each allocator chunk contains a pointer to
Allocatorin its footer metadata block.
struct AllocatorChunkFooter {
allocator: *const Allocator,
/* other fields */
}
struct Vec<'a, T> {
ptr: NonNull<T>,
len: u32,
capacity: u32,
_marker: PhantomData<&'a ()>,
}
const CHUNK_ALIGNMENT_BITS: u32 = 5;
const CAPACITY_MASK: u32 = u32::MAX >> CHUNK_ALIGNMENT_BITS;
const CHUNK_ALIGNMENT_SHIFT: u32 = 32 - CHUNK_ALIGNMENT_BITS;
const ALLOCATOR_FIELD_MASK: usize = usize::MAX - size_of::<AllocatorChunkFooter>() + 1
+ std::mem::offset_of!(AllocatorChunkFooter, allocator);
impl<'a, T> Vec<'a, T> {
pub fn len(&self) -> u32 { self.len }
pub fn capacity(&self) -> u32 { self.capacity & CAPACITY_MASK }
pub fn push(&mut self, value: T) {
let len = self.len;
if len == self.capacity() { self.grow_for_push(); }
unsafe { self.ptr.add(len).write(value) };
self.len = len + 1;
}
#[cold]
fn grow_for_push(&mut self) {
let allocator = self.allocator();
// Reallocate `Vec` using `allocator`
}
fn allocator(&self) -> &'a Allocator {
let ptr = self.ptr.as_ptr().cast::<u8>();
let power = (self.capacity >> CHUNK_ALIGNMENT_SHIFT) as usize;
let chunk_end_minus_one_addr = ptr as usize | ((1 << power) - 1);
let allocator_field_addr = chunk_end_minus_one_addr & ALLOCATOR_FIELD_MASK;
let allocator_field_ptr = ptr.add(allocator_ptr_addr - ptr as usize).cast::<*const Allocator>();
let allocator_ptr = *allocator_field_ptr;
allocator_ptr.as_ref().unwrap_unchecked()
}
}
Notes:
- Only overhead for reading capacity is 1 x bitwise AND operation.
- This does unfortunately affect
Vec::pushand other potentially-resizing operations. - The logic for locating pointer to
Allocatoris a bit complex, but it's in a cold path. - Logic for getting
Allocatorptr is 100% cheap bitwise ops. - Individual arena chunks are limited to 2 GiB max (this corresponds to max alignment on Mac OS).
- There is no limit on size of arena (arena can consist of any number of chunks).
- If minimum arena chunk size is 64 KiB (1 << 16 bytes), could use top 4 bits of capacity instead of 5 bits.
- It'd be even better if stored
32 - powerin top 5 bits ofcapacity. Thenchunk_end_minus_one_addr = ptr as usize | (usize::MAX >> inverted_power). This removes 1 operation: https://godbolt.org/z/x3s5bbn71 - If
push()is more common thanlen(), could storepowerin top 5 bits oflenfield too. Then "is capacity full?" check inpush()becomes justself.len == self.capacity(remove an AND operation), at the cost of moving that AND operation intolen()instead.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reading the linked issue #9706 and locating the Vec and Allocator definitions in the repository. Trace the allocator chunk footer metadata and resizing paths shown here; done means Vec is reduced to 16 bytes while capacity limits, allocator lookup, growth, and existing behavior remain correct. No files or tests are named in this issue.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100