Lesson 27-Performance Optimization – TianyaSchool – Science, Technology & Engineering Learning Platform

Performance Analysis Tools

gprof (GNU Profiler)

gprof is a performance analysis tool in the GNU toolchain used to measure program execution time and function call relationships.

Usage Steps

Add -g and -pg options during compilation:

gcc -g -pg -o program program.c

gcc -g -pg -o program program.c

Run the program:

./program

./program

This generates a gmon.out file.

Analyze the results:

gprof program gmon.out > analysis.txt

gprof program gmon.out > analysis.txt

Analysis Report Interpretation

Typical output includes:

Flat profile: Execution time proportion of each function
Call graph: Function call relationship graph

Example output snippet:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 30.1      0.30     0.30    10000     0.03     0.04  expensive_function
 25.6      0.58     0.28    20000     0.01     0.01  another_function
 ...

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 30.1      0.30     0.30    10000     0.03     0.04  expensive_function
 25.6      0.58     0.28    20000     0.01     0.01  another_function
 ...

Limitations

Can only measure sampling time, not precise
Not suitable for multithreaded programs
May be inaccurate for short functions

perf (Linux Performance Events)

perf is a more powerful performance analysis tool provided by the Linux kernel.

Basic Usage

Record CPU cycles: perf record -e cycles ./program
Generate report: perf report
View hot functions: perf top

Advanced Features

Analyze cache hit rate: perf stat -e cache-misses,cache-references ./program
Analyze branch prediction: perf stat -e branch-misses,branches ./program
Record call stack: perf record -g ./program
Generate flame graph: perf script | FlameGraph/stackcollapse-perf.pl | FlameGraph/flamegraph.pl > flamegraph.svg

perf Advantages

More precise time measurement
Supports hardware performance counters
Can analyze multithreaded programs
Supports multiple event types

Memory Access Optimization

Cache Hit Rate Optimization

Modern CPUs rely on multi-level caches (L1/L2/L3); improving cache hit rate is crucial.

Data Locality Principles

Temporal locality: Recently used data is likely to be used again soon
Spatial locality: Data at adjacent addresses is likely to be accessed together

Optimization Techniques

Array access order:

// Bad order (column-major)
for (int j = 0; j < N; j++) {
	for (int i = 0; i < M; i++) {
		sum += matrix[i][j];
	}
}

// Good order (row-major)
for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
		sum += matrix[i][j];
	}
}

// Bad order (column-major)
for (int j = 0; j < N; j++) {
	for (int i = 0; i < M; i++) {
		sum += matrix[i][j];
	}
}

// Good order (row-major)
for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
		sum += matrix[i][j];
	}
}

Struct member ordering:

// Bad order (as declared)
struct {
	char a;    // 1 byte
	int b;     // 4 bytes
	char c;    // 1 byte
} s;

// Good order (sorted by size)
struct {
	int b;     // 4 bytes
	char a;    // 1 byte
	char c;    // 1 byte
	// May have padding bytes
} ;

// Bad order (as declared)
struct {
	char a;    // 1 byte
	int b;     // 4 bytes
	char c;    // 1 byte
} s;

// Good order (sorted by size)
struct {
	int b;     // 4 bytes
	char a;    // 1 byte
	char c;    // 1 byte
	// May have padding bytes
} ;

Prefetching Techniques

Prefetching is a technique to load data into the cache ahead of time.

Compiler Automatic Prefetching

Modern compilers automatically insert prefetch instructions, controllable via compile options:

gcc -fprefetch-loop-arrays  # Enable prefetching for arrays in loops

gcc -fprefetch-loop-arrays  # Enable prefetching for arrays in loops

Manual Prefetching

#include <xmmintrin.h>  // SSE instruction set

void process_array(float* array, int size) {
    for (int i = 0; i < size; i++) {
        if (i + 16 < size) {
            _mm_prefetch(&array[i+16], _MM_HINT_T0);  // Prefetch into L1 cache
        }
        // Process array[i]
    }
}

#include <xmmintrin.h>  // SSE instruction set

void process_array(float* array, int size) {
    for (int i = 0; i < size; i++) {
        if (i + 16 < size) {
            _mm_prefetch(&array[i+16], _MM_HINT_T0);  // Prefetch into L1 cache
        }
        // Process array[i]
    }
}

Prefetching Considerations

Prefetching too early may cause data to be evicted by other data
Prefetching too late has no effect
Needs adjustment based on specific hardware characteristics

Loop Optimization Techniques

Loop Unrolling

A technique to reduce loop control overhead.

Manual Unrolling

// Original loop
for (int i = 0; i < N; i++) {
    sum += array[i];
}

// Unroll 4 times
for (int i = 0; i < N; i += 4) {
    sum += array[i] + array[i+1] + array[i+2] + array[i+3];
}
// Need to handle remaining elements

// Original loop
for (int i = 0; i < N; i++) {
    sum += array[i];
}

// Unroll 4 times
for (int i = 0; i < N; i += 4) {
    sum += array[i] + array[i+1] + array[i+2] + array[i+3];
}
// Need to handle remaining elements

Compiler Automatic Unrolling

gcc -funroll-loops  # Enable loop unrolling

gcc -funroll-loops  # Enable loop unrolling

Smart Unrolling

// Use macro to simplify unrolling
#define UNROLL4(i) \
    sum += array[i]; \
    sum += array[i+1]; \
    sum += array[i+2]; \
    sum += array[i+3];

for (int i = 0; i < N; i += 4) {
    UNROLL4(i)
}

// Use macro to simplify unrolling
#define UNROLL4(i) \
    sum += array[i]; \
    sum += array[i+1]; \
    sum += array[i+2]; \
    sum += array[i+3];

for (int i = 0; i < N; i += 4) {
    UNROLL4(i)
}

Vectorization

Use SIMD instructions to process multiple data in parallel.

Compiler Automatic Vectorization

gcc -ftree-vectorize  # Enable automatic vectorization

gcc -ftree-vectorize  # Enable automatic vectorization

Manual Vectorization (SSE Example)

#include <xmmintrin.h>

void add_vectors(float* a, float* b, float* c, int n) {
    for (int i = 0; i < n; i += 4) {
        __m128 va = _mm_loadu_ps(&a[i]);
        __m128 vb = _mm_loadu_ps(&b[i]);
        __m128 vc = _mm_add_ps(va, vb);
        _mm_storeu_ps(&c[i], vc);
    }
}

#include <xmmintrin.h>

void add_vectors(float* a, float* b, float* c, int n) {
    for (int i = 0; i < n; i += 4) {
        __m128 va = _mm_loadu_ps(&a[i]);
        __m128 vb = _mm_loadu_ps(&b[i]);
        __m128 vc = _mm_add_ps(va, vb);
        _mm_storeu_ps(&c[i], vc);
    }
}

AVX Extension (256-bit)

#include <immintrin.h>

void add_vectors_avx(float* a, float* b, float* c, int n) {
    for (int i = 0; i < n; i += 8) {
        __m256 va = _mm256_loadu_ps(&a[i]);
        __m256 vb = _mm256_loadu_ps(&b[i]);
        __m256 vc = _mm256_add_ps(va, vb);
        _mm256_storeu_ps(&c[i], vc);
    }
}

#include <immintrin.h>

void add_vectors_avx(float* a, float* b, float* c, int n) {
    for (int i = 0; i < n; i += 8) {
        __m256 va = _mm256_loadu_ps(&a[i]);
        __m256 vb = _mm256_loadu_ps(&b[i]);
        __m256 vc = _mm256_add_ps(va, vb);
        _mm256_storeu_ps(&c[i], vc);
    }
}

Inline Assembly

Inline assembly allows embedding assembly instructions directly in C code.

Basic Syntax

asm volatile (
    "movl %1, %%eax\n\t"  // Move parameter 1 to eax register
    "addl %2, %%eax\n\t"  // eax += parameter 2
    "movl %%eax, %0\n\t"  // Store result back to parameter 0
    : "=r"(result)        // Output operand
    : "r"(a), "r"(b)      // Input operands
    : "%eax"              // Modified register
);

asm volatile (
    "movl %1, %%eax\n\t"  // Move parameter 1 to eax register
    "addl %2, %%eax\n\t"  // eax += parameter 2
    "movl %%eax, %0\n\t"  // Store result back to parameter 0
    : "=r"(result)        // Output operand
    : "r"(a), "r"(b)      // Input operands
    : "%eax"              // Modified register
);

Constraint Specifiers

Constraint	Meaning
r	Any general-purpose register
m	Memory address
i	Immediate value
=	Output operand
+	Read-write operand

Practical Example: Fast Inverse Square Root

float fast_inverse_sqrt(float x) {
    float xhalf = 0.5f * x;
    int i = *(int*)&x;                       // Interpret float as int
    i = 0x5f3759df - (i >> 1);               // Magic number
    x = *(float*)&i;                         // Interpret int back as float
    x = x * (1.5f - xhalf * x * x);          // Newton iteration
    return x;
}

float fast_inverse_sqrt(float x) {
    float xhalf = 0.5f * x;
    int i = *(int*)&x;                       // Interpret float as int
    i = 0x5f3759df - (i >> 1);               // Magic number
    x = *(float*)&i;                         // Interpret int back as float
    x = x * (1.5f - xhalf * x * x);          // Newton iteration
    return x;
}

Notes

Destructive registers must be listed
Inline assembly may disrupt optimization
Poor portability
Modern compilers usually generate better code

Compilation Optimization Options

Common Optimization Levels

Option	Description
-O0	No optimization (debug-friendly)
-O1	Basic optimization (dead code elimination, etc.)
-O2	Moderate optimization (default recommended)
-O3	Aggressive optimization (loop unrolling, vectorization, etc.)
-Os	Optimize for code size
-Ofast	Ignore strict standards (more aggressive optimization)

Link-Time Optimization (LTO)

gcc -flto -O2 -c file1.c file2.c
gcc -flto -O2 file1.o file2.o -o program

gcc -flto -O2 -c file1.c file2.c
gcc -flto -O2 file1.o file2.o -o program

LTO advantages:

Cross-file optimization
Better inlining decisions
Global code layout optimization

Specific Optimization Options

Option	Description
-funroll-loops	Loop unrolling
-ftree-vectorize	Automatic vectorization
-fprefetch-loop-arrays	Prefetch loop arrays
-fomit-frame-pointer	Omit frame pointer (reduce register pressure)
-fno-exceptions	Disable exceptions (reduce code size)

Comprehensive Optimization Case

High-Performance Matrix Multiplication

// Naive implementation
void matmul(float* A, float* B, float* C, int N) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            float sum = 0;
            for (int k = 0; k < N; k++) {
                sum += A[i*N + k] * B[k*N + j];
            }
            C[i*N + j] = sum;
        }
    }
}

// Optimized version
void matmul_optimized(float* A, float* B, float* C, int N) {
    #pragma omp parallel for collapse(2)  // OpenMP parallelization
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            float sum = 0;
            // Loop unrolling
            for (int k = 0; k < N; k += 4) {
                sum += A[i*N + k] * B[k*N + j];
                sum += A[i*N + k+1] * B[(k+1)*N + j];
                sum += A[i*N + k+2] * B[(k+2)*N + j];
                sum += A[i*N + k+3] * B[(k+3)*N + j];
            }
            C[i*N + j] = sum;
        }
    }
}

// Naive implementation
void matmul(float* A, float* B, float* C, int N) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            float sum = 0;
            for (int k = 0; k < N; k++) {
                sum += A[i*N + k] * B[k*N + j];
            }
            C[i*N + j] = sum;
        }
    }
}

// Optimized version
void matmul_optimized(float* A, float* B, float* C, int N) {
    #pragma omp parallel for collapse(2)  // OpenMP parallelization
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            float sum = 0;
            // Loop unrolling
            for (int k = 0; k < N; k += 4) {
                sum += A[i*N + k] * B[k*N + j];
                sum += A[i*N + k+1] * B[(k+1)*N + j];
                sum += A[i*N + k+2] * B[(k+2)*N + j];
                sum += A[i*N + k+3] * B[(k+3)*N + j];
            }
            C[i*N + j] = sum;
        }
    }
}

Compilation Command

gcc -O3 -march=native -funroll-loops -ftree-vectorize -fopenmp matmul.c -o matmul

gcc -O3 -march=native -funroll-loops -ftree-vectorize -fopenmp matmul.c -o matmul

Performance Optimization Principles

Measure First: Measure before optimizing
Local Optimization: Optimize hot code first
Balance Trade-offs: Trade-offs between speed, memory, and readability
Portability: Consider differences across hardware platforms
Continuous Monitoring: Monitor performance changes after optimization

By reasonably combining these techniques and tools, the performance of C programs can be significantly improved. In practical applications, appropriate optimization strategies should be selected based on specific scenarios, and the optimization effects should be verified using performance analysis tools.

Course: Mastering C Programming From Basics to Advanced Techniques