Why are nested loops considered bad practice?

Question

My lecturer mentioned today that it was possible to "label" loops in Java so that you could refer to them when dealing with nested loops. So I looked up the feature as I didn't know about it and many places where this feature was explained it was followed by a warning, discouraging nested loops.

I don't really understand why? Is it because it affects the readability of the code? Or is it something more "technical"?

Answer 1

Nested loops are fine as long as they describe the correct algorithm.

Nested loops have performance considerations (see @Travis-Pesetto's answer), but sometimes it's exactly the correct algorithm, e.g. when you need to access every value in a matrix.

Labeling loops in Java allows to prematurely break out of several nested loops when other ways to do this would be cumbersome. E.g. some game might have a piece of code like this:

Player chosen_one = null;
...
outer: // this is a label
for (Player player : party.getPlayers()) {
  for (Cell cell : player.getVisibleMapCells()) {
    for (Item artefact : cell.getItemsOnTheFloor())
      if (artefact == HOLY_GRAIL) {
        chosen_one = player;
        break outer; // everyone stop looking, we found it
      }
  }
}

While code like the example above may sometimes be the optimal way to express a certain algorithm, it is usually better to break this code into smaller functions, and probably use return instead of break. So a break with a label is a faint code smell; pay extra attention when you see it.

Answer 2

Nested loops are frequently (but not always) bad practice, because they're frequently (but not always) overkill for what you're trying to do. In many cases, there's a much faster and less wasteful way to accomplish the goal you're trying to achieve.

For example, if you have 100 items in list A, and 100 items in list B, and you know that for each item in list A there's one item in list B that matches it, (with the definition of "match" left deliberately obscure here), and you want to produce a list of pairs, the simple way to do it is like this:

for each item X in list A:
  for each item Y in list B:
    if X matches Y then
      add (X, Y) to results
      break

With 100 items in each list, this will take an average of 100 * 100 / 2 (5,000) matches operations. With more items, or if the 1:1 correlation is not assured, it becomes even more expensive.

On the other hand, there's a much faster way to perform an operation like this:

sort list A
sort list B (according to the same sort order)
I = 0
J = 0
repeat
  X = A[I]
  Y = B[J]
  if X matches Y then
    add (X, Y) to results
    increment I
    increment J
  else if X < Y then
    increment I
  else increment J
until either index reaches the end of its list

If you do it this way, instead of the number of matches operations being based on length(A) * length(B), it's now based on length(A) + length(B), which means your code will run much faster.

Answer 3

One reason to avoid nesting loops is because it's a bad idea to nest block structures too deeply, irrespective of whether they're loops or not.

Each function or method should be easy to understand, both it's purpose (the name should express what it does) and for maintainers (it should be easy to understand the internals). If a function is too complicated to easily understand, that usually means that some of the internals should be factored out into separate functions so they can be referred to in the (now smaller) main function by name.

Nested loops can get difficult to understand relatively quickly, though some nesting of loops is fine - providing, as others point out, that doesn't mean you're creating a performance issue by using an extremely (and unnecessarily) slow algorithm.

Actually, you don't need nested loops to get absurdly slow performance bounds. Consider, for example, a single loop that in each iteration takes one item from a queue, then possibly puts several back - e.g. breadth-first search of a maze. The performance isn't decided by the depth of nesting of the loop (which is only 1) but by the number of items that get put in that queue before it's eventually exhausted (if it's ever exhausted) - how big the reachable part of the maze is.

Answer 4

Given the case of many nested loops you end up with polynomial time. For example given this pseudo code:

set i equal to 1
while i is not equal to 100
  increment i
  set j equal to 1
  while j is not equal to i
    increment j
  end
 end

This would be considered O(n^2) time which would be a graph similar to:

Where the y-axis is the amount of time your program takes to terminate and the x-axis is the amount of data.

If you get too much data your program will be so slow nobody will wait for it. and It's not that much around 1,000 data entries I believe will take it too long.

Answer 5

Driving a thirty ton truck instead of a small passenger vehicle is bad practice. Except when you need to transport 20 or 30 tons of stuff.

When you use a nested loop, it’s not bad practice. It’s either utterly stupid, or it’s exactly what is needed. You decide.

However, someone complained about labelling loops. The answer for that: if you have to ask the question, then don’t use labelling. If you know enough to decide yourself, then you decide yourself.

Answer 6

There's nothing inherently wrong or necessarily even bad about nested loops. They do however have certain considerations and pitfalls.

The articles you were led to, likely in the name of brevity or due to a psychological process known as being burnt, skipping over the specifics.

Being burnt is when you have a negative experience of something with the implicating being you then avoid it. For example I might cut vegetables with a sharp knife and cut myself. I might then say sharp knives are bad don't use them to cut vegetables to try to make it impossible for that bad experience to ever happen again. That's obviously very impractical. In reality you just need to be careful. If you're telling someone else to cut vegetables then you have an even stronger sense of this. If I were instructing children to cut vegetables I would very strongly feel to tell them to not use a sharp knife especially if I can't supervise them closely.

The problem is in programming is that you'll not meet peak efficiency if you always prefer safety first. In this case the kids can only cut soft vegetables. Confronted with anything else and they're only going to make a mess of it using a blunt knife. It's important to learn the proper use of loops including nested loops and you can't do that if they're deemed bad and you never try to use them.

As many answers here point out a nested for loop is an indication of the performance characteristics of your program which may get exponentially worse each nesting. That is, O(n), O(n^2), O(n^3) and so on which comprises O(n^depth) where depth represents how many loops you have nested. As your nesting grows, the time required grows exponentially. The problem is with this is that it's not a certainty either that your time or space complexity will be that (quite often a * b * c but not all nest loops may run all the time either) nor is it a certainty that you'll have a performance problem even if it is that.

For many people, particularly students, writers and lecturers who to be frank, rarely program for a living or on a day to day basis for loops may also be something they're not used to and that induced too much cognitive load on early encounters. This is a problematic aspect because there's always a learning curve and avoiding it wont be effective in converting students into programmers.

Nested loops can go wild, that is they can end up nested very deeply. If I go through each continent, then through each country, then through each city, then through each shop, then through each shelf, then through each product if it's a can of beans through each bean and measure it's size to get the average then you can see that'll nest very deeply. You'll have a pyramid and a lot of wasted space away from the left margin. You may even end up going off the page.

This is a problem that would be more significant historically where screens were small and of low resolution. In those cases even a few levels of nesting could genuinely take up a lot of space. This is a lesser concern today where the threshold is higher though it can still present a problem if there's enough nesting.

Related is the aesthetics argument. Many people do not find nested for loops aesthetically pleasing in contrast to layouts with more consistent alignment this may or may not be linked to what people are used to, eye tracking and other concerns. It is however problematic in that it tends to be self reinforcing and may ultimately make code harder to read as breaking up a block of code and encapsulating loops behind abstractions such as functions also risks breaking up the mapping of the code to the flow of execution.

There's a natural tendency towards what people are used to. If you're programming something in the simplest way the probability of needing no nesting is highest, the probability of needing one level drops off by an order of magnitude, the probability for another level drops off again. The frequency dropping and essentially meaning the deeper the nesting the less trained the human senses are to anticipate it.

Related to that is that in any complex construct, which a nested loop can be considered, then you should always ask is that the simplest possible solution as there's potential for a missed solution needing less loops. The irony is that a nested solution often is the simplest way to produce something that works with the minimum amount of effort, complexity and cognitive load. It's often natural to nest for loops. If you consider for example one of the answers above where the much faster way than a nested for loop is also far more complex and consists of significantly more code.

A great deal of care is needed as it's often possible to abstract loops away or flatten them yet with the end result ultimately being a cure worse than the disease particularly if you're not for example receiving a measurable and significant performance enhancement from the effort.

It's very common for people to frequently experience performance problems in association to loops which are telling the computer to repeat an action many times and will inherently often be implicated in performance bottlenecks. Unfortunately responses to this can be very superficial. It becomes common for people to see a loop and see a performance problem where there is none and then hide the loop from sight to no real effect. The code "looks" fast but put it on the road, key in the ignition, floor the accelerator and take a look at the speedometer and you might find it's still about as fast as an old lady walking her zimmer frame.

This kind of hiding is similar to if you have ten muggers on your route. If instead of having a straight route to where you want to go you arrange it so that there's a mugger behind every corner then it gives the illusion as you start your journey that there are no muggers. Out of sight out of mind. you're still going to get mugged ten times but now you wont see it coming.

The answer to you're question is that it's both, but neither concerns is absolute. They're either entirely subjective or only contextually objective. Unfortunately sometimes the entirely subjective or rather opinion takes precedent and dominates.

As a rule of thumb, if it needs a nested loop or that seems like the next obvious step, it's best not to deliberate and simply do it. However if any doubts linger then it should be later reviewed.

Another rule of thumb is that you should always check the cardinality and ask yourself is this loop going to be a problem. In my previous example I went through cities. For testing I might only go through ten cities but what's a reasonable maximum number of cities to expect in real world usage? I then might multiply that by the same for continents. It's a rule of thumb to always consider with loops especially that iterate a dynamic (variable) amount of times what that might translate to down the line.

Regardless always do what works first. The way when you do see an opportunity for optimisation your can compare your optimised solution against the easiest to get working and confirm that it yielded the benefits expected. You can also spend too long prematurely optimising before the measurements are in and that leads to YAGNI or a lot of wasted time and missed deadlines.