oxc-project / oxc-project/backlog

Reduce size of `Vec` to 16

Open
#174 0 comments 1 reaction 0 assignees View on GitHub

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 capacity field (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 Vec is limited to 134 million (1 << 27).
  • Do not store pointer to Allocator as separate field, but deduce it from data pointer + the top 5 bits of capacity.
  • Each allocator chunk contains a pointer to Allocator in 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::push and other potentially-resizing operations.
  • The logic for locating pointer to Allocator is a bit complex, but it's in a cold path.
  • Logic for getting Allocator ptr 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 - power in top 5 bits of capacity. Then chunk_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 than len(), could store power in top 5 bits of len field too. Then "is capacity full?" check in push() becomes just self.len == self.capacity (remove an AND operation), at the cost of moving that AND operation into len() instead.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.