Program Optimization

Performance Realities

There's more to performance than asymptotic complexity

Constant factors matter

• You can see a 10:1 performance range depending on how code is written.
• Many levels that can be optimized: algorithm, data representation, procedures, and loops.

Understand the system to optimize performance

• How are programs compiled and executed.
• How modern processors + memory systems operate
• How to measure program performance and identify bottlenecks
• How to improve performance without destroying code modularity and generality

Optimizing Compilers

• Provide efficient mapping of program to machine

  • register allocation
  • code selection and ordering (scheduling)
  • dead code elimination
  • eliminating minor inefficiencies

• Don’t (usually) improve asymptotic efficiency

  • up to programmer to select best overall algorithm
  • big-O savings are (often) more important than constant factors but constant factors also matter

• Have difficulty overcoming “optimization blockers”

  • potential memory aliasing
  • potential procedure side-effects

Limitations of Optimizing Compilers

• Operate under fundamental constraint

  • Must not cause any change in program behavior. Except, possibly when program making use of nonstandard language features
  • Often prevents it from making optimizations that would only affect behavior under pathological conditions.

• Behavior that may be obvious to the programmer can be obfuscated by languages and coding styles

  • e.g., Data ranges may be more limited than variable types suggest

• Most analysis is performed only within procedures

  • Whole-program analysis is too expensive in most cases
  • Newer versions of GCC do interprocedural analysis within individual files. But, not between code in different files

• Most analysis is based only on static information

  • Compiler has difficulty anticipating run-time inputs

• When in doubt, the compiler must be conservative

Useful Optimizations

These are optimizations that you or the compiler should do regardless of processor/compiler

Code Motion: Reduce frequency with which computation performed.

• Reduce if it will always produce the same result
• Especially moving code out of the loop.

For example:

// BEFORE
void set_row(double *a, double *b, long i, long n) {  
	long j;
    for (j = 0; j < n; j++)
    a[n*i+j] = b[j];
}

// AFTER
long j;  
int ni = n*i;  
for (j = 0; j < n; j++)
	a[ni+j] = b[j];

• We the multiplication n*i*j outside of the loop because it will always produce the same results. Multiplication is expensive.

Strength Reduction: replace costly operations with simpler ones.

• Shift or add instead of multiply and divide.
  • E.g., 16*x --> x << 4
  • Note: this is utility machine dependent. It depends on the cost of the multiply or divide instruction. E.g., On Intel Nahelem, integer multiply requires 3 CPU cycles.
• Recognize sequence of products

For example:

// BEFORE
for (i = 0; i < n; i++) {
	int ni = n*i;
	for (j = 0; j < n; j++)
	    a[ni + j] = b[j];
}

// AFTER

int ni = 0;
for (i = 0; i < n; i++) {
	for (j = 0; j < n; j++)
		a[ni + j] = b[j];
	ni += n;
}

• We do ni += n on each loop instead of multiplying n * i

Share common subexpressions: reuse portions of expression.

• GCC does this with -O1. If the compiler does this automatically, then you don't have to do it for the sake of readibility.

For example:

/* Sum neighbors of i,j */

// BEFORE
up =    val[(i-1)*n + j  ];
down =  val[(i+1)*n + j  ];
left =  val[i*n     + j-1];
right = val[i*n     + j+1];
sum = up + down + left + right;

// AFTER
long inj = i*n + j;
up =    val[inj - n];
down =  val[inj + n];
left =  val[inj - 1];
right = val[inj + 1];
sum = up + down + left + right;

• We went from 3 multiplications (i*n, (i–1)*n, (i+1)*n) to 1 multiplications (i*n)

Optimization Blocker

Procedure Calls For example: converting string to lower case:

void lower(char *s) {
	size_t i;
	for (i = 0; i < strlen(s); i++)
	    if (s[i] >= 'A' && s[i] <= 'Z')
			s[i] -= ('A' - 'a');
}

• This has quadratic performance

However, if we convert loop to GoTo Form, strlen is executed at every iteration:

void lower(char *s) {
	size_t i = 0;
	if (i >= strlen(s))
		goto done;
	loop:
		if (s[i] >= 'A' && s[i] <= 'Z')
			s[i] -= ('A' - 'a');
			
		i++;
		if (i < strlen(s))
			goto loop;
	done:
}

• strlen performance is to scan its entire length looking for a null character.
• The overall performance of a string of length N would O(N^2) because you make N calls to strlen

To improve this, we can move call to strlen outside of loop.

• This is a form of code motion.
• Now there is a linear performance of this optimized lower function

The compiler didn't move strlen outside fo the inner loop because the procedure can have side effects (the global state is altered each time its called) and the function may not return the same value for the given arguments (depends on the other parts of the global state since lower could interact with strlen).

• The compiler treats procedure calls as a black box so they don't optimize them a lot.
• Remedies: use inline functions (GCC does this with -O1 within a signle file) or do your own code motion.

Memory Aliasing Aliasing is when two memory references specify a single location.

• This is easy to have happen in C since we are allowed to do address arithmetic and we have direct access to storage structures.

Get in a habit of introducing local variables

• accumulating within loops
• your way of telling the compiler to not check for aliasing.

Exploiting Instruction-Level Parallelism

• Need general understanding of modern processor design: hardware can execute multiple instructions in parallel.
• Performance limited by data dependencies
• Simple transformations can yield dramatic performance improvement
  • Compilers often cannot make these transformations
  • Lack of associativity and distributivity in floating-point arithmetic

Express performance of program that operates on vectors or list through Cycles Per Elements (CPE)