How Does absl::InlinedVector Avoid Heap Allocations for Small Sizes?

absl::InlinedVector avoids heap allocations for small sizes by storing elements in an internal, statically-sized buffer embedded within the object itself through a union-based storage scheme, only allocating on the heap when the element count exceeds the pre-computed inline capacity.

absl::InlinedVector is a hybrid container in the Abseil C++ library designed to optimize for small, fixed-size collections by eliminating dynamic memory allocation until absolutely necessary. Unlike std::vector, which always stores elements on the heap, InlinedVector keeps a small buffer inside the object itself to handle common small-size scenarios without touching the allocator. According to the abseil/abseil-cpp source code, this is achieved through a sophisticated union-based storage mechanism that switches between inline and heap memory automatically.

Embedded Inline Storage via Union

At the core of absl::InlinedVector is a union that holds either an inline buffer or a heap-allocated region. In absl/container/internal/inlined_vector.h (lines 424–447), the implementation defines an Inlined struct containing a properly aligned byte array, and an Allocated struct for heap memory, combined in a Data union:

struct Inlined { 
  alignas(ValueType<A>) unsigned char inlined_data[sizeof(ValueType<A>[kOptimalInlinedSize])]; 
};

union Data { 
  Allocated allocated; 
  Inlined inlined; 
};

The Inlined struct uses alignas(ValueType<A>) to ensure proper alignment for the stored elements, while the inlined_data array provides the actual storage space. This union occupies only as much space as the larger of the two alternatives, keeping the object size compact while supporting both storage modes.

Compile-Time Capacity Optimization

The inline buffer size is determined at compile-time by the kOptimalInlinedSize constant, defined at line 440 in absl/container/internal/inlined_vector.h. This constexpr calculation ensures the buffer can hold at least N elements (the user-requested size), but may be larger to avoid wasting space:

static constexpr size_t kOptimalInlinedSize = (std::max)(N, sizeof(Allocated) / sizeof(ValueType<A>));

This optimization guarantees that if the overhead of tracking a heap allocation (sizeof(Allocated)) would waste space equivalent to additional elements, those bytes are used to extend the inline capacity instead. The result is a buffer that minimizes object size while maximizing allocation-free storage.

Fast-Path Construction and Insertion

When constructing or inserting elements, InlinedVector checks capacity against the inline limit before considering heap allocation. The Initialize method (lines 318–332) demonstrates this logic:

if (new_size > GetInlinedCapacity()) { 
  /* allocate */ 
} else { 
  construct_data = GetInlinedData(); 
}

Similarly, the EmplaceBack method (lines 218–226) uses a branch-prediction-friendly check to avoid allocation during growth:

if (ABSL_PREDICT_TRUE(n != storage_view.capacity)) { 
  /* construct in-place */ 
}

When n (the current size) does not equal capacity, the element is constructed directly in the inline storage using AllocatorTraits<A>::construct, bypassing the allocator entirely.

Bit-Encoded Allocation Tracking

To distinguish between inline and heap storage without extra memory overhead, InlinedVector encodes the allocation status in the least significant bit of the size field. The GetIsAllocated accessor (lines 70–73) reveals this implementation:

bool GetIsAllocated() const { 
  return GetSizeAndIsAllocated() & 1; 
}

This bit-packed approach allows every operation to cheaply test GetIsAllocated() and decide whether to access data via GetInlinedData() or GetAllocatedData(), ensuring zero-cost dispatch for the common case of inline storage.

Practical Example

The following example demonstrates the allocation-free behavior for small sizes:

#include "absl/container/inlined_vector.h"
#include <iostream>

int main() {
  // Inline capacity of 4 ints (N = 4)
  absl::InlinedVector<int, 4> v;

  // No heap allocation yet – all elements stored inside `v`.
  for (int i = 0; i < 4; ++i) v.push_back(i);
  std::cout << "size = " << v.size() << "\n";   // prints 4

  // The next push forces a heap allocation.
  v.push_back(42);
  std::cout << "size = " << v.size() << "\n";   // prints 5
}

In this example, the first four push_back calls hit the fast-path in EmplaceBack and use the internal inlined_data buffer. The fifth insertion exceeds the inline capacity, triggering the slow path (EmplaceBackSlow), which allocates a heap buffer, moves the existing four elements, and appends the new value.

Summary

• Union-based storage: A Data union combines Inlined and Allocated structs, keeping a fixed-size buffer inside the object while supporting heap fallback.
• Optimal capacity calculation: kOptimalInlinedSize maximizes inline storage by using space that would otherwise be wasted by allocation overhead.
• Fast-path operations: Methods like Initialize and EmplaceBack check GetInlinedCapacity() before allocating, ensuring zero-cost insertion for small vectors.
• Bit-packed status: The least significant bit of size_and_is_allocated_ tracks whether storage is heap-allocated, enabling efficient dispatch between inline and heap data accessors.
• Automatic promotion: When size exceeds inline capacity, the vector automatically transitions to heap storage without user intervention.

Frequently Asked Questions

What is the maximum number of elements absl::InlinedVector can store without allocating?

The allocation-free capacity is determined by kOptimalInlinedSize, which is at least the template parameter N but may be larger. Specifically, it calculates the maximum of N and sizeof(Allocated) / sizeof(ValueType<A>), meaning the inline buffer may hold additional elements if the heap allocation metadata would otherwise waste space.

How does absl::InlinedVector compare to std::vector for small collections?

Unlike std::vector, which always allocates on the heap, absl::InlinedVector stores small collections directly within the object, eliminating allocator overhead and improving cache locality. This makes it ideal for collections where the size is typically small but may occasionally grow, such as function argument lists or small result sets.

What happens when an absl::InlinedVector exceeds its inline capacity?

When the size exceeds GetInlinedCapacity(), the vector allocates a heap buffer, transfers all existing elements from the inline storage to the new buffer, sets the allocation flag in size_and_is_allocated_, and from that point forward behaves like a standard heap-based vector until destruction.

Is absl::InlinedVector compatible with standard allocators?

Yes, absl::InlinedVector is fully compatible with standard allocators and follows the Allocator concept requirements. It uses AllocatorTraits<A> to construct and destroy elements, and only invokes the allocator when transitioning from inline to heap storage or when reallocating the heap buffer.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}