When I'm defining a recursive function, is it better/safer to allocate local variables on heap, and then clean them up before the function returns, than to allocate them on stack. The stack size on embedded systems is very limited, and there is a danger of stack overflow, when the recursion runs too deep.
Asked
Active
Viewed 2,349 times
2
-
3You could just turn the recursion into a loop. – Christian Hackl Oct 02 '15 at 14:45
-
2I think you answered your question yourself. – Some programmer dude Oct 02 '15 at 14:46
-
1I think you'd better provide some more details, because as it is currently written, it is rather unclear what exactly are you asking. – Petr Oct 02 '15 at 14:46
-
Heap allocation on embedded systems is not always recommended or even possible. – Peter - Reinstate Monica Oct 02 '15 at 14:47
-
3In proper systems the stack and the heap grow towards each other so that you will run out at about the same recursion depth, though the heap tends to have overhead while the stack does not. On improper system use whatever is bigger. – nwp Oct 02 '15 at 14:47
-
If the stack size is limited, what are the heap size limits? Limited RAM is limited RAM. – Andrew Henle Oct 02 '15 at 14:47
-
If you are concerned make sure that your memory consumption has a finite maximum; @Christian's advice is usually preferred, recursion and dynamic memory allocation both are frowned upon or outright forbidden in systems which must not fail. – Peter - Reinstate Monica Oct 02 '15 at 14:48
-
There is no general answer. Stack usage may be a concern if the recursion can be deep or a lot of temporary memory is used. Heap usage may be a concern for performance. Also, there may be a completely different solution that avoids both problems. – Vaughn Cato Oct 02 '15 at 14:54
-
I see no question in the OP post. – SergeyA Oct 02 '15 at 14:59
-
Note that heap allocations are more expensive then stack allocations (costs can be reduced by using a proper memory pool). Also most compilers can optimize stack allocations better out then heap allocations. – Naios Oct 02 '15 at 15:10
-
1You should neither use recursion nor heap allocation on an embedded system, period. If you find yourself in need of either, there is around 99.9% chance that the need is created from muddy program design and over-engineering. There are extremely few cases where it would make sense to use recursion in an embedded system and [there is not a single case where you need to use heap allocation](http://electronics.stackexchange.com/questions/171257/realloc-wasting-lots-of-space-in-my-mcu/171581#171581). – Lundin Oct 02 '15 at 15:11
3 Answers
5
The answer depends on your application domain and the specifics of your platform. "Embedded system" is a fuzzy term. A big oscilloscope running MS Windows or Linux is on one end of the spectrum. Most of it can be programmed like a normal PC. They should not fail, but if they do, one simply reboots them.
On the other end of the spectrum are controllers in safety-critical fields. Consider these Siemens switches which must react under all circumstances within milliseconds. Failure is not an option. They probably do not run Windows. Available resources are limited. Programming rules and procedures are much different here.
Now let's examine the options you have, recursion (or not!) with dynamic or automatic memory allocation.
Performance-wise the stack is much faster, so it is preferred. Dynamic allocation also involves some memory overhead for book keeping which is big if the data units are small. And there can be issues with memory fragmentation which cannot occur with automatic memory (although the scenarios which lead to fragmentation -- different lifetimes of objects -- are probably not directly solvable without dynamic allocation).
But it is true that on some systems the stack size is (much) smaller than the heap size; you must read about the memory layout on your system. The oscilloscope will have lots of memory and big stacks; the power switch will not.
If you are concerned about running out of memory I would follow Christian's advice to avoid recursion altogether and instead use a loop. Iteration may just keep the memory usage flat. Besides, recursion always uses stack space, e.g. for the return address and -value. The idea to allocate "local" variables dynamically would only make sense for larger data structures because you would still have to hold pointers to the data as automatic variables, which use up space on the stack, too (and would increase overall memory foot print).
In general, on systems with limited resources it is important to limit the maximum resource use by your program. Time is also a resource; dynamic allocation makes real time near impossible.
The application domain dictates the safety requirements. In safety-critical fields (pacemaker!) the program must not fail at all. That ideal is impossible to achieve unless the program is trivial, but great efforts are made to come close. In other fields a program may fail in a defined way under circumstances it cannot handle, but it must not fail silently or in undefined ways (for example, by overwriting data). For example, instead of allocating unknown amounts of data dynamically one would just have a pre-defined array of fixed size for data and use the elements in the array instead, with bound checks.
Peter - Reinstate Monica
- 15,048
- 4
- 37
- 62
0
When I'm defining a recursive function, is it better/safer to allocate local variables on heap, and then clean them up before the function returns, than to allocate them on stack.
You have both the C and C++ tags. Its a valid question for both, but I can only comment on C++.
In C++, its better to use the heap even though its slightly less efficient. That's be cause new can fail if you run out of heap memory. In the case of failure, new will throw an exception. However, running out of stack space does not cause an exception, and its one of the reasons alloca is frowned upon in C++.
0
I think generally speaking you should avoid recursion in embedded systems altogether, as every time the function is called the return address is pushed to the stack. This could cause an unexpected overflow. Try switching to a loop.
Back to your question though, mallocing will be slower but safer. If there is no heap space then malloc will return an error and you can safely clean up the memory. This comes at a large cost in speed as malloc can be quite slow.
If you know how many iterations you expect ahead of time, you have the option of mallocing an array of the variables that you need. That way you will only malloc once which saves time, and won't risk unexpectedly filling up the heap or stack. Also you will only be left with one variable to free.
Sotsukun
- 1
- 5