C Speed Optimizations

speed_optimizations.md

C Speed Optimization Checklist

This is a list of general-purpose optimizations for C programs, from the most impactful to the tiniest low-level micro-optimizations to squeeze out every last bit of performance. It is meant to be read top-down as a checklist, with each item being a potential optimization to consider. Everything is in order of speed gain.

Algorithm && Data Structures

Choose the best algorithm and data structure for the problem at hand by evaluating:

1. time complexity
2. space complexity
3. maintainability

Precomputation

Precompute values that are known at compile time using:

1. constexpr
2. sizeof()
3. lookup tables
4. __attribute__((constructor))

Parallelization

Find tasks that can be split into smaller ones and run in parallel with:

Technique	Pros	Cons
SIMD	lightweight, fast	limited application, portability
Async I/O	lightweight, zero waste of resources	only for I/O-bound tasks
SWAR	lightweight, fast, portable	limited application, small chunks
Multithreading	relatively lightweight, versatile	data races, corruption
Multiprocessing	isolation, true parallelism	heavyweight, isolation

Zero-copy

Optimize memory access, duplication and stack size by using zero-copy techniques:

1. pointers: avoid passing large data structures by value, pass pointers instead
2. one for all: avoid passing multiple pointers of the same structure separately, pass a single pointer to a structure that contains them all
3. memory-mapped I/O: avoid copying data from a file to memory, directly map the file to memory instead
4. scatter-gather I/O: avoid copying data from multiple sources to a single destination, directly read/write from/to multiple sources/destinations instead
5. dereferencing: avoid dereferencing pointers multiple times, store the dereferenced value in a variable and reuse that instead

Memory Allocation

Prioritize stack allocation for small data structures, and heap allocation for large data structures:

Alloc Type	Pros	Cons
Stack	Zero management overhead, fast, close to CPU cache	Limited size, scope-bound
Heap	Persistent, large allocations	Higher latency (malloc/free overhead), fragmentation, memory leaks

Function Calls

Reduce the overall number of function calls:

1. System Functions: make fewer system calls as possible
2. Library Functions: make fewer library calls as possible (unless linked statically)
3. Recursive Functions: avoid recursion, use loops instead (unless tail-optmized)
4. Inline Functions: inline small functions

Compiler Flags

Add compiler flags to automatically optimize the code, consider the side effects of each flag:

1. -O3: general optimization
2. -ffast-math: floating point optimizations
3. -march=native: optimize for the current CPU
4. -funroll-all-loops: unroll loops
5. -fomit-frame-pointer: don't save the frame pointer
6. -fno-stack-protector: disable stack protection
7. -flto: link-time optimization

Branching

Minimize branching:

1. Most Likely First: order if-else chains by most likely scenario first
2. Switch: use switch statements or jump tables instead of if-else forests
3. Sacrifice Short-Circuiting: don't immediately return if that implies using two separate if statements in the most likely scenario
4. Combine if statements: combine multiple if statements into a single one, sacrificing short-circuiting if necessary
5. Masks: use bitwise & and | instead of && and ||

Aligned Memory Access

Use aligned memory access:

1. __attribute__((aligned())): align stack variables
2. posix_memalign(): align heap variables
3. _mm_load and _mm_store: aligned SIMD memory access

Compiler Hints

Guide the compiler at optimizing hot paths:

1. __attribute__((hot)): frequently called functions
2. __attribute__((cold)): rarely called functions
3. __builtin_expect(): most likely outcome of a conditional
4. __builtin_assume_aligned(): aligned memory access
5. unreachable(): a certain path is unreachable (Don't Care)
6. restrict: two pointers don't overlap
7. const: a variable is constant