C++ Pointer/HEAP Question

Whether you're a newbie or an experienced programmer, any questions, help, or just talk of any language will be welcomed here.

Moderator: Coders of Rage

GameDevver4Evr
Chaos Rift Newbie
Chaos Rift Newbie
Posts: 33
Joined: Mon Mar 08, 2010 9:34 pm

C++ Pointer/HEAP Question

Post by GameDevver4Evr »

Alright, I'd like to make this question as simple as possible.. so bear with me.. but I was just reviewing my SAMS C++ Book on Pointers. Now my question is related to pointers and using memory on the free store/HEAP. Now according to the book, you can allocate memory/ and deallocate memory to the free store using the "new" and "delete" keywords respectively (with your pointers). Now I also understand the importance of freeing this memory where it is necessary, and the dangers of using Pointers, etc.

So my question is to in regards of such a situation where this allocated/deallocated memory plays a role in game programming in general. Do we need to worry about using the free store with pointers, or is it more based on something you would use for libraries to access memory at a particular location via a returned pointer?, or in other words, should you only be concerned with your memory allocation VIA any libraries you are using, rather than the use of them within your program itself?

Or if this is useful for your program itself, wondering if anyone could give an example possibly?

Thanks guys :)
User avatar
dandymcgee
ES Beta Backer
ES Beta Backer
Posts: 4709
Joined: Tue Apr 29, 2008 3:24 pm
Current Project: https://github.com/dbechrd/RicoTech
Favorite Gaming Platforms: NES, Sega Genesis, PS2, PC
Programming Language of Choice: C
Location: San Francisco
Contact:

Re: C++ Pointer/HEAP Question

Post by dandymcgee »

Pointers are most commonly used when you are going to need to reference one object from many places or you need to pass a large object as a parameter. Using pointers allows you to store or pass a memory location (generally referred to as "passing by reference") as opposed to a copy of the object, thereby greatly reducing your application's memory usage.

Simple enough?
Falco Girgis wrote:It is imperative that I can broadcast my narcissistic commit strings to the Twitter! Tweet Tweet, bitches! :twisted:
User avatar
avansc
Respected Programmer
Respected Programmer
Posts: 1708
Joined: Sun Nov 02, 2008 6:29 pm

Re: C++ Pointer/HEAP Question

Post by avansc »

Code: Select all

#define MAX 10000

int main(int argc, char * const argv[]) 
{
	//int temp[MAX][MAX];
	
	int **data = (int**)malloc(sizeof(int*)*MAX);
	for(int a = 0;a < MAX;a++)
		data[a] = (int*)malloc(sizeof(int)*MAX);
	
    return 0;
}

if you uncomment the first line you should see a runtime error, well at least i get one, the stack is outa space.. but the heap has no issue.
Some person, "I have a black belt in karate"
Dad, "Yea well I have a fan belt in street fighting"
User avatar
Falco Girgis
Elysian Shadows Team
Elysian Shadows Team
Posts: 10294
Joined: Thu May 20, 2004 2:04 pm
Current Project: Elysian Shadows
Favorite Gaming Platforms: Dreamcast, SNES, NES
Programming Language of Choice: C/++
Location: Studio Vorbis, AL
Contact:

Re: C++ Pointer/HEAP Question

Post by Falco Girgis »

GameDevver4Evr wrote:Alright, I'd like to make this question as simple as possible.. so bear with me.. but I was just reviewing my SAMS C++ Book on Pointers. Now my question is related to pointers and using memory on the free store/HEAP. Now according to the book, you can allocate memory/ and deallocate memory to the free store using the "new" and "delete" keywords respectively (with your pointers). Now I also understand the importance of freeing this memory where it is necessary, and the dangers of using Pointers, etc.

So my question is to in regards of such a situation where this allocated/deallocated memory plays a role in game programming in general. Do we need to worry about using the free store with pointers, or is it more based on something you would use for libraries to access memory at a particular location via a returned pointer?, or in other words, should you only be concerned with your memory allocation VIA any libraries you are using, rather than the use of them within your program itself?

Or if this is useful for your program itself, wondering if anyone could give an example possibly?

Thanks guys :)
Neither post really answered your question (sorry guys), so I'm going to.

dandymcgee's comment showed a common use of pointers, but your question was about dynamically allocated memory on the heap, not pointers. avansc demonstrated that (generally speaking) there is more heap space than stack space.

First of all, let me just tell you that this is an essential part of almost any modern day program. The only real exception is for microprocessors, where you have limited amounts of memory (and can't afford to be using new/delete).

A simple question arises during the development of any application that leads a programmer to require dynamic allocation. "How many do I need?"

Now have a look at the declaration of a static array containing 10 objects:

Code: Select all

Object object[10]
Please note that these are being allocated on the STACK, and their size (10) MUST be defined at compile time. What if you don't know how many objects you're going to be needing? What if these objects are bullets, particles, onscreen enemies, or any entity whose amount is undeterministic at compile time? You have two choices: 1) Allocate more space than you need at COMPILE TIME or 2) dynamically allocate the amount that you need at RUNTIME.

In certain scenarios, #1 is actually the better way to go. In others, #2 is the smart choice. When you chose number 2, you are allocating (and deallocating) memory as you need it.

So now, lets say that you need a number of objects equal to a user specified number. Check it out:

Code: Select all

int amount;
Object *object;
cout << "How many of the bastards do you desire?" << endl;
cin >> amount;

object = new Object[amount];
Now you have dynamically allocated an array on the heap whose size was determined at runtime rather than compile time.

For more advanced applications, such as adding a new entity to a list (rather than allocating them all at once) you will need to start looking into abstract data structures such as lists, growable arrays (vectors), linked lists, etc. But that is a lecture that we will leave for another time. ;)
User avatar
avansc
Respected Programmer
Respected Programmer
Posts: 1708
Joined: Sun Nov 02, 2008 6:29 pm

Re: C++ Pointer/HEAP Question

Post by avansc »

Good post, but another question (might have been mentioned and i missed it) must be asked as well on top of "how many do i need", and it being "how fast do i need it".
dynamically allocating memory is a lot slower.
Some person, "I have a black belt in karate"
Dad, "Yea well I have a fan belt in street fighting"
GameDevver4Evr
Chaos Rift Newbie
Chaos Rift Newbie
Posts: 33
Joined: Mon Mar 08, 2010 9:34 pm

Re: C++ Pointer/HEAP Question

Post by GameDevver4Evr »

Wow guys, thanks for the quick responses!, and I'm defiantly seeing now some ideas I could apply this to within the program. I have looked into the STL data structures for this as well, so I'm fairly familiar, it's really just the matter of how I'm going to use them in a real application. Right now it's really up to me messing around with it and trying out these snippets posted. Thanks everyone that responded, very helpful :) .
User avatar
AerisAndMe
ES Software Engineer
ES Software Engineer
Posts: 381
Joined: Tue Apr 07, 2009 9:29 pm
Current Project: Elysian Shadows
Favorite Gaming Platforms: PC, SNES, PS3
Programming Language of Choice: C/++
Location: Madison AL
Contact:

Re: C++ Pointer/HEAP Question

Post by AerisAndMe »

avansc wrote:dynamically allocating memory is a lot slower.
Well... I wouldn't say it's a lot slower. It takes microseconds longer to allocate memory dynamically, but once it's allocated, accessing it's just as fast as if it were allocated on the stack. The extra time it takes to allocate memory dynamically would only be an issue if you're either working with a microprocessor or making thousands of allocations per frame, which usually is not the case. :)
qpHalcy0n
Respected Programmer
Respected Programmer
Posts: 387
Joined: Fri Dec 19, 2008 3:33 pm
Location: Dallas
Contact:

Re: C++ Pointer/HEAP Question

Post by qpHalcy0n »

If we're gonna expound on this one, then I'd say that for sure....the answer is not always quite as simple.
What heap allocation tells a programmer MORE is the expected persistence of the object. So, if I see heap allocations, I tend to believe that object persists beyond the scope of its allocation.

For all intents and purposes, if you need a small amount of memory in one scope, stack allocate it. If you need massive amounts of memory or if the memory must extend across the scope of its allocation, heap allocate it.

To be more thorough, heap allocation is far more complex (in almost all cases) than stack allocation. Stack allocation (in almost all cases) is accomplished by growing the stack (moving the stack pointer). Most implementations (including STL implementations...which are very fast) of heap allocated memory must search the heap for available memory when allocating and reduce fragmentation (at best) when de-allocating memory.

As an aside, there are FAR more considerations here when working on parallel architectures (HT, Multi-core chips, the CBE, Xeon chips...etc). The caveat is that heap allocation IS NOT thread safe.To account for this the compiler MUST enter a critical section and halt all other processes for the duration of the allocation. This comes at a VERY high cost especially when allocating in tightly coupled loops or deep branches. This also ties into temporal locality of the memory which is EASILY the single biggest CPU bottleneck issue plaguing most games. (Note: I said CPU bottleneck). Using primitive types from the stack results in a much better temporal locality (the chances that the operands will exist closely together in memory is higher) and results in less down time from memory fetches (which are not asynchronous...x86 chips combat this to some degree). Thusly, most games benefit from custom implemented memory paging systems which reserve gobs of memory up front and manage the fragmentation according to their need. That said, x64 architectures can address much larger pools of memory, so applications compiled under 64 bit environments for 64 bit targets can enjoy a beefier stack.

All that said, when compiling w/ general optimization rules your compilers JOB is to determine what code is NOT used at compile time. It will reduce and inline code beyond what you can anticipate really. So it's the errand of a fool to try to outsmart the thing. It makes it difficult to accurately gauge what's going on realistically in terms of these allocations.

Long story short. Need a little bit of memory now and here? Stack. Need a lot of memory or need it for long? Heap.
Let the compiler do it's job and invest in learning how to use (properly) a code profiler and interpret the results. Many times (surprisingly) it'll put your assumptions through the wringer and you may be surprised to find heap allocation bottlenecks ;) .....for reasons you may have never suspected. Do not try to out-optimize the compiler....optimize where it is necessary to optimize.

"Foolish consistency is the hobgoblin of small minds." Apply that to the above. :)
K-Bal
ES Beta Backer
ES Beta Backer
Posts: 701
Joined: Sun Mar 15, 2009 3:21 pm
Location: Germany, Aachen
Contact:

Re: C++ Pointer/HEAP Question

Post by K-Bal »

qpHalcy0n wrote:Most implementations (including STL implementations...which are very fast) of heap allocated memory must search the heap for available memory when allocating and reduce fragmentation (at best) when de-allocating memory.
I am very sure that this is managed by the OS.
User avatar
Maevik
Chaos Rift Junior
Chaos Rift Junior
Posts: 230
Joined: Mon Mar 02, 2009 3:22 pm
Current Project: www.keedepictions.com/Pewpew/
Favorite Gaming Platforms: PC
Programming Language of Choice: C++
Location: Long Beach, CA

Re: C++ Pointer/HEAP Question

Post by Maevik »

Super informative thread!

I have not used new or delete as of yet (my C++ professor said you don't need it if you're creative and it can be dangerous) so I'm a little hazy on the application of it. This thread pulls most of it together for me, but when do you delete the allocated memory? I know "when you're done with it" is the basic answer, but is this usually in the deconstructor (for classes)? Where do you delete memory allocated with the malloc() function? In avansc's code sample there was no use of the delete keyword, is this common/appropriate? If it's ok, why?
My love is like a Haddoken, it's downright fierce!
User avatar
hurstshifter
ES Beta Backer
ES Beta Backer
Posts: 713
Joined: Mon Jun 08, 2009 8:33 pm
Favorite Gaming Platforms: SNES
Programming Language of Choice: C/++
Location: Boston, MA
Contact:

Re: C++ Pointer/HEAP Question

Post by hurstshifter »

Maevik wrote:This thread pulls most of it together for me, but when do you delete the allocated memory? I know "when you're done with it" is the basic answer
Yes. You delete it when you are done with it, usually at the end of the function that created it but that is not always the case.
Maevik wrote:Where do you delete memory allocated with the malloc() function? In avansc's code sample there was no use of the delete keyword, is this common/appropriate? If it's ok, why?
I think avansc did not delete the memory just because it was a quick example and everything was in main(). Memory is (in every case I can think of) always freed once the application ends if it had not been previously freed. In a malloc() case which is C-style dynamic memory you would use the free() function.
"Time is an illusion. Lunchtime, doubly so."
http://www.thenerdnight.com
User avatar
Falco Girgis
Elysian Shadows Team
Elysian Shadows Team
Posts: 10294
Joined: Thu May 20, 2004 2:04 pm
Current Project: Elysian Shadows
Favorite Gaming Platforms: Dreamcast, SNES, NES
Programming Language of Choice: C/++
Location: Studio Vorbis, AL
Contact:

Re: C++ Pointer/HEAP Question

Post by Falco Girgis »

Maevik wrote:Super informative thread!

I have not used new or delete as of yet (my C++ professor said you don't need it if you're creative and it can be dangerous) so I'm a little hazy on the application of it. This thread pulls most of it together for me, but when do you delete the allocated memory? I know "when you're done with it" is the basic answer, but is this usually in the deconstructor (for classes)? Where do you delete memory allocated with the malloc() function? In avansc's code sample there was no use of the delete keyword, is this common/appropriate? If it's ok, why?
Your C++ professor said you don't NEED it? Smack him in the face, please.

While being "creative" can certainly prevent you from using dynamic memory, it usually isn't the best idea, and CERTAINLY isn't the most eloquent. What are your alternatives for persisting memory? Static member variables, global functions? Some of those are bad programming habits, and you still run the risk of overflowing a stack with massive amounts of data like that.

And in avansc's case, that would be a memory leak. But new and delete are C++ dynamic allocation operators. malloc() and free() are dynamic allocators for plain C. In avansc's example, he allocated memory with a C-style call to malloc(), this must be deleted using free(), not new. You can't mix C-style and C++-style memory allocations.
qpHalcy0n
Respected Programmer
Respected Programmer
Posts: 387
Joined: Fri Dec 19, 2008 3:33 pm
Location: Dallas
Contact:

Re: C++ Pointer/HEAP Question

Post by qpHalcy0n »

K-Bal wrote:
qpHalcy0n wrote:Most implementations (including STL implementations...which are very fast) of heap allocated memory must search the heap for available memory when allocating and reduce fragmentation (at best) when de-allocating memory.
I am very sure that this is managed by the OS.

Unfortunately this is not the case.

Most operating systems can only deal with large-"ish" blocks of memory which are specifically aligned and mapped to physical memory via translation vectors. This is the OS's primary job in terms of mapping memory. It used to be the case that programmers had free reign over the exact same memory the OS had. This is now abstracted by the language runtime.

Either way, if the program returned and received memory on a "per-need" basis, the entire kernel would be locked up in critical section blocks and your program would come to a complete crawl. This is because the manager doesn't always return memory to optimally local regions in the virtual memory table. Nor does it disperse memory in that manner either. Therefore, if the runtime attempts to return memory to the kernel in smaller chunks it will fail. (These failures are kernel failures and are normally unrecoverable). Also, see the x64 caveat for evidence of this....it deals w/ the OS's scheduler.

So what usually happens here is that an available pool of memory is "mapped" to the app upon entry and most OS's reserve the entire range of virtual memory to the application. The runtime then manages small addressable blocks based on language constraints. The benefit here is that the runtime (not the OS) is responsible for merging and consolidating fragmented sections of memory and is consequently the primary reason that heap allocation can get very slow. As such the allocators provided by Microsoft, GNU, or whomever vary significantly. Furthermore it's not always necessary that the particular compiler use them. There are TONS of implementations of malloc and free. Tons and tons and tons.

So to wrap up another long story, no this is not primarily managed on a fine grained level by the OS in any way, shape, or form (Certainly not the case in C/C++). As a matter of fact, the OS is rather naive as to the application's needs for memory. It's primary responsibility is to keep the virtual to physical vector table in order and schedule page or segment requests (whether its segmented or paged memory model...most are paged) and extend the memory mapping to the application in large-ish chunks. This is wildly dependent on the OS. Some have massive requirements for block addressing, some can address individual bytes natively (Usually not, though, this is expensive). It behooves the programmer to be aware of these types of things and realize that C/C++ is *NOT* an implementation, but a specification. Realizing and understanding how a toolchain deals with memory allocation can be of great benefit to the programmer who is concerned and constrained by memory allocation. Opposed to just assuming that the OS simply handles it.

You'll note that when you crash a program in windows on a 0C5 error for freeing memory that has not been allocated, you'll see that this is a C Runtime error, not a kernel error. Kernel errors in this regard are irrecoverable and result in system crashes. (Which you can do directly from the dos shell if you're so inclined....thereby bolstering the point that most OS's memory models are rather flexible and fairly naive.)
K-Bal
ES Beta Backer
ES Beta Backer
Posts: 701
Joined: Sun Mar 15, 2009 3:21 pm
Location: Germany, Aachen
Contact:

Re: C++ Pointer/HEAP Question

Post by K-Bal »

:lol: Thanks for the explanation ;)
User avatar
GroundUpEngine
Chaos Rift Devotee
Chaos Rift Devotee
Posts: 835
Joined: Sun Nov 08, 2009 2:01 pm
Current Project: mixture
Favorite Gaming Platforms: PC
Programming Language of Choice: C++
Location: UK

Re: C++ Pointer/HEAP Question

Post by GroundUpEngine »

Damn, Thas what I call Edjukation! Great information here! :)
Post Reply