A1 - efficiency

• efficient optimised code is often:

  • less readable
  • less modular
  • longer

• therefore, there is a trade-off between speed vs maintainability

• compilers perform some optimisation

> gcc -0 my_prog.exe my_code.c -o{x}

• -o0: no optimisation

• -o1: eliminate redundant code, unroll loops, remove invariants from loops

• -o2: unroll nested loops, reorder operations to prevent pipeline stalls, etc

• o3: array padding, function in-lining, loop reordering, etc

• there are many other compiler-dependent flags controlling vectorisation or optimisation for specific target architectures

• CPU only understands a few basic operations such as: load, store, add, multiply, shift, compare

• these can usually be executed in a single CPU cycle

• modern CPUs can perform multiple Fused Multiply-Add (FMA) operations per cycle

• other operations such as divide, sqrt, log, exp, power, sin, cos, must be implemented with microcode, which is a sequence of operations stored in the CPU firmware

• eg: a divide operation can take 30-100 CPU cycles

• avoiding microcode:

  • y=0.5*x instead of y = x/2.0
  • y=x*x*xinstead of y = pow(x,3) or y = x**3

• loop optimisation:

for (i = 0; i < N; i++) {
	x[i] = 2.0 * p * (float) i / k1;
	y[i] = 2.0 * p * (float) i / k2;
}

// remove repetition of 2 * p * i (compiler will do this)
for (i = 0; i < N; i++) {
	t1 = 2.0 * p * (float) i;
	x[i] = t1 / k1;
	y[i] = t1 / k2;
}

// remove invariant from the loop (compiler should do this)
t2 = 2.0 * p;
for (i = 0; i < N; i++) {
	t1 = t1 * (float) i;
	x[i] = t1 / k1;
	y[i] = t1 / k2;
}

// store k1 and k2 as inverse (compiler might do this)
t1 = 2.0 * p / k1;
t2 = 2.0 * p / k2;
for (i = 0; i < N; i++) {
	x[i] = t1 * (float) i;
	y[i] = t2 * (float) i;
}

• compiler cannot perform algebra:

for (i = 0; i < N; i++) {
	E[i] = A[i] / B[i] + C[i] / D[i];
}
// 2 divides and 1 add per iteration

for (i = 0; i < N; i++) {
	t1 = 1.0 / (B[i] * D[i]);
	E[i] = t1 * (A[i] * D[i] + C[i] * B[i] ) ;
}
// 1 divide, 4 multiplies and 1 add per iteration

• note that results may differ slightly due to floating point representation