new and delete/ heap and stack

Pages: 12
As an example imagine you want to implement a simple single linked list. It is often implemented by having nodes containing the element value and a pointer to the next node.
1
2
3
4
5
struct Node
{
	T value;
	Next* next;
};

The list itself just contains a pointer the first node (null if empty).

When a new element is inserted at the front of the list a new node is dynamically allocated using new and the pointers are adjusted.
1
2
3
4
Node* newNode = new Node;
newNode->value = newElementValue;
newNode->next = firstNode;
firstNode = newNode

Now try to think of a way to do this without using new. You can't allocate the node as a local variable inside the function because then the node will go out of scope at the end of the function. Only possible way I can think of would be to have each list preallocate an array of nodes that it can use. That would waste memory and put an unnecessary limit on the number of nodes you can have in each list.

Note that using a lot of memory can have an impact on the performance even if you don't run out of memory, mainly because it becomes less cache-friendly

metulburr wrote:
1
2
3
4
5
int main(){
    int size;
    std::cin >> size;
    int arr[size];
}

This is not valid C++. The array size has to be a compile time constants. Some compilers allows it as an extension.

I think you have to read more about the stack to really understand why it have all the limitations that it have.
http://en.wikipedia.org/wiki/Call_stack
Last edited on
Even if you do have 20GB of RAM (make your lie worth it and take us a picture, it's not something I see everyday), not everyone else does.
Its really not that hard to believe. The PC originally had 8GB of RAM, 4 slots of 2GB chips, which i switched out 2 of those chips for 8GB a piece. so 2x2x2x2 replacing 2 those with 2 8GB chips, 2x2x8x8 = 20GB

I am a gamer that always throws money into upgrading my desktop to the max. If i had more money i would prefer 32GB RAM, 8x8x8x8, but i dont have enough right now to upgrade it that much yet.
Last edited on
closed account (Dy7SLyTq)
hes not asking how you got there. it is hard to believe cause its not something we see everyday
well believe it or not, i dont really care, its what the system has. And 1 TB is not that much to me. I have a 3TB external pretty much full:
1
2
3
4
5
6
7
8
9
10
11
12
13
metulburr@ubuntu:~$ df -h
Filesystem      Size  Used Avail Use% Mounted on
/dev/sda6        99G  7.5G   86G   9% /
none            4.0K     0  4.0K   0% /sys/fs/cgroup
udev            6.9G  4.0K  6.9G   1% /dev
tmpfs           1.4G 1008K  1.4G   1% /run
none            5.0M     0  5.0M   0% /run/lock
none            6.9G  2.0M  6.9G   1% /run/shm
none            100M   40K  100M   1% /run/user
/dev/sda7       443G   35G  386G   9% /home
/dev/sdb1        15G  3.3G   12G  23% /media/metulburr/sd card
/dev/sdf1       2.8T  2.7T   96G  97% /media/metulburr/3TB Hard Drive
metulburr@ubuntu:~$ 


I just figured that PC's selling in walmart now are selling 8 GB RAM, with 1TB HDD, let alone a high end desktop, I didnt think people even still used computers with such low RAM of 256 anymore.

With a gaming desktop, i am just use to replacing my desktop every 2-3 years, if not upgrading as it cant handle the latest games after 3+ years. I guess people dont replace their PC's as much as i thought they do
Last edited on

1
2
3
4
5
int main(){
    int size;
    std::cin >> size;
    int arr[size];
}
This is not valid C++. The array size has to be a compile time constants


1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>
#include <string>


int main(){
    int size;
    std::cin >> size;
    int arr[size];
    for (int i=0; i<size; i++)
        std::cout << arr[i]<< " ";
}


I do not understand as this is the output from this:
1
2
12
-296046908 32767 -296046904 32767 23072896 0 12 0 -240370256 32699 -296046864 32767


Last edited on
closed account (Dy7SLyTq)
a) you didnt initialize arr
b) even though some compilers allow variable size arrays like that, its not recommended.
isn't line 9 initializing it?
int arr[size];


isn't that the same as this?:
1
2
int size = 9;
int arr[size];
Last edited on
closed account (Dy7SLyTq)
no thats allocating memory. initializing it would be something like this:
int arr[5] = {0, 1, 2, 3, 4};
If you use GCC it will allow the array size to be non-constant but if you pass the -pedantic flag it will warn you.
GCC wrote:
test.cpp: In function ‘int main()’:
test.cpp:9:17: warning: ISO C++ forbids variable length array ‘arr’ [-Wvla]
i have been using g++

but i updated gcc and g++ from 4.7.something to 4.8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
metulburr@ubuntu:~$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.8/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 4.8.1-2ubuntu1~13.04' --with-bugurl=file:///usr/share/doc/gcc-4.8/README.Bugs --enable-languages=c,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.8 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.8 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --with-system-zlib --disable-browser-plugin --enable-java-awt=gtk --enable-gtk-cairo --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64/jre --enable-java-home --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64 --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-4.8-amd64 --with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-objc-gc --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.8.1 (Ubuntu 4.8.1-2ubuntu1~13.04) 
metulburr@ubuntu:~$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.8/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 4.8.1-2ubuntu1~13.04' --with-bugurl=file:///usr/share/doc/gcc-4.8/README.Bugs --enable-languages=c,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.8 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.8 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --with-system-zlib --disable-browser-plugin --enable-java-awt=gtk --enable-gtk-cairo --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64/jre --enable-java-home --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64 --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-4.8-amd64 --with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-objc-gc --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.8.1 (Ubuntu 4.8.1-2ubuntu1~13.04) 
metulburr@ubuntu:~$ 

and after that i saw some different things, like a carrot pointer for compile errors, like this
1
2
3
4
test2.cpp: In function ‘int main()’:
test2.cpp:8:9: warning: division by zero [-Wdiv-by-zero]
     1 / 0;
         ^

which i dont remember on 4.7 or below

EDIT:
yeah that must be 4.8, because i donwgraded to 4.7 and no longer see that
metulburr@ubuntu:~/programs/cplusplus$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.8/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 4.8.1-2ubuntu1~13.04' --with-bugurl=file:///usr/share/doc/gcc-4.8/README.Bugs --enable-languages=c,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.8 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.8 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --with-system-zlib --disable-browser-plugin --enable-java-awt=gtk --enable-gtk-cairo --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64/jre --enable-java-home --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64 --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-4.8-amd64 --with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-objc-gc --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.8.1 (Ubuntu 4.8.1-2ubuntu1~13.04)

metulburr@ubuntu:~/programs/cplusplus$ sudo update-alternatives --config gcc
There are 2 choices for the alternative gcc (providing /usr/bin/gcc).

Selection Path Priority Status
------------------------------------------------------------
0 /usr/bin/gcc-4.7 60 auto mode
1 /usr/bin/gcc-4.7 60 manual mode
* 2 /usr/bin/gcc-4.8 40 manual mode

Press enter to keep the current choice[*], or type selection number: 0
update-alternatives: using /usr/bin/gcc-4.7 to provide /usr/bin/gcc (gcc) in auto mode

metulburr@ubuntu:~/programs/cplusplus$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.7/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.7.3-2ubuntu4' --with-bugurl=file:///usr/share/doc/gcc-4.7/README.Bugs --enable-languages=c,c++,go,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.7 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.7 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --with-system-zlib --enable-objc-gc --with-cloog --enable-cloog-backend=ppl --disable-cloog-version-check --disable-ppl-version-check --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.7.3 (Ubuntu/Linaro 4.7.3-2ubuntu4)
metulburr@ubuntu:~/programs/cplusplus$


and the same code is given the error:
1
2
test2.cpp: In function ‘int main()’:
test2.cpp:8:9: warning: division by zero [-Wdiv-by-zero]
Last edited on
ive read through your guys posts over and over trying to undestand the heap and stack, and read the wiki of the link given for call stack. Reading that wiki though makes my brain hurt. Its like trying to read a medical dictionary. And im suppose to know this to be able to program in c++?

storing it in the stack is essentially not using new/delete and letting the end of the fuction delete it from returning?

If you store it on the heap when is it "its too big" . How do you know whats too big? So i could store 1GB on the heap wiht 20GB RAM, and someone with 256 RAM could store 2 MB on the heap. How do you know how "much" you can store associated with each computer?

You need to access it outside the scope of the original stack frame

isnt this just global?
Last edited on
isnt this just global?

Nope, it's on a stack space which could be used from another variable at a second time.
And im suppose to know this to be able to program in c++?

You are, if you want them to perform and act good.
But wiki's aren't really much friendly.
How do you know how "much" you can store associated with each computer?

If you cannot allocate enough memory, an exception is thrown.
You use try/catch to deal with it.
storing it in the stack is essentially not using new/delete and letting the end of the fuction delete it from returning?

Also, but stack cannot allocate memory in arbitrary size.
The memory it allocates must be known at compile-time for stack.

One of the advantages of using dynamic memory (heap) is having unlimited objects in a game, as an example.
You don't want to be limited to 5000 on a gaming pc, do you? heheh.

Let me try to help you (In the hope this time my network does not crash as I send the message like it did last time).

Tutorial for the Stack:
About terminology, you can virtually "split" stack and heap, because if your stack is accessed in a bad position,
you get a "Stack overflow" error (Which is also another C++-based website).

Info in case you get this error:
The stack overflow *WILL* force your program to terminate as there's no solution to this kind of problem
(You actually "ate" your programflow-informations, "puking" your data on it).

Here's a sample of the Stack usage.
Remember you have a fixed stack usage allowed.
You use too much stack space, your program crashes, and we're in the 64kb line by default.

In these examples I WILL assume the most common sizes (4byte for int and pointers)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// --- Read the someFunction comments later! ---
void someFunction()
{
    int myInt = 0; // Your old stack usage was 12 - Now it's 16.
    return; // Now it's going back to 8, the old stack pointer is "released".
    // Return to the main() comments.
}

// --- Begin here ---
int main()
{
    //4bytes of stack used because of how the call systems work
    int myInt = 0;
    // Now, add 4 bytes used to your stack.
    someFunction(); // have a function call: The pointer to the old stack is passed,
    // add 4 bytes to the used quota. Now switch to the someFunction comments.
    return 0; // You're on 8 bytes now, myInt and old stack pointer freed, you're back to 0.
}


As you can see, there is NO WAY the stack is able to "lose" memory.
It always automatically "frees" his memory, because of how the assembly code comes out.

Your stack is on a constant line of bytes long 64kb.
When you enter a function, your stack becomes shorter, because the new function sees the stack as if it was in another place.

See it like a long road.


________________
^     ^       ^
a     b       c


The road is always the same length.
But A, B, and C see the road from a different place.

Actually, A put all his cars in the space between A and B.
And B put his cars between B and C.

They're all stretched, because one wanted to come after the other one.
If A didn't put a car in there, B could have used one car more.

Now for C++, translate Road to Stack, Length to Size, Place to Offset and Car to Memory.

Tutorial for the Heap:
Heap is not a single "big" block of memory.
Heap is a random (usually small, of the size of 1kb) block of memory into your RAM.
(Also the stack is into your ram, but stack is in a fixed width between his beginning and his ending.
Say the stack could be in a RAM space between 0x1000 and 0x2000 <Theorical numbers!>.
The heap can be as wide as your PC allows, ranging from 0 to (maximum integer for your platform).

But, usually you will NEVER access address 0, and you will always see their addresses in a higher position.
Example: 0x0fcb03f2
What it means is, you're (translate 0x0fcb03f2 from hex to decimal) bytes far from the beginning of your RAM.
)

If this theory wasn't enough:

Heap can start at any address in your ram.
You simply request some memory from your OS.

Let's go into some code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

void ChangeValue(int * myInt)
{
    // Set the memory given from windows to 0 or an arbitrary int value
    *myInt = 0;
}

int main()
{
    // "new int" can be translated into:
    // Hey windows, I want a block of memory of size "sizeof(int)" (4 bytes) from you.
    // Where can I find some?
    int * myInt = new int;
    // What can happen now is:
    // 1. Windows has the memory and gives you a valid pointer
    // 2. Windows doesn't have the memory and throws an exception.
    // We'll deal with exceptions at a second time and we'll see what happens with a valid pointer

    // myInt is now a valid pointer. You are free to use that memory.
    ChangeValue(myInt);
    // now "*myInt" is 0.
    // "myInt" is a big number between 0 and the maximum address of your RAM,
    // and it is called a pointer.

    // The problem is, once you've used that memory, as the memory you get with the heap isn't one
    // block right after the other, Windows does not know when it can give the same "memory packet"
    // to another program (Or even to you a second time).
    // To signal to windows you finished using it, you delete it.
    delete myInt;
    // To avoid using it again (It may crash your program,
    // the value may be changed from another application or so on...),
    // clear the pointer's value.
    myInt = 0;
    // Remember, it's not the same of "*myInt = 0;"
    // Also myInt is pointing to memory you should (and can) not access.
    // Doing "*myInt = 0;" at this point will crash your program with "Access Violation" error.
    return 0;
}


Some more code...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// Now you're thinking, why so much for the heap?
// It's hard to use and I must keep track of everything!
// Let's do everything on the stack!

// What's the problem?
// 1. Size. As I said, you have a fixed stack size
// 2. The heap's power. You cannot allocate arbitrary sizes from the stack.

int main()
{
    int mySize = (rand()%1024)+1; // Random memory size between 1 and 1024
    // Allocate the memory depending on the random number you just received
    int * myIntMany = new int[mySize];
    // Careful: Don't use a size of 0 or a size too high.
    // Try to split the memory in different memory blocks if you're going over 64kb of memory in use
    
    for(int i = 0; i < mySize; i++)
    {
        myIntMany[i] = rand(); // You can safely access from myIntMany[0] to myIntMany[mySize-1]
    }

    delete[] myIntMany; // Another note:
    /* int* myInt = new int;
     *   is followed by
     * delete myInt;
     * int* myInt = new int[myNumber];
     *   is followed by
     * delete[] myInt;
     * I think you are able to see the difference.
     */
    return 0;
}


EDIT:
Oh wow I forgot exception handling.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Fast exception example
#include <iostream>
int main()
{
    char * myTestAllocation = 0;
    try {
        myTestAllocation = new char[0xffffffff];
    // Very big size, it's the 32-bit systems' ram limit.
    // Remember: An int is 4 bytes. A char is 1 byte.
        delete[] myTestAllocation;
    } catch(std::exception& e)
    {
        // Wherever your program will crash because of a standard exception,
        // you're given a second try to save your ass by ending up RIGHT here.
        // finished the catch "block", you're back in the normal program flow,
        // unless the exception came from a (con/de)structor.
        std::cout << e.what(); // Print the error message
        int i = 0;
        std::cin >> i; // Rudimentary on-the-fly way to stop the message.
    }
    return 0;
}


Now for the questions?

P.S. :
Actually, you can use more memory.
For a 4GB system like mine, (even if 32-bit) i've been able to get almost all of the 3GB-limit.
Heck this must be my longer post, 7985 bytes wasted for all of you b**ches!
Fear me my dear twicker for I will reach the 8192 character limit one day!
Last edited on
wow that was a well written explanation. I bookmarked it for future reference. thanks a lot!!

So you have a stack overflow when the stack reaches the end of the allotted space for the stack. How do you know how much each computer stack size is? how can you allocate more if needed? What is the "general" or basic size?

EDIT:
Or does the program allocate the size during compile time? which that would make sense why it cannot create it dynamically.

Your stack is on a constant line of bytes long 64kb.

why 64KB?
Last edited on
The maximum stack size very much depends on the architecture of the machine and OS you're running on. Does your hardware/OS use 32 bit addressing? 64 bit addressing?

There are a number of components that comprise the address space of a program: .
- program code including libraries (non-modifiable)
- globals
- stack space
- heap
All of these have to fit with the address space allocated to your program by the operating system.
oh its the architecture? I was thinking the RAM size

Well most of my computers are 64 bit linux distros, but i have a couple virtual machines running windows 7 for compatibility testing running 32 bit, and maybe one of my laptops also, and i know one of my netbooks is using 32 bit linux. So i could be working on either or at any time.

- program code including libraries (non-modifiable)

So the more libraries you include the larger the stack size?
Last edited on
So the more libraries you include the larger the stack size?

No. It doesn't work that way. All four areas come out of a single address space.
i.e. a pointer (which is a 32 or 64 bit address) has to be able to refer any of the 4 items I listed. In most HW today, the high order address bit is a protection bit, so you get 1/2 the address space for protected storage (code) and 1/2 the address for unprotected storage (data).
So the more libraries you include the larger the stack size?


C++ as a language has no concept of a stack in regards to the memory model, so this issue is entirely implementation (or even o/s) dependent. When it is said a variable is allocated on the stack, it would probably be more correct to say the variable has automatic storage duration. When it is said a variable is allocated on the heap, it would probably be more correct to say the variable has dynamic storage duration. Where the memory is allocated from is not specified by the standard.

You should consult the documentation for your tools/environment to discover such internal workings and the ways that you may affect them.
I like c and c++ because it is really close to hardware. If you really want to understand how and why it is working, you should read some books about computer architecture. In your case, you should take special notice in memory management (for example: https://en.wikipedia.org/wiki/Memory_management ).
Topic archived. No new replies allowed.
Pages: 12