Software Optimization Techniques #15: Removing Code From the Worst-Case Path

Continuing the series of blog posts on optimizing embedded software with the aim of improving (i.e. reducing) worst-case execution times, this week’s topic is removing code from the worst-case path.

Software optimization techniques which improve worst-case execution times #15: Removing Code From the Worst-Case Path

A useful approach to take when attempting to minimise the worst-case execution time is to review the code on the worst-case path, asking whether all the code found on that path implements functionality that is essential or whether some of it could be carried out elsewhere.

There are two commonly used constructs that can lead to unnecessary code appearing on the worst-case path. These are if…else if…else and switch statements.

Example: if-else if-else

if(length == 0)
	{
		/* process empty message */
	}
	else if(length < 50)
	{
		/* process short message */
	}
	else if(length < 100)
	{
		/* process medium message */
	}
	else
	{
		/* process long message */
		/* worst-case path */
	}

Consider the code in the example above. Let us assume that the worst-case execution time of the code has been analysed and that the code in the final else branch, used to process long messages, is on the worst-case path. To reach the final else branch, each of the three conditions needs to be evaluated. However this is unnecessary. The code could be reordered so that the first condition evaluated is (length >= 100) as shown below. Although the re-ordered code implements exactly the same functionality, the evaluation of two conditions has been removed from the worst-case path. Note that this optimisation could be the exact opposite of optimising for best average-case behaviour; for example if empty messages are the most common.

Example: Re-ordered conditions

if(length >= 100)
	{
		/* process long message */
		/* shorter worst-case path */
	}
	else if(length >= 50)
	{
		/* process medium message */
	}
	else if(length > 0)
	{
		/* process short message */
	}
	else
	{
		/* process empty message */
	}

Switch statements are often expanded by the compiler into what is effectively a long series of if…else if…else constructs. Here, the same style of optimisation can be applied. The case branch that is on the worst-case path should be placed first in the switch statement. It is wise to check the compiler documentation or assembler code produced to determine how switch statements are implemented and to ensure that the order in which the cases are implemented is as expected.

Next week: Removing average case optimizations