Any reason not to change the stack size?

generally if you're needing to do it then you are "wrongly" allocating big arrays or big objects on the stack when they should be allocated on the heap.

-me

Stack allocations have additional constraints besides merely size considerations.

First, there's the order: if A is allocated after B, then B will be deallocated after A.

Also, if A is allocated inside a function, then it will be deallocated when the execution leaves the function.

Then, as you said, the size of stack-allocated memory must be known at compile-time—only C99 allows variable-size stack arrays.

Quote:

Original post by ToohrVyk Then, as you said, the size of stack-allocated memory must be known at compile-time—only C99 allows variable-size stack arrays.

I have a multidimensional array[256][256] and it's too large to fit on the stack. The size of the array will not change, and I couldn't grasp how to allocate it on the heap. Edit: I saw a few solutions, but they were all too complicated for me to understand.

Do you think I still should avoid creating it on the stack? I'd have to increase the stack size for that. Feels bad.

and when you're done using it:



-me

Quote:

Original post by SymLinked Quote: Original post by ToohrVyk Then, as you said, the size of stack-allocated memory must be known at compile-time—only C99 allows variable-size stack arrays. I have a multidimensional array[256][256] and it's too large to fit on the stack. The size of the array will not change, and I couldn't grasp how to allocate it on the heap. Edit: I saw a few solutions, but they were all too complicated for me to understand. Do you think I still should avoid creating it on the stack? I'd have to increase the stack size for that. Feels bad.

Doing things the wrong way because you didn't understand the correct way is generally not a good idea. If you're having trouble understanding how to allocate multidimensional arrays you can use a single dimensional array and do some index arithmetic.

obj* array = new obj[256 * 256];
obj[row * 256 + col] instead of obj[row][col]
row∈[0,255], col∈[0,255]

EDIT: bah, too slow =]

Quote:

Original post by Palidine *** Source Snippet Removed *** and when you're done using it: *** Source Snippet Removed *** -me

Thanks Palidine. That's the approach I tried to understand previously. What worries me is how you access the array.

get (256, 256); // Wouldn't that overflow?

((256 * 256) + 256) = 65792
That would be more than the size of 65536.

I realize I'm missing something as many obviously use this method and it's recommended in different FAQ's, but what exactly is it I'm missing? Is my math incorrect up there? :)

Thanks again. (Edit: And thanks Omid!)

Quote:

Original post by SymLinked get (256, 256); // Wouldn't that overflow?

No, it would fail to compile (the assert would evaluate to false; assuming an assert does what I think it does).

Quote:

Original post by SymLinked Quote: Original post by Palidine *** Source Snippet Removed *** and when you're done using it: *** Source Snippet Removed *** -me Thanks Palidine. That's the approach I tried to understand previously. What worries me is how you access the array. get (256, 256); // Wouldn't that overflow? ((256 * 256) + 256) = 65792 That would be more than the size of 65536. I realize I'm missing something as many obviously use this method and it's recommended in different FAQ's, but what exactly is it I'm missing? Is my math incorrect up there? :) Thanks again.

Arrays are zero-based in C++, which means that if you allocate n elements you have indices i∈[0,(n-1)], so for n=256 the last index would be 255 and 256 would be out of bounds. That's why Palidine put an assert in the function for run-time bounds checking. The last element is
get(255, 255) which results in index 255*256 + 255 = 65535 = n-1

EDIT: run-time ofcourse, thank you Driv3MeFar [smile]

[Edited by - Omid Ghavami on August 14, 2007 4:55:41 PM]

Quote:

Original post by SymLinked Quote: Original post by Palidine *** Source Snippet Removed *** and when you're done using it: *** Source Snippet Removed *** -me Thanks Palidine. That's the approach I tried to understand previously. What worries me is how you access the array. get (256, 256); // Wouldn't that overflow? ((256 * 256) + 256) = 65792 That would be more than the size of 65536. I realize I'm missing something as many obviously use this method and it's recommended in different FAQ's, but what exactly is it I'm missing? Is my math incorrect up there? :) Thanks again. (Edit: And thanks Omid!)

0 based index, so 256 is not a valid index [smile].

Doh! Thanks guys.

i think one interesting question keeps open (for me at least):

assume that some programmer - probably me - loves stack based allocation, because it perfectly suits his needs (speed and such), what would be the problem with increasing the stack size to lets say 256 mbyte ?

is there any technical problem associated with that? where would be the difference if i would do the same with the heap and dynamic memory allocation, besides the obvious things like memory management ?

One I heard of is that you can't recover from a failed stack allocation, while you can from heap allocation.

Quote:

Original post by Mushu Quote: Original post by SymLinked get (256, 256); // Wouldn't that overflow? No, it would fail to compile (the assert would evaluate to false; assuming an assert does what I think it does).

Assertions are triggered at run-time, it would compile fine.

Quote:

Original post by hercis there any technical problem associated with that? where would be the difference if i would do the same with the heap and dynamic memory allocation, besides the obvious things like memory management ?

Yes, there's a reason there's a stack and a heap. It has to do with virtual memory and paging.

Stack is intended to be paged as little as possible. If you define 256Mb stack, you either fall back to usual paging faults when system manages memory, or you define all of it as non-commitable, completely depriving the system of that particular chunk of RAM.

Don't fix what isn't broken.

For example, Java VM partitions heap (stack is irrelevant in that case) into several different blocks, each based on how long an object will live. The longer an object lives, the higher it gets pushed up.

This mimics the cache strategy employed by processors (L1 <- L2 <- RAM). Stack serves the same purpose. Short-lived allocations are performed on stack (function calls, temporaries), the rest goes into heap.

There's a whole lot of science behind stack and heap sizes, sizes of allocations, cache efficiency, ...

When dealing with large continuous data structures, cache coherency will determine performance, not where it's allocated.

Quote:

Original post by SymLinked Quote: Original post by Palidine *** Source Snippet Removed *** and when you're done using it: *** Source Snippet Removed *** -me Thanks Palidine. That's the approach I tried to understand previously. What worries me is how you access the array.

There's another way to go about it (which is interesting because it allows natural usage, while also having decent spatial locality):

size_t const D1 = 256;size_t const D2 = 256;int * * array = new int *[D1];array[0] = new int[D1*D2];for( int i = 1; i < D1; ++i )  array = &array[0][i * D2];// ...// You can therefore use it as normal:array[3][55] = 324;std::cout << array[252][75];// ...delete [] array[0];delete [] array;

But then again, if you're going to go through the trouble, you might as well install and use boost::multi_array (or at least wrap Palidine's solution so that you have a subscript operator).

Quote:

Original post by herc assume that some programmer - probably me - loves stack based allocation, because it perfectly suits his needs (speed and such), what would be the problem with increasing the stack size to lets say 256 mbyte ? is there any technical problem associated with that?

One issue is threads. Most people don't bother to give a stack size to CreateThread so when a thread does spin up it uses whatever the default thread size is for the executable. If the default thread stack size is 256MB it only takes a couple of threads before you are completely out of contiguous address space. Note that even if you don't do threads various system components do. It could be made to work but you'd probably get occasional wierd behaviors in different environments / OS versions.

Of course if your app was native 64-bit 256MB of address space is chicken feed :).

Quote:

Original post by ToohrVyk Then, as you said, the size of stack-allocated memory must be known at compile-time—only C99 allows variable-size stack arrays.

alloca works with older version of C.

There is also portability to be taken into account - not all system (especially embedded) will allow the stack size to be changed.

Quote:

Original post by Driv3MeFar Quote: Original post by Mushu Quote: Original post by SymLinked get (256, 256); // Wouldn't that overflow? No, it would fail to compile (the assert would evaluate to false; assuming an assert does what I think it does). Assertions are triggered at run-time, it would compile fine.

Ah, okay. I guess I should do some more reading.

You can do a compile time assert if you so very wish:

#define COMPILE_TIME_ASSERT( a )     {        int Temp[ ( a ) ? 1 : 0 ];    }

Although these generally shouldn't be needed, used, or glanced at.