Repository navigation
SmallVector: Benchmarks and documentation #76
Description
Parent
Part of #5. Depends on #71, #72, #73, #74.
Summary
Add benchmarks comparing SmallVector against std::vector and std::array across relevant workloads, and write the documentation page.
Benchmarks
Key scenarios to measure
| Benchmark | What it shows |
|---|---|
push_back N elements, N <= inline capacity |
Pure inline path — no heap, no alloc |
push_back N elements, N > inline capacity |
Heap transition cost amortized |
Random access (operator[]) |
Should be identical to std::vector |
| Iteration over elements | Cache behaviour of contiguous storage |
| Copy small vector | Element-wise copy cost |
| Move small vector — inline | O(N) move, vs O(1) for heap |
| Move small vector — heap | O(1) pointer steal |
| Function call passing by value | SBO avoids alloc for typical small sizes |
Baselines to compare
std::vector<T>— always heapstd::array<T, N>— always stack, fixed size (upper bound reference)llvm::SmallVector<T, N>if available — the most widely used existing implementation
Documentation page
Cover:
- When to prefer
SmallVectoroverstd::vector(frequent small allocations, hot-path vectors) - When NOT to use it (large N wastes stack space; N=0 is valid but just a heap vector)
- The inline/heap transition and iterator invalidation rules
- Move semantics caveat — inline move is O(N), not O(1)
- Choosing N: profile first, typical values are 4–16 for most use cases
Notes
The move semantics caveat deserves prominent documentation — users coming from std::vector expect O(1) moves always, which is not guaranteed here.
Activity