SPO Week 3.2 - Optimization Techniques

In week 3 along with the massive lab 3 that we did, we also went over some of the most common compiler optimization techniques. Understanding how compilers optimize code can help us write better, cleaner programs and save us from spending unnecessary time on micro-optimizations. In this blog, we’ll explore some of the key techniques that I learned this week and thought were cool.

1. Code Rewriting Optimizations

These optimizations are performed on the intermediate representation (IR) of code and help to simplify, speed up, or shrink the program without altering its behavior.

Dead Code Elimination

• What It Is: Removing code that doesn’t contribute to the program’s output.
• Example: If a variable is assigned a value but never used, the compiler can safely remove the assignment.

Strength Reduction

• What It Is: Replacing expensive operations with cheaper ones.
• Example: Multiplying by 2 (x * 2) can be replaced with adding the number to itself (x + x).

Hoisting

• What It Is: Moving computations that don’t change during loop iterations (loop-invariant code) to outside the loop.
• Example: Instead of recalculating a constant value 100 times inside a loop, calculate it once before the loop starts.

Loop Unswitching

• What It Is: Moving conditionals out of loops to avoid repeated checks.
• Example: If an if statement inside a loop checks a condition that doesn’t change, the compiler can move it outside the loop to create two separate loops.

Loop Unrolling

• What It Is: Expanding the loop body to reduce the number of iterations and condition checks.
• Example: Instead of looping 10,000 times, unrolling might mean the compiler rewrites the loop to perform two iterations per cycle, effectively halving the number of loop condition checks.

Inlining

• What It Is: Integrating the code of a function directly into the place where it’s called, avoiding the overhead of a function call.
• Example: Instead of jumping to a separate function and returning, the compiler replaces the function call with the function’s actual code.

Common Subexpression Elimination

• What It Is: Identifying and reusing calculations that are repeated in different parts of the code.
• Example: If a * b is calculated multiple times, the compiler can calculate it once, store the result, and reuse it.

Jump Threading

• What It Is: Simplifying multiple conditionals that result in the same outcome.
• Example: If a sequence of if statements can be condensed into one, the compiler will do so to save on conditional checks.

Test Reordering

• What It Is: Reordering condition checks to prioritize simpler or more likely outcomes.
• Example: Instead of evaluating a complex condition first, the compiler may check a simple condition to short-circuit the evaluation and save time.

Dead Store Elimination

• What It Is: Removing assignments to variables that are never used again.
• Example: If a variable is set but then overwritten or not used before being reset, the compiler can skip the original assignment.

2. Machine Code Optimizations

Beyond rewriting the code, compilers also tweak how instructions are handled at the machine level for further improvements.

Block Rearrangement

• What It Is: Changing the order of code blocks to enhance CPU cache performance.
• Example: Moving rarely-executed error-handling code away from the main execution path helps the CPU cache the more critical parts of the program.

Instruction Selection

• What It Is: Choosing faster or more efficient machine instructions.
• Example: Using XOR EAX, EAX to zero out a register instead of using MOV EAX, 0, as it’s faster and takes up less space.

3. Profile-Guided and Link-Time Optimizations

These techniques allow the compiler to optimize code based on real-world usage or more holistic views of the program.

Profile-Guided Optimization (PGO)

• What It Is: The compiler collects data on how the program is used in real-world scenarios and uses this data to optimize hot paths (code that runs often).
• Example: During a test run, the program might reveal that a particular function is used frequently. The compiler can optimize this function more aggressively in subsequent builds.

Link-Time Optimization (LTO)

• What It Is: Delays certain optimizations until all parts of the program are linked together, allowing the compiler to optimize across module boundaries.
• Example: LTO can identify and remove redundant calculations across different files in a way that would be impossible during the individual compilation of modules.

4. Why Understanding Compiler Optimizations Matters

As developers, knowing how compilers work helps us write better code. While it’s tempting to manually optimize every bit of code, understanding the following can free us up to focus on higher-level improvements:

• Write Code for Clarity: Trust the compiler to handle the micro-optimizations. Write code that is logical, easy to understand, and maintainable. The compiler will handle the rest.
• Focus on Algorithms: Compilers can’t change your algorithms. If your code uses an inefficient algorithm, no amount of compiler optimization can save it. Instead, prioritize choosing the right data structures and algorithms for the task at hand.
• Use Compiler Flags: Familiarize yourself with optimization flags like -O2, -O3, and -Os to control how aggressively the compiler optimizes your code. Experiment with them to see how they impact performance and binary size.

5. Advanced Techniques for Developers

While compilers handle most low-level optimizations, developers can still apply strategies like memoization and precomputation to improve performance in areas the compiler can’t touch. For example:

• Memoization: Store the results of expensive function calls and return the cached result when the same inputs occur again.
• Precomputation: Pre-calculate a set of values and store them for quick lookup during execution, instead of recalculating them each time.

Conclusion

Modern compilers are incredibly sophisticated, capable of applying a wide range of optimizations to make your code run faster and more efficiently. By understanding these optimizations, developers can write cleaner code, geared so that compiler can do their optimization more easily.