Is the variable distributed on the stack if I go back before declaring it?

Question

Suppose I have a function whose rough structure looks like this:

int aRecursiveFunction(const SomeLargeStructure *a, int x) { if (end recursion) return 0; // ... if (something that is mostly true) return aRecursiveFunction(a, x+1)+1; // ... SomeLargeStructure copy = *a; alter(&copy); return aRecursiveFunction(&copy, x); } 

What I need to know for performance reasons is whether the space for copy (which is a large structure) will be created on the stack in 90% of cases when the function ends up to this point. Or does it really not even matter? Does it depend on the compiler? Is it better to separate this part as another function?

Thanks.

EDIT . To clarify, sizeof(SomeLargeStructure) is about 500, it has only basic types and arrays (there are no special constructors or assignment operators, etc.).

EDIT 2 : Well, the conclusion is that the stack space is likely to be allocated each time, but this does not affect performance. Stack overflow is not a problem here, therefore it is closed.

Answer 1

On most platforms, the maximum stack space that may be required is allocated when the function is entered. But usually the allocation of stack space is simply added, so the amount of allocated space does not affect performance.

Your question reads like premature optimization. This is not an algorithmic problem, and you have no performance problem. So why do you even think about micro-optimization?

Answer 2

Some compilers can optimize your tail recursive call . When they are optimized, the call stack frame is reused, so it will not grow (therefore, the tail call is optimized as "goto with arguments"). IIRC, for the recent GCC , you are in a case where tail-call is not optimized (but I can be wrong, and GCC is progressing in this area).

You might want to compile assembler code, for example. using g++ -fverbose-asm -S -Wall -O and look at the generated assembler code to find out.

Of course, you should not expect every C ++ compiler to optimize tail calls like yours.

If this is so important to you, and if portability is less dangerous, you can use alloca (3) , and then place the new statement.

  SomeLargeStructure* copyptr = new (alloca(sizeof(SomeLargeStructure))) SomeLargeStructure; *copyptr = *a; alter(copyptr); return aRecursiveFunction(copyptr, x); 

^{If you have a copy constructor, use new (alloca(sizeof(SomeLargeStructure))) SomeLargeStructure(*a); instead of this.}

By the way, I'm not sure if it’s worth the call frame size to be half a kilobyte, on modern desktop computers or servers (where the stack space is often a little more than megabytes), if you don't think your recursion is really deep (like over a thousand levels of recursion).

With recent GCC, you might be interested in compiler options such as -fstack-usage or - Wstack-usage =

Answer 3

It really comes down to how much information the compiler can get while analyzing how your code will run at runtime. In the worst case (i.e., the Compiler cannot conclude that this data will ever be executed), the compiler must have it in order to allocate stack space for each function call:

 struct SomeLargeStructure { double arr[20]; }; int aRecursiveFunction(const SomeLargeStructure *a, int x) { int val; cin >> val; // User input isn't foresee-able if (val == 29) return 0; // ... if (val) return aRecursiveFunction(a, x + 1) + 1; // ... SomeLargeStructure copy = *a; if (val == 22) copy.arr[0] = 2.0; // whatever return aRecursiveFunction(&copy, x); } int main(int argc, char *argv[]) { SomeLargeStructure obj; aRecursiveFunction(&obj, 2); } 

For this, the full stack distribution is required for each call ( -O3 ):

 aRecursiveFunction(SomeLargeStructure const*, int): pushq %r15 pushq %r14 pushq %rbx subq $176, %rsp // stack alloc movl %esi, %ebx movq %rdi, %r14 leaq 172(%rsp), %rsi 

Also, in cases where human deduction may think that “it is definitely not required,” the compiler can still choose to allocate stack space.

It is impossible to answer this question correctly without seeing the full code and / or studying the compiler behavior in this case. You must compile your code and independently view the created and optimized assembly. A simple allocation of stack space is usually not performance-related (unless you have one).

A word of recommendation, though: this is usually a premature optimization , as others have noted, you should not worry about this low-level problem, but rather focus on your algorithm and how your data is used, especially because if your consumption of stack space does not prove / seem The problem is the profiling phase, which will tell you about the red areas where optimization is most needed.