Analyzing New Heap Allocation Overhead in Linux Virtual Address Space

Why memory problems appear in C++ programs

During normal C++ development you may notice that a program’s memory usage grows over time, eventually causing crashes or severe slowdown. These symptoms are often tied to heap memory allocation, especially the new operator.

Linux virtual address space

Each Linux process has its own virtual address space, which is a logical view of memory ranging from 0 to a large limit (e.g., 0‑4 GB on 32‑bit systems). The virtual addresses are mapped to physical memory via page tables. Different regions of the address space have distinct purposes and management rules.

Code segment : read‑only area that stores compiled machine instructions.

Data segment : contains initialized globals, static variables, and the BSS for uninitialized data.

Heap segment : used for dynamic allocation; objects created with new reside here.

Stack segment : holds function call frames, local variables, and return addresses; managed automatically by the OS.

Other regions : read‑only data, shared memory, etc.

When a process accesses a virtual address, the MMU splits it into a virtual page number and offset, looks up the corresponding physical page frame in the page table, and combines them to obtain the physical address. If the page is not present, a page‑fault interrupt triggers loading from disk or page replacement (e.g., LRU).

New heap allocation process

Class loading check : before allocating memory, the runtime verifies that the class is loaded, linked, and initialized.

Pointer‑bump allocation : if the heap is contiguous, a pointer is moved forward by the object size to reserve space.

Free‑list allocation : when the heap is fragmented, the allocator scans a free‑list to find a suitably sized block.

CAS‑based concurrency control : multiple threads may attempt allocation simultaneously; compare‑and‑swap with retry ensures atomicity.

Thread‑local allocation buffer (TLAB) : each thread can obtain a private buffer to reduce contention.

Initialization and object header setup : after space is reserved, the memory is zero‑initialized (or set to defaults), the object header (hash code, lock state, type pointer, etc.) is written, and the constructor is invoked.

Overhead analysis

(1) Memory fragmentation

Frequent new and delete of small objects can leave scattered free blocks. When a large allocation is later requested, the allocator may fail to find a contiguous region despite sufficient total free memory.

#include <iostream>
#include <vector>
int main() {
    std::vector<int*> smallMemList;
    // 1. Allocate many small blocks
    for (int i = 0; i < 10000; ++i) {
        int* p = new int(1);
        smallMemList.push_back(p);
    }
    // 2. Free every other block, creating gaps
    for (int i = 0; i < smallMemList.size(); i += 2) {
        delete smallMemList[i];
        smallMemList[i] = nullptr;
    }
    // 3. Attempt a large contiguous allocation
    char* bigBuf = new char[1024 * 100];
    delete[] bigBuf;
    // Clean up remaining blocks
    for (int* p : smallMemList) {
        if (p != nullptr) delete p;
    }
    return 0;
}

The program demonstrates that after freeing alternating blocks, the heap becomes fragmented, making a subsequent large allocation slower or impossible.

(2) Time overhead

Each new may need to traverse a free‑list, update pointers, or handle a page‑fault if the required page is not resident, incurring noticeable latency, especially when the free‑list is long or when disk I/O is involved.

#include <iostream>
#include <chrono>
#include <vector>
int main() {
    auto start = std::chrono::high_resolution_clock::now();
    std::vector<char*> memList;
    // Frequent small allocations
    for (int i = 0; i < 500000; ++i) {
        char* p = new char[32];
        memList.push_back(p);
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto cost = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "Total new time: " << cost.count() << "ms" << std::endl;
    for (char* p : memList) delete[] p;
    return 0;
}

The benchmark shows that while a single small allocation is cheap, the cumulative cost of millions of allocations becomes significant.

(3) Space overhead

Beyond the user data, each allocation carries metadata (size, status, links) stored in the allocator’s bookkeeping structures. When many tiny objects are allocated, the metadata can dominate memory usage.

#include <iostream>
#include <vector>
int main() {
    std::vector<int*> smallMem;
    // Many small allocations
    for (int i = 0; i < 10000; ++i) {
        smallMem.push_back(new int(0));
    }
    // One large allocation
    int* bigMem = new int[10000];
    std::cout << "Many small allocations incur high metadata overhead" << std::endl;
    std::cout << "Single large allocation improves memory utilization" << std::endl;
    for (int* p : smallMem) delete p;
    delete[] bigMem;
    return 0;
}

Both programs allocate the same total amount of user data, but the first incurs far more metadata, reducing effective memory utilization.

Real‑world case study

A simple logging system creates a LogEntry object for each message, allocating a std::string on the heap inside the constructor. When logging hundreds of thousands of messages, the repeated new calls cause severe heap fragmentation and performance degradation.

#include <iostream>
#include <vector>
#include <string>
#include <ctime>
class LogEntry {
public:
    LogEntry(int level, const std::string& message)
        : logLevel(level), timeStamp(std::time(nullptr)), logMessage(new std::string(message)) {}
    ~LogEntry() { delete logMessage; }
private:
    int logLevel;
    time_t timeStamp;
    std::string* logMessage;
};
class Logger {
public:
    void log(int level, const std::string& message) { entries.push_back(LogEntry(level, message)); }
private:
    std::vector<LogEntry> entries;
};
int main() {
    Logger logger;
    for (int i = 0; i < 100000; ++i) {
        std::string msg = "This is log message " + std::to_string(i);
        logger.log(1, msg);
    }
    return 0;
}

Mitigation strategies demonstrated:

Reduce unnecessary allocations by reusing identical log messages.

Introduce a memory pool for LogEntry objects to avoid per‑object new / delete.

Replace raw std::string* with std::unique_ptr<std::string> (or better, store the string directly) to automate memory management.

Consider alternative containers (e.g., std::list) if frequent insertions/deletions cause costly reallocations in a std::vector.

Conclusion

In Linux, each process’s virtual address space is divided into code, data, heap, and stack regions, with page‑table‑driven mapping to physical memory. The C++ new operator performs class‑loading checks, chooses an allocation strategy (pointer bump or free‑list), handles concurrency via CAS or TLAB, initializes memory, sets object headers, and finally runs constructors. Its overhead manifests as memory fragmentation, time latency, and extra space for metadata, all of which can degrade application performance. Understanding these mechanisms and applying techniques such as memory pooling, smart pointers, and appropriate container choices can substantially mitigate the costs.