CODEWITHSUNDEEP
c++memory
gilad
gilad

Reputation: 436

Stack allocation of unknown size complexity

I know that stack allocation takes constant time. From what I understand, this happens because the allocation size can be determined in compile time. In this case the program knows how much memory is needed to run (for example) a function and the entire chunk of memory that is needed can be allocated at once.

What happens in cases where the allocation size is only known at run time?

Consider this code snippet,

void func(){
  int n;
  std::cin >> n;

  // this is a static allocation and its size is only known at run time
  int arr[n]; 
}

Edit: I'm using g++ 5.4 on linux and this code compiles and runs.

Upvotes: 3

Views: 935

Answers (4)

Rinat Veliakhmedov
Rinat Veliakhmedov

Reputation: 1039

It is impossible (using standard C++ language) to allocate space on the stack without knowing how much space to allocate.

The line int arr[n]; is not a valid C++ code. It only compiles because the compiler you are using decided to let you do that, so for more information you should refer to your compiler documentation.

For GCC, you might take a look at this page: https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html

Upvotes: 5

Guillaume Racicot
Guillaume Racicot

Reputation: 41750

I'm using g++ 5.4 on linux and this code compiles and runs.

Yes, and this invalid code compiles under MSVC 2010:

int& u = 0;

The standard sais that this code is ill formed. Yet MSVC compiles it! This is because of a compiler extension.

GCC accepts it because it implements it as an extension.

When compiling with -pedantic-errors, GCC will reject the code correctly.

Likewise, MSVC has the /permissive- compiler argument to disable some of it's extensions.

Upvotes: 2

eerorika
eerorika

Reputation: 238301

What happens in cases where the allocation size is only known at run time?

Then the program is ill-formed, and therefore compilers are not required to compile the program.

If a compiler does compile it, then it is up to the compiler to decide what happens (other than issuing a diagnostic message, as required by the standard). This is usually called a "language extension". What probably happens is: amount of memory is allocated for the array, determined by the runtime argument. More details may be available in the documentation of the compiler.

Upvotes: 5

harshrd
harshrd

Reputation: 79

The memory allocation procedure varies when the size to be allocated is determined at runtime. Instead of allocation on stack, memory is reserved on the heap when the size is not known at compile time. Now allocation of memory is possible on the heap until the main memory of the computer is completely used up. Also, in some languages like C,C++ the allocation is permanent and the user is required to deallocate the memory after use.

In the example given above, memory of size n*sizeof(int) is reserved on the heap and is garbage collected (in java or python) or manually deallocated if the memory is assigned a pointer. (in c/c++)

Upvotes: 1

Related Questions