Introduction

You already know how to write correct and modular C programs. In this lesson, you’ll learn how to make them fast and efficient. We’ll focus on understanding algorithm complexity, finding bottlenecks with profiling tools, improving memory usage, writing tight loops and control flow, and leveraging compiler optimizations.

Optimization in C is as much about measuring as it is about changing code. You’ll see how to reason about performance, inspect real programs, and apply practical techniques that scale from toy programs to production systems.

Algorithm Complexity and Its Impact on Performance

Even a perfectly optimized C loop can’t save a fundamentally inefficient algorithm. Before micro-optimizing, you must understand time complexity.

Big-O in Practice

Consider two functions that find the maximum in an array. One naïve O(n^2) version, and one optimal O(n) version:

#include <stdio.h>
#include <limits.h>

int max_quadratic(const int *a, int n) {
    int max = INT_MIN;
    for (int i = 0; i < n; ++i) {
        int is_max = 1;
        for (int j = 0; j < n; ++j) {
            if (a[j] > a[i]) {
                is_max = 0;
                break;
            }
        }
        if (is_max && a[i] > max) {
            max = a[i];
        }
    }
    return max;
}

int max_linear(const int *a, int n) {
    int max = a[0];
    for (int i = 1; i < n; ++i) {
        if (a[i] > max)
            max = a[i];
    }
    return max;
}

int main(void) {
    int arr[5] = {3, 7, 2, 9, 4};
    printf("max_quadratic: %d\n", max_quadratic(arr, 5));
    printf("max_linear:    %d\n", max_linear(arr, 5));
    return 0;
}

// Output:
max_quadratic: 9
max_linear:    9

Both functions are correct and produce the same output, but max_quadratic does roughly n² comparisons, while max_linear does about n. For n = 1,000,000, the difference is enormous. Optimization always starts with checking if your algorithm is asymptotically efficient.

Identifying Bottlenecks with Profiling

Once the algorithm is appropriate, you need to find where your program spends its time.

Using gprof (Conceptual Overview)

1. Compile with profiling enabled:

   gcc -pg -O2 main.c -o app
   

2. Run the program to generate gmon.out:

   ./app
   

3. Generate report:

   gprof ./app gmon.out > profile.txt
   

In profile.txt, look for functions with the highest self time and cumulative time. These are your bottlenecks. That’s where low-level C tweaks (loop optimization, better data layout, caching results) will have real impact.

On Linux, tools like perf, valgrind --tool=callgrind, or IDE profilers provide similar insights with more detail.

Memory Management Techniques for Performance

Correct memory handling is not enough; you also want efficient memory use.

Minimize Heap Allocations in Hot Paths

Dynamic allocation is relatively expensive. Avoid calling malloc/free inside performance-critical loops when possible.

#include <stdio.h>
#include <stdlib.h>

void process_with_many_allocs(int iterations) {
    for (int i = 0; i < iterations; ++i) {
        int *p = malloc(sizeof(int));
        if (!p) exit(EXIT_FAILURE);
        *p = i;
        // ... some simple work ...
        free(p);
    }
}

void process_with_reused_buffer(int iterations) {
    int *p = malloc(sizeof(int));
    if (!p) exit(EXIT_FAILURE);

    for (int i = 0; i < iterations; ++i) {
        *p = i;
        // ... same work ...
    }

    free(p);
}

int main(void) {
    process_with_many_allocs(5);
    process_with_reused_buffer(5);
    printf("Done.\n");
    return 0;
}

// Output:
Done.

Both approaches behave the same from the user’s perspective, but process_with_reused_buffer pays allocation cost only once, which can dramatically improve performance.

Improve Locality and Cache Usage

Prefer contiguous arrays and structures-of-arrays when iterating sequentially. Accessing memory linearly leverages CPU caches better than jumping around with scattered pointers.

• Keep frequently used data together in structs or arrays.
• Avoid unnecessary pointer indirections inside tight loops.

Optimizing Loops and Control Structures

Hoist Invariants and Reduce Work Per Iteration

Move computations that don’t change inside a loop (loop-invariant code) to outside the loop.

#include <stdio.h>

int sum_slow(const int *a, int n, int scale) {
    int result = 0;
    for (int i = 0; i < n; ++i) {
        result += a[i] * scale * scale;  // scale*scale recalculated each time
    }
    return result;
}

int sum_fast(const int *a, int n, int scale) {
    int result = 0;
    int scale_sq = scale * scale;        // computed once
    for (int i = 0; i < n; ++i) {
        result += a[i] * scale_sq;
    }
    return result;
}

int main(void) {
    int arr[4] = {1, 2, 3, 4};
    printf("slow: %d\n", sum_slow(arr, 4, 3));
    printf("fast: %d\n", sum_fast(arr, 4, 3));
    return 0;
}

// Output:
slow: 90
fast: 90

Same result, but the optimized version avoids repeated multiplication.

Favor Simple Branch Patterns

Branches (if, switch) mispredicted by the CPU can slow down tight loops. Some tips:

• Place the common case in the if branch and rare cases in else.
• Avoid unnecessary if checks inside inner loops (precompute flags once outside).
• When possible, use array indexing or lookup tables instead of deep nested if chains.

Leveraging Compiler Optimizations and Flags

The compiler can do a lot of optimization work for you—if you let it.

Common GCC/Clang Optimization Levels

• -O0 – no optimization (fastest compile, slowest code)
• -O1 – basic optimizations
• -O2 – good balance; use for most builds
• -O3 – more aggressive optimizations (may increase code size)
• -Os – optimize for size

Typical build for performance and useful debug info:

gcc -O2 -g -Wall -Wextra main.c -o app

Additional Useful Flags

• -march=native – enable instructions supported by your CPU
• -flto – link-time optimization across translation units
• -DNDEBUG – disables assert checks (after you finish debugging)

You should always measure before and after changing flags. Sometimes -O3 gives little benefit over -O2 but grows code size significantly.

Let the Compiler Inline Small Functions

Inline hints (static inline functions in headers) can remove function call overhead in hot paths, but overusing them may increase binary size and hurt instruction cache performance. Trust the compiler’s inliner, and only force inlining when profiling shows clear benefit.

Putting It All Together: A Small Optimized Example

Below is a basic example that combines several ideas: efficient algorithm, good memory layout, and compiler optimizations.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Compute dot product of two vectors

float dot_product_naive(const float *a, const float *b, int n) {
    float sum = 0.0f;
    for (int i = 0; i < n; ++i) {
        // redundant bounds/conditions could go here in a real naive version
        sum += a[i] * b[i];
    }
    return sum;
}

float dot_product_unrolled(const float *a, const float *b, int n) {
    float sum = 0.0f;
    int i = 0;
    // loop unrolling by 4
    for (; i + 3 < n; i += 4) {
        sum += a[i]     * b[i]
             + a[i + 1] * b[i + 1]
             + a[i + 2] * b[i + 2]
             + a[i + 3] * b[i + 3];
    }
    // handle remaining elements
    for (; i < n; ++i) {
        sum += a[i] * b[i];
    }
    return sum;
}

int main(void) {
    const int N = 8;
    float *a = malloc(sizeof(float) * N);
    float *b = malloc(sizeof(float) * N);
    if (!a || !b) return 1;

    for (int i = 0; i < N; ++i) {
        a[i] = (float)i;
        b[i] = (float)(N - i);
    }

    float r1 = dot_product_naive(a, b, N);
    float r2 = dot_product_unrolled(a, b, N);

    printf("naive:    %.2f\n", r1);
    printf("unrolled: %.2f\n", r2);

    free(a);
    free(b);
    return 0;
}

// Output:
naive:    84.00
unrolled: 84.00

For small N, performance is similar. For large N (e.g., millions of elements, compiled with -O2 or higher), the unrolled version typically performs better by reducing loop overhead and helping the compiler vectorize the loop.

Summary / Key Takeaways

In this lesson Performance Optimization Techniques, you have learned:

• Algorithm complexity dominates performance: Choosing O(n) or O(n log n) algorithms instead of O(n²) has far greater impact than minor code-level tweaks.
• Profiling is essential before optimizing: Use tools like gprof, perf, or callgrind to locate true bottlenecks instead of guessing.
• Efficient memory management improves speed: Reducing dynamic allocations in hot paths and improving data locality lead to better cache usage and lower overhead.
• Optimized loops reduce per-iteration cost: Hoisting invariants, minimizing branching, and unrolling critical loops can significantly accelerate core computations.
• Control structure design affects branch prediction: Organizing conditions so common cases are fast and predictable helps modern CPUs execute code more efficiently.
• Compiler optimization flags matter: Building with levels like -O2, plus flags such as -march=native and -flto, allows the compiler to apply powerful optimizations automatically.
• Micro-optimizations should be guided by measurements: Always measure before and after changes; focus on hot paths identified by profiling rather than optimizing random code.
• Maintainability still counts: Optimized code should remain readable and testable; balance performance gains against code complexity and future maintenance costs.