Are some allocators lazy?

Question

I wrote a C program in Linux that mallocs memory, ran it in a loop, and TOP didn't show any memory consumption.

then I've done something with that memory, and TOP did show memory consumption.

When I malloc, do I really "get memory", or is there a "lazy" memory management, that only gives me the memory if/when I use it?

(There is also an option that TOP only know about memory consumption when I use it, so I'm not sure about this..)

Thanks

Disembodied

Answer 1

On Linux, malloc requests memory with sbrk() or mmap() - either way, your address space is expanded immediately, but Linux does not assign actual pages of physical memory until the first write to the page in question. You can see the address space expansion in the VIRT column, while the actual, physical memory usage in RES.

Devitalize

is that the same for windows? – Gaynell

I'm not familiar with what Windows does, sorry. – Devitalize

bdonlan: Correct, but he should watch out for the effect's of fork " * The child does not inherit its parent's memory locks (mlock(2), mlockall(2)). " Which will be how most app's load when he's looking at top – Wallpaper

What happens in the page table? Is there a special bit to indicate it's not present, but also not on disk (i.e. unallocated)? – Bernhardt

@Bernhardt Talking about x86: In the page table there is only a present bit. If it is not set, the CPU ignores all other bits and issues a page fault exception. The OS can then either investigate those other bits to figure out, what to do, or it can lookup an internal structure or it can do a combination of both. – Gillmore

Answer 2

This starts a little off subject ( and then I'll tie it in to your question ), but what's happening is similar to what happens when you fork a process in Linux. When forking there is a mechanism called copy on write which only copies the memory space for the new process when the memory is written too. This way if the forked process exec's a new program right away then you've saved the overhead of copying the original programs memory.

Getting back to your question, the idea is similar. As others have pointed out, requesting the memory gets you the virtual memory space immediately, but the actual pages are only allocated when write to them.

What's the purpose of this? It basically makes mallocing memory a more or less constant time operation Big O(1) instead of a Big O(n) operation ( similar to the way the linux scheduler spreads it's work out instead of doing it in one big chunk ).

To demonstrate what I mean I did the following experiment:

rbarnes@rbarnes-desktop:~/test_code$ time ./bigmalloc 

real    0m0.005s
user    0m0.000s
sys 0m0.004s
rbarnes@rbarnes-desktop:~/test_code$ time ./deadbeef 

real    0m0.558s
user    0m0.000s
sys 0m0.492s
rbarnes@rbarnes-desktop:~/test_code$ time ./justwrites 

real    0m0.006s
user    0m0.000s
sys 0m0.008s

The bigmalloc program allocates 20 million ints, but doesn't do anything with them. deadbeef writes one int to each page resulting in 19531 writes and justwrites allocates 19531 ints and zeros them out. As you can see deadbeef takes about 100 times longer to execute than bigmalloc and about 50 times longer than justwrites.

#include <stdlib.h>    

int main(int argc, char **argv) {

int *big = malloc(sizeof(int)*20000000); // allocate 80 million bytes

return 0;

}

.

#include <stdlib.h>    

int main(int argc, char **argv) {

int *big = malloc(sizeof(int)*20000000); // allocate 80 million bytes

// immediately write to each page to simulate all at once allocation

// assuming 4k page size on 32bit machine

for ( int* end = big + 20000000; big < end; big+=1024 ) *big = 0xDEADBEEF ;    

return 0;

}

.

#include <stdlib.h>

int main(int argc, char **argv) {

int *big = calloc(sizeof(int),19531); // number of writes

return 0;
}

Agglutinogen

Awesome answer, thanks! (Was quite surprised to learn that 0xDEADBEAF is a known term en.wikipedia.org/wiki/Hexspeak) – Disembodied

Answer 3

Yes, the memory isn't mapped into your memoryspace unless you touch it. mallocing memory will only setup the paging tables so they know when you get a pagefault in the allocated memory, the memory should be mapped in.

Sonorant

Answer 4

Are you using compiler optimizations? Maybe the optimizer has removed the allocation since you're not using the allocated resources?

Vitiated

Thanks Ryan, I did look at the binary with disassembler and the 'malloc' call was there. – Disembodied

+1 to counter the negative votes. This is a good answer for the question as it is. – Multifaceted

Compiler cannot remove a function without a visible implementation or one which may have side effects. – Expense

@BeeOnRope: Compilers have quite notably removed calls to memset(0) for buffers about to be deallocated, on the basis that it's a no-op from the abstract machine's perspective - it will never observe the written values. Any function defined in the standards is in theory subject to this treatment. See also C++'s upcoming constexpr new – Psychotic

@phil agreed, I've learned much since I wrote that. Even more to the point, compilers definitely eliminate malloc calls. I had thought they would qualify as opaque (indeed they can be interposed hence "observed" in some environments) - but evidently that is not the case. – Expense

Answer 5

The feature is called overcommit - kernel "promises" you memory by increasing the data segment size, but does not allocate physical memory to it. When you touch an address in that new space the process page-faults into the kernel, which then tries to map physical pages to it.

Chowchow

Answer 6

Yes, note the VirtualAlloc flags,

MEM_RESERVE
MEM_COMMIT

.

Heh, but for Linux, or any POSIX/BSD/SVR# system, vfork(), has been around for ages and provides simular functionality.

The vfork() function differs from fork() only in that the child process can share code and data with the calling process (parent process). This speeds cloning activity significantly at a risk to the integrity of the parent process if vfork() is misused.

The use of vfork() for any purpose except as a prelude to an immediate call to a function from the exec family, or to _exit(), is not advised.

The vfork() function can be used to create new processes without fully copying the address space of the old process. If a forked process is simply going to call exec, the data space copied from the parent to the child by fork() is not used. This is particularly inefficient in a paged environment, making vfork() particularly useful. Depending upon the size of the parent's data space, vfork() can give a significant performance improvement over fork().

Wallpaper