23

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?

  • 8
    I get confused why you jump from indentation to levels of looping? You have a large quote discussing indentation and suddenly from that follows a question about nested loops. – Pieter B Dec 23 '15 at 12:11
  • 5
    Linus is probably not (only) joking in that section, but note that this is only one style guide, and the same style guide stresses that "Kernel coding style is super simple", i.e. more so than other styles. – user7043 Dec 23 '15 at 12:18
  • 5
    @Akiva You can't go through a 4-dimensional matrix without having 4 nested loops. I find it insane that someone would limit the amount of nested loops you can have. Linus was obviously being very general and you shouldn't take everything you read as holy scripture. – Alternatex Dec 23 '15 at 12:20
  • 9
    @Alternatex That you need 4 loops does not mean they have to be lexically nested. It is quite obvious from the quote that we're talking about how to organize the code, not about the execution. – user7043 Dec 23 '15 at 12:26
  • 4
    @delnan I'm not saying 4 nested loops are visually pleasing and I'm aware there are other ways to go about it but I find it silly how OP took Linus' words so literally. 4th level of indentation = end of the world. Give me a break. – Alternatex Dec 23 '15 at 13:30
19

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.

  • So do you think that with lower level languages such as C, deeply nested loops are generally more taboo because projects utilizing lower level languages benefit from a coding style that focusses on simpler algorithms? – Akiva Dec 23 '15 at 15:06
  • 4
    @Akiva I wouldn't tie it to lower level languages or C as such, but rather to the domain of code. I think that similar guidelines would apply for any language when writing code that must be robust, security focused and auditable at the expense of other things. E.g. an encryption library written in Java or Haskell should also be written in a style that keeps things as simple as possible, limits nesting, and tries to separate everything into chunks that can be easily analyzed with all their possible consequences. – Peteris Dec 23 '15 at 15:13
  • A very insightful and useful comment/answer. Just curious; what kind of project done today which utilizes a low level language, would not focus on being robust, audit-able, and secure? – Akiva Dec 23 '15 at 15:18
  • 7
    @Akiva for example, machine learning code where you may want to use C just for performance reasons but don't care much about robustness or security since it will be run internally in controlled conditions. Also, implementing simple business functionality on small embedded microcontrollers - in practice this often has a business like focus on features and development speed at the expense of quality and security, but uses low level languages. – Peteris Dec 23 '15 at 15:26
49

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.

  • 6
    I believe the "declaration" that tabs are 8 characters are specifically in the context of kernel development. This quote is taken from a coding guideline for a specific project and isn't intended to be a general use guideline, and thus it is expected to be quite opinionated. – Lie Ryan Dec 23 '15 at 15:52
  • 6
    @LieRyan: Then it's still tosh - a coding guideline for anything has no business dictating how wide I set my tabs! But I suspect Linus knows that. – Lightness Races with Monica Dec 23 '15 at 15:53
  • 6
    and of course it's language-dependent -- in c# it is common that you indent inside your namespace, in your class, and in your method.. you're already at 3 levels of indentation before you even talk about control flow statement bodies being indented. – PeterL Dec 23 '15 at 16:55
  • 3
    @LightnessRacesinOrbit I interpret the "Tabs are 8 characters" comment to not mean that you must personally view tabs as 8 wide in your editor, but for the purpose of other rules in the style guide (such as "The limit on the length of lines is 80 columns and this is a strongly preferred limit.") one must treat tabs as being 8 colums, this is also relevant to other rules regarding argument alignment in function calls. Again, I don't think the intent of that line is forcing you to view tabs that way at all, I have done kernel patching before with 4 wide tabs and reflowed the code at the end. – Vality Dec 23 '15 at 18:19
  • 4
    @underscore_d: It appears that I'm wrong: Outside of comments, documentation and except in Kconfig, spaces are never used for indentation, and the above example is deliberately broken. -- 6 paragraphs down from the quote in the OP. – slebetman Dec 23 '15 at 22:40
16

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.

  • 11
    Exactly. It's too easy to suggest Torvalds is a loon. (He is, of course.) He may be too rigid for your taste, but he's describing a real development concern that causes real problems. You don't have to do exactly what he says, but you should think about why he's saying it. – Scant Roger Dec 23 '15 at 13:38
  • 7
    @ScantRoger Actually, that Torvalds-quote only sounds too rigid if you don't get his sense of humor. As I remember, earlier on in the same document, he suggests to print out a copy of the GNU coding style guidelines, only to burn them in some sort of ceremony. You'll hardly take that seriously, do you? In this quote, his main point is to define indentation for the linux kernel to be eight spaces, nothing more, and nothing less, that is what he's rigid about. The last sentence is only to underline that point, not to say that you must not use more levels of indentation - no rigidness implied. – cmaster Dec 23 '15 at 14:35
  • 1
    @cmaster Thanks for the context, right on! In answer to your query, I hardly take anything seriously. ;) – Scant Roger Dec 23 '15 at 15:02
  • 2
    @cmaster and then one reads his responses to github pull requests and line length of commit messages. He is a total nut-case. – Gusdor Dec 23 '15 at 15:28
  • 3
    Ceremoniously burning the GNU coding guidelines may not actually be necessary, but it is entirely in order at any point in time. – dmckee Dec 23 '15 at 16:40
13

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.

  • 3
    Wonderfull answer. One of the cases that would deserve a +2... (Note: No wrong spaces around . in this comment ;-) ) – cmaster Dec 23 '15 at 20:38
  • 2
    Linus's intro paragraph that you pointed out is very important so thank you for doing that! I think the first sentence is also very important for context, specifically preferred coding style as well as but this is what goes for anything that I have to be able to maintain – Chris Haas Dec 23 '15 at 20:56
9

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.

3

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.

1

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).

  • 1
    Looks like the Problem 31 doesn't require bruteforce and could be solved using a dynamic programming algorithm (edit: which means your code structure isn't the best if you're using a bruteforce algorithm). Also, Linus's point is that if your code requires many levels of indentation, it's likely not the best structure for the code. – Vincent Savard Dec 23 '15 at 14:00
  • 2
    @VincentSavard Never said it required brute force. Disagree with your 2nd point - sometimes it is the clearest and most succinct approach, not to mention the most efficient in some cases. – Robbie Dee Dec 23 '15 at 14:04
  • 1
    With that kind of problem I usually don't indent the loops. I think I had one case with 20 nested loops, absolutely trivial to write, and no indentation so you could see the loops were almost identical. – gnasher729 Dec 23 '15 at 14:14
  • 1
    @RobbieDee: My point is that your example of a problem solved by many loops is that your algorithm isn't as efficient as a dynamic programming solution, which doesn't require as many levels of indentation. Thus, as Linus said, your levels of indentation can be removed by using a better solution. You also misunderstood my second point because I agree with what you said. Sometimes, it's the best solution. Sometimes isn't often, and isn't likely. – Vincent Savard Dec 23 '15 at 14:41
  • 1
    The Linus quote pretty much explicitly says that if some code requires something like bruteforcing that Problem-31, then you're screwed anyway - it will not be fast nor simple, and kernel operations must be fast and simple. Including any O(n^4) algorithm in kernel is a significant risk of performance or denial of service problems, so in this context the recommendation simply warns that this is a sign of code that may be fundamentally inappropriate and wanted in Linux. – Peteris Dec 23 '15 at 15:24
0

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.

  • 2
    While this might be the official guideline, it's trivial to find places in the kernel code where the guideline isn't enforced. – MikeB Dec 23 '15 at 18:00
  • 1
    @MikeB: All the more reasons to enforce guidelines automatically... – Matthieu M. Dec 23 '15 at 18:03
  • 1
    @MatthieuM. Are you sure you understand the difference between guidelines and mandatory requirements? As a general "rule of thumb" (a guideline if you like), guidelines are more like recommendations and aren't enforced. – Brendan Dec 28 '15 at 10:17

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