Dynamic Vs. Static

If you know the size ahead of time use a static array. If you don't know the size ahead of time, at runtime allocate an appropriately sized array on the heap.

For example you cant do this:
int size;
cin >> size;
int array[size]; // ERROR!

You would have to do this:
int size;
cin >> size;
int* array = new int[size];

if you know the size at compile time, then you should probably use a declared array, i.e.



however you should be aware of where this is allocated: it is allocated on the stack... if your function with the array is recursive (or called by a recursive function) and the array is large you might run out of stack space if the recursion depth and/or th earray is big (i.e. if array size if like 10000 and the dpeth is like 100, then the stack space is not going to be enough) however, accessing data from the stack is faster than accessing from the heap, but you need to really make sure you don't write past the size of your array, because for stack allocated arrays you might write over the return address of the calling function and then all hell will break loose.

Quote:

Original post by kRogue however you should be aware of where this is allocated: it is allocated on the stack... if your function with the array is recursive (or called by a recursive function) and the array is large you might run out of stack space.

Who said it was declared on the stack? That code snipped does not have enough information for you to deduce that.

For example:

// This array is/will be located on the stack (when the function eventually executes)
int main(){
int array[1000];
...
}

// This array is located int the code segment of the executable
int array[1000];
int main(){
...
}

So basically if I know the size of the array, then the only difference between the two (dynamic and static) is that the static one is faster but has less capacity?

Quote:

Original post by AdamGL So basically if I know the size of the array, then the only difference between the two (dynamic and static) is that the static one is faster but has less capacity?

No. Rather the main differences are these:

A static array has to have its size has to be defined a compile time and dynamically allocated arrays need its size is defined at runtime.

The static array will make your executable larger. The dynamically allocated array will take (some) time to allocate during execution. Though they are the same speed when it comes to accessing elements.

I did not actually read all of kRogue's post ...

Quote:

Original post by kRogue accessing data from the stack is faster than accessing from the heap,

This is not true.

Quote:

Original post by kRogue but you need to really make sure you don't write past the size of your array, because for stack allocated arrays you might write over the return address of the calling function and then all hell will break loose.

A good compiler/debugger should notify you that you have corrupted your own stack by writing past the end of a stack allocated array. VC7 for example does this.

You should be more concerned about others using buffers on the stack to overwrite function return addresses. This is exactly what a buffer overflow exploit is.

you should probably be using an std::vector anyways; if you know the size you can always vector.reserve() it in advance.

1000 integers is not that much in the grand scheme of things so it is safe to put it on the stack. 1000 large sized objects (as obtained by sizeof) would be a problem.

Many people like to think there are 2 types of memory, stack and heap ... because that's all most people have to think about most the time, there are really more than that.

There is data segment data (as mentioned by fpsgamer) and memory mapped i/o addresses (for instance when you write to video buffers or files, it is not using normal ram, it is just that certain addresses are mapped by the os to write to certain destinations).

between the 3 you can control:



The dataSegment normallys grows the size of your executable to hold it. This data will then be loaded in main memory when the program loads, along with the rest of the application.

The stack values are pushed onto the stack when the function is called and poped off when it returns. if a function is in the call stack more than once (ie recursion) than there is memory in the stack for each instance, and that memory may of course have different values.

paramters to function are passed on the stack. In fact the purpose of the stack is to hold the return address of the function, its parameters, and its local variables.

there is a stack PER THREAD.

The heap values are allocated by the language or operating system from a dynamic pool of memory. The heap is shared by all threads in a process (in most normal OSes) so it can be slower to use heap memory in multithread capable apps because they must use locks to protect allocations and returns that use the heap. Many advanced systems have been built to have block allocating heaps, or thread specific heaps to eliminate various costs when it is important.

In general the cost of accessing any memory once allocated is not at all based on stack / data segment / heap ... but instead is based on whether or not the memory is currently in the CPU cache, if not, it causes a cache miss. This is based almost exclusively on how recently the memory was accessed, so hitting the same area in the heap 500 times in a row is no different than hitting the stack 500 times in a row. But hitting 40 variables right next to each other in the stack is less likely to use many data pages of cache than hitting 40 variables allocated on the heap ... especially if those variables we're allocated at different times in the application, and vary in size, etc.

The stack is often very limited in size (like 8kb on many platforms), so it is a VERY bad choice to use the stack for large data. Although the normal reason you choose between heap and stack is not size, but object lifetime. If the variable needs to exist only for the life of the function - and is known at compile time, it should be put on the stack (unless it is very large). If it needs to exist for longer than the life of the function it cannot be put on the stack, so only heap and data segment are possible. data segment values are, by definition, alive for the entire application and are effectively permanent globals / statics.

Xai, that was beautiful. That put an end to all of my confusion. Thank you so much. Now, onwards with my coding! Thank you all!

Quote:

// This array is located int the code segment of the executable int array[1000]; int main(){ ... }

Generally such an array would be located in the bss or data segments (bss is for uninitialized data, data is for initialized data) rather than the code segment.

Quote:

Original post by fpsgamer If you know the size ahead of time use a static array. If you don't know the size ahead of time, at runtime allocate an appropriately sized array on the heap. For example you cant do this: int size; cin >> size; int array[size]; // ERROR! You would have to do this: int size; cin >> size; int* array = new int[size];

I have found no compiler where I could not do the first one! I think it is legal in c++ but was not in c.

Quote:

Original post by dragongame Quote: Original post by fpsgamer If you know the size ahead of time use a static array. If you don't know the size ahead of time, at runtime allocate an appropriately sized array on the heap. For example you cant do this: int size; cin >> size; int array[size]; // ERROR! You would have to do this: int size; cin >> size; int* array = new int[size]; I have found no compiler where I could not do the first one! I think it is legal in c++ but was not in c.

Afaik it is the other way around - legal in the latest version of the C standard, but not legal in C++ yet.

Variable sized arrays are illegal in ISO C++98, but some compilers allow them if you don't use strict error checking compiler flags (like g++ -pedantic). In C99 variable sized arrays are legal, but not in C90.

If you're using C99 or do not care about violating the standards, you can use variable sized arrays. Variable sized arrays are cleaned up automatically, but they are allocated on the automatic store ("the stack"), which has limitations in size (dependant on the platform, etc). If the arrays needed are large (hundreds of bytes could be a good limit), you should use the freestore ("the heap") instead.

Of course, allocating on the freestore (especially in C++) requires you to write some extra clean up. A simple clean up (delete[] array or free(array)) is trivial to do, but you must do this in every exceptional execution path. This means every function call that can fail in one way or another, either by returning an error code, throwing an exception or another method of error handling (setjmp, etc). This gets awfully problematic with generic programming (templates), when you don't know what functions may throw exceptions and what may not.

Writing a lot of clean up code can be avoided using std::vector, boost::shared_array or another method that cleans up after itself. Using std::vector does not require an object to be default constructible, which is sometimes useful with generic programming.

-Riku

Quote:

Writing a lot of clean up code can be avoided using std::vector, boost::shared_array or another method that cleans up after itself. Using std::vector does not require an object to be default constructible, which is sometimes useful with generic programming.

A technique which in its more generic form is known as RAII