Recursion in C, efficiency vs. elegance

Gullible Jones · 2012-06-26 17:46:14

From what I have been told, recursive functions are much loved in C programming due to their "elegance" and the compactness of their code, and because they can be easier to understand than their iterative equivalents.

On the other hand, recursive functions are spectacularly inefficient in C. They use more memory with each recursion, and the context switching due to calling the function over and over again also slows things down. This seems to me like it's mostly a losing proposition.

There is the readability/maintainability perspective... But C conventions already encourage terseness and efficiency over readability (at least if the K&R text is anything to judge by). If your code is already compact and mostly inscrutable, what's the point of making it a little more readable at the cost of completely destroying its performance? Is there something here I'm not understanding?

Bellum · 2012-06-26 18:54:07

You should be writing your code to be as readable as possible, imo. Optimization can come after you've figured out that performance is actually a problem that needs solving.

Cloudef · 2012-06-26 18:56:19

^Excatly, premature optimizations are a bad thing,.

Xyne · 2012-06-26 19:04:42

Gullible Jones wrote:

There is the readability/maintainability perspective... But C conventions already encourage terseness and efficiency over readability (at least if the K&R text is anything to judge by). If your code is already compact and mostly inscrutable, what's the point of making it a little more readable at the cost of completely destroying its performance? Is there something here I'm not understanding?

Code legibility is relative. I would expect that most authors are consistent in their own conventions and so do not necessarily consider their own code "mostly inscrutable". Authors may therefore find that their own code is more legible to themselves with a recursive paradigm.

My own rule of thumb is to always try to avoid recursion in C unless the logic of the code clearly (in my opinion) calls for it, or it would be much simpler than an iterative implementation.

Guiding principles should include maintainability and efficiency. The first implies legibility for the coder, but not necessarily for the casual reader. Comments should be included to orient the latter if necessary.

Last edited by Xyne (2012-06-26 19:05:45)

lunar · 2012-06-26 19:42:13

@Gullible Jones: The efficiency of recursive functions depends on the kind of recursion, i.e. whether the function is tail-recursive or not. The former will be optimized into a straight loop by any decent C compiler, and is hence generally just as efficient as a hand-written loop. Only the latter is indeed less efficient, because non-tail calls cannot be optimized into loops. However, for many non-tail-recursive algorithms you need some kind of manual stack management in iterative implementations, too. For instance, iterative implementations of many graph or tree algorithms of this kind, i.e. BFS, need a stack of previous values. Thus, it's only just the context switches in functions that matter for non-tail-recursive functions, which of course may or may not be relevant

Trilby · 2012-06-26 20:13:34

I think the idea of worrying about optization later is a bit of a red herring. If the question is on optimization versus elegance/readability, one could also argue that you can just get working code first, then worry about making it readable/elegant later.

Certainly in a "first draft" you may just want to get it working. But the question remains, when you do go back to polish the code up, do you prioritize effeciency or readability. Thus the point that one can optimize later is irrelevant: it is later, what then do we prioritize.

Personally I prioritize efficiency. Readability is aided by comments and documentation, these can be tailored to the human recipient; the code should be as "efficient" as possible, or tailored to it's recipient: the machine.

Last edited by Trilby (2012-06-26 20:15:26)

Bellum · 2012-06-26 21:31:24

Trilby wrote:

I think the idea of worrying about optization later is a bit of a red herring. If the question is on optimization versus elegance/readability, one could also argue that you can just get working code first, then worry about making it readable/elegant later.
Certainly in a "first draft" you may just want to get it working. But the question remains, when you do go back to polish the code up, do you prioritize effeciency or readability. Thus the point that one can optimize later is irrelevant: it is later, what then do we prioritize.
Personally I prioritize efficiency. Readability is aided by comments and documentation, these can be tailored to the human recipient; the code should be as "efficient" as possible, or tailored to it's recipient: the machine.

I don't think so. Code needs to be maintained for a long time and often by different people. Comments are nice, but most code is already under-documented, and the documentation might not come from the original author. Readability shouldn't be an afterthought. Maintenance is almost always a problem, whereas optimization isn't. There's been a few times I've written a program, come back to it a few months later, and had absolutely no idea how it worked or how to modify it. I'm sure I'm not the only one.

brebs · 2012-06-27 07:59:18

Gullible Jones wrote:

From what I have been told, recursive functions... can be easier to understand than their iterative equivalents

"Can be", eh? As in, "is not, usually".

Ramses de Norre · 2012-06-27 11:27:47

Trilby wrote:

Personally I prioritize efficiency. Readability is aided by comments and documentation, these can be tailored to the human recipient; the code should be as "efficient" as possible, or tailored to it's recipient: the machine.

I think Fowler said it pretty succinct:

Martin Fowler wrote:

Any fool can write code that a computer can understand. Good programmers write code that humans can understand.

Grinch · 2012-06-27 13:50:11

Ramses de Norre wrote:

I think Fowler said it pretty succinct:
Martin Fowler wrote:
Any fool can write code that a computer can understand. Good programmers write code that humans can understand.

I'm with Trilby, a program is created to perform a function, the quality of that program is how well it performs that functionaly and in many cases the speed at which it performs has a great bearing on it's usefulness. Any programmer worth his/her salt should be able to follow optimized code if it's sufficiently documented, deliberately writing slower code just to make it easier for another programmer to follow is something I almost take offense at.

As for recursion it is indeed an elegant solution in many cases, unfortunately when people who don't know what they are doing try to employ it the result is often exploding stack usage with poor performance as a result, I'm sure someone else has mentioned tail-recursion, look it up.

edit: just looked through my programming links and found this and after skimming over it seems to be a good explanation of recursive programming (must have been some reason I saved the link!), perhaps it can be of interest to Gullible Jones: http://www.ibm.com/developerworks/linux … ndex.html/

Last edited by Grinch (2012-06-27 14:30:49)

Trilby · 2012-06-27 14:06:12

Bellum wrote:

Comments are nice, but most code is already under-documented, and the documentation might not come from the original author. Readability shouldn't be an afterthought.

True enough, but that too, I think, is a tangential topic. Readability need not be an afterthought to be included in comments as the code is written. The code itself should be for the computer, there can be comments in with the code (that the preprocessor eventually chops out) that help the human reader follow. The fact that some people write crap code that lacks any comments is evidence only that some people write crap code that lacks any comments.

The solution to poorly commented code is to encourage people to include better comments, not to encourage people to write less efficient code. Trying to write code that is less efficient with the purpose of making it understandable is really the worst of both worlds: you give them computer sub-optimal instructions, and your communication with human readers is constrained to what can legally be put in the code. Instead have instructions for the computer and comments for the humans.

Frankly, it takes much less effort to put an explanation in a comment, than it does to rework a section of code so it can be understandable to both human and computer.

I would never think "how can I rework this code so it is clear to someone who looks at it what is going on". I may often think "I should add a comment here to clarify what is going on." From the same starting point, the latter option allows the code to stay optimized for the computer, is almost always easier to implement, and is even easier for future readers of the code to understand because the comments can be in plain english.

Edit: that said, I agree some need to know how to use comments. I loathe comments like

    // loop through variable i from zero to value of boggle:
    for(i=0; i<=boggle; i++){

What an utterly useless comment. It just takes up space. Anyone who does not get that much information from the for command itself has no business looking at the code. A more useful comment might say where "boggle" was defined, what it represents, and why were bothering to loop through it.

Last edited by Trilby (2012-06-27 14:10:18)

zorro · 2012-06-27 21:20:15

There are applications where efficiency is vital but this is only in small areas of the code. If the readability of this small area is compromised then comments are required. Maintenance of systems is absolutely fundamental, saving a few clock cycles may seem to be an honourable goal but when the next person updates the software incorrectly because they have not understood it, all efficiency arguments go to the wall - ask RBS.

I believe in only having a few comments in the code. If I'm writing a comment, I ask myself, does this mean the code is poor and should be restructured or variables named more appropriately. All comments should have merit and not be easily deduced by reading the code. Comments are typically not maintained and may mis-direct the next person.

Recursion is very powerful when used wisely, it shouldn't be over used.

A few clock cycles on a modern CPU is irrelevant. Consider how many clock cycles a modern Operating System uses.

Trilby · 2012-06-27 21:28:28

But a few clock cycles can quickly become relevant in a section of recursive or iterated code.

Xyne · 2012-06-27 21:51:10

zorro wrote:

A few clock cycles on a modern CPU is irrelevant. Consider how many clock cycles a modern Operating System uses.

That along with "disk is cheap" is a common mantra. The problem is that mass adoption of that attitude has a cumulative and noticeable effect. <insert some saying about drops in the ocean and floods or however it goes>

Sometimes I think that if everyone had to run development code on 10 year old hardware, everything would be much faster and more efficient.

Bellum · 2012-06-27 22:21:52

Xyne wrote:

zorro wrote:
A few clock cycles on a modern CPU is irrelevant. Consider how many clock cycles a modern Operating System uses.
That along with "disk is cheap" is a common mantra. The problem is that mass adoption of that attitude has a cumulative and noticeable effect. <insert some saying about drops in the ocean and floods or however it goes>
Sometimes I think that if everyone had to run development code on 10 year old hardware, everything would be much faster and more efficient.

My computer is about that old. Things are certainly slower. Certainly a small handful of poorly designed programs will crawl. But things aren't as bad as you imply. A program that is easy to read does not imply bad algorithms (Which is a design issue), and actually my 10 year old computer using modern software is quite usable. Performance is not important unless it is. Using the right methods in the wrong place doesn't help anybody and can cause problems for everybody.

zorro · 2012-06-28 22:34:47

Efficiency no longer comes from counting clock cycles but from creating a smart solution. A "sorting" function can be tuned to perfection and it will be tranced by an averagely written one that is using a better algorithm. Small programs can be written however the author chooses. Any medium/large program that is create by a team of developers, needs to be designed and coded well. There may be a few extra indirect invocations made to allow the program to be easily updated (design patterns) but these only add a few nano seconds. It would take an incredible amount of these before it became noticeable and after addressing the few areas responsible, any additional clocks would be undetectable.

There have been experiments that have confirmed that splitting large sequential code into many functions resulted in faster execution. The overhead of the invocations was easily compensated for by the compiler making more efficient use of the registers.

As I am using a 500Mhz latop, I only use responsive applications and hate bloatware. Designing and writing software that is flexible and maintainable does not have a negative effect on performance.

Grinch · 2012-06-30 12:38:36

zorro wrote:

Efficiency no longer comes from counting clock cycles but from creating a smart solution.

Ehh what? A smart solution bringing better efficiency is a solution which solves it's problem faster, thus using fewer clockcycles. What do you think profiling your code is about?

zorro wrote:

A "sorting" function can be tuned to perfection and it will be tranced by an averagely written one that is using a better algorithm.

I don't know what 'tranced' means, and also what does 'tuned to perfection' mean in this context if it does not involve using a 'better algorithm'???

zorro wrote:

There may be a few extra indirect invocations made to allow the program to be easily updated (design patterns) but these only add a few nano seconds.

There are certainly areas in programs where there's absolutely no point spending time optimizing, like parts which are called very seldom, obviously you will focus your optimization on areas which are heavily used during the programs execution, again profiling allows you to easily pinpoint these areas.

zorro wrote:

There have been experiments that have confirmed that splitting large sequential code into many functions resulted in faster execution. The overhead of the invocations was easily compensated for by the compiler making more efficient use of the registers.

I don't see this happening, dividing functions into smaller segments helps in organizing the code more efficiently but really the compiler register allocator should not have any particular problem with optimizing a larger function than several small ones, unless I'm mistaking what you wrote here. For each call there's also the overhead of potential cache misses, stack management etc, there's a reason there's an 'inline' keyword (although compiler heuristics have become better at automatically determining when to inline, particularly when the function is defined as 'static' or the compiler is using link-time-optimization which allows it to optimize the program as a whole entity rather than on a file-by-file basis).

You said there have been experiments, can you point me to these?

zorro wrote:

As I am using a 500Mhz latop, I only use responsive applications and hate bloatware. Designing and writing software that is flexible and maintainable does not have a negative effect on performance.

Optimized code does not equal non-maintainability, I'm not sure what you mean by 'flexibility' but certainly in performance terms it's most often so that a special solution particularly tailored for the problem at hand will beat a generic solution, often by a wide margin depending on just how optimized the 'special solution' is and of course what the problem is and what possibilities for optimization it offers.

zorro · 2012-06-30 21:31:00

Grinch wrote:

A smart solution bringing better efficiency is a solution which solves it's problem faster, thus using fewer clockcycles. What do you think profiling your code is about?

This thread is discussing whether we should structure code so that is efficient or maintainable. I'm stating that the biggest gains come from how you solve the problem, only in a few cases it is necessary to optimise small sections at the expense of clarity. 99% for maintenance, 1% for efficiency. I enjoy profiling, it is interesting to discover what is taking the time and consider ways of improving this.

Grinch wrote:

I don't know what 'tranced' means, and also what does 'tuned to perfection' mean in this context if it does not involve using a 'better algorithm'???

Tranced -> easily out performed. Once the optimum algorithm is being used, other improvements are marginal. Yes, code written badly may have a large effect.

Grinch wrote:

There are certainly areas in programs where there's absolutely no point spending time optimizing, like parts which are called very seldom, obviously you will focus your optimization on areas which are heavily used during the programs execution, again profiling allows you to easily pinpoint these areas.

In complete agreement - this will be the majority of the code in a reasonably sized application.

Grinch wrote:

I don't see this happening, dividing functions into smaller segments helps in organizing the code more efficiently but really the compiler register allocator should not have any particular problem with optimizing a larger function than several small ones, unless I'm mistaking what you wrote here. For each call there's also the overhead of potential cache misses, stack management etc, there's a reason there's an 'inline' keyword (although compiler heuristics have become better at automatically determining when to inline, particularly when the function is defined as 'static' or the compiler is using link-time-optimization which allows it to optimize the program as a whole entity rather than on a file-by-file basis).
You said there have been experiments, can you point me to these?

There is a limited number of registers and local proximity of data/jumps results in efficiency gains. The trainers of a functional programming course specifically performed this experiment to show that breaking large sequential blocks into functions actually improves performance.

Grinch wrote:

Optimized code does not equal non-maintainability, I'm not sure what you mean by 'flexibility' but certainly in performance terms it's most often so that a special solution particularly tailored for the problem at hand will beat a generic solution, often by a wide margin depending on just how optimized the 'special solution' is and of course what the problem is and what possibilities for optimization it offers.

Also agree with you on this point. Flexibility - this is where the same code can be easily reused without modification to perform a similar task. When software is configured, tested and scrutinised, it is better if this does not have to be updated - see factory or decorator patterns etc.

Xyne · 2012-07-01 00:05:23

zorro wrote:

Tranced -> easily out performed

Are you sure you don't mean "trounced"?

Grinch · 2012-07-01 12:52:02

zorro wrote:

There is a limited number of registers and local proximity of data/jumps results in efficiency gains. The trainers of a functional programming course specifically performed this experiment to show that breaking large sequential blocks into functions actually improves performance.

I don't quite follow this reasoning, I see no correlation between dividing code into smaller functions and improved optimization.

If anything it will make it slower as I see it given the overhead of function calls and also optimizations like block reordering (to reduce branching and improve cache locality) within functions will suffer when they are made smaller (unless they are declared as static and as such gives the optimizer more possibilities in regards to inlining), and it's not as if the register allocator is negatively impacted by large functions, it still divides the code in a function into hot/cold segments and will make sure to reserve registers for hot parts while using stack storage for cold parts if necessary, it's more likely to do a better job in a large function than when divided into several small ones.

Again a larger-scale example of this is link-time optimization where the optimizer looks at the entire program at the same time does giving it much better information on which to base it's optimizations which is known to yield great results. A 'manual' example of this would be sqlite's 'amalgamation' approach which joins all source-files into one single file before compiling giving 5-10% increased performance.

In short, I don't see how very small functions would improve performance, certainly not from a register allocation standpoint as the registers doesn't magically become more numerous because of smaller functions, add to this the function call overhead and any improvement in performance seems very unlikely. I'd love to see any examples if you could point me to them as I'm a bit of an optimization freak (occupational hazard).

saline · 2012-07-01 17:07:52

Grinch wrote:

zorro wrote:
There is a limited number of registers and local proximity of data/jumps results in efficiency gains. The trainers of a functional programming course specifically performed this experiment to show that breaking large sequential blocks into functions actually improves performance.
I don't quite follow this reasoning, I see no correlation between dividing code into smaller functions and improved optimization.
If anything it will make it slower as I see it given the overhead of function calls and also optimizations like block reordering (to reduce branching and improve cache locality) within functions will suffer when they are made smaller (unless they are declared as static and as such gives the optimizer more possibilities in regards to inlining), and it's not as if the register allocator is negatively impacted by large functions, it still divides the code in a function into hot/cold segments and will make sure to reserve registers for hot parts while using stack storage for cold parts if necessary, it's more likely to do a better job in a large function than when divided into several small ones.

Since a function call is essentially some stack pushes and a jump, there is a point where larger functions pushing and popping to accommodate the need for registers offers diminishing returns.

zorro · 2012-07-01 20:20:15

This was the question from the original poster:

Gullible Jones wrote:

what's the point of making it a little more readable at the cost of completely destroying its performance?.

If the code does not meet its performance requirements then targeted optimisation needs to be done. This does not rule out approaches, such as recursion, unless it is causing the bottleneck. Recursion can be more readable and give good performance for a small set of specific problems.

Code reuse and maintainability are absolutely key to developing larger solutions that require development/maintenance teams. Heavily optimised code may be required for a few key areas that has a very specific task to perform within strict timing constraints. The remaining code forms the large majority and should be more generic, maybe it's a fraction less optimal, but its operation will be proven. This reuse will reduce the time, effort and cost, whilst improving its stability and functionality. Writing this generic code so that it can be understood supports this reuse.

Wrt optimisation from functional decomposition.

Grinch, does taking your argument to its logical conclusion suggest that performance is never degraded by inlining functions?

Inline functions and registers are discussed here: http://www.cplusplus.com/forum/articles/20600/

Last edited by zorro (2012-07-01 20:22:09)

Grinch · 2012-07-01 22:52:59

saline wrote:

Since a function call is essentially some stack pushes and a jump, there is a point where larger functions pushing and popping to accommodate the need for registers offers diminishing returns.

Well you don't do any less pushing and popping when calling another function than just doing it in the function you are already in (it's not as if you get new registers to play with as soon as you enter a new function), all you do is add call overhead. I'm not sure I follow your logic, maybe I'm misunderstanding you?

zorro wrote:

Grinch, does taking your argument to its logical conclusion suggest that performance is never degraded by inlining functions?

I can't see how the claim that it would increase function size and thus induce cache misses makes any sense. If you have a function in which inlining a function would cause some of the code in that function to fall out of the cache (and thus cause a cache miss) then that same cache miss would happen when you instead don't inline the code and call it as an external function. However that doesn't always mean there's anything of real performance to gain by inlining, I'd say it only makes sense in tight loops where you want to avoid call overhead and potential cache misses of calling an external function. As always, profile your performance critical code.

edit: I thought of one situation where inlining does have potential cache problems, and that is if you call an external function from _multiple places_ in a function, inlining that external function would obviously make the code larger than the original function + external function and thus have higher cache miss potential. Generally I doubt you will inline the same external function at several places within another function, particularly if the inlined function is big enough to negatively affect the cache locality, but yes, I must admit that could happen.

Last edited by Grinch (2012-07-01 23:03:23)

saline · 2012-07-03 00:49:19

Grinch wrote:

saline wrote:
Since a function call is essentially some stack pushes and a jump, there is a point where larger functions pushing and popping to accommodate the need for registers offers diminishing returns.
Well you don't do any less pushing and popping when calling another function than just doing it in the function you are already in (it's not as if you get new registers to play with as soon as you enter a new function), all you do is add call overhead. I'm not sure I follow your logic, maybe I'm misunderstanding you?

I think most of my thoughts stayed in my head, before...

I meant to suggest that there may be an ideal complexity of a function where the cost of the function call is equivalent to the cost of the stack manipulations incurred by inlined code that performs the same function. Of course, this would be highly dependent on the context, but being able to identify that level of complexity would mean knowing when to break out code into its own function (for readability). I doubt this is very practical, however.

Last edited by saline (2012-07-03 00:50:00)

Lux Perpetua · 2012-07-03 10:15:53

Here's my rule of thumb about recursive functions in C, which is pretty similar to Xyne's. As we all know, any recursive function can be transformed into a functionally identical nonrecursive function. At worst, one explicitly has to maintain an extra stack data structure, which is what the compiled recursive function would be doing anyway. My rule of thumb is that if I can't easily do better than that in the nonrecursive version, i.e., if I'd pretty much have to make my own stack anyway, then I don't feel too bad about writing the recursive function. In most other cases, I prefer the nonrecursive version.

Arch Linux

#1 2012-06-26 17:46:14

Recursion in C, efficiency vs. elegance

#2 2012-06-26 18:54:07

Re: Recursion in C, efficiency vs. elegance

#3 2012-06-26 18:56:19

Re: Recursion in C, efficiency vs. elegance

#4 2012-06-26 19:04:42

Re: Recursion in C, efficiency vs. elegance

#5 2012-06-26 19:42:13

Re: Recursion in C, efficiency vs. elegance

#6 2012-06-26 20:13:34

Re: Recursion in C, efficiency vs. elegance

#7 2012-06-26 21:31:24

Re: Recursion in C, efficiency vs. elegance

#8 2012-06-27 07:59:18

Re: Recursion in C, efficiency vs. elegance

#9 2012-06-27 11:27:47

Re: Recursion in C, efficiency vs. elegance

#10 2012-06-27 13:50:11

Re: Recursion in C, efficiency vs. elegance

#11 2012-06-27 14:06:12

Re: Recursion in C, efficiency vs. elegance

#12 2012-06-27 21:20:15

Re: Recursion in C, efficiency vs. elegance

#13 2012-06-27 21:28:28

Re: Recursion in C, efficiency vs. elegance

#14 2012-06-27 21:51:10

Re: Recursion in C, efficiency vs. elegance

#15 2012-06-27 22:21:52

Re: Recursion in C, efficiency vs. elegance

#16 2012-06-28 22:34:47

Re: Recursion in C, efficiency vs. elegance

#17 2012-06-30 12:38:36

Re: Recursion in C, efficiency vs. elegance

#18 2012-06-30 21:31:00

Re: Recursion in C, efficiency vs. elegance

#19 2012-07-01 00:05:23

Re: Recursion in C, efficiency vs. elegance

#20 2012-07-01 12:52:02

Re: Recursion in C, efficiency vs. elegance

#21 2012-07-01 17:07:52

Re: Recursion in C, efficiency vs. elegance

#22 2012-07-01 20:20:15

Re: Recursion in C, efficiency vs. elegance

#23 2012-07-01 22:52:59

Re: Recursion in C, efficiency vs. elegance

#24 2012-07-03 00:49:19

Re: Recursion in C, efficiency vs. elegance

#25 2012-07-03 10:15:53

Re: Recursion in C, efficiency vs. elegance

Board footer