MDAY@XX.LCS.MIT.EDU (Moderator, Mark S. Day) (01/11/88)
Soft-Eng Digest Sun, 10 Jan 88 Volume 4 : Issue 2
Today's Topics:
---SPECIAL ISSUE ON PROGRAM COMPLEXITY METRICS---
Program Complexity Metrics (10 msgs)
Summary of Metrics Responses
Examples: Optimizing Complexity Reduces Code Quality (2 msgs)
----------------------------------------------------------------------
Date: 10 Dec 87 15:35:01 GMT
From: ndsuvax!ncmagel@uunet.uu.net (ken magel)
Subject: Program Complexity Metrics
Does anyone actually use program complexity metrics for practical
work? I am interested in how companies actually use complexity metrics
ranging from lines of code to cyclomatic complexity to software science to
the many other metrics which have been proposed. Today one get get either
public domain or as a commercial product programs which will compute and
report several different metrics. Are these actually used?
If you do not use program complexity metrics, what sort of proof, evidence
or demonstrations would your company need to cause you to consider using
them? What kinds of payoffs do they have to have and how would those payoffs
be established to your satisfaction?
I am particularly interested in answers to the second paragraph of
questions.
Thank you.
------------------------------
Date: 14 Dec 87 00:35:24 GMT
From: munnari!mulga!ditmela!latcs1!ken@uunet.uu.net (Ken Lew)
Subject: Program Complexity Metrics [what are metrics?]
[...]
Program complexity metric is used to indicate the "quality" of a program by
measuring certain characteristics such as program size, number of
decision statements, information flow, etc.
For example, McCabe's cyclomatic number measures the number of
independent paths in a program and is related to the number of decision
statements. McCabe has used the metric to control the number of paths in a
program module to increase the program test coverage.
Although non of the complexity metrics has been validated, some empirical
studies have found them useful in software development.
For reference, read: Software Metrics: An analysis and evaluation,
ed. A. Perlis et. al., MIT, 1981
ken@latcs1
------------------------------
Date: 14 Dec 87 17:15:02 GMT
From: ihnp4!homxb!whuts!mtune!petsd!pedsga!chip@ucbvax.Berkeley.EDU
Subject: Program Complexity Metrics [what are metrics?]
According to my textbook: Software Enginneering, by Shooman, McGraw-Hill,
complexity metrics serve the following purposes:
1. As a rank of the difficulty of various software modules to be used along
with other factors in the assignment of personnel
2. In the case of module complexity, as a guide to judge whether subdivision
of a complex module is warrented
3. As a direct measure of progress and an indirect measure of quality during
the various phases of development.
4. As an aid in normalizing data used in retrospective studies of past
development projects.
Personally, I feel that the second use is of most value.
The general idea is to be able to apply formulas to software (either as a
whole or individually to modules) to determine the "quality" of the software.
One of the more famous complexity metrics papers was written by Thomas McCabe
(IEEE Transactions on Software Engineering, 12/76 pp 308-320) in which he
describes his graph-theoretic complexity measure. His approach is that
the more paths there is in a given module, the more complex it is (seems
simple enough). The formula will produce a complexity value for a module.
His conclusion is that modules with complexity values over 10 will have
a tendency to have more errors (I guess the programmer can't track
all possible paths). By breaking the module up into smaller modules, you
reduce the chance for inherent code errors. Putting it simply, the formula
is as follows:
v = sum(branches, loops, case, conditions,...ANDs, ORs, NOTs) + 1
His studies showed that in several large projects, that 23% of the routines
with a value greater than 10 accounted for 53% of the bugs.
Metrics can provide a lot of insight to software quality. Unfortunately,
they are not viewed as a means of bringing software development out of
its "primitive state" (said in jest of course, see previous articles in
this newsgroup :-)
Hope this provides some insight to a relatively unknown topic.
--
Chip ("My grandmother called me Charles once. ONCE!!") Maurer
Concurrent Computer Corporation, Tinton Falls, NJ 07724 (201)758-7361
uucp: {mtune|purdue|rutgers|princeton|encore}!petsd!pedsga!chip
arpa: pedsga!chip@UXC.CSO.UIUC.EDU
------------------------------
Date: 18 Dec 87 11:12:47 GMT
From: mcvax!ukc!stc!datlog!dlhpedg!cl@uunet.uu.net (Charles Lambert)
Subject: Program Complexity Metrics [what are metrics?]
As the name implies, they are techniques to measure the complexity of
a (proposed) programming task; they estimate how laborious and difficult
it will be to implement. From an analysis of complexity, you can predict
several things (according to the advocates), for instance:
(i) how much the implementation will cost (in terms of effort);
(ii) the number of errors you can expect;
(iii) the number and type of test cases you will need;
(iv) how costly the system will be to maintain.
Ideally, you want to make these predictions as early in the development
as possible; however, my studies to date show that the current techniques
address the detailed Module Design best, the System Design less well and
the Functional Specification not at all.
In their excellent survey of software development techniques [1], Birrel
and Ould describe complexity measurements at the stages of System Design
and System Production (the latter being Module Design and Coding). For
System Design, they describe only one measurement that I would truly
call a complexity measurement: the "interconnectivity metric" of Kafura
and Henry [2]. In contrast, three measurements are described for the
Module Design: "McCabe's (cyclomatic) number [3]", "Halstead's E [4]" and
"control entropy". I quote, without permission.
On interconnectivity:
"[Kafura and Henry] describe it as follows. 'The first [phase]
involves generating a set of relations indicating the flow of
information through input parameters, output parameters, returned-
values functions and data structures. The second phase generates
an information-flow structure from these relations. The third
phase analyses the information-flow structure to determine the
derived calls, the local flows and the global flows'. A special
notation is used to record the result of the first analysis so
that automated tools can be used for the second and third phases.
The analysis can be carried out on any level of design or
production provided a precise enough description is available..."
On cyclomatic numbers:
"McCabe (1976) introduced the cyclomatic number of the control flow
graph of a program as a measure of program complexity. The
cyclomatic number of a graph counts the number of linearly
independent cycles in the graph and thus gives the number of basic
paths through the program.....
"Alternatively it can be shown that for structured programs the
cyclomatic number can be obtained by adding one to the number of
predicates in the program segment...
"The cyclomatic number has been shown to correlate quite well with
the number of errors found in the code and the programming time.
It can also clearly be used as an indicator of the number of test
cases that should be applied to a module to test all basic paths."
References
----------
[1] Birrell, N.D. and Ould, M.A; A Practical Handbook for Software Development.
Cambridge University Press. 1985. ISBN 0 521 25462 0
[2] Kafura, D. and Henry, S; "Software quality metrics based on
interconnectivity" in the Journal of Systems and Software, 2, 121-131.
1981.
[3] McCabe, T.J; "A complexity measure" in IEEE Transactions on Software
Engineering, SE-2, 308-320. 1976.
[4] Halstead, M; Elements of Software Science. Elsevier North-Holland,
New York. 1977.
------------------------------
Date: 17 Dec 87 12:49:01 GMT
From: phri!dasys1!samperi@nyu.edu (Dominick Samperi)
Subject: Program Complexity Metrics
If McCabe's cyclomatic complexity metric is essentially equal to the number of
decisions in a program module (IF's, AND, OR, etc.) plus 1, I don't see the
advantage in giving it a graph-theoretic interpretation. It is not equal to
the number of paths through a module, and it seems to be little more than the
number of forkings in a control graph (plus one). True, it can be computed
by counting nodes, edges, and components, but it is much easier to simply
count the number of forks and add 1, or to dispense with the control graph
altogether and simply count IF's, AND's, NOT's, etc. In Shooman's Software
Engineering text 'phantom paths' are added to a graph in order to compute
its cylomatic complexity. I don't see the point here at all (and the formula
used in this text, V(G) = e - n + p, will not work for graphs with p > 1;
must use V(G) = e - n + 2p).
--
Dominick Samperi, Manhattan College, New York, NY
...!ihnp4!cmcl2!manhat!samperi
...!ihnp4!cmcl2!phri!dasys1!samperi
------------------------------
Date: 18 Dec 87 14:26:39 GMT
From: uh2@psuvm.bitnet (Lee Sailer)
Subject: Program Complexity Metrics
This is an interesting topic. How would YOU "measure" the complexity
of a module? How can we "validate" the measures?
The <number of paths> thru a module doesn't impress me at all. A very simple
module constructed from a sequence of big CASE or SWITCH statements will have
many paths, but is easy to understand.
How 'bout a measure based on the *hierarchy* of Data Flow Diagrams? For
example, some modules might have a simple top level, with increasing
complexity as you break down each level. Another module might have a
complex top level, but the lower levels might be simple. Which is more
complex overall, the first or the second?
My *guess* is that the first is simpler, overall, on the principle that
it hides the complexity. Yet, it probably has more paths, more tokens, more
ifs, ands, and whiles (fewer gotos?).
The main point is that the COMPLEXITY of a module depends to some extent
on how detailed an understanding of the module you want or need.
lee
------------------------------
Date: 18 Dec 87 18:05:00 GMT
From: necntc!dandelion!ulowell!apollo!marc@husc6.harvard.edu (Marc Gibian)
Subject: Program Complexity Metrics
The current crop of complexity measures do NOT improve the code. There
is an excellent article in a past ACM Communications on this issue. The
conclusions of the acticle match the experiences of a major software
organization in Raytheon. I will take the liberty here to summarize
the ACM article since I forget the issue number. The basic conclusion of
the article is that no complexity measure currently exists that has been
designed specifically for the purpose for which it is being used by
software developers. Secondly, current complexity measures do not
validate when tested against these software development goals.
The application of complexity measures at Raytheon, required by almost
every software contract there, is usually accomplished by requiring that
every module (however a module is defined) has a set of complexity values
less than some arbitrary number. Unfortunately, the process of reducing
the measured complexity of a module most often decreased the quality of
the module, made it harder to maintain, harder to understand, and generally
did not accomplish the intended goal. I can provide specific examples if
anyone is interested.
I believe that a measure designed specifically to accomplish software
development goals, and validated against those goals, could be quite
helpful. In the meantime, I think it is very dangerous to use the
current instruments since they mislead management and customers into
believing they have a good means of measuring some aspects of their
software.
Marc S. Gibian
Software Engineer
Apollo Computer
email: marc@apollo.UUCP
------------------------------
Date: 22 Dec 87 17:35:57 GMT
From: ihnp4!homxb!mtuxo!mtune!petsd!pedsga!tom@ucbvax.Berkeley.EDU
Subject: Program Complexity Metrics
Marc states (very well) an important point, but I, for one, would like to
see some examples. The phrase "the process of reducing the measured
complexity" worries me a bit. The article Marc posted led me to beleive
that Raytheon has used the complexity formula to "reverse engineer" their
standard for software development. Just because their particular standard
resulted in "decreased quality", does not mean there isn't a standard that
results in a high level of quality PLUS a favorable complexity value.
I have used the term quality to refer to the original article:
maintainability, readability. It still makes sense that lower complexity
values would improve this quality. I'm not sure that Raytheon's bad
experience disproves this. It certainly bears further investigation.
------------------------------
Date: 24 Dec 87 19:26:04 GMT
From: littlei!ogcvax!pase@uunet.uu.net (Douglas M. Pase)
Subject: Program Complexity Metrics
In article <PSUVM.28001UH2> UH2@PSUVM.BITNET (Lee Sailer) writes:
>The <number of paths> thru a module doesn't impress me at all. A very simple
>module constructed from a sequence of big CASE or SWITCH statements will have
>many paths, but is easy to understand.
>How 'bout a measure based on the *hierarchy* of Data Flow Diagrams?
As I see it there are two problems. The first is the complexity of the
paths through a module. A number of metrics have been proposed elsewhere
and mentioned in this forum (cycle count, independent path count, etc.).
The second problem is the complexity of the conditions each path places
on the data that passes through, a la Floyd/Hoare program verification.
for example, simple arithmetic expressions replace old conditions with
new. An example might be: x > 5 --> 'x := x + 1' --> x > 6. Other types
of expressions may replace old conditions with new, or add new restrictions.
'if' expressions are bad news, 'while' and recursive expressions can be worse.
But, not all 'if', 'while', or recursive expressions are equally bad, and it's
not just the relative location of each in a program.
Lest anyone think I'm saying something profound, all I have said is that if
one wishes to measure the complexity of a program, one must consider the program
itself (or equiv. its tranformations of the data it modifies) and not just
the flow of data through it.
--
Doug Pase -- ...ucbvax!tektronix!ogcvax!pase or pase@cse.ogc.edu.csnet
------------------------------
Date: 5 Jan 88 13:33:20 GMT
From: ndsuvax!ncmagel@uunet.uu.net (ken magel)
Subject: Summary of Metrics Responses
In December I sent a request for comments on use of software complexity
metrics and what demonstrations people would require to cause them to use
metrics. This message summarizes the nine responses I have received.
Before summarizing the responses, let me define some vocabulary. A program
complexity metric is a single number or small set of numbers which represents
how difficult some task is with the source code of a program. The most common
metric is the number of lines of code. Tasks might include debugging, program
modification, or program understanding. A software complexity metric is a
single number or small set of numbers which represents how difficult some task
is with the source code of a complete software system, usually consisting of
several programs. A system complexity metric is a single number or small set of
numbers which predict or measure how difficult some task is when done on either
system requirements or specifications.
Now to summarize the responses. Some people are using the cyclomatic
complexity metric proposed by McCabe in the mid-1970's. Those people use the
cutoff of 10 in the cyclomatic complexity which McCabe proposed. That is, if
a program has a cyclomatic complexity greater than 10, the program must be
rewritten. Several people requested system complexity metrics rather than
program or software complexity metrics. They stated that the payoff would be
much greater with system complexity metrics. The most common response, however,
was a request to find out what complexity metrics were.
------------------------------
Date: 8 Jan 88 18:17:00 GMT
From: apollo!marc@beaver.cs.washington.edu (Marc Gibian)
Subject: Examples: Optimizing Complexity Reduces Code Quality
As promised, here are some examples of decreasing the quality of code
while reducing the complexity measure value. The complexity measure
used was Raytheon/ED/SSL-s version of the McCabe metric. They made
one modification to the algorithm because they judged that they did
not want to count each case in a switch as an increment in complexity.
The contractual requirement was that every procedure and function
have a McCabe value less than or equal to 10. I must admit that since
I no longer work for them, the examples I am providing are not being
extracted from product libraries. Instead, they are constructed examples
describing the things that were actually done to the product I worked on
while at Raytheon.
Example 1:
original fragment:
if (a == value1) then
y = target1;
else if (b == value2) then
y = target2;
else if (c == value3) then
y = target3;
else if (d == value4) then
y = target4;
else if (e == value5) then
y = target5;
else if (f == value6) then
y = target6;
end if;
transformed fragment:
new_func((a == value1), target1);
new_func((b == value2), target2);
new_func((c == value3), target3);
new_func((d == value4), target4);
new_func((e == value5), target5);
new_func((f == value6), target6);
with new_func defined as:
new_func(relation_value, target)
{
if (relation_value) then
y = target;
end if;
}
discussion:
This example shows an original code fragment which tests a number of similar
variables against a number of values. This can not be transformed into a
CASE construct, so some way of removing the if else if chain must be found.
The resulting code moves the tests into new_func. Note that this particular
example uses y as global to new_func, to allow new_func to represent a single
iteration of the if else if chain.
Some may argue that the transformed code is better. I argue, though, that is
hides the logic, while the original code was quite clear, therefore easily
maintained.
Example 2:
original code fragment:
if (failing) then
if (color_display) then
color = red;
else
inverse = TRUE;
end if;
else if (mode = offline) then
color = color_1;
else if (sub_mode = training) then
color = color_2;
end if;
transformed fragment:
if (! fail_func) then
if (! mode_func) then
sub_mode_fun;
end if;
end if;
where fail_func is :
BOOLEAN fail_func()
{
if (failing) then
if (color_display) then
color = red;
else
inverse = TRUE;
end if;
return (TRUE);
else
return (FALSE);
end if;
}
discussion:
The original code fragment handles the problem of selecting a color for a field in a
display. The algorithm for this is a hierarchical checking of a number of variables.
The fragment mearly moves testings into less obvious locations, while the main code
fragment is reduced to calling functions that set the color.
I believe the transformed code is more complex and harder to maintain because it is bigger,
includes more interfacing, and separates the decisions relating to the color to use.
Thats all I have time for now...
I would like to repeat my feelings regarding complexity measures, based upon my
experience in using them:
I agree with the goal of using a metric to measure the characteristics of
code, I simply believe that no metric now exists that truly measures the
qualities that people (management, customers) want to measure.
Marc S. Gibian
Software Engineer
Apollo Computers
email: marc@apollo.UUCP
------------------------------
Date: 9 Jan 88 07:09:54 GMT
From: decvax!cca!g-rh@ucbvax.Berkeley.EDU (Richard Harter)
Subject: Examples: Optimizing Complexity Reduces Code Quality
I would agree that the altered code is less desirable than the
original code -- indeed the altered code is not correct in that it is
not equivalent to the original code! The altered code goes through all
tests whereas the original code stops testing when a match is found.
The fundamental problem with the complexity measure in this case
is, I believe, twofold: (a) that the language being used lacks the construct
being used, and (b) the complexity measure is incorrectly calculated.
The language doesn't really capture the parallelism of the
construct. The desired construct, in pseudocode, runs something like
this:
define value list A = {a,b,c,d,e,f}
define desired value list B corresponding to A =
{value1,value2,value3,value4,value5,value6}
define target list C corresponding to A =
{target1,target2,target3,target4,target5,target6}
loop through list A
if item from A equals coresponding desired item from B then
set y to target in C corresponding to item from A
and exit from loop
If the lists are short one prefers to embed them implicitly in the code;
if they are long one prefers to be put them in tables. However this solution
is not available if the types in the the value list are not all the same.
If we borrow the naked select statement from PL/I the code would look like
this
select {
a==value1: y = target1;
break;
b==value2: y = target2;
break;
......
f==value6: y = target6;
break;
}
Whether each case should count as an increment in complexity depends on the
cases. In this instance the cases are parallel -- I would feel that the
appropriate measure of complexity is the logarithm of the number of cases.
If, however, the cases are not parallel, then I would feel that the compexity
goes up linearly with the number of case. [I am not prepared to defend this
position.]
In any case what we see here is a complex structure that uses code repetition
rather than data repetition. Neither the language being used, nor the
complexity measure being used provide means for dealing with the higher
level construct. Each, in its own way, deals with the higher level construct
only in terms of lower level constructs.
I would agree that the complexity measure being used does not adequately
measure the complexity of the code -- I would argue that the fault lies
in the lack of adequate means for heirarchical composition of structure
in the language and a corresponding lack of measurement in the complexity
measurement tool.
--
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
Richard Harter, SMDS Inc.
------------------------------
End of Soft-Eng Digest
******************************
-------