Dynamic Memory
- Object Lifetimes:
- Global objects are allocated at program startup and destroyed at program end.
- Local objects are created when entering a block and destroyed when leaving the block.
- Local
staticobjects are allocated before first use and destroyed at program end. - Dynamically allocated objects: Can only be explicitly released.
- Object Memory Locations:
- Static memory is used to hold local
staticobjects, classstaticobjects, and variables defined outside any function. - Stack memory is used to hold non-
staticobjects defined inside functions. - Heap memory, also known as free space, is used to store dynamically allocated objects.
- Static memory is used to hold local
Dynamic Memory and Smart Pointers
- Dynamic Memory Management:
new: Allocates space for an object in dynamic memory and returns a pointer to that object.delete: Accepts a pointer to a dynamic object, destroys the object, and releases the associated memory.
- Smart Pointers:
- Manage dynamic objects.
- Behave like regular pointers.
- Responsible for automatically releasing the pointed-to objects.
- Smart pointers are also templates.
shared_ptr Class
Operations Supported by Both shared_ptr and unique_ptr:
| Operation | Explanation |
|---|---|
shared_ptr<T> sp unique_ptr<T> up | Empty smart pointer that can point to an object of type T |
p | Use p as a condition; true if p points to an object |
*p | Dereference p to get the object it points to. |
p->mem | Equivalent to (*p).mem |
p.get() | Returns the pointer stored in p; use with caution—if the smart pointer releases the object, the returned pointer becomes invalid. |
swap(p, q) p.swap(q) | Swap the pointers in p and q |
Operations Unique to shared_ptr:
| Operation | Explanation |
|---|---|
make_shared<T>(args) | Returns a shared_ptr pointing to a dynamically allocated object of type T. Initializes the object using args. |
shared_ptr<T>p(q) | p is a copy of shared_ptr q; this operation increments the counter in q. The pointer in q must be convertible to T* |
p = q | p and q are both shared_ptr; the pointers they hold must be convertible to each other. This operation decrements p‘s reference count and increments q‘s; if p‘s reference count becomes 0, the original memory it managed is released. |
p.unique() | Returns true if p.use_count() is 1; otherwise false |
p.use_count() | Returns the number of smart pointers sharing the object with p; may be slow, mainly for debugging. |
- Three Reasons to Use Dynamic Memory:
- The program doesn’t know how many objects it needs (e.g., container classes).
- The program doesn’t know the exact type of objects needed.
- The program needs to share data among multiple objects.
Direct Memory Management
- Dynamically allocate and initialize objects with
new.newcannot name the allocated object (since memory allocated in free space is unnamed), so it returns a pointer to the object.int *pi = new int(123);- If memory is exhausted, throws an exception of type
bad_alloc.
- Return dynamic memory to the system with
delete.- Accepts a pointer to the object to release.
- Pointer after
deleteis called a dangling pointer.
- Three common problems with managing dynamic memory using
newanddelete:- Forgetting to
deletememory.
- Using already released objects.
- Releasing the same memory twice.
- Forgetting to
- Adhering to using only smart pointers can avoid all these problems.
Combining shared_ptr and new
Other Ways to Define and Change shared_ptr:
| Operation | Explanation |
|---|---|
shared_ptr<T> p(q) | p manages the built-in pointer q to the object; q must point to memory allocated by new and be convertible to T* type |
shared_ptr<T> p(u) | p takes over ownership of the object from unique_ptr u; sets u to null |
shared_ptr<T> p(q, d) | p takes over ownership of the object pointed to by built-in pointer q. q must be convertible to T* type. p will use callable object d instead of delete. |
shared_ptr<T> p(p2, d) | p is a copy of shared_ptr p2, the only difference is that p will use callable object d instead of delete. |
p.reset() | If p is the only shared_ptr pointing to its object, reset releases this object. If an optional built-in pointer q is passed, makes p point to q, otherwise sets p to null. If parameter d is also passed, calls d instead of delete to release q. |
p.reset(q) | Same as above |
p.reset(q, d) | Same as above |
Smart Pointers and Exceptions
- If using smart pointers, even if the block ends prematurely due to an exception, the smart pointer class ensures the memory is released when no longer needed.
- Smart Pointer Pitfalls:
- Do not initialize (or
reset) multiple smart pointers with the same built-in pointer - Do not
deletethe pointer returned byget(). - If using the pointer returned by
get(), remember that when the last corresponding smart pointer is destroyed, your pointer becomes invalid. - If the resource managed by the smart pointer is not memory allocated by
new, remember to pass it a deleter.
- Do not initialize (or
unique_ptr
- At any given time, only one
unique_ptrcan point to a given object. - Does not support copy or assignment operations.
- Backward compatible:
auto_ptr: Old version, with some features ofunique_ptr. In particular, cannot storeauto_ptrin containers, nor returnauto_ptrfrom functions.
unique_ptr Operations:
| Operation | Explanation |
|---|---|
unique_ptr<T> u1 | Empty unique_ptr that can point to an object of type T. u1 uses delete to release its pointer. |
unique_ptr<T, D> u2 | u2 uses a callable object of type D to release its pointer. |
unique_ptr<T, D> u(d) | Empty unique_ptr pointing to an object of type T, using object d of type D instead of delete |
u = nullptr | Releases the object pointed to by u, sets u to null. |
u.release() | u relinquishes control of the pointer, returns the pointer, and sets u to null. |
u.reset() | Releases the object pointed to by u |
u.reset(q) | Makes u point to the object pointed to by q |
u.reset(nullptr) | Sets u to null |
weak_ptr
weak_ptris a smart pointer that does not control the lifetime of the pointed-to object.- Points to an object managed by
shared_ptr, without changing the reference count of theshared_ptr. - Once the last
shared_ptrpointing to the object is destroyed, the object is released, regardless of whether there areweak_ptrpointing to it.
weak_ptr Operations:
| Operation | Explanation |
|---|---|
weak_ptr<T> w | Empty weak_ptr that can point to an object of type T |
weak_ptr<T> w(sp) | weak_ptr sharing the same object as shared_ptr sp. T must be convertible to the type pointed to by sp. |
w = p | p can be a shared_ptr or a weak_ptr. After assignment, w and p share the object. |
w.reset() | Sets w to null. |
w.use_count() | Number of shared_ptr sharing the object with w. |
w.expired() | Returns true if w.use_count() is 0, otherwise false |
w.lock() | If expired is true, returns an empty shared_ptr; otherwise returns a shared_ptr pointing to the object of w. |
Dynamic Arrays
new and Arrays
newa dynamic array:- Add square brackets after the type name, specifying the number of objects to allocate (must be integer, not necessarily constant).
- Returns a pointer to the first object.
int *p = new int[size];
deletea dynamic array:delete [] p;
unique_ptrand Arrays:unique_ptrpointing to an array does not support member access operators (dot and arrow).
| Operation | Explanation |
|---|---|
unique_ptr<T[]> u | u can point to a dynamically allocated array, with element type T |
unique_ptr<T[]> u(p) | u points to the dynamically allocated array pointed to by built-in pointer p. p must be convertible to type T*. |
u[i] | Returns the object at position i in the array owned by u. u must point to an array. |
allocator Class
- The standard library
allocatorclass, defined in the headermemory, helps separate memory allocation from object construction. - Allocates raw, unconstructed memory.
allocatoris a template.allocator<string> alloc;
Standard Library allocator Class and Its Algorithms:
| Operation | Explanation |
|---|---|
allocator<T> a | Defines an allocator object named a that can allocate memory for objects of type T |
a.allocate(n) | Allocates a piece of raw, unconstructed memory to hold n objects of type T. |
a.deallocate(p, n) | Releases memory starting from address in T* pointer p, which holds n objects of type T; p must be a pointer previously returned by allocate. And n must be the size requested when p was created. Before calling deallocate, the user must call destroy on each object created in this memory. |
a.construct(p, args) | p must be a pointer of type T* pointing to raw memory; args are passed to a constructor of type T to construct an object in the memory pointed to by p. |
a.destroy(p) | p is a pointer of type T*; this algorithm destroys the object pointed to by p. |
Allocator Algorithms:
| Operation | Explanation |
|---|---|
uninitialized_copy(b, e, b2) | Copies the range from iterator b to e to the raw memory starting at iterator b2. The memory pointed to by b2 must be unconstructed. |
uninitialized_copy_n(b, n, b2) | Copies n elements starting from iterator b to the raw memory starting at b2. |
uninitialized_fill(b, e, t) | Constructs objects in the range from b to e with value t. |
uninitialized_fill_n(b, n, t) | Constructs n objects starting from b with value t. |
Memory Leaks
Memory leaks occur when a program fails to release dynamically allocated memory after it is no longer needed. This can lead to gradual memory exhaustion, causing performance degradation or program crashes.
Common Causes of Memory Leaks
- Forgetting to Free Memory: Failing to call
deleteordelete[]after usingnewornew[]. - Lost Pointers: Overwriting a pointer to allocated memory without freeing it first.
- Exceptions: Exceptions thrown before memory is freed.
- Circular References: In reference-counted systems, objects referencing each other prevent reference counts from reaching zero.
Detecting Memory Leaks
- Valgrind: A powerful tool for detecting memory leaks and errors on Linux.
- Visual Studio Debugger: Built-in tools for Windows developers.
- Address Sanitizer: Compiler flag (
-fsanitize=address) for GCC/Clang. - Custom Allocators: Override global
newanddeleteto track allocations.
Example: Using Valgrind
Compile your program with debug symbols:
g++ -g -o program program.cpp
Run with Valgrind:
valgrind --leak-check=full ./program
Valgrind will report any leaked memory and where it was allocated.
Preventing Memory Leaks
- Use Smart Pointers: Prefer
std::unique_ptrandstd::shared_ptrover raw pointers. - RAII Principle: Use Resource Acquisition Is Initialization to tie resource lifetime to object lifetime.
- Avoid Raw Pointers: When raw pointers are necessary, use them sparingly and document ownership.
- Regular Code Reviews: Check for proper memory management in peer reviews.
- Automated Testing: Include unit tests that check for leaks using tools like Valgrind.
Example: Preventing Leaks with Smart Pointers
#include <memory>
void process() {
std::unique_ptr<int> ptr(new int(42));
// Use ptr
// No need to delete; automatically freed when ptr goes out of scope
}
Memory Alignment
Memory alignment refers to the way data is arranged and accessed in computer memory. Proper alignment can improve performance and prevent hardware exceptions.
Alignment Requirements
- Most processors require that objects are aligned to multiples of their size.
- For example:
- 2-byte types (short) aligned to even addresses.
- 4-byte types (int, float) aligned to addresses multiple of 4.
- 8-byte types (double, long long) aligned to addresses multiple of 8.
Alignment in Structures
Compilers add padding bytes to structures to ensure proper alignment.
Example
struct Unaligned {
char c; // 1 byte
int i; // 4 bytes (may add 3 padding bytes)
};
struct Aligned {
int i; // 4 bytes
char c; // 1 byte (may add 3 padding bytes)
};
Use sizeof to check structure sizes.
Controlling Alignment
#pragma pack(n): Set alignment to n bytes.alignas(n): Specify alignment for variables or types (C++11+).std::aligned_alloc: Allocate aligned memory (C++17+).
Example: Using alignas
struct alignas(16) Vector4 {
float x, y, z, w;
};
Alignment Utilities
std::align: Align a pointer within a buffer.__builtin_assume_aligned: GCC extension for assuming alignment.
Buffer Overflow
Buffer overflow occurs when data is written beyond the boundaries of a buffer, potentially corrupting adjacent memory or enabling security exploits.
Causes
- String Operations: Using
strcpy,strcatwithout bounds checking. - Array Indexing: Accessing arrays with invalid indices.
- Input Reading: Reading more data than buffer can hold (e.g.,
gets). - Off-by-One Errors: Miscalculating loop bounds.
Detection
- Compiler Warnings: Enable all warnings (
-Wall -Wextrain GCC). - Static Analysis: Tools like Coverity, Clang Static Analyzer.
- Dynamic Analysis: Address Sanitizer (
-fsanitize=address). - Fuzz Testing: Tools like AFL (American Fuzzy Lop).
Prevention
- Use Safe Functions:
strncpy,strncat,snprintfinstead of unsafe ones. - Bounds Checking: Always check array indices and input sizes.
- Smart Pointers and Containers: Use
std::vector,std::stringwhich handle resizing. - Compiler Protections: Stack canaries (
-fstack-protector), ASLR. - Code Reviews: Check for potential overflows in input handling.
Example: Safe String Copy
#include <cstring>
#include <iostream>
int main() {
char dest[10];
const char* src = "Hello, World!";
std::strncpy(dest, src, sizeof(dest) - 1);
dest[sizeof(dest) - 1] = '\0'; // Ensure null-termination
std::cout << dest << std::endl; // Outputs: Hello, Wo
return 0;
}
Memory Pool
A memory pool is a pre-allocated block of memory from which smaller allocations are made. This can improve performance by reducing allocation overhead and fragmentation.
Benefits
- Faster allocations (no system calls after initial allocation).
- Reduced memory fragmentation.
- Better cache locality.
- Deterministic behavior in real-time systems.
Implementation
Memory pools can be implemented with fixed-size blocks or variable sizes.
Simple Fixed-Size Memory Pool Example
#include <vector>
#include <cstddef>
class MemoryPool {
public:
MemoryPool(size_t blockSize, size_t blockCount)
: _blockSize(blockSize), _pool(blockSize * blockCount) {
for (size_t i = 0; i < blockCount; ++i) {
_freeBlocks.push_back(&_pool[i * blockSize]);
}
}
void* allocate() {
if (_freeBlocks.empty()) {
return nullptr; // Or throw exception
}
void* block = _freeBlocks.back();
_freeBlocks.pop_back();
return block;
}
void deallocate(void* block) {
_freeBlocks.push_back(block);
}
private:
size_t _blockSize;
std::vector<char> _pool;
std::vector<void*> _freeBlocks;
};
int main() {
MemoryPool pool( sizeof(int), 10 );
int* p1 = static_cast<int*>(pool.allocate());
*p1 = 42;
pool.deallocate(p1);
return 0;
}
Popular Memory Pool Libraries
- Apache Portable Runtime (APR) Pools
- Boost.Pool
- jemalloc (has pooling for small allocations)
- tcmalloc (Google’s Thread-Caching Malloc)
Slab Allocation
Slab allocation is a memory management technique used in operating systems and applications to efficiently manage memory for objects of fixed size.
How It Works
- Pre-allocates large chunks (“slabs”) of memory.
- Divides slabs into fixed-size slots for objects.
- Maintains lists of full, partial, and empty slabs.
- Allocations from partial or empty slabs.
- Deallocations return slots to partial slabs.
Advantages
- Fast allocation/deallocation (O(1) time).
- Reduces external fragmentation.
- Improves cache performance (objects of same type clustered).
- Easy to implement object-specific constructors/destructors.
Implementation Example
A simple slab allocator for a specific class:
#include <vector>
#include <cstddef>
template <typename T>
class SlabAllocator {
public:
SlabAllocator(size_t slabSize) : _slabSize(slabSize) {
allocateNewSlab();
}
T* allocate() {
if (_freeSlots.empty()) {
allocateNewSlab();
}
T* obj = _freeSlots.back();
_freeSlots.pop_back();
new (obj) T(); // Placement new
return obj;
}
void deallocate(T* obj) {
obj->~T(); // Call destructor
_freeSlots.push_back(obj);
}
private:
void allocateNewSlab() {
_slabs.emplace_back(new char[_slabSize * sizeof(T)]);
char* slab = _slabs.back();
for (size_t i = 0; i < _slabSize; ++i) {
_freeSlots.push_back(reinterpret_cast<T*>(slab + i * sizeof(T)));
}
}
size_t _slabSize;
std::vector<char*> _slabs;
std::vector<T*> _freeSlots;
};
Garbage Collection in C++
C++ does not have built-in garbage collection (GC), but GC can be implemented or used via libraries.
Conservative GC
- Boehm-Demers-Weiser GC: A conservative collector for C/C++.
- Scans memory for potential pointers.
- May retain some garbage (false positives).
Using Boehm GC
Install libgc:
sudo apt install libgc-dev # On Ubuntu
Code:
#include <gc/gc.h>
int main() {
GC_INIT();
int* p = static_cast<int*>(GC_MALLOC(sizeof(int)));
*p = 42;
// No need to free; GC will collect
return 0;
}
Compile with -lgc.
Precise GC
- Requires compiler support or manual registration of roots.
- More efficient but harder to implement in C++.
Hybrid Approaches
- Use smart pointers for most objects.
- Implement GC for specific subsystems.
- Reference counting (like
std::shared_ptr) is a form of GC.
Pros and Cons of GC in C++
Pros:
- Reduces memory leaks.
- Simplifies code (no manual deletes).
Cons:
- Non-deterministic collection.
- Performance overhead.
- Pauses during collection.
- Not standard in C++.
For most C++ applications, manual management with smart pointers is preferred over full GC.
Cache Coherency
Cache coherency ensures that multiple caches in a multi-processor system have a consistent view of shared data.
Cache Coherency Protocols
- MSI (Modified, Shared, Invalid): Basic protocol.
- MESI (Modified, Exclusive, Shared, Invalid): Adds Exclusive state.
- MOESI: Adds Owned state for better performance.
False Sharing
Occurs when threads modify variables in the same cache line, causing unnecessary invalidations.
Mitigation:
- Pad structures to cache line size (typically 64 bytes).
- Use thread-local storage.
- Align variables to cache lines.
Example: Avoiding False Sharing
#include <thread>
#include <atomic>
struct PaddedCounter {
alignas(64) std::atomic<long long> count;
};
void increment(PaddedCounter& counter) {
for (int i = 0; i < 1000000; ++i) {
++counter.count;
}
}
int main() {
PaddedCounter c1, c2;
std::thread t1(increment, std::ref(c1));
std::thread t2(increment, std::ref(c2));
t1.join();
t2.join();
return 0;
}
Atomic Operations
Use std::atomic for lock-free synchronization, which handles cache coherency automatically.
Memory Barriers
Memory barriers (fences) ensure proper ordering of memory operations in multi-threaded programs.
Types
- Compiler Barriers: Prevent compiler reordering.
- Hardware Barriers: Ensure CPU doesn’t reorder operations.
In C++:
std::atomic_thread_fence: Full barrier.std::atomic_signal_fence: For signals.
Acquire/Release Semantics
- Acquire: Ensures loads after are not reordered before.
- Release: Ensures stores before are not reordered after.
Used with std::memory_order_acquire and std::memory_order_release in atomics.
Example
#include <atomic>
#include <thread>
std::atomic<bool> ready(false);
int data = 0;
void producer() {
data = 42;
ready.store(true, std::memory_order_release);
}
void consumer() {
while (!ready.load(std::memory_order_acquire)) {}
// data is now visible as 42
}
int main() {
std::thread t1(producer);
std::thread t2(consumer);
t1.join();
t2.join();
return 0;
}
Full Fence
std::atomic_thread_fence(std::memory_order_seq_cst): Strongest ordering, acts as a full barrier.
NUMA Awareness
Non-Uniform Memory Access (NUMA) systems have multiple nodes with local memory. Accessing remote memory is slower.
NUMA in C++
- Use
numalibrary on Linux. - Bind threads to nodes.
- Allocate memory on specific nodes.
Example with libnuma
Install libnuma-dev.
Code:
#include <numa.h>
#include <thread>
#include <vector>
void worker(int node) {
numa_run_on_node(node);
// Allocate local memory
std::vector<char> data(1024 * 1024);
// Work on data
}
int main() {
if (numa_available() < 0) {
return 1;
}
int num_nodes = numa_num_configured_nodes();
std::vector<std::thread> threads;
for (int i = 0; i < num_nodes; ++i) {
threads.emplace_back(worker, i);
}
for (auto& t : threads) {
t.join();
}
return 0;
}
Compile with -lnuma.
Best Practices
- Profile for NUMA effects.
- Use node-local allocation.
- Balance load across nodes.
- Consider NUMA in data structures (e.g., per-node caches).
Memory Management in Containers
C++ standard containers manage memory internally, but understanding their behavior is crucial for efficient use.
Vector
- Uses contiguous memory.
- Reallocates on growth (may copy elements).
reserve()to pre-allocate.shrink_to_fit()to reduce capacity.
Example
#include <vector>
int main() {
std::vector<int> v;
v.reserve(1000); // Pre-allocate
for (int i = 0; i < 500; ++i) {
v.push_back(i); // No reallocations
}
v.shrink_to_fit(); // Reduce memory usage
return 0;
}
List
- Non-contiguous, node-based.
- Constant time insertions/deletions.
- Higher memory overhead per element.
Deque
- Multiple fixed-size blocks.
- Efficient at both ends.
- Not truly contiguous.
Map/Set
- Typically red-black trees.
- Node-based allocation.
- Higher memory per element due to pointers and colors.
Custom Allocators
Containers support custom allocators for fine-grained control.
Example: Statefull Allocator
#include <vector>
#include <memory>
template <typename T>
class TrackingAllocator {
public:
using value_type = T;
TrackingAllocator() = default;
template <typename U>
TrackingAllocator(const TrackingAllocator<U>&) {}
T* allocate(std::size_t n) {
std::cout << "Allocating " << n * sizeof(T) << " bytes" << std::endl;
return static_cast<T*>(::operator new(n * sizeof(T)));
}
void deallocate(T* p, std::size_t n) {
std::cout << "Deallocating " << n * sizeof(T) << " bytes" << std::endl;
::operator delete(p);
}
};
template <typename T, typename U>
bool operator==(const TrackingAllocator<T>&, const TrackingAllocator<U>&) { return true; }
template <typename T, typename U>
bool operator!=(const TrackingAllocator<T>&, const TrackingAllocator<U>&) { return false; }
int main() {
std::vector<int, TrackingAllocator<int>> v;
v.push_back(1);
return 0;
}
Small Object Optimization
Some implementations use SOO for small containers to avoid allocations (e.g., small string optimization in std::string).
Virtual Memory
Virtual memory allows programs to use more memory than physically available by using disk as backing store.
Page Table
- Maps virtual addresses to physical addresses.
- Multi-level for efficiency (e.g., 4-level in x86-64).
Paging
- Memory divided into pages (typically 4KB).
- Pages swapped to/from disk as needed.
TLB (Translation Lookaside Buffer)
- Cache for page table entries.
- Improves translation speed.
- Flushed on context switches.
Huge Pages
- Larger pages (2MB or 1GB) to reduce TLB misses.
- Configure with
hugepagesin Linux.
Example: Using Huge Pages in Code
Use mmap with MAP_HUGETLB flag.
#include <sys/mman.h>
#include <iostream>
int main() {
size_t size = 2 * 1024 * 1024; // 2MB
void* ptr = mmap(nullptr, size, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB, -1, 0);
if (ptr == MAP_FAILED) {
std::cerr << "mmap failed" << std::endl;
return 1;
}
// Use ptr
munmap(ptr, size);
return 0;
}
Overcommit
Linux overcommits memory by default, allowing more allocations than available RAM + swap.
Control with /proc/sys/vm/overcommit_memory.
Memory-Mapped Files
Memory-mapped files allow treating files as memory, enabling efficient I/O.
mmap
- Maps file into address space.
- Access via pointers.
- Changes are synced to file.
Example
#include <sys/mman.h>
#include <fcntl.h>
#include <unistd.h>
#include <iostream>
#include <cstring>
int main() {
int fd = open("file.txt", O_RDWR | O_CREAT, 0666);
if (fd == -1) return 1;
size_t size = 1024;
ftruncate(fd, size);
char* map = static_cast<char*>(mmap(nullptr, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0));
if (map == MAP_FAILED) return 1;
std::strcpy(map, "Hello, mmap!");
std::cout << map << std::endl;
munmap(map, size);
close(fd);
return 0;
}
Advantages
- Efficient for large files.
- Shared memory between processes (MAP_SHARED).
- Lazy loading (pages loaded on access).
Caveats
- File must exist and be sized properly.
- Changes may not be immediate (use msync).
- Error handling crucial.
Stack vs Heap Allocation
Stack Allocation
- Automatic (local variables).
- Fast (just adjust stack pointer).
- Limited size (typically 1-8MB).
- LIFO lifetime.
Heap Allocation
- Manual (new/malloc).
- Slower (search for free block).
- Larger size (limited by virtual memory).
- Arbitrary lifetime.
When to Use Each
- Stack: Small, short-lived objects.
- Heap: Large objects, dynamic sizes, long-lived.
Performance Comparison Example
#include <chrono>
#include <iostream>
const int N = 1000000;
void stackAlloc() {
for (int i = 0; i < N; ++i) {
int x = i;
(void)x;
}
}
void heapAlloc() {
for (int i = 0; i < N; ++i) {
int* p = new int(i);
delete p;
}
}
int main() {
auto start = std::chrono::high_resolution_clock::now();
stackAlloc();
auto end = std::chrono::high_resolution_clock::now();
std::cout << "Stack: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << std::endl;
start = std::chrono::high_resolution_clock::now();
heapAlloc();
end = std::chrono::high_resolution_clock::now();
std::cout << "Heap: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << std::endl;
return 0;
}
Stack is typically much faster.
Custom Memory Allocators
Custom allocators allow fine-tuned memory management for specific needs.
Global new/delete Override
Override global operators for all allocations.
Example
#include <new>
#include <iostream>
#include <cstdlib>
void* operator new(size_t size) {
std::cout << "Allocating " << size << " bytes" << std::endl;
return std::malloc(size);
}
void operator delete(void* p) noexcept {
std::cout << "Deallocating" << std::endl;
std::free(p);
}
int main() {
int* p = new int(42);
delete p;
return 0;
}
Class-Specific new/delete
Override within a class for that type only.
Example
class Foo {
public:
static void* operator new(size_t size) {
std::cout << "Foo::new " << size << std::endl;
return ::operator new(size);
}
static void operator delete(void* p) noexcept {
std::cout << "Foo::delete" << std::endl;
::operator delete(p);
}
};
int main() {
Foo* f = new Foo();
delete f;
return 0;
}
STL Allocators
As shown earlier, for containers.
Use Cases
- Performance-critical applications.
- Embedded systems with limited memory.
- Custom pooling for frequent small allocations.
- Debugging and profiling.
Memory Fragmentation
Memory fragmentation occurs when free memory is broken into small, non-contiguous blocks, making large allocations difficult.
Types
- External Fragmentation: Free memory scattered, total free sufficient but no single block large enough.
- Internal Fragmentation: Allocated blocks larger than needed, wasting space within blocks.
Causes
- Frequent allocations/deallocations of varying sizes.
- Long-lived small allocations preventing compaction.
Mitigation
- Memory Pools: For fixed-size objects.
- Slab Allocators: For kernel or specific sizes.
- Buddy System: Power-of-two allocations to reduce external frag.
- Compaction: Move allocated blocks (hard in C++ due to pointers).
- Use Appropriate Sizes: Round up to powers of two or multiples.
- jemalloc/tcmalloc: Modern allocators with better frag handling.
Monitoring
- Track allocation stats.
- Use tools like Massif (Valgrind) for heap profiles.
RAII (Resource Acquisition Is Initialization)
RAII is a C++ idiom where resource acquisition occurs during object initialization, and release during destruction.
Benefits
- Automatic resource management.
- Exception-safe.
- Reduces leaks.
Examples
- Smart Pointers: As above.
- Locks:
std::lock_guard,std::unique_lock. - Files: Custom wrapper.
File Wrapper Example
#include <fstream>
#include <string>
class FileHandle {
public:
FileHandle(const std::string& filename) : _file(filename) {
if (!_file.is_open()) {
throw std::runtime_error("Failed to open file");
}
}
~FileHandle() {
_file.close();
}
std::ofstream& get() { return _file; }
private:
std::ofstream _file;
};
void useFile() {
FileHandle file("output.txt");
file.get() << "Hello, RAII!" << std::endl;
// File auto-closed on exit
}
Extensions
- Scope guards for arbitrary cleanup.
- Lambdas with destructors (C++11+).
Scope Guard Example
class ScopeGuard {
public:
ScopeGuard(std::function<void()> f) : _func(f) {}
~ScopeGuard() { _func(); }
private:
std::function<void()> _func;
};
void func() {
FILE* f = fopen("file.txt", "w");
ScopeGuard guard([&] { fclose(f); });
// Use f
}
Move Semantics and Memory
Move semantics (C++11+) allow efficient transfer of resources without copying.
rvalue References
T&&: rvalue reference.- Binds to temporary objects.
std::move
- Casts to rvalue reference.
- Enables move constructors/assignments.
Example
class String {
public:
String() : _data(nullptr), _size(0) {}
String(const char* str) {
_size = std::strlen(str);
_data = new char[_size + 1];
std::strcpy(_data, str);
}
// Copy constructor
String(const String& other) {
_size = other._size;
_data = new char[_size + 1];
std::strcpy(_data, other._data);
}
// Move constructor
String(String&& other) noexcept : _data(other._data), _size(other._size) {
other._data = nullptr;
other._size = 0;
}
~String() { delete[] _data; }
private:
char* _data;
size_t _size;
};
int main() {
String s1("Hello");
String s2 = std::move(s1); // Move, no copy
return 0;
}
Benefits for Memory
- Avoids unnecessary allocations/copies.
- Efficient for containers (e.g., vector growth).
- Crucial for unique ownership transfer.
noexcept
Specify move operations as noexcept for better optimizations.
Memory Sanitizers
Memory sanitizers detect memory errors at runtime.
AddressSanitizer (ASan)
- Detects out-of-bounds, use-after-free, etc.
- Enabled with
-fsanitize=addressin GCC/Clang.
UndefinedBehaviorSanitizer (UBSan)
- Detects undefined behavior like integer overflow.
ThreadSanitizer (TSan)
- Detects data races.
Usage
Compile and run:
g++ -fsanitize=address -g program.cpp
./a.out
ASan will report errors with stack traces.
Integration
- In build systems (CMake:
add_compile_options(-fsanitize=address)). - In CI for automated testing.
Object Lifetime Management
Proper management of object lifetimes prevents use-after-free and dangling references.
Rules
- Destroy objects in reverse order of construction.
- Don’t use objects after destruction.
- Be careful with object slicing in inheritance.
Tools
- Smart pointers for automatic management.
std::enable_shared_from_thisfor shared_ptr from this.- Static analysis for lifetime issues.
enable_shared_from_this Example
#include <memory>
#include <iostream>
class Widget : public std::enable_shared_from_this<Widget> {
public:
std::shared_ptr<Widget> getShared() {
return shared_from_this();
}
};
int main() {
auto w = std::make_shared<Widget>();
auto shared = w->getShared();
std::cout << shared.use_count() << std::endl; // 2
return 0;
}
Dangling References
Avoid returning references to locals.
Bad Example
const int& getValue() {
int x = 42;
return x; // Dangling!
}
Use values or smart pointers instead.
Custom Memory Management Operators
Beyond overriding new/delete, placement new allows constructing objects in pre-allocated memory.
Placement new
- Constructs object at specific address.
- Doesn’t allocate memory.
Example
#include <new>
int main() {
char buffer[sizeof(int)];
int* p = new (buffer) int(42); // Placement new
// Use *p
p->~int(); // Manual destructor
return 0;
}
Uses
- Custom allocators.
- Memory pools.
- Avoiding default construction in containers.
operator new Variants
operator new(size_t): Allocates raw memory.operator new(size_t, nothrow_t): Non-throwing version.- Placement forms.
Memory Consumption Profiling
Profiling helps identify memory usage patterns and leaks.
Tools
- Valgrind Massif: Heap profiler.
- Heaptrack: Linux heap profiler.
- Visual Studio Performance Profiler: For Windows.
- Instruments: On macOS.
- gperftools: Google’s heap profiler.
Using Massif
valgrind --tool=massif ./program
ms_print massif.out.*
Generates allocation timeline graph.
Custom Profiling
Instrument allocations with logging.
Example
#include <map>
#include <mutex>
std::map<void*, size_t> allocations;
std::mutex alloc_mutex;
void* operator new(size_t size) {
void* p = std::malloc(size);
{
std::lock_guard<std::mutex> lock(alloc_mutex);
allocations[p] = size;
}
return p;
}
void operator delete(void* p) noexcept {
{
std::lock_guard<std::mutex> lock(alloc_mutex);
allocations.erase(p);
}
std::free(p);
}
// Periodically print allocations.size() or total size
Cache Optimization Techniques
Optimizing for CPU caches improves performance dramatically.
Data Locality
- Spatial: Access nearby data.
- Temporal: Reuse data soon.
Techniques
- Structure of Arrays (SoA) vs Array of Structures (AoS):
- SoA better for SIMD and cache.
Example
// AoS
struct ParticleAoS {
float x, y, z;
float vx, vy, vz;
};
// SoA
struct ParticleSoA {
std::vector<float> x, y, z;
std::vector<float> vx, vy, vz;
};
- Cache Blocking: Process data in blocks fitting cache.
- Prefetching:
__builtin_prefetchin GCC. - Alignment: As discussed earlier.
- Avoid False Sharing: As above.
- Data Compression: Reduce memory bandwidth.
Tools
- Cachegrind (Valgrind): Simulates cache.
- perf: Linux performance counter.
Thread-Local Storage
TLS provides per-thread variables.
In C++
thread_localkeyword (C++11+).
Example
#include <thread>
#include <iostream>
thread_local int tls_var = 0;
void func() {
++tls_var;
std::cout << tls_var << std::endl;
}
int main() {
std::thread t1(func);
std::thread t2(func);
t1.join();
t2.join();
return 0;
}
Each thread sees its own tls_var.
Uses
- Per-thread caches.
- Thread-specific error states (like errno).
- Avoiding locks for thread-private data.
Caveats
- Initialization/destruction ordering.
- Limited in dynamic libraries.
Lock-Free Programming
Lock-free algorithms use atomics for concurrency without locks.
Benefits
- Better scalability.
- No deadlocks.
- Progress guarantee.
Tools
std::atomic<T>- Compare-and-Swap (CAS):
compare_exchange_strong/weak
Lock-Free Stack Example
#include <atomic>
template <typename T>
class LockFreeStack {
private:
struct Node {
T data;
Node* next;
};
std::atomic<Node*> _head;
public:
void push(const T& data) {
Node* newNode = new Node{data, _head.load()};
while (!_head.compare_exchange_weak(newNode->next, newNode)) {}
}
bool pop(T& result) {
Node* oldHead = _head.load();
while (oldHead && !_head.compare_exchange_weak(oldHead, oldHead->next)) {}
if (oldHead) {
result = oldHead->data;
delete oldHead;
return true;
}
return false;
}
};
Challenges
- ABA problem: Solved with tagged pointers.
- Memory ordering.
- Debugging difficulties.
Memory Models in C++
C++11 introduces a memory model defining how threads see memory operations.
Sequential Consistency
- Strongest: All operations appear in a total order.
std::memory_order_seq_cst
Relaxed
- Weakest: No ordering guarantees.
std::memory_order_relaxed
Acquire/Release
- As mentioned earlier.
Consume
- Weaker acquire for data dependencies.
Choosing Orders
- Use seq_cst for simplicity if performance allows.
- Optimize with weaker orders carefully.
Advanced Allocation Strategies
Buddy Allocator
- Divides memory into power-of-two blocks.
- Merges/splits as needed.
- Reduces external fragmentation.
Simple Buddy Example
Implementing a full buddy is complex; here’s a sketch:
class BuddyAllocator {
// Free lists for each power-of-two size
std::vector<std::list<void*>> freeLists;
// ...
};
Segregated Free Lists
- Multiple free lists for different size classes.
- Fast for small allocations.
Used in jemalloc, tcmalloc.
Thread-Caching Allocators
- Per-thread caches for small objects.
- Reduces contention.
tcmalloc: Thread-Caching Malloc.
Memory Compression
Compress memory pages to save RAM.
zSwap (Linux)
- Compresses swap pages in RAM.
Application-Level
- Compress rarely used data.
- Libraries like zstd, snappy.
Example with zstd
Install libzstd.
#include <zstd.h>
#include <vector>
std::vector<char> compress(const std::vector<char>& data) {
size_t maxSize = ZSTD_compressBound(data.size());
std::vector<char> compressed(maxSize);
size_t size = ZSTD_compress(compressed.data(), maxSize, data.data(), data.size(), 3);
compressed.resize(size);
return compressed;
}
std::vector<char> decompress(const std::vector<char>& compressed) {
size_t decompressedSize = ZSTD_findDecompressedSize(compressed.data(), compressed.size());
std::vector<char> data(decompressedSize);
ZSTD_decompress(data.data(), decompressedSize, compressed.data(), compressed.size());
return data;
}
Link with -lzstd.
Huge Pages in Applications
As mentioned earlier, reduces TLB misses for large allocations.
Transparent Huge Pages (THP)
Enabled in Linux kernel.
Check: cat /sys/kernel/mm/transparent_hugepage/enabled
Explicit Use
mmapwithMAP_HUGETLBhugetlbfsfilesystem.
Pre-allocate huge pages:
echo 100 > /proc/sys/vm/nr_hugepages
Memory Hotplug
Adding/removing memory at runtime.
In Linux
- For virtual machines.
memory_hotplugsubsystem.
Not typically used in applications directly.
Out-of-Memory Handling
Handle low memory situations gracefully.
std::bad_alloc
Thrown by new on failure.
Handling
try {
int* p = new int[1000000000];
} catch (const std::bad_alloc& e) {
std::cerr << "Allocation failed: " << e.what() << std::endl;
}
new_handler
Custom handler for allocation failures.
Example
#include <new>
void my_new_handler() {
std::cerr << "Allocation failed" << std::endl;
std::abort();
}
int main() {
std::set_new_handler(my_new_handler);
// ...
return 0;
}
Overcommit Handling
In Linux, OOM killer may terminate processes.
Adjust with vm.overcommit_memory.
Memory Debugging Techniques
Advanced debugging for memory issues.
Electric Fence
- Library that detects overflows/underflows.
- Link with
-lefence.
DUMA (Detect Unintended Memory Access)
- Similar to Electric Fence.
mprotect
- Change page protections to detect accesses.
Example: Detect Use-After-Free
#include <sys/mman.h>
void* alloc(size_t size) {
void* p = mmap(nullptr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
return p;
}
void dealloc(void* p, size_t size) {
mprotect(p, size, PROT_NONE); // Make inaccessible
// Don't munmap to catch accesses
}
Access after dealloc will segfault.
Conditional Breakpoints
In GDB: break if condition
For memory watches: watch expression
Arena Allocation
Arena (region-based) allocation: Allocate from a large block, free all at once.
Benefits
- Fast allocation (bump pointer).
- No individual deallocations.
- Good for temporary objects.
Simple Arena Example
class Arena {
public:
Arena(size_t size) : _buffer(new char[size]), _ptr(_buffer), _end(_buffer + size) {}
~Arena() { delete[] _buffer; }
void* allocate(size_t size) {
if (_ptr + size > _end) return nullptr;
void* p = _ptr;
_ptr += size;
return p;
}
private:
char* _buffer;
char* _ptr;
char* _end;
};
int main() {
Arena a(1024);
int* p = static_cast<int*>(a.allocate(sizeof(int)));
*p = 42;
// No delete; freed with arena
return 0;
}
Uses
- Compilers (per-phase allocations).
- Games (per-frame temp memory).
- Protocol buffers.
Linear Allocation
Similar to arena, but often for specific types.
Bump allocator: Increment pointer for each allocation.
No free; reset for reuse.
Example
class LinearAllocator {
public:
LinearAllocator(size_t size) : _buffer(new char[size]), _ptr(_buffer) {}
~LinearAllocator() { delete[] _buffer; }
template <typename T, typename... Args>
T* alloc(Args&&... args) {
void* p = _ptr;
_ptr += sizeof(T);
return new (p) T(std::forward<Args>(args)...);
}
void reset() { _ptr = _buffer; }
private:
char* _buffer;
char* _ptr;
};
Stack Allocation with alloca
alloca: Allocates on stack, auto-freed on return.
Non-standard, but available in many compilers.
Example
#include <alloca.h>
#include <cstring>
#include <iostream>
void func(int size) {
char* buf = static_cast<char*>(alloca(size));
std::strcpy(buf, "Hello");
std::cout << buf << std::endl;
// Auto-freed
}
Risks
- Stack overflow if size large.
- Not portable.
- Can’t return pointer.
Prefer std::vector for dynamic stack-like allocation.
Memory Reuse Patterns
Reuse memory to reduce allocations.
Object Pools
As memory pools, but for objects.
Call constructor on allocation, destructor on return.
Example
template <typename T>
class ObjectPool {
public:
ObjectPool(size_t size) {
for (size_t i = 0; i < size; ++i) {
_pool.push_back(new T());
}
}
~ObjectPool() {
for (auto p : _pool) delete p;
}
T* acquire() {
if (_pool.empty()) return new T();
T* obj = _pool.back();
_pool.pop_back();
return obj;
}
void release(T* obj) {
_pool.push_back(obj);
}
private:
std::vector<T*> _pool;
};
Flyweight Pattern
Share immutable objects to save memory.
Example: String interning.
Simple String Interner
#include <unordered_map>
#include <string>
class StringInterner {
public:
const std::string& intern(const std::string& str) {
auto it = _strings.insert(str);
return *it.first;
}
private:
std::unordered_set<std::string> _strings;
};
Memoization
Cache function results.
Example: Fibonacci Memoization
#include <map>
std::map<long long, long long> memo;
long long fib(long long n) {
if (n <= 1) return n;
auto it = memo.find(n);
if (it != memo.end()) return it->second;
long long result = fib(n-1) + fib(n-2);
memo[n] = result;
return result;
}
Cache Warming
Pre-load data into cache for better performance.
Techniques
- Prefetch Instructions:
_mm_prefetchfor SSE. - Touch Data: Access data before critical section.
- Sequential Access: Design algorithms for linear memory access.
Example: Prefetch
#include <xmmintrin.h>
void process(float* data, size_t size) {
for (size_t i = 0; i < size; ++i) {
if (i + 8 < size) _mm_prefetch(&data[i + 8], _MM_HINT_T0);
// Process data[i]
}
}
When to Use
- Predictable access patterns.
- Performance-critical loops.
- Startup initialization.
Memory Bandwidth Optimization
Optimize to reduce memory traffic.
Techniques
- Data Compression: As above.
- Cache Blocking: Process sub-matrices.
- Fusion: Combine loops accessing same data.
- Vectorization: Use SIMD to process more data per load.
- Avoid Unnecessary Copies: Use references, move semantics.
Measuring
- perf stat: Cache misses, instructions.
- Intel VTune: Memory access analysis.
Matrix Transpose Optimization Example
Naive:
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
b[j][i] = a[i][j];
Blocked:
const int BLOCK = 32;
for (int ii = 0; ii < N; ii += BLOCK)
for (int jj = 0; jj < N; jj += BLOCK)
for (int i = ii; i < ii + BLOCK; ++i)
for (int j = jj; j < jj + BLOCK; ++j)
b[j][i] = a[i][j];
Better cache usage.
LRU Cache Implementation
Least Recently Used cache evicts least recently accessed items.
Example Implementation
#include <unordered_map>
#include <list>
#include <utility>
class LRUCache {
public:
LRUCache(int capacity) : _capacity(capacity) {}
int get(int key) {
auto it = _cache.find(key);
if (it == _cache.end()) return -1;
_lru.splice(_lru.begin(), _lru, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = _cache.find(key);
if (it != _cache.end()) {
_lru.splice(_lru.begin(), _lru, it->second);
it->second->second = value;
return;
}
if (_cache.size() == _capacity) {
int removeKey = _lru.back().first;
_lru.pop_back();
_cache.erase(removeKey);
}
_lru.emplace_front(key, value);
_cache[key] = _lru.begin();
}
private:
int _capacity;
std::list<std::pair<int, int>> _lru;
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> _cache;
};
int main() {
LRUCache cache(2);
cache.put(1, 1);
cache.put(2, 2);
std::cout << cache.get(1) << std::endl; // 1
cache.put(3, 3); // evicts 2
std::cout << cache.get(2) << std::endl; // -1
return 0;
}
LFU Cache Implementation
Least Frequently Used evicts least frequently used items.
Example (Simplified)
#include <unordered_map>
#include <list>
#include <utility>
struct FreqNode {
int freq;
std::list<int> keys;
std::list<int>::iterator keyIt;
};
class LFUCache {
public:
LFUCache(int capacity) : _capacity(capacity), _minFreq(0) {}
int get(int key) {
auto it = _cache.find(key);
if (it == _cache.end()) return -1;
updateFreq(it->second);
return it->second.val;
}
void put(int key, int value) {
if (_capacity == 0) return;
auto it = _cache.find(key);
if (it != _cache.end()) {
it->second.val = value;
updateFreq(it->second);
return;
}
if (_cache.size() == _capacity) {
evict();
}
_minFreq = 1;
_freq[1].keys.push_front(key);
_cache[key] = {value, 1, _freq[1].keys.begin()};
}
private:
struct Node {
int val, freq;
std::list<int>::iterator it;
};
void updateFreq(Node& node) {
_freq[node.freq].keys.erase(node.it);
if (_freq[node.freq].keys.empty() && node.freq == _minFreq) ++_minFreq;
++node.freq;
_freq[node.freq].keys.push_front(0); // dummy
node.it = _freq[node.freq].keys.begin();
}
void evict() {
auto& keys = _freq[_minFreq].keys;
int key = keys.back();
keys.pop_back();
_cache.erase(key);
}
int _capacity, _minFreq;
std::unordered_map<int, Node> _cache;
std::unordered_map<int, FreqNode> _freq;
};
(Note: This is a simplified version; full implementation needs careful handling.)
Cache Replacement Policies
Besides LRU and LFU, other policies:
- FIFO (First-In, First-Out): Replace in entry order.
- LFU (Least Frequently Used): Replace least used.
- Random: Random selection.
- Clock Algorithm: Combines FIFO and LRU, scans with use bits.
- Second Chance: Gives entries a second chance.
Advanced Smart Pointer Usage
Smart pointers are crucial for automatic dynamic memory management in C++. They use RAII to handle resources.
Weak Pointers and Lifetime Management
std::weak_ptr doesn’t increment shared_ptr count. Used to break cycles.
Example
#include <memory>
#include <iostream>
class Node {
public:
Node(int val) : _value(val) {}
~Node() { std::cout << "Node " << _value << " destroyed" << std::endl; }
int getValue() const { return _value; }
private:
int _value;
};
void weakPointerExample() {
std::shared_ptr<Node> sharedNode = std::make_shared<Node>(42);
std::weak_ptr<Node> weakNode(sharedNode);
if (auto ptr = weakNode.lock()) {
std::cout << "Value: " << ptr->getValue() << std::endl;
} else {
std::cout << "No longer valid" << std::endl;
}
// When sharedNode destroyed, weakNode invalidates
}
int main() {
weakPointerExample();
return 0;
}
Custom Deleters
For custom cleanup or non-new resources.
Example
#include <memory>
#include <iostream>
class Resource {
public:
~Resource() { std::cout << "Resource released" << std::endl; }
};
// Custom deleter
struct CustomDeleter {
void operator()(Resource* p) const {
std::cout << "Custom deletion logic" << std::endl;
delete p;
}
};
void customDeleterExample() {
std::unique_ptr<Resource, CustomDeleter> resource(new Resource(), CustomDeleter());
}
int main() {
customDeleterExample();
return 0;
}
Persistence Management
Combine smart pointers with serialization for persistence.
Example with cereal
(Installation as above)
#include <memory>
#include <fstream>
#include "cereal/archives/binary.hpp"
#include "cereal/types/vector.hpp"
class Data {
public:
Data(int x, double y) : _x(x), _y(y) {}
int getX() const { return _x; }
double getY() const { return _y; }
private:
friend class cereal::access;
template<class Archive>
void serialize(Archive & ar) {
ar(_x, _y);
}
int _x;
double _y;
};
void serializationExample() {
std::shared_ptr<Data> data = std::make_shared<Data>(42, 3.14);
std::ofstream file("data.bin", std::ios::binary);
cereal::BinaryOutputArchive output(file);
output(*data);
file.close();
std::ifstream fileIn("data.bin", std::ios::binary);
std::shared_ptr<Data> loadedData = std::make_shared<Data>(0, 0.0);
cereal::BinaryInputArchive input(fileIn);
input(*loadedData);
fileIn.close();
std::cout << "Loaded data: " << loadedData->getX() << ", " << loadedData->getY() << std::endl;
}
int main() {
serializationExample();
return 0;
}



