Code Optimization

Reducing Code Motion

When we write code, we want to be cognizant of code motion — how often a computation is performed. The most common example is recomputing constant values over and over again inside a loop. For example, consider the following code:

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];
	}
}

Here, the value n * i is computed over and over again within the loop, when it doesn't have to be. What we can instead do is initialize this as a value outside the loop:

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

Reducing Costly Operations

Another area for optimization is replacing costly operations with simpler ones. For example, addition, multiplication, and division can often be replaced with bitshifts. For example, instead of computing:

int y = 2;
int x = 16 * y;

a less expensive computation would be:

int y = 2;
int x = y << 4;

Of course, how useful this is depends on the cost of the multiply or divide instructions on the machine. Modern machines tend to use less CPU cycles for these operations, leading to low cost savings from using the bit shift approach.

Sharing Common Subexpressions

It's often the case that a program's expressions follow a general form. For example, consider the following code for navigating through a matrix:

up   = val[ (i-1)*n + j   ];
down = val[ (i+1)*n + j   ];
down = val[ (i*n)   + j-1 ];
down = val[ (i*n)   + j+1 ];

sum = up + down + left + right;

Examining the code above, there are three unique multiplication expressions that must be computed. With just some algebraic manipulation, we can reduce that number to 1:

long inj = i*n + j
up   = val[ inj - n ];
down = val[ inj + n ];
down = val[ inj - 1 ];
down = val[ inj + 1 ];

sum = up + down + left + right;

Limitations on Compiler Optimization

As much as compilers have gotten smarter, there's a rule that even compilers today won't cross: The compiler must not change the program's behavior. This stems from the fact that the compiler's core task is to translate the programmer's high-level source code into some lower-level language, be that Assembly or bytecode. Because of this rule, compilers will not perform their optimizations if they find that it would lead to different program behavior.

There is, however, one exception to the rule: If the program uses nonstandard language features (also called language extensions), the compiler is free to make the decisions necessary to translating the program. This exception exists to ensure compiler writers aren't burdened with accomodating every possible language feature (otherwise we'd have very few, if any, compiler writers).

Language features are usually provided by some compiler for the language. For example, the GCC compiler extends C by allowing programmers to give branch likelihoods. This effectively provides hints to the compiler:

#define likely(x)    __builtin_expect((x), 1)
#define unlikely(x)  __builtin_expect((x), 0)

void f(int arg) {
	if (unlikely(arg == 0)) {
		call_this_function();
		return;
	} else {
		call_that_function();
	}
}

This feature, however, will not work with other compilers — e.g., clang.

Additionally, there are limitations on how far a compiler will optimize code. First, for most compilers today, optimization analysis is limited to procedures. An analysis of the entire program would be far too expensive. Some compilers go a bit further, like GCC. GCC will perform its optimization analyses based on its read of an entire file, but not be comparing code in different files.

Second, much of the analysis is limited to static data. Currently, it's diffcult to write compilers that can predict runtime inputs.

Instruction-level Parallelism

Roughly, the modern CPU can be viewed as follows:

At any given moment, different parts of the processor may be working at the same time. For example, as operation bits are sent to the functional units, addresses are being sent to the instruction cache, and operation results are being sent to the retirement unit. This phenomenon is called parallelism.

Parallelism has its limits. Ultimately, it depends on how many functional units the processor has. For example, the schematic above shows a processor with three arithmetic units. Because each of these units have the same purpose — performing arithmetic — we can perform three different arithmetic operations at the same time. Alongside the load, store, and branch units, we can perform loading and arithmetic at the same time, branching and storing at the same time, branching, storing, loading, and arithmetic at the same time, and so on.

Let's consider an example. Say we had the following C code:

typedef struct {
	size_t length;
	int *data;
} Vector;

/**
 * Gets a vector element and stores it in the pointer val
 **/
int get_vector_element(Vector *v, size_t idx, int *val) {
	if (idx >= v->length) {
		return 0;
	}
	*val = v->data[idx];
	return 1;
}
/**
 * Creates a instance of a vector
 **/
Vector *newVector(size_t length, int *arr) {
	Vector *v = (Vector*)malloc(sizeof(Vector));
	v->length = length;
	v->data = (int*)malloc(sizeof(int)*length);
	size_t i;
	for (i = 0; i < length; i++) {
		v->data[i] = arr[i];
	}
	return v;
}
/**
 * Returns the vector length
 **/
size_t get_vector_length(Vector *v) {
	return v->length;
}
/**
 * Prints the vector
 **/
void print_vector(Vector *v) {
	long i;
	for (i = 0; i < get_vector_length(v); i++) {
		int val;
		get_vector_element(v, i, &val);
		printf("%d", val);
	}
}
/**
 * Sums all of the vector's elements
 **/
void sum_vector_element(Vector *v, int *destination) {
	long int i;
	*destination = 0;
	for (i = 0; i < get_vector_length(v); i++) {
		int val;
		get_vector_element(v, i, &val);
		*destination = *destination + val;
	}
}

int main() {
	Vector *v = newVector(5, (int[]){1,2,3,4,5});
	int result = 0;
	sum_vector_element(v, &result);
	printf("result=%d\n", result);
}
/**
 * Note: The syntax (int[]){1,2,3,4,5}
 * is called compound literal syntax.
 * It allows us to pass an array argument
 * without having to first initialize
 * it in the stack then passing a pointer
 **/

15

The key functions to focus on are sum_vector_element() and get_vector_element(). For the sum_vector_element() function, the time (𝑇) it takes to execute the function is given by the equation:

where ${\cal{C}}$ is the number of cycles per element and ${\cal{O}}$ is the overhead. ${\cal{C}}$ can be determined by recording the function's execution time with an increasing number of elements.¹ The slope of the best fit line is ${\cal{C}.}$ For example, if the slope of the line is 9.0, then it takes roughly 9 CPU cycles to execute the function for ${n}$ elements.

Running the code above with different data types (rewriting the code above as needed) we get the following data (numeric values is the time 𝑇):

The optimizations made:

1. Move the get_vector_length() call outside the loop.
2. Avoid a bounds check on each cycle.
3. Accumulate the sum/product in a temporary variable.

Thus, for the sum_vector_element() function, the optimized code appears as follows:

void sum_vector_element(Vector *v, int *destination) {
	long i;
	long length = get_vector_length(v);
	int t = 0;
	int *d = v->data;
	for (i = 0; i < length; i++) {
		t = t + d[i];
	}
	*destination = t;
}

The CPU cycle savings are drastic because the x86-64 is a superscalar processor — a processor that can issue and execute multiple instructions in one cycle. This is done by the processor retrieving instructions from the instruction stream, and then scheduling them dynamically.

Branches

For branches, the general rule of thumb is: Avoid unpredictable branches whenever possible. Modern processors maintain a branch table that let's them predict where the program is headed next, but all of that goes out the window when we have a branch that requires the processor to unravel all of the work it's done before. We can help the processor by providing the branch's test conditions well ahead of time. For example, consider the this function that decodes a hex digit:

int hex_digit_to_decimal(unsigned char c) {
  if (c >= '0' && c <= '9') return c - '0';
  if (c >= 'A' && c <= 'F') return c - 'A' + 10;
  if (c >= 'a' && c <= 'f') return c - 'a' + 10;
  return -1;
}

The first optimization we can make is to use else if and else branches. Otherwise, all of the branches must be evaluated:

int hex_digit_to_decimal(unsigned char c) {
  if (c >= '0' && c <= '9') return c - '0';
  else if (c >= 'A' && c <= 'F') return c - 'A' + 10;
  else if (c >= 'a' && c <= 'f') return c - 'a' + 10;
  else return -1;
}

The second optimization we can make is to replace the characters with the numeric ASCII values (assuming there are other checks to ensure that only ASCII-encoded characters are provided):

int hex_digit_to_decimal(unsigned char c) {
  if (c >= 48 && c <= 57) return c - 48;
  else if (c >= 65 && c <= 70) return c - 65 + 10;
  else if (c >= 97 && c <= 102) return c - 97 + 10;
  else return -1;
}

The third optimization we cane make is to move the exit case to the top (we want to exit as soon as possible):

int hex_digit_to_decimal(unsigned char c) {
	if (c < 48 && c > 102) return -1;
  else if (c >= 48 && c <= 57) return c - 48;
  else if (c >= 65 && c <= 70) return c - 65 + 10;
  else return c - 97 + 10;
}

Again, all of this is assuming that security measures are in place, and that the argument passed is ASCII encoded.

The ultimate optimization to branching, however, is to not branch at all. This sounds silly, but it's a valid consideration that's often neglected. There are cases where branching can be replaced by either (1) replacing the branch structure with a hardcode data structure, or (2) using a ternary operator instead of an if-else structure.

For example, these two operations are applicable to the hex_digit_to_decimal() function we wrote. Instead of using a branching structure, we can construct a lookup table and use a ternary operator (most compilers will translate this into a negation followed by a right-shift):

int hex_digit_to_decimal(unsigned char c) {
	int ASCIIHexToInt[] ={
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1,
		-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	};
	int result = ASCIIHexToInt[c];
	return (result >= 0 ? result : -1);
}