At what point is it taboo to have loops within loops?

Question

Just curious. The most I have ever had was a for loop within a for loop, because after reading this from Linus Torvalds:

Tabs are 8 characters, and thus indentations are also 8 characters. There are heretic movements that try to make indentations 4 (or even 2!) characters deep, and that is akin to trying to define the value of PI to be 3.

Rationale: The whole idea behind indentation is to clearly define where a block of control starts and ends. Especially when you've been looking at your screen for 20 straight hours, you'll find it a lot easier to see how the indentation works if you have large indentations.

Now, some people will claim that having 8-character indentations makes the code move too far to the right, and makes it hard to read on a 80-character terminal screen. The answer to that is that 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

I figured it was an unacceptable practice for me to go to a third layer of looping, and would restructure my code (Primarily Qt).

Was Linus joking?

Does it depend on the language or application?

Are there some things which absolutely need three or more levels of looping?

Answer 1

To a degree, I stopped taking this quote seriously at "Tabs are 8 characters". The whole point of tabulators is that they are not a fixed number of characters (if anything, a tab is one character). What a load of tosh. Similarly, I'm not completely convinced that setting a hard-and-fast rule of "three levels of indentation" is sane (as much as setting a hard-and-fast rule for anything is sane).

However, limiting your levels of indentation is in general a reasonable suggestion, and not one that should come as a surprise to you.

Ultimately, if your program needs three levels of iteration, that's what your program needs. The spirit of the quote is not to magically alleviate that requirement from your project, but to hive off logic into functions and types so that your code is terser and more expressive.

This just feeds back into the same guideline given above regarding indentation levels. It's about how you structure your code and keep it readable, maintainable and fun to modify for years to come.

Answer 2

The kernel strongly prefers simple algorithms

While a variety of algorithms may require deeply nested loops within loops, in context of the Linux kernel (in which the quote was said) you generally need quick real time responses. In that context, deep nesting is a smell that may indicate that the code flow is too complex for this domain and may needs to be changed because of it's execution characteristics, not readability or indentation issues.

Furthermore, Linux kernel is different from most application code as for the requirements of auditability and testing - and thus would prefer to not have a 4+ level nested algorithm in a single function. It should be obvious to see what each code fragment does exactly and in detail, including all the possible control flow and edge cases. Deeply nested code hampers that.

Answer 3

The point is the same as for any flow-control constructs: if the code is hard to understand, you need to refactor it. If you're doing some simple manipulation of a multi-dimensional array, then having loops nested five or six deep may be appropriate, as long as the logic in the innermost loop is straightforward. However, if you're processing some complicated business logic and the body of your loop is a dozen lines or more, then you will probably not want to nest that more than one loop deep. You can try calculating the cyclomatic complexity of the code, but what it really comes down to is the readability and maintainability of the code in question.

Answer 4

Was Linus joking?

The piece is written in a playful style which suggests that the author is familiar with the way coding style is discussed among serious practitioners: We all have our preferences, and we defend them rabidly, but with tongue at least partially in cheek. We understand perfectly well that much of it is just a matter of personal taste. He says, in so many words, "Coding style is very personal, and I won't _force_ my views on anybody" -- at least outside of code he personally maintains. But consistency of style in a given project is a very good idea. I'd much rather code to a style I dislike than deal with multiple styles in a given function.

Here's an example of clearly playful writing:

However, there is one special case, namely functions: they have the
opening brace at the beginning of the next line, thus:

int function(int x)
{
    body of function
}

Heretic people all over the world have claimed that this inconsistency
is ...  well ...  inconsistent, but all right-thinking people know that
(a) K&R are _right_ and (b) K&R are right.  Besides, functions are
special anyway (you can't nest them in C).

Playful(1).

It's arguably good advice to try to keep indenting from getting out of control, though a three level maximum might be hyperbolic. I'm not going to grep the kernel source and count sequences of four tab characters, but I'd bet money you could find at least one that Torvalds wrote.

On the other hand, if somebody can write the Linux kernel without often exceeding three levels of indenting, a three-level limit might be an exercise worth trying out for a while in your own code, just to see where it takes you. This isn't like a sex change, you know. It's not a lifetime commitment.

If you run into somebody on the Internet who thinks he understands programming much better than Torvalds(2), well, you know what kind of people like to talk big on the Internet.

On the other hand, he is criminally wrong about eight-space tabs. That is the raving of a man who should be kept in restraints and fed through a slot. Four spaces is obviously correct.

(1) But note how he erroneously puts a space before the ellipses, and two spaces after them, and two spaces after a full stop. WRONG, WRONG, WRONG. And then he has the brazen gall to castigate heretics. The heretic is you, Torvalds! IT IS YOU!

(2) If you want to talk about "understanding how to design a source control system", there might be some room for debate.

Note: Dear fellow user who has repeatedly submitted the same edit: The formatting in the quoted material is kept exactly as the author meant for it to be. That's because it's from an essay about the formatting of fixed-width text, written in fixed width text, by somebody who has given the formatting of fixed width text a fair amount of thought. The formatting is a conscious and deliberate part of the author's intent, and it's relevant to the subject.

In addition, I referred back to that formatting in my own text. If you take out the pre-formatting, my footnote (1) becomes gibberish. If the pre-formatting is removed, so should be the text in my footnote (1) referring to the pairs of spaces after the full stops at the ends of sentences. I can see a rationale for removing that footnote anyway, on account of it being less funny than it seemed when I wrote it. But to remove the formatting without removing the footnote is unhelpful.

Answer 5

Linus has a very blunt speaking style, and a dry sense of humor, but he was not joking in this instance. There are situations where an algorithm needs nesting deeper than two levels, but you can accomplish this using other means than indenting your code. The Linux kernel style guide strongly prefers these other methods, because of the difficulty of maintaining deeply nested loops, and that is what Linus is saying here.

For some examples of alternative methods, you can use recursion, split off inner loops into their own functions, or make intermediate data structures.

Excessive nesting is one of those cases that's easier to write, but harder to read. Setting a large tab depth is Linus' way of making it more annoying to write too.

Answer 6

There are many questions where the advice is different for someone asking the question than for someone who doesn't ask. If you ask "Should I ever have loops that are nested more than two levels deep" then for you, the person asking that question, the answer is NO. If you ask, then don't do it. If you have enough experience that you don't need to ask, then you know what's the correct answer in each case. And don't argue if you don't agree with the answer, because the answer is not for you.

Answer 7

This would appear to be a textbook case of the tail wagging the dog.

If you have an 80 character display then of course you are going to try and make the code fit as best you can even if it doesn't produce the best structure for the code.

Tackling the remainder of your points head on:

I figured it was an unacceptable practice.

I think you're reading too much into this. Resist the urge to take everything you read as gospel without properly understanding the context.

Was he joking?

Hard to ascertain the context, but see my original point above.

Does it depend on the language or application?

Very much so. Take any mainframe/midrange language where you're likely to be coding on a terminal (or terminal emulator).

Are there some things which absolutely need three or more levels of looping?

Yes, it is very common in some brute force algorithms. See Problem 31 on Project Euler. This is a classic example of a problem that could be solved with brute force using a number of loops (8 to be exact).

Answer 8

Was Linus joking?

No, those are the official guidelines.

Does it depend on the language or application?

Coding guidelines are generally dependent on the language and application, however deeply nested code always taxes the reader.

The issue with nested code is that in general it increases cyclomatic complexity: that is, the more nested the code is, the more potential execution paths exist within the function. A combinatorial explosion of potential execution paths makes it difficult to reason about the code, and therefore should be avoided in general.

So why 3? A subjective coding guideline is both hard to enforce and impossible to enforce automatically. Setting up an objective coding guideline on the maximum level of indentation requires agreeing on a number: in the Linux kernel they picked 3.

It's arbitrary, and apparently sufficient for them.

Are there some things which absolutely need three or more levels of looping?

Algorithm-wise, probably, however in sufficiently expressive languages you can always refactor the code into smaller chunks (whether with functions or closures).

You can obviously write obfuscated code with little nesting and lots of small functions calling each other without ever spelling their contract...

... however, small functions with clear contracts are much easier to audit than large functions with clear contracts in general.