How does automatic memory allocation actually work in C++?

Question

In C++, assuming no optimization, do the following two programs end up with the same memory allocation machine code?

int main()
{     
    int i;
    int *p;
}

int main()
{
    int *p = new int;
    delete p;
}

Answer 1

To better understand what's happening, let's imagine that we have only a very primitive operating system running on a 16-bit processor that can run only one process at a time. This is to say: only one program can run at once. Furthermore, let's pretend that all interrupts are disabled.

There is a construct in our processor called the stack. The stack is a logical construct imposed on physical memory. Let's say that our RAM exists in addresses E000 to FFFF. This means that our running program can use this memory any way we want to. Let's imagine that our operating system says that E000 to EFFF is the stack, and F000 to FFFF is the heap.

The stack is maintained by the hardware and by machine instructions. There really isn't much we need to do to maintain it. All we (or our OS) needs to do is to make sure we set a proper address for the start of the stack. The stack pointer is a physical entity, residing in the hardware (processor) and is managed by processor instructions. In this case, our stack pointer would be set to EFFF (assuming the stack grows BACKWARDS, which is pretty common,-). With a compiled language like C, when you call a function, it pushes whatever arguments you have passed in to the function on the stack. Each argument has a certain size. int is usually 16 or 32 bits, char is usually 8 bits, etc. Let's pretend that on our system, int and int* are 16 bits. For each argument, the stack pointer is DECREMENTED (--)by sizeof(argument), and the argument is copied onto the stack. Then, any variables you've declared in scope are pushed on the stack in the same way, but their values are not initialized.

Let's reconsider two examples similar to your two examples.

int hello(int eeep)
{
    int i;
    int *p;
}

What happens here on our 16-bit system is the following: 1) push eeep onto the stack. This means that we decrement the stack pointer to EFFD (because sizeof(int) is 2) and then actually copy eeep to address EFFE (the current value of our stack pointer, minus 1 because our stack pointer points to the first spot that is available after the allocation). Sometimes there are instructions that can do both in one fell swoop (assuming you are copying data that fits in a register. Otherwise, you'd have to manually copy each element of a datatype to its proper place on the stack --order matters!).

2) create space for i. This probably means just decrementing the stack pointer to EFFB.

3) create space for p. This probably means just decrementing the stack pointer to EFF9.

Then our program runs, remembering where our variables live (eeep starts at EFFE, i at EFFC, and p at EFFA). The important thing to remember is that even though the stack counts BACKWARDS, the variables still operate FORWARDS (this is actually dependent upon endianness, but the point is that &eeep == EFFE, not EFFF).

When the function closes, we simply increment (++) the stack pointer by 6, (because 3 "objects", not the c++ kind, of size 2 have been pushed on the stack.

Now, your second scenario is much more difficult to explain because there are so many methods for accomplishing it that it's almost impossible to explain on the internet.

int hello(int eeep)
{
    int *p = malloc(sizeof(int));//C's pseudo-equivalent of new
    free(p);//C's pseudo-equivalent of delete
}

eeep and p are still pushed and allocated on the stack as in the previous example. In this case, however, we initialize p to the result of a function call. What malloc (or new, but new does more in c++. it calls constructors when appropriate, and everything else.) does is it goes to this black-box called the HEAP and gets an address of free memory. Our operating system will manage the heap for us, but we have to let it know when we want memory and when we are done with it.

In the example, when we call malloc(), the OS will return a block of 2 bytes (sizeof(int) on our system is 2) by giving us the starting address of these bytes. Let's say that the first call gave us address F000. The OS then keeps track that addressess F000 and F001 are currently in use. When we call free(p), the OS finds the block of memory that p points to, and marks 2 bytes as unused (because sizeof(star p) is 2). If instead we allocate more memory, address F002 will likely be returned as the starting block of the new memory. Note that malloc() itself is a function. When p is pushed onto the stack for malloc()'s call, the p is copied onto the stack again at the first open address that has enough room on the stack to fit the size of p (probably EFFB, because we only pushed 2 things on the stack this time of size 2, and sizeof(p) is 2), and the stack pointer is decremented again to EFF9, and malloc() will put its local variables on the stack starting in this location. When malloc finishes up, it pops all of its items off the stack and sets the stack pointer to what it was before it was called. The return value of malloc(), a void star, will likely be placed in some register (usually the accumulator on many systems) for our use.

In implementation, both examples REALLY aren't this simple. When you allocate stack memory, for a new function call, you've got to make sure that you save your state (save all the registers) so the new function doesn't wipe the values out permanently. This usually involves pushing them on the stack, too. In the same way, you will usually save the program counter register so that you can return to the correct place after the subroutine returns. Memory managers use up memory of their own in order to "remember" what memory has been given out and what hasn't. Virtual memory and memory segmentation complicate this process all the more, and memory management algorithms must continually move blocks around (and protect them, too) in order to prevent memory fragmentation (a whole topic of its own), and this ties in to virtual memory as well. The 2nd example really is a big can of worms compared the first example. Additionally, running multiple processes makes all of this much more complicated, as each process has its own stack, and the heap can be accessed by more than one process (which means it must protect itself). Additionally, each processor architecture is different. Some architectures will expect you to set the stack pointer to the first free address on the stack, others will expect you to point it to the first non-free spot.

I hope this has helped. please let me know.

notice, all of the above examples are for a fictional machine that is overly simplified. On real hardware, this gets a little more hairy.

edit: the asterisks aren't showing up. i replaced them with the word "star"

---

For what it's worth, if we use (mostly) the same code in the examples, replacing "hello" with "example1" and "example2", respectively, we get the following asembly output for intel on wndows.

    .file   "test1.c"
    .text
.globl _example1
    .def    _example1;  .scl    2;  .type   32; .endef
_example1:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $8, %esp
    leave
    ret
.globl _example2
    .def    _example2;  .scl    2;  .type   32; .endef
_example2:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $8, %esp
    movl    $4, (%esp)
    call    _malloc
    movl    %eax, -4(%ebp)
    movl    -4(%ebp), %eax
    movl    %eax, (%esp)
    call    _free
    leave
    ret
    .def    _free;  .scl    3;  .type   32; .endef
    .def    _malloc;    .scl    3;  .type   32; .endef