How does memory on the heap get exhausted?

Question

I have been testing out some of my own code to see how much allocated memory it takes to exhaust the memory on the heap or free store. However, unless my code is wrong in the testing of it, I am getting completely different results in terms of how much memory can be put on the heap.

I am testing two different programs. The first program creates vector objects on the heap. The second program creates integer objects on the heap.

Here is my code:

#include <vector>
#include <stdio.h>

int main()
{
    long long unsigned bytes = 0;
    unsigned megabytes = 0;

    for (long long unsigned i = 0; ; i++) {

        std::vector<int>* pt1 = new std::vector<int>(100000,10);

        bytes += sizeof(*pt1);
        bytes += pt1->size() * sizeof(pt1->at(0));
        megabytes = bytes / 1000000;

        if (i >= 1000 && i % 1000 == 0) {
            printf("There are %d megabytes on the heap\n", megabytes);
        }

    }
}

The final output of this code before getting a bad_alloc error is: "There are 2000 megabytes on the heap"

In the second program:

#include <stdio.h>

int main()
{
        long long unsigned bytes = 0;
        unsigned megabytes = 0;

        for (long long unsigned i = 0; ; i++) {

           int* pt1 = new int(10);

           bytes += sizeof(*pt1);
           megabytes = bytes / 1000000;

           if (i >= 100000 && i % 100000 == 0) {
              printf("There are %d megabytes on the heap\n", megabytes);
        }

    }
}

The final output of this code before getting a bad_alloc error is: "There are 511 megabytes on the heap"

The final output in both programs is vastly different. Am I misunderstanding something about the free store? I thought that both results would be about the same.

Not sure, if it related, but [Linux allocates memory lazily](https://stackoverflow.com/questions/864416/are-some-allocators-lazy) — P. Dmitry, Oct 13 '19 at 06:27
@P.Dmitry it shouldn't matter: the data allocated here are initialized by `10`. — Ruslan, Oct 13 '19 at 06:28
@Ruslan Mostly right, but the compiler can see, that this value is unused and can (?) remove this initialization — P. Dmitry, Oct 13 '19 at 06:29
@P.Dmitry this happens in a debug build (just tested). I wouldn't expect such optimizations to happen in this case. — Ruslan, Oct 13 '19 at 06:32
FWIW, I also get about 4× difference between the first and the second case (4000 vs 1071). Might be due to overhead for managing 4-byte vs 100000-byte allocated chunks. — Ruslan, Oct 13 '19 at 06:35
I'm just going to mention that your first calculation of `MB` would be off because unless `ints` are atleast `10 bytes` on your machine, any number of bytes less than a million will make that initial calculation 0. Of course I'm talking about the first example with the vectors, but I think you are loosing even more precision with the second example — smac89, Oct 13 '19 at 07:05

NPE · Accepted Answer · 2019-10-13T06:59:00.090

It is very likely that pointers returned by new on your platform are 16-byte aligned.

If int is 4 bytes, this means that for every new int(10) you're getting four bytes and making 12 bytes unusable.

This alone would explain the difference between getting 500MB of usable space from small allocations and 2000MB from large ones.

On top of that, there's overhead of keeping track of allocated blocks (at a minimum, of their size and whether they're free or in use). That is very much specific to your system's memory allocator but also incurs per-allocation overhead. See "What is a Chunk" in https://sourceware.org/glibc/wiki/MallocInternals for an explanation of glibc's allocator.

Allocating chunks of 16 bytes with `malloc` (and accounting for them) still leaves about 2× difference for me: 2142 MB vs 4000 MB. — Ruslan, Oct 13 '19 at 06:44

score 0 · Answer 2 · answered Oct 13 '19 at 07:02

First of all you have to understand that operating system assign memory to process in quite large chunks of memory called pages (it is a hardware property). Page size is about 4 -16 kB.

Now standard library try use memory in efficient way. So it have to find a way to chop pages to smaller pieces and manage them. To do that some extra information about heap structure have to be maintained.

Here is cool Andrei Alexandrescu cppcon talk more or less how it works (it omits information about pages management).

So when you allocating lots of small objects information about heap structure is quite large. On other hand if you allocating smaller number of larger objects is more efficient - less memory is waisted on tracking memory structure.

Note also that depending on heap strategy sometimes (when small piece of memory is requested) it is more efficient to waste some memory and return larger size of memory then it was requested.

How does memory on the heap get exhausted?

2 Answers2