Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My programming professor has told me that it is a good programming practice (at least in C/C++) to declare a function with the inner loop when nesting loops (not for loops, since when, i.e. looping through a multidimensional array this is very intuitive). For example, if I write

int main()
{
    while (cond1)
    {
        // ...(1)...
        while (cond2)
        {
            // ...(2)...
        }
    }
}

then it is better:

type inner_loop(param)
{
    // ...(1)...

    while (cond2)
    {
        // ...(2)...
    }
}

int main()
{
    while (cond1)
    {
        inner_loop(param);
    }
}

What improvements do imply this method? Is there any case in which this way of programming nested loops can be counterproductive? Thanks in advance.

share|improve this question
1  
see also: Why are nested loops considered bad practice? – gnat Dec 6 '13 at 11:31
up vote 17 down vote accepted

It adds a lot of readability at the expense of a little function call overhead, assuming you choose a better name than inner_loop. Unless you truly need every ounce of performance, there aren't many situations where it isn't advisable.

One thing to take note is that it hides the complexity of your algorithm. In general, this is a good thing. However, I once saw similar nested loops in functions create an O(n^6) function out of what should be O(n) or better, simply because maintainers way down the road didn't notice the nested loops when they were working on the outer layers.

share|improve this answer
1  
+1 for the example you cite – GlenH7 Feb 4 '13 at 15:00
1  
If you worry about performance, you should advise your compiler to inline the function. – Martin Schröder Feb 5 '13 at 12:34
    
That doesn't help much if someone manages to change O (n) to O (n^6). And both with gcc and Clang I have found situations where a really performance critical inner loop ran significantly faster when inlining was prevented. – gnasher729 Apr 18 at 21:39
    
O(n^6) Wow! I'd like to see how someone managed to accomplish that! I've once written an O(n^8) but I had no choice--I was validating a dataset to ensure there were no dead ends. Given the sparseness of paths through it it only took overnight. – Loren Pechtel Apr 19 at 2:32

There are advantages and disadvantages to both approaches. Which approach you prefer should depend upon your team's style and guidelines. For now, since your professor doesn't like a particular method, you shouldn't use it for the code you submit.

But don't get too hung up on either approach.

Calling a function from within the outer loop simplifies the task of analyzing the outer loop. But it also increases the overhead from the stack creation / deletion with a large number of function calls. It can also be more difficult to code since shared variables between the loops will need to be passed and returned with each function call.

Nested loops are a little quicker to write. But they can drag out the length of the function. Longer functions tend to be more brittle, which makes maintenance more difficult. Longer functions are also more difficult to wrap your head around since they're ... longer. It's a bit obvious, but worth pointing out.

There's a lot of existing C code written with nested loops without additional function calls. So you'll see a lot of it in the wild. However, just because "it's always been done that way" doesn't necessarily mean it's the right way.

share|improve this answer

The advantage is that your main() is now simpler and easier to read (especially if the body of the inner loop is at all complicated).

It would be a disadvantage if the inner loop were very obvious, since it would then take slightly more effort to read something that should take almost no effort.

Do whatever results in more readable code.

share|improve this answer

as I get deeper and deeper into my developent career, I find myself losing interest in the academicians who spout truisms about levels of nesting, anti-patterns and etc.

I'll share what seems to work well for me in a pragmatic, enterprise-focused development environment:

"...solve for the specific case in front of you, THEN refactor for the general case."

i.e. write it "all in a row." Then start extracting things that are obvious function-like constructs. If you're writing code about the real world and it's processes, you'll surely encounter a lot of "function-ish" things that you likely do several times, if not over-and-over...extract them, parameterize them, make them into methods/functions that you can apply across other cases.

Here's a good way to gauge if you're "done" refactoring: if your test cases all look very simple, direct. (you ARE writing test cases, right?) If your tests are obvious and simple, chances are your code is structured pretty well.

share|improve this answer

The more general advice is: watch out for deep levels of nesting. I've heard it called the "arrowhead" or "mountain range" anti-pattern, because that's what the code starts to look like. If you're nesting 2 levels for loops, then another level for if...then, and then if..thens inside the if...thens, the level of nesting can make the code really hard to follow.

  • I read an article where a team had huge maintenance problems with their code, so they implemented a policy of a maximum depth of nesting. Their bug rate dropped to almost nothing.

  • Someone famous once said, any code nested more than 3 layers deep is incomprehensible.

Hm. I can't find that quote now, but I did find a related article about nesting if...thens:

http://www.drdobbs.com/architecture-and-design/refactoring-deeply-nested-code/231500074

EDIT: here it is: "if you need more than 3 levels of indentation, you're screwed anyway, and should fix your program."

https://www.kernel.org/doc/Documentation/CodingStyle

share|improve this answer

Eventually you will learn about refactoring. Refactoring is about changing a program so that its structure is different, while it does exactly the same thing as before. Two refactoring methods that are often used are splitting a function into two functions, and combining two functions into one.

The art is twofold: First, being able to work focused and refactoring code without introducing bugs. Second, to identify which way is better - in this case, whether the nested loop in one function is better, or the loops distributed over two functions.

By claiming that you should always split nested loops into separate functions, your professor isn't doing you a favour. The split increases total complexity. It's beneficial if each loop on its own is so complex that nesting makes it too complex (Sometimes each loop is already too complex. Combining them would give you something that is much too complex). It's negative if the combined loop is simple enough to be left alone. Your job is to decide which one is it.

Modern languages have features that can actually remove boilerplate code and reduce the complexity of nested loops. Learning to use these features will get you a lot further then having complexity in your code and splitting it up.

And where is the split loop counter-productive? Fact is that a modern computer will likely handle anything you throw at it easily - except nested loops. Iterate through 10,000 items, taking 1 microsecond for each - the user doesn't even notice. Iterate through 10,000 times 10,000 items and it takes 100 seconds. In many cases you must find some better way than a nested loop (if you can't, ask on stackoverflow).

With your nested loop split over two functions, you have one function that calls a function in a straightforward loop - hard to see how to improve that. And you have a function with a simple loop - hard to see how to improve that. Any improvement must consider the combination of both, and you have broken the connection. That makes it harder to see that improving the efficiency of your code is needed, and that it can be done.

share|improve this answer

In theory declaring functions for your nested loops may sound good. In practice you have to be very careful with hiding complexity.

Maybe I can explain better with an example. Consider you have a list. Now you make an add function, but you don't want duplicates, so the add function checks all items and only adds an item if there's no duplicates. Easy enough, computers are fast, it won't take long in your tests.

Next you start with an empty list and add items one by one. Easy enough, it goes fast in test.

Half a year in you get complaints from your customers that your app is slow, just because well, there's 10 000 items added to your list and because you hid the complexity, you didn't see you made an (n^2) situation.

Complexity needs to be clear or otherwise it will bite you.

share|improve this answer

For different scenarios different approaches are considered. When we want to submit a code which is easy to understand by the teacher or any other friend then we should definitely avoid using nested loops as it becomes difficult for the checker to trace the calls for all the variables one by one. But if there is no such case then there is no harm in using the nested loops as there is not such any change in the complexities. Making additional functional calls just increases the number of the activation records used for different functions and also the memory required for the current activation record pointer and the other pointers that point to the previous records of the functions increases.Thus in both the ways the memory increases but it is up to the programmer which approach to use.But the preferred one is to make functions for different purposes as it becomes easy for the programmer also to understand the code after if he/she reviews it after some time.

share|improve this answer
    
this post is rather hard to read (wall of text). Would you mind editing it into a better shape? – gnat Apr 18 at 21:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.