Software Optimization Techniques #16: Removing Average Case Optimizations

Our series of blog posts on optimizing embedded software with the aim of improving (i.e. reducing) worst-case execution times continues with a look at removing average case optimizations.

Software optimization techniques which improve worst-case execution times #16: Removing Average Case Optimizations

Probably the most common reason why unnecessary code is found on the worst-case path is an application written with good average case performance in mind.

The following example illustrates how code that shortcuts loop iteration to obtain a faster average case execution time makes the worst-case longer.

In the ripple sort example below, the nested for loops sort the contents of the array a[] into order, smallest value first. On each iteration of the outer loop, if no elements have been swapped, then the array is sorted and the loop can exit early. This implementation has reasonable average case behaviour, for example, given a sorted array the inner loop iterates only once. However, with the worst-case arrangement of data, setting and checking the sorted variable is superfluous and only adds to the worst-case execution time.

Example: Ripple sort

void
ripple_sort1(Uint32 *a,
	Uint32 length)
{
	Uint32 i,j,k, tmp;
	Uint8 sorted;

	for(i = length - 1; i>0; i--)
	{
		sorted = TRUE;
		for(j=0; j<i; j++)
		{
			k = j+1;
			if(a[j] > a[k])
			{
				tmp = a[k];
				a[k] = a[j];
				a[j] = tmp;
				sorted = FALSE;
			}
		}
		if(sorted)
		{
			break;
		}
	}
}

The worst-case execution time of the two ripple sort implementations are given in the table below. The worst-case execution times assume a maximum length of 10 for the array.

Next week: Repositioning code and state machines