Nested loops and their performance cost

Understanding Nested loops and their performance cost

A nested loop is not two loops running side by side. The inner loop is part of the outer loop's body, so it is set up, run to completion, and thrown away once per outer pass. With three rows and four columns the inner loop starts three times while its body runs twelve times, because the number of (row, column) combinations is 3 × 4, not 3 + 4. That product is the number to reason about when you ask what a nested loop costs.

Because counts multiply, cost tracks the product of the bounds, and when both bounds come from the same input the work grows as n². Doubling the input quadruples the work; a third level makes it n³, so an eight-fold larger input means 512 times the work. The version that actually bites people is the inner loop they never typed: includes, indexOf, find, filter, and a lookup by scanning all walk an array from the start, so calling one inside a loop is a second loop wearing a method name.

Two fixes exist and they are not interchangeable. Hoisting work that does not depend on the inner variable up one level, or starting the inner index at i + 1 when a pair (a, b) means the same as (b, a), strips out a constant factor: twelve calls become three, thirty-six comparisons become fifteen. Building a Set or Map once before the outer loop changes something deeper, because each lookup stops depending on array length at all, so n² collapses to roughly n. That is the difference between a page that stalls at large input and one that does not.

const rows = ['a', 'b', 'c'];
const cols = [1, 2, 3, 4];

let innerStarts = 0; // how often the inner loop is set up
let bodyRuns = 0;    // how often the innermost body runs
const pairs = [];

for (let i = 0; i < rows.length; i++) {
  innerStarts++;
  for (let j = 0; j < cols.length; j++) {
    bodyRuns++;
    pairs.push(rows[i] + cols[j]);
  }
}

console.log(pairs.join(' '));
console.log('inner loop started', innerStarts, 'times');
console.log('body ran', bodyRuns, 'times =', rows.length, '*', cols.length);

Worked examples

const ids = [4, 7, 4, 9, 7, 1];

let comparisons = 0;
const nestedDupes = [];
for (let i = 0; i < ids.length; i++) {
  for (let j = i + 1; j < ids.length; j++) {
    comparisons++;
    if (ids[i] === ids[j] && !nestedDupes.includes(ids[i])) {
      nestedDupes.push(ids[i]);
    }
  }
}
console.log('nested:', nestedDupes.join(','), 'in', comparisons, 'comparisons');

let visits = 0;
const seen = new Set();
const setDupes = new Set();
for (let i = 0; i < ids.length; i++) {
  visits++;
  if (seen.has(ids[i])) setDupes.add(ids[i]);
  seen.add(ids[i]);
}
console.log('set:', [...setDupes].join(','), 'in', visits, 'visits');

let big = 0;
for (let i = 0; i < 1000; i++) {
  for (let j = i + 1; j < 1000; j++) {
    big++;
  }
}
console.log('same nested search over 1000 ids:', big, 'comparisons');

let calls = 0;
function normalize(name) {
  calls++;
  return name.trim().toLowerCase();
}

const names = ['  Ada ', ' Grace', 'Alan '];
const queries = ['ada', 'alan', 'lin', 'grace'];

let hits = 0;
for (let i = 0; i < names.length; i++) {
  for (let j = 0; j < queries.length; j++) {
    if (normalize(names[i]) === queries[j]) hits++;
  }
}
console.log('inside inner loop: hits', hits, 'normalize calls', calls);

calls = 0;
hits = 0;
for (let i = 0; i < names.length; i++) {
  const name = normalize(names[i]);
  for (let j = 0; j < queries.length; j++) {
    if (name === queries[j]) hits++;
  }
}
console.log('hoisted one level: hits', hits, 'normalize calls', calls);

const sizes = [10, 20, 40, 80];

for (let s = 0; s < sizes.length; s++) {
  const n = sizes[s];
  let steps = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      steps++;
    }
  }
  console.log('n =', n, 'body runs =', steps);
}

Important notes

Common mistakes

Try it yourself