Loop Optimization

Definition

Loop optimization targets code inside loops specifically, since loop bodies execute many times, so even small improvements there yield large overall performance gains.

Key Points — Techniques

• Code Motion (Loop-Invariant Code Motion): moving computations that don't change across iterations outside the loop, so they run once instead of every iteration.
• Induction Variable Elimination: replacing variables that change by a fixed amount each iteration (e.g., array-index computations) with simpler updates, often removing multiplications.
• Strength Reduction: replacing expensive operations with cheaper equivalents inside the loop (e.g., replacing multiplication with repeated addition, or i*4 with a running total incremented by 4).
• Loop Unrolling: replicating the loop body multiple times to reduce loop-control overhead (fewer branch/condition checks per iteration).

Example

Before optimization:

for (i = 0; i < n; i++) {
    x = y * z;      // loop-invariant — same every iteration
    a[i] = i * 4;   // induction variable computation
}

After optimization:

x = y * z;               // moved outside (code motion)
t = 0;
for (i = 0; i < n; i++) {
    a[i] = t;             // strength-reduced (t += 4 each iteration)
    t = t + 4;
}

📌 CSS Frequency: High (explicitly 2017 repeated) — frequently a standalone numeric question: "optimize the given loop."

Model Answer (short)

"Loop optimization focuses on loop bodies because they execute repeatedly, so gains compound. Code motion hoists loop-invariant computations outside the loop; induction variable elimination and strength reduction replace expensive repeated arithmetic (like multiplication) inside the loop with cheaper incremental updates; and loop unrolling reduces per-iteration branch overhead by replicating the loop body. Together these reduce the total instruction count executed across all iterations."

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-I · Q7(c), 2019 · Q8(b), 2023 · Q7(c) · 6, 5 and 6 marks

Q. How would you optimise a loop? Describe the techniques briefly with examples.

Ans. Loops execute many times, so even small savings inside them matter greatly.

• Code motion (loop-invariant hoisting): move computations whose value does not change out of the loop.

for (i = 0; i < n; i++) x[i] = y * z + i;     →     t = y * z;  for (...) x[i] = t + i;

• Strength reduction: replace costly operations with cheaper ones (multiplication by addition, i * 2 by i << 1).
• Induction variable elimination: if several variables change in step (i and 4·i), keep only one and derive the others.
• Loop unrolling: repeat the body several times per iteration to cut loop-control overhead (more code size).
• Loop fusion (jamming): merge two loops over the same range to reduce overhead and improve cache use.
• Loop fission, interchange and tiling: improve cache behaviour.
• Dead-code and redundant-test elimination: remove statements and conditions that never matter.