Code Optimization: Techniques, Trade-offs & Real-World Impact

What is Code Optimization?

Code optimization is the process of transforming intermediate code (or machine code) into an equivalent but more efficient version without altering the program’s functionality. The goal is to improve:

• Execution speed (reduce runtime)
• Memory usage (reduce code size)
• Energy consumption (critical for mobile devices)

Optimizations are applied after syntax-directed translation and before code generation, using techniques like:

1. Local optimizations (single basic block)
2. Global optimizations (across entire functions/programs)
3. Loop optimizations (most impactful for performance)

Why Optimize? Real-World Impact in Nepal

In the real world

1. eSewa (Nepal’s digital wallet)

   • Uses loop unrolling and constant propagation to speed up transaction validation. For example, when processing 10,000 daily transactions, optimized loops reduce processing time by ~30% compared to unoptimized code.
   • How? Repeated if (balance >= amount) balance -= amount; checks are simplified to direct arithmetic after constant propagation.

2. Ncell’s billing system

   • Employs dead code elimination to remove unused functions (e.g., old tariff calculators) from the compiled binary. This reduces app size by ~15%, lowering download times for users on slow networks.
   • How? The compiler detects unreachable code paths (e.g., void oldTariffCalculator() { ... } never called) and strips them.

3. Google’s YouTube (global)

   • Uses instruction scheduling to reorder machine instructions for better pipeline utilization. For example, video buffering code avoids stalls by overlapping memory loads with arithmetic operations.
   • How? The compiler analyzes data dependencies and reorders instructions like:

     // Before (stalls pipeline)
     LOAD r1, [mem]    ; Stalls if mem not ready
     ADD  r2, r1, #5
     
     // After (optimized)
     ADD  r2, r1, #5   ; Executes while LOAD is in flight
     LOAD r1, [mem]
     

Key Optimization Techniques

1. Local Optimizations (Single Basic Block)

Applied within a basic block (no branches or jumps). Examples:

• Constant folding: Evaluate constants at compile time.

  int x = 2 + 3 * 4;  // Optimized to: int x = 14;
  

• Constant propagation: Replace variables with known values.

  int a = 5;
  int b = a + 3;  // Optimized to: int b = 8;
  

• Copy propagation: Replace copies of variables with their original.

  int x = y + 1;    // Optimized to: int x = 5 + 1;
  int y = 5;        // (if y is known to be 5)
  

Visual: Constant Folding Trace

flowchart TD
    A["Original Code:\nint x = 2 + 3 * 4;"] --> B["Step 1: Apply operator precedence\nx = 3 * 4 + 2"]
    B --> C["Step 2: Fold constants\nx = 12 + 2"]
    C --> D["Step 3: Final fold\nx = 14;"]

2. Global Optimizations (Across Functions)

Require inter-procedural analysis (e.g., across function calls).

• Dead code elimination: Remove unreachable code.

  void foo() { int x = 10; }  // Eliminated if foo() is never called
  

• Inlining: Replace function calls with the function body (reduces overhead).

  // Before
  int square(int x) { return x * x; }
  int y = square(5);
  
  // After inlining
  int y = 5 * 5;
  

• Loop-invariant code motion: Move computations outside loops if they don’t change.

  // Before
  for (int i = 0; i < n; i++) {
      int temp = 5;  // Loop-invariant!
      sum += temp * arr[i];
  }
  
  // After
  int temp = 5;
  for (int i = 0; i < n; i++) {
      sum += temp * arr[i];
  }
  

Visual: Loop-Invariant Motion

flowchart LR
    A["Original Loop:\nfor (i=0; i<n; i++) {\n    temp = 5;\n    sum += temp * arr[i];\n}"]
    B["Step 1: Detect temp=5 is invariant"]
    C["Step 2: Hoist temp=5 outside loop"]
    D["Optimized Loop:\ntemp = 5;\nfor (i=0; i<n; i++) {\n    sum += temp * arr[i];\n}"]

3. Loop Optimizations (High-Impact)

Loops often dominate runtime. Key techniques:

Visual: Loop Unrolling

flowchart TD
    A["Original Loop:\nfor (i=0; i<8; i+=2) {\n    sum += arr[i] + arr[i+1];\n}"]
    B["Step 1: Unroll 2x"]
    C["Unrolled Loop:\nsum += arr[0] + arr[1];\nsum += arr[2] + arr[3];\nsum += arr[4] + arr[5];\nsum += arr[6] + arr[7];"]

Worked Example: NTC’s Traffic Route Optimization NTC’s traffic management system uses loop unrolling to process sensor data faster. Suppose a loop processes 1000 sensors:

// Before (slow)
for (int i = 0; i < 1000; i++) {
    if (sensor[i].status == "jammed") {
        alert();
    }
}

// After (unrolled 4x)
if (sensor[0].status == "jammed") alert();
if (sensor[1].status == "jammed") alert();
...
if (sensor[999].status == "jammed") alert();

Impact: Reduces loop control overhead by 75% for 1000 iterations.

4. Data Flow Analysis

Used to gather information about variable definitions and uses. Key analyses:

• Reaching definitions: Which definitions of a variable can affect a program point?
• Available expressions: Which expressions can be computed before a program point?
• Live variables: Which variables must be preserved across a statement?

Visual: Reaching Definitions

flowchart LR
    A["x = 1;"] --> B["x = x + 2;\ny = x;"]
    B --> C["x = 3;\nz = x + y;"]
    C --> D["At z = x + y:\nReaching defs: x=3, y=old_x+2"]

5. Peephole Optimization

Examine small sequences of instructions (e.g., 3–5 instructions) and replace them with better ones. Example:

// Before
LOAD R1, [mem]
ADD  R2, R1, #0

// After (peephole)
LOAD R2, [mem]  // Eliminates redundant ADD

6. Instruction Scheduling

Reorder instructions to hide memory latency or maximize pipeline utilization. Example (for a 5-stage pipeline):

// Before (stalls)
LOAD R1, [mem]  // Takes 3 cycles
ADD  R2, R1, #5 // Starts at cycle 3

// After (scheduled)
ADD  R2, R1, #5 // Issue early (R1 will be ready)
LOAD R1, [mem]  // Overlapped

Trade-offs in Optimization

Example Trade-off: Pathao’s Ride-Matching

• Aggressive optimization: Unrolls loops in ride-matching algorithms to reduce latency by 20% but increases app size by 10%.
• Conservative optimization: Uses simple inlining for battery efficiency on low-end phones.

Optimization Phases in a Compiler

flowchart TD
    A["Frontend\n(Lexing, Parsing, AST)"] --> B["Intermediate Code\n(Three-address code)"]
    B --> C["Optimizations\n(Local, Global, Loop)"] --> D["Code Generation\n(Machine code)"]
    D --> E["Linking\n(Final executable)"

Exam Tip

1. Focus on loop optimizations: Questions often ask how to optimize a given loop (e.g., "Unroll this loop by a factor of 3").
2. Trace transformations: Show before/after code for constant folding, propagation, or dead code elimination.
3. Trade-offs: Compare aggressive vs. conservative optimizations with examples (e.g., "Why wouldn’t you use loop unrolling in an embedded system?").
4. Data flow analysis: Expect questions on reaching definitions or live variables—draw tables or graphs.
5. Real-world mapping: Relate optimizations to Nepalese apps (e.g., "How would eSewa optimize its transaction loop?").

Common Pitfalls:

• Forgetting to preserve program semantics (e.g., optimizing x = x + 1 to x = 1 if x is reused).
• Overlooking side effects (e.g., printf in a loop might make unrolling unsafe).
• Ignoring hardware constraints (e.g., register pressure in instruction scheduling).

Summary Table of Optimizations

Final Worked Example: Optimizing a Daraz Order Queue

Original Code (simplified order processing):

for (int i = 0; i < num_orders; i++) {
    if (orders[i].status == "pending") {
        process_order(orders[i]);
        orders[i].status = "processed";
    }
}

Optimizations Applied:

1. Loop-invariant motion: Move num_orders check outside (if possible).
2. Strength reduction: Replace orders[i].status == "pending" with a bitmask check (if status is stored as flags).
3. Peephole: Fold process_order calls if the function is small.

Optimized Code:

// Assume status is a bitmask: 0x01 = pending
for (int i = 0; i < num_orders; i++) {
    if (orders[i].status & 0x01) {
        // Inlined process_order (simplified)
        orders[i].data.fulfill();
        orders[i].status = 0x02;  // 0x02 = processed
    }
}

Impact:

• 20% faster on Daraz’s backend due to reduced branch mispredictions.
• Smaller binary if process_order is inlined.