Array allocation on HEAP (Separate allocation vs ... contiguous?)

Question

In this answer: https://stackoverflow.com/a/8547993/5324086

The person has done allocation of arrays on HEAP in two ways:

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif
}

What is the difference between the two ways of allocation?

Is the second method in else block allocating in a contiguous manner?

yep. at least the virtual memory will be contiguous, not necessarily in /dev/ram ... also what kind of weird architecture is this code for? o.0 — hanshenrik, Sep 15 '15 at 07:49
@Spandan Because the code is allocating space for *4* buffers? — Some programmer dude, Sep 15 '15 at 09:22

Basile Starynkevitch · Accepted Answer · 2015-09-16T04:21:26.663

^{(I am focusing on a Linux point of view; adapt it to your operating system and/or compiler implementation)}

The code in your question has a C-like look and feel. Genuine C++ would use new, that is in the non ALLOCATE_SEPARATE case something like

 double *a1 = new double[4*n];
 double *b1 = a1 + n;

and if the memory allocation failed you'll get a std::bad_alloc exception.

What is the difference between the two ways of allocation?

The ALLOCATE_SEPARATE case is doing four calls to malloc. Notice that:

every individual malloc could fail and you should check that, e.g. with
```
double *a1 = (double*)malloc(n * sizeof(double));
if (!a1) { perror("malloc a1"); exit (EXIT_FAILURE); };
```
assuming that you want some C code. And malloc can fail e.g. when the kernel is not able to give more virtual memory, e.g. because mmap(2) failed, some limits have been reached (see getrlimit(2)...), swap space has been exhausted (with memory overcommit being disabled), etc.... Read about paging & page cache, and the man pages of malloc(3), notably its NOTES section.... BTW, your computer has finite resources, so they can be overflown. On a cheap laptop you won't be able to successfully malloc ten terabytes of memory (and reliably use the memory zone) in 2015. Of course for n = 100000 the malloc will usually succeed.
in practice malloc might fail if you ask for a lot of memory (gigabytes), but some operating systems have memory overcommitment (I personally dislike that feature and disable in on my Linux systems) and give you some pointer even if there is not enough space for the huge memory zone
in the unlikely case n * sizeof(double) is overflowing size_t, disaster will happen.

The non-ALLOCATE_SEPARATE is asking for malloc(n * sizeof(double) * 4) and that could overflow with a smaller value of n (still very large in practice). The * 4 is needed because we ask for enough space to fit four distinct non-aliasing pointers and their non-overlapping memory zones.

Is the second method in else block allocating in a contiguous manner?

Of course yes (and as I told that might overflow or fail for a smaller value of n, .e.g. when n * sizeof(double) * 4 that is n * 32 on a 32 bits Linux (i.e. Android) tablet is larger than e.g. 3 gigabytes, and probably even one gigabyte.

Actually, you should use C++11 containers and code:

#include <vector>
int main(){
   const int n = 100000;
   std::vector<double> vec(n);

the vector's data would sit in heap, and the destructor of vec would release it.

Of course, heap data is allocated in the address space of the virtual memory of your process (on Linux, probably using the mmap(2) -or sometimes sbrk- syscall).

If you want to manage the memory on a lower level (you don't always want vectors everywhere, they are troublesome for some types) you could (should?) use [this](http://www.cplusplus.com/reference/memory/allocator/) class. — Marandil, Sep 15 '15 at 09:37
Why would malloc fail for a large memory request? Isn't it robust enough to handle such requests? — Spandan, Sep 15 '15 at 09:43
@Spandan: your laptop don't have ten terabytes of memory; so you cannot `malloc` that much — Basile Starynkevitch, Sep 15 '15 at 10:08
From: http://linux.die.net/man/3/malloc `By default, Linux follows an optimistic memory allocation strategy. This means that when malloc() returns non-NULL there is no guarantee that the memory really is available.` You should test the returned pointer with `malloc_usable_size()` to ensure that you have the real space available. Personally, I find this really stupid as it breaks a pretty basic and understandable precondition. I have no idea what the linux ppl were smoking when they did that. — Adrian, Sep 15 '15 at 22:32

Array allocation on HEAP (Separate allocation vs ... contiguous?)

1 Answers1