lazy allocation for c++ object arrays

Question

If I do something like:

void f() {
    const int n = 1<<14;
    int *foo = new int [n];
}

or

void f() {
    const int n = 1<<14;
    int *foo = new int [n]();
}

Will the Linux kernel will use lazy memory allocation? For the second case, in the same way than when creating static arrays?

How far can I take this? For instance, having a struct that will be filled with 0s, will it always be allocated lazily, or will it actually allocate physical RAM when it is initialized?

struct X {
    int a, b, c, d, f, g, ..., z;
}

void f() {
    int *foo = new X();//lazy?
    const int n = 1<<14;
    int *foo = new X [n]();//lazy?
}

it depend on the implementation of `new` but it is very likely that `new` is implement with `brk` witch can't be lazy, if you want lazy allocation you should look at `mmap` — Tyker, Jun 19 '18 at 15:03
Please take a look at [this SO post](https://stackoverflow.com/questions/864416/are-some-allocators-lazy). I'd imagine `new` uses `malloc` under the hood. — Ron, Jun 19 '18 at 15:03
@Ron one thing not mentioned in the link is that `malloc` uses data for internal bookkeeping and will write to the allocated data just after the `brk` call making it a not lazy — Tyker, Jun 19 '18 at 15:21
The Linux kernel in its usual/default configuration where overcommit is enabled, will usually not back any allocations with physical pages until the virtual addresses are actually written to. — Jesper Juhl, Jun 19 '18 at 15:27
@Tyker: For a large allocation, the pages touched by `malloc` will be few (or even zero if it uses `mmap`). — Davis Herring, Jun 21 '18 at 03:41

score 2 · Accepted Answer · answered Oct 17 '20 at 21:15

For a standard Ubuntu 20.04 machine running Linux 5.4.0-51-generic....

We can observe this directly. In the code below, I increased the n value to 1 << 24 (~16 million ints = 64MB for 32-bit int) so it's the dominant factor in overall memory usage. I compiled, ran, and observed memory usage in htop:

#include <unistd.h>
int main() {
    int *foo = new int [1 << 24];
    sleep(100);
}

htop values: VIRT 71416KB / RES 1468KB

The virtual address allocations include the memory allocated by new, but the resident memory size is much smaller - indicating that distinct physical backing memory pages weren't needed yet for all the 64MB allocated.

After changing to int *foo = new int[1<<24]();:

htop values: VIRT 71416KB / RES 57800KB

Requesting the memory be zeroed resulted in a resident memory value just under the 64MB that was initialised, and it won't have been due to memory pressure (I have 64GB RAM), but some algorithm in the kernel must have decided to page out some of the backing memory after it was zeroed (I suspect kswapd?). The large RES value suggests that each page zeroed was given a distinct page of physical backing memory (as distinct from e.g. being mapped to the OS's zero-page for COW-allocation of an actual backing page).

With structs:

#include <unistd.h>

struct X {
    int a[1 << 24];
};

int main() {
    auto foo = new X;
    sleep(100);
}

htop values: VIRT 71416KB / RES 1460KB

This shows insufficient RES for the static arrays to have distinct backing pages. Either the virtual memory has been pre-mapped to the OS zero-page, or it's unmapped and will be mapped initially to the zero-page when accessed, then given its own physical backing page if written to - I'm not sure which, but in terms of actual physical RAM usage it doesn't make any difference.

After changing to auto foo = new X{};

htop values: VIRT 71416KB / RES 67844KB

You can clearly see that initialising the bytes to 0s resulted in use of backing memory for the arrays.

Addressing your questions:

Will the Linux kernel will use lazy memory allocation?

The virtual memory allocation is done when the new is done. Distinct physical backing memory is allocated lazily when an actual write is done to the memory by the user-space code.

For the second case, in the same way than when creating static arrays?

#include <unistd.h>

int g_a[1 << 24];

int f(int i) {
    static int a[1 << 24];
    return a[i];
}

int main(int argc, const char* argv[]) {
    sleep(20);
    int k = f(2930);
    sleep(20);
    return argc + k;
}

VIRT 133MB RES 1596KB

When this was run, the memory didn't jump after 20 seconds, indicating all the virtual address space was allocated during program loading. The low resident memory shows that the pages were not accessed and zeroed the way they were for new.

Just to address a potential point of confusion: while the Linux Kernel will zero out backing memory the first time it's provided to the process, any given call to new won't (in any implementation I've seen) know whether the memory allocated is being recycled from earlier dynamic allocations - which might have had non-zero values written into it - that have since been deleted/freed. Because of this, if you use memory-zeroing forms like new X{} or new int[n]() then the memory will be unconditionally cleared by the user-space code, causing the full amount of backing memory to be assigned and faulted in.

Anonymous1847 · Answer 2 · 2020-10-17T17:24:23.683

As many comments said, operator new usually uses malloc under the hood. malloc allocates space but does not by default allocate physical pages. However, malloc often writes internal data to the beginning of a block of memory, so only the first or first couple of pages allocated as virtual address space will fault and be allocated physically by the Linux kernel. The Linux kernel zeroes all allocated physical pages so whether you add () to the end of the allocation to zero-initialize the allocated memory probably has no effect, in terms of new physical pages being assigned. (Already allocated physical pages mapped to the allocated virtual address range are zeroed in that case.)

lazy allocation for c++ object arrays

2 Answers2

Linked