19.6. Control Structures and Complexity

One reason so much attention has been paid to control structures is that they are a big contributor to overall program complexity. Poor use of control structures increases complexity; good use decreases it.

One measure of "programming complexity" is the number of mental objects you have to keep in mind simultaneously in order to understand a program. This mental juggling act is one of the most difficult aspects of programming and is the reason programming requires more concentration than other activities. It's the reason programmers get upset about "quick interruptions" such interruptions are tantamount to asking a juggler to keep three balls in the air and hold your groceries at the same time.

Make things as simple as possible but no simpler.

Albert Einstein

Intuitively, the complexity of a program would seem to largely determine the amount of effort required to understand it. Tom McCabe published an influential paper arguing that a program's complexity is defined by its control flow (1976). Other researchers have identified factors other than McCabe's cyclomatic complexity metric (such as the number of variables used in a routine), but they agree that control flow is at least one of the largest contributors to complexity, if not the largest.

How Important Is Complexity?

Computer-science researchers have been aware of the importance of complexity for at least two decades. Many years ago, Edsger Dijkstra cautioned against the hazards of complexity: "The competent programmer is fully aware of the strictly limited size of his own skull; therefore, he approaches the programming task in full humility" (Dijkstra 1972). This does not imply that you should increase the capacity of your skull to deal with enormous complexity. It implies that you can never deal with enormous complexity and must take steps to reduce it wherever possible.

Cross-Reference

For more on complexity, see "Software's Primary Technical Imperative: Managing Complexity" in Section 5.2.

Control-flow complexity is important because it has been correlated with low reliability and frequent errors (McCabe 1976, Shen et al. 1985). William T. Ward reported a significant gain in software reliability resulting from using McCabe's complexity metric at Hewlett-Packard (1989b). McCabe's metric was used on one 77,000-line program to identify problem areas. The program had a post-release defect rate of 0.31 defects per thousand lines of code. A 125,000-line program had a post-release defect rate of 0.02 defects per thousand lines of code. Ward reported that because of their lower complexity, both programs had substantially fewer defects than other programs at Hewlett-Packard. My own company, Construx Software, has experienced similar results using complexity measures to identify problematic routines in the 2000s.

General Guidelines for Reducing Complexity

You can better deal with complexity in one of two ways. First, you can improve your own mental juggling abilities by doing mental exercises. But programming itself is usually enough exercise, and people seem to have trouble juggling more than about five to nine mental entities (Miller 1956). The potential for improvement is small. Second, you can decrease the complexity of your programs and the amount of concentration required to understand them.

How to Measure Complexity

You probably have an intuitive feel for what makes a routine more or less complex. Researchers have tried to formalize their intuitive feelings and have come up with several ways of measuring complexity. Perhaps the most influential of the numeric techniques is Tom McCabe's, in which complexity is measured by counting the number of "decision points" in a routine. Table 19-2 describes a method for counting decision points.

1. Start with 1 for the straight path through the routine.

2. 2. Add 1 for each of the following keywords, or their equivalents: if while repeat for and or

3. 3. Add 1 for each case in a case statement.

Further Reading

The approach described here is based on Tom McCabe's influential paper "A Complexity Measure" (1976).

Here's an example:

if ( ( (status = Success) and done ) or      ( not done and ( numLines >= maxLines ) ) ) then ...

In this fragment, you count 1 to start, 2 for the if, 3 for the and, 4 for the or, and 5 for the and. Thus, this fragment contains a total of five decision points.

What to Do with Your Complexity Measurement

After you have counted the decision points, you can use the number to analyze your routine's complexity:

0 5	The routine is probably fine.
6 10	Start to think about ways to simplify the routine.
10+	Break part of the routine into a second routine and call it from the first routine.

Moving part of a routine into another routine doesn't reduce the overall complexity of the program; it just moves the decision points around. But it reduces the amount of complexity you have to deal with at any one time. Since the important goal is to minimize the number of items you have to juggle mentally, reducing the complexity of a given routine is worthwhile.

The maximum of 10 decision points isn't an absolute limit. Use the number of decision points as a warning flag that indicates a routine might need to be redesigned. Don't use it as an inflexible rule. A case statement with many cases could be more than 10 elements long, and, depending on the purpose of the case statement, it might be foolish to break it up.

Other Kinds of Complexity

The McCabe measure of complexity isn't the only sound measure, but it's the measure most discussed in computing literature and it's especially helpful when you're thinking about control flow. Other measures include the amount of data used, the number of nesting levels in control constructs, the number of lines of code, the number of lines between successive references to variables ("span"), the number of lines that a variable is in use ("live time"), and the amount of input and output. Some researchers have developed composite metrics based on combinations of these simpler ones.

Further Reading

For an excellent discussion of complexity metrics, see Software Engineering Metrics and Models (Conte, Dunsmore, and Shen 1986).

cc2e.com/1985

Checklist: Control-Structure Issues

• Do expressions use true and false rather than 1 and 0?

• Are boolean values compared to true and false implicitly?

• Are numeric values compared to their test values explicitly?

• Have expressions been simplified by the addition of new boolean variables and the use of boolean functions and decision tables?

• Are boolean expressions stated positively?

• Do pairs of braces balance?

• Are braces used everywhere they're needed for clarity?

• Are logical expressions fully parenthesized?

• Have tests been written in number-line order?

• Do Java tests uses a.equals(b) style instead of a == b when appropriate?

• Are null statements obvious?

• Have nested statements been simplified by retesting part of the conditional, converting to if-then-else or case statements, moving nested code into its own routine, converting to a more object-oriented design, or have they been improved in some other way?

• If a routine has a decision count of more than 10, is there a good reason for not redesigning it?