Templates and compile time Vs run time

[adam2016]

This question kind of relates to both templates and how they relate to compile vs run time,

so with a lot of compilers you cannot create an array on the stack at run time,and rightfully so as stack frames are allocated at compile time

but you can get around this using templates,how is this possible when you get to the line Array<10> arr2,it will create a template class with 10 as N,but isn't this still compile time,I thought it is frowned upon to create an array at compile time and as said this is still compile time? (some compilers will actually allow you to create arrays of varying sizes at compile time but shouldn't be done)

so this also leads me to my next question,what is compile time vs run time,I know that when allocating memory on the free store this is run time,but isn't all of our code compiled how does this code actually get executed at run time?

thanks

  #include <iostream>

using namespace std;

template <int N>
class Array{

public:

    int arr[N];

};

int main()
{
   int size = 0;
   cout << "enter size" << endl;
   cin >> size;
   int arr[size]; // not ok

   Array<size> arr2; // this is ok or is it??
}

[keskiverto]

What does your compiler say?

The cpp.sh says:

#include <iostream>

template <int N> class Array{
public:
    int arr[N];
};

int main()
{
   int size = 0;
   std::cin >> size;
   Array<size> arr2;
}

 In function 'int main()':
12:10: error: the value of 'size' is not usable in a constant expression
10:8: note: 'int size' is not const
12:14: error: the value of 'size' is not usable in a constant expression
10:8: note: 'int size' is not const
12:14: note: in template argument for type 'int'
12:20: error: invalid type in declaration before ';' token
12:16: warning: unused variable 'arr2' [-Wunused-variable]

note: 'int size' is not const
error: the value of 'size' is not usable in a constant expression (Array<size> arr2;).

That is quite clearly "not ok".


A function is a set of instructions. That includes instructions to reserve space from stack for functions arguments, return value and automatic variables when the function is called. If those need, say 42 bytes, then the binary has "advance the stack pointer by 42 bytes" instruction that executes if the function is called during runtime. When the function call returns, the stack pointer comes back those same 42 bytes.

Allocating memory dynamically calls an OS function. How OS keeps record of what memory it has allocated for whom, is not our concern. When you compile your code, it simply has a call to OS function.

[adam2016]

thanks kes

great answer.I think I get it here was a question asked on stackoverflow which is quite similar to what I'm trying to figure out

https://stackoverflow.com/questions/50573519/arrays-created-in-functions-compile-time-or-run-time/50573736#50573736


this is the sample code from his/her question

#include <iostream>

void someFunction(int number){

    int sampleArray[number];

    for(int i = 0; i < number; i++){

        sampleArray[i] = 0;
    }
    // I know what I'm doing is pointless but is it possible?
}

int main()
{
   int number = 0;
   int choice = 0;

   std::cout << "do you want to create an array? press 1 for yes" << std::endl;
   std::cin >> choice;
   if(choice == 1){

   std::cout << "enter size" << std::endl;
   std::cin >> number;

   someFunction(number);

   }
}

won't someFunction() be called at runtime? since the user has to choose weather or not to enter the function? but does that mean that someFunction() is compiled at compile time or run time?

and if someFunction() is called at run time how come passing an argument number which is determined at run time frowned upon and won't work in many compilers if someFunction() is called at runtime?

[icy1]

what are you actually trying to do?

on the stack because const int for a size
int arr[14];

on the heap, dynamic (delete afterwards)

int n;
cin >> n;
int* arr = new int[n];

In C++ you may want to use <array> for known sizes and <vector> for dynamic

std::array<int, 14> arr;
std::vector<int> v;

Not sure how this question relates to templates... this is really about knowing the limitations of basic arrays.

[Peter87]

won't someFunction() be called at runtime?

Yes.

does that mean that someFunction() is compiled at compile time or run time?

Things are always compiled at compile time because that's what compile time means. There is something called just-in-time compilation (JIT) which involves some compilation at runtime but it still has to follow all the rules of C++ so nothing really changes. JIT is not widely used for C++ anyway.

if someFunction() is called at run time how come passing an argument number which is determined at run time frowned upon and won't work in many compilers if someFunction() is called at runtime?

This feature is called variable-length array (VLA). It was added in C99 but since C11 it's just an optional feature that C compilers doesn't need to support. It has never been part of C++, but if it were to be added it would most likely be made backwards compatible with C, but right now it doesn't look like it's going to happen.

One concern with VLAs is that the amount of stack space that it takes up depends on a runtime value (normally stack frames have fixed size) and since the size of the stack is typically very limited compared to the heap you run a much greater risk of getting a stack overflow if you're not careful. It also means that, sizeof(vla) is not a constant expression, which is inconsistent with every other use of sizeof.

Note that if you want an array with the size decided at runtime (and you don't mind heap allocations, something that VLA was allowed to use all along) you could use an std::vector.

void someFunction(int number){

	std::vector<int> sampleArray(number);
	
	for(int i = 0; i < number; i++){
		sampleArray[i] = 0;
	}
}

[dhayden]

with a lot of compilers you cannot create an array on the stack at run time

You most definitely CAN create an array on the stack. What you can't do is create one whose size isn't known until runtime. The standard doesn't support it, although some compilers will allow it as an extension.

and rightfully so as stack frames are allocated at compile time

The frames themselves are created at runtime, but size is known at compile time. A little more specifically, the compiler generates code to reserve the right amount of space on the stack for the local variables. That code runs at runtime.

but you can get around this using templates,

No, the array template just moves the issue to the array created in the template.

I know that when allocating memory on the free store this is run time,but isn't all of our code compiled how does this code actually get executed at run time?

The local variables are allocated on the stack at runtime also. In fact, you could say that all variables are allocated at runtime, even the global ones. Those are just allocated before main() is called.

The important things to remember are
- the stack is limited in size - typically a few megabytes vs. gigabytes in the heap. So don't allocate huge amounts of data on the stack. In pratice, that means don't allocate large arrays on the stack.
- Allocating and freeing data on the stack is much faster than on the heap. It is usually a single instruction to allocate all the space for local variables in a function. Note that I'm just talking about the time to allocate the memory, not the time to call the constructors and destructors.

[adam2016]

hi Icy,I know how to get memory from the free store and I know you if you want a variable length array you would need to dynamically allocate an array,

but that wasn't my question the question was why not how,I'm well aware of when to use a std::vector and dynamically allocated arrays as opposed to fixed sized arrays on the stack.

[keskiverto]

Allocating and freeing data on the stack is much faster than on the heap. It is usually a single instruction to allocate all the space for local variables in a function.

It is simple to add to the binary, during compilation, an instruction that allocates "next X bytes from stack", where the X is a constant value written as part of the instruction.

Heap allocation, whether the X is decided already during compilation or merely computed from user input during execution of the program, means that the program requests X bytes from the OS, the OS has to figure out from which part of unallocated heap it has to carve those X bytes, update the usage map of the heap, and return address of the newly-allocated block of memory.

A lot more bookkeeping than the "next X bytes".

[adam2016]

thanks guys I think I understand now :)

so from my understanding,everything no matter what is compiled at compiled time,but some code will be executed (compiler will put this code somewhere) at run time such as popping and pushing of stack frames

The frames themselves are created at runtime, but size is known at compile time. A little more specifically, the compiler generates code to reserve the right amount of space on the stack for the local variables. That code runs at runtime.

so stack frames size will always be decided at compile time no matter what?

thanks Peter,DHayden and Icy :)

[Cubbi]

adam2016 wrote:

so stack frames size will always be decided at compile time no matter what?

It will be decided at run time in a C program that uses a variable-length array whose size is not available until run time: https://godbolt.org/g/3a7oAm

1 2 3 4 5 6 7 8 9 10

void f(char*); void demo(size_t sz) { char a[sz]; // C's VLA, invalid C++ f(a); // prevent from optimizing out }

demo: // rdi holds sz pushq %rbp addq $15, %rdi // make sure rdi is aligned andq $-16, %rdi movq %rsp, %rbp // save the old stack position subq %rdi, %rsp // move stack position (allocates rdi bytes on stack) movq %rsp, %rdi call f leave // restore the stack position (deallocates rdi bytes) ret

[adam2016]

thanks guys :)