
The upcoming series of blog posts will contain my study of Rust standard library. I’ve partially written some parts of the series in scattered places and want to gather them in one place for better and easier access. I intend to update whenever I discover something interesting/important to remember.
I’m referring to implementations in Rust stable v1.33.0.
This post covers some details of std::vec that I found important.
Vec<T>
Vec<T>
is a dynamic array which only grows and never shrinks automatically.
A contiguous growable array type with heap-allocated contents.
Rust std doc
Notice the difference between its counterpart stack-allocated fixed-size array [T; N]
(where at this time N
needs to be a specified non-negative integer. Constant generic hopefully will come soon).
Ok! let’s dig in to it. Vec<T>
contains (pointer, capacity, length).
Vec pointer
- The pointer will never be null, so it enjoys null-pointer-optimization.
- The pointer may not actually point to allocated memory for example in
Vec::new(), vec![]
orVec::with_capacity(0)
.
Vec capacity and length
- The capacity of a vector is the amount of space allocated for any future elements that will be added onto the vector.
- The length is the number of actual elements pushed/inserted in the vector.
Vec
allocates memory iffmem::size_of::<T>() * capacity() > 0
. So it does not allocate for a Zero-Sized-Type (ZST) even with positive capacity.- When length matches the capacity,
Vec
will (re)allocate by a certain growth factor. This makes insertion amortized. Right now the growth factor is 2. However, comparing to other languages such as C++, Java, etc. it doesn’t seem to be optimal given any global first-fit allocator. Heuristically, 1.5 or a number a bit less than golden ratio is considered optimal. Here’s the related issue that’s currently open. I found it interesting to dig in!
- How about shrink factor? for example, if we
pop
half of the elements out, would a quarter of the memory be freed? No, actually! That’s ifpop
ing all the elements the capacity won’t change leaving a hole on the heap. Therefore,pop
(from back) isand not amortized
If you need to free up some memory, use
.shrink_to_fit
- If need to use
Vec
for FFI or as a memory-backed collection, be sure to deallocate memory withfrom_raw_parts
and then drop explicitly. - If used in FFI and need to pass as pointer, for safety remember to call
shrink_to_fit
ortruncate
by the length prior to passing the (as_mut_ptr()
oras_ptr()
) to not pass uninitialized memory buffer. - The order of elements is always guaranteed to be the same if coerced into slice.
Here’s the stripped down definition
struct Vec<T> { buf: RawVec<T>, len: usize, } // Default Global allocator struct RawVec<T, A: Alloc = Global> { ptr: Unique<T>, cap: usize, a: A, } #[repr(transparent)] struct Unique<T: ?Sized> { pointer: *const T, _marker: PhantomData<T>, }
Unique<T>
- #[repr(transparent)] enforces that
Unique<T>
type representation is the same as*const T
. Unique<T>
is the covariant version of*mut T
(wrtT
) and has stronger semantic thanNonNull<T>
.- Unlike
*mut T
, the pointer must always be non-null. - In fact,
Box<T>
wrapsUnique<T>
i.e.struct Box<T: ?Sized>(Unique<T>)
. - It can be accessed in nightly through
#![feature(ptr_internals)]
andcore::ptr::Unique
. - If
T
isSend/Sync
thenUnique<T>
isSend/Sync
. - The presence of
PhantomData<T>
marker is only important for rustc dropck to understand that we logically own aT
causing the main difference betweenUnique<T>
andNonNull<T>
where it’s defined as
// NonNull<T> doesn't own the referent whereas Unique<T> does #[repr(transparent)] struct NonNull<T: ?Sized> { pointer: *const T, }
Leave a Reply