New blog for complexity study

My continuing investigation into the effect of TDD on code complexity (and maybe other things, too) will continue on this new blog.

Debunking Debunking Cyclomatic Complexity

Over at SDTimes, this article by Andrew Binstock contains a claim that this result by Enerjy somehow "debunks" cyclomatic complexity as an indicator of problems in code. He suggests that what's shown is that for low complexity of methods (which is overwhelmingly the most common kind of complexity of methods) increasing complexity of methods is not (positively) correlated with the likelihood of defects. Binstock suggests that:

What Enerjy found was that routines with CCNs of 1 through 25 did not follow the expected result that greater CCN correlates to greater probability of defects.

Not so. What Enerjy say their result concerns is:

the correlation of Cyclomatic Complexity (CC) values at the file level [...] against the probability of faults being found in those files [...]). [my emphasis]

It's interesting all by itself that there's a sweet spot for the total complexity of the code in a file, which for Java pretty much means all the methods in a class. However, Binstock suggests that

[...] for most code you write, CCN does not tell you anything useful about the likelihood of your code’s quality.

Which it might not if you only think about it as a number attached to a single method, and that there are no methods of high complexity. But there are methods of high complexity—and they are likely to put your class/file into the regime where complexity is shown to correlate with the likelyhood of defects. Watch out for them.

TDD at QCon

Just finished a presentation of the current state of my TDD metrics thinking at QCon. The slides [pdf] are up on the conference site, video should be there soon, too.

Complexity at Agile 2007

This thread came from here, and will be continued...

Just walked out of the first keynote at Agile 2007: I don't need to hear about an amature mountaineer's love-life (yes, really) no matter how "inspirational" it's supposed to be. What have we come to?

Anyway, that gives me time to get ready for the latest adventure in test-driven development and complexity.

later...

Well, that didn't go quite a smoothly as I'd hoped. The room I'd been given was in some sort of bunker under the hotel and while it did technically have a wireless network connection the feeble signal that we had was unable to support as many laptops as there were in the room. So it was a bit of a struggle to get folks set up to use the tool.

However, some people did manage to gather some interesting data of which I hope that some will be shared here. Certainly, folks have found some interesting correlations between the numbers that the tool emits and their experiences working with their code. Especially encouraging is that folks are applying the tool to long lived codebases of their own and looking at historical terends. These are the sorts of stories that I need to gather now.

Note: the tool is GPL (and the source is in the measure.jar along with the classes). Several folks are interested in C# and Ruby versions, which I'd love to see and am happy to help with.

I sat down with Laurent Bossavit and we experimented to see if we could get equally interesting results from looking at the distribution of size (ie, counting line ends) in a codebase, and it turns out not. Which is a shame, as that would be easier to talk about, but is also what I expected, so that's kind-of OK.

A lot of good questions came up in the session, pointers to where I need to look next: Is there a difference between code written by solo programmers vs teams? Do you get the same effect from using functional (say, Fit style) tests as from unit tests? Is there any correlation with test coverage? Exactly what effect does refactoring have on the complexity distribution? Thanks all for these.

Laurent seemed at one point to have a counterexample to my hypothesis (which was a very exciting proposition), code that he knew had been done with strong test-first, but had a Pareto slope of about 1.59 (and an amazing R^2 of 1.0). But on closer examination it turned out that the codebase was a mixture of solid TDD code that by itself had a slope of 2.41, and some other code (which we had good reason to believe was a, poor and b, not test-driven) that by itself had a slope of 1.31

Unfortunately, I wasn't able to make it to the research paper session where this thing was discussed, or this. But I need to catch up with those folks. In particular, the IBM group report that with TDD they don't see the compelxity of the code increase in the way that they expect from experience with non TDD projects.

Complexity Results from Spa 2007

The story came from here

Spa 2007 attendees saw this presentation, then ran the measure tool over a range of code and kindly recorded some of their observations in comments here. Many thanks to them.

Especially rewarding is Duncan's observation regarding the time-variance of the figures across a refactoring episode. Several attendees also confirmed my suspicion that there's something odd about language implementations.

The story continues here.

Complexity and Test-first 3

The story came from here.

At XPDay last year I ran a session exploring some of the ideas about complexity and TDD that I've discussed here before. Attendees at the session got a very early copy of a tool, "measure", which calculates some of the statistics I'm intersted in. From that came some good feedback which I've incorporated into a new version of the tool, avilable here. Note to XPDay attendees: this is a much more informative bit of software than the one you have, I suggest you upgrade.

The session will be repeated at Spa this year.

New Tool Features

Measure now shows the parameters for both a Zipf and Pareto distribution modelling how the complexity is found in the codebase. It also shows the R-squared value for the regression through the data points. This was a particular request from the XPDay session and, with due care and attention, can be used to get some idea of how good a fit the distributions are.

Measure also now accepts a -h flag and will display some information about how to interpret the results.

New Results

Using this updated tool, I examined some more codebases (and reëxamined some from before). This table table shows the Zipf distribution paramters. It's getting to be quite difficult to find Java code these days that doens't come with tests, so some of the codebases with an N shown there are ones from SourceForge that haven't had a commit made for several years.

Codebase	Slope	Intercept	R^2	Automatedunit tests?
Jasml 0.1	0.95	3.52	0.73	N
Jruby 0.9.2	1.47	6.27	0.76	Y
Smallsql 0.16	1.54	5.87	0.80	Y
Sunflow 0.06.3	1.59	5.67	0.90	N
m-e-c scehdule α3-10	1.69	4.94	0.92	N
NanoXML 2.2.1	1.77	5.26	0.94	N
Syncbuilder1999	1.84	5.93	0.9	N
Itext 1.4.8	1.88	7.99	0.91	N
Xcool 0.1	1.93	4.60	0.84	N
Ant 1.7.0	2.25	8.90	0.93	Y
Jfreechart 1.0.3	2.30	8.58	0.94	Y
MarsProject 2.79	2.33	7.9	0.96	Y
Log4j 1.2.14	2.43	7.34	0.96	Y
Junit 3.8.1	2.49	5.99	0.94	Y
Jmock 1.1.0	2.79	6.38	0.96	Y
Spring 2.0.1	2.78	9.70	0.96	Y

So, the lower slope and higher incercept of JRuby was a surprise. But note also that the R-squared is quite low. This causes me to refine my thinking about these (candidate) metrics. A low R-squared means that the linear regression through the (log-log) points describing the complexity distribution is not good. This suggests that the actual distribution then is not modelled well by a Zipf type of relation. Maybe there's something about language implementations that produces this? It's worth checking against, say, Jython.

Meanwhile, those codebases with a high R-squared (say, 0.9 or above) seem to confirm my hypothesis that (now I must say "in the case of codebases with very strongly Zipf distributions of complexity) having tests produces a steeper slope to the (log-log) linear regression throught the distribution. And it looks as if a slope of 2.0 is the breakpoint. Still lots more to do though.

Further Investigation

I'd be particularly interested from anyone who finds a codebase with an R-squared of 0.9 or more and tests, but a slope less than 2.0

The discovery of codeases whos complexity distribution is not well modelled by Zipf is not a surprise. The fact that such codebases do not match the tests => steeper slope hypothesis is very interesting and suggests strongly that the next feature ot add to measure is a chart of the actual complexity distribution to eyball.

Note to publishers of code

This sort of research would be impossible without your kind generosity in publishing your code, and I thank your for that. If your code appears here, and has been given a low intercept, this should not be interpreted as indicating that your code is of low quality, merely that it does not exibit particularly strongly the property that I'm investigating.

The Story continues here.

Thanks to Vin for the table formatting fix

Complexity and Test-first 2

The story came from here.

Of course, I'm not the first to notice that software (or, OO software, anyway) has the scale free property. These folks have done a bunch of interesting work on the scale-free nature of the object graph in running systems, and also in various static properties of code. I might just, though, be the first person to observe that the distributions are quantitatively different for different design methodologies.

What the Wellington group are trying to do is disprove what they call the Lego Hypothesis, that all software can be built out of lots of small interchangeable components. Instead, they claim, because of the scale-free nature of software, the biggest components in bigger systems will be bigger than the biggest ones in smaller systems. I'd read some of this research before, but had forgotten that--conciously, anyway--until reminded of it by Kent Beck. Thanks, Kent.

The story continues here.

Complexity and Test-first 1

The story began here.

Interesting to note that a similar discussion, albeit brief, sparked up on the XP egroup. I posted a link to my previous blog post there, but it seemed to get lost in the flood. Oh well. It will be interesting to compare my results with those in the Muller paper.

Anyway, I've managed to find the time to look at a very small sample of Java codebases, find their distribution of complexity, fit it to a Pareto distribution and take a look at the slope of the best fit straight line. Here's the outcome, codebases ordered by published unit tests per unit total cyclomatic complexity (where applicable):

codebase	#tests/ total CC	slope
jasml 0.10	0	1.18
logica smpp library	0	1.39
itext 1.4.1	0	1.96
jfreechart 1.0.1	0.02	2.43
junit 3.8.2	0.14	2.47
ust (proprietary)	0.35	2.79

A few points present themselves: each of the code bases with no tests published has a substantially lower slope (and so substantially greater representation of more complex methods) than any of those with; of those with published tests, number of tests per "unit" of complexity is positively correlated (at about 0.96, very good for "social science", reasonable for "hard science", but this is "computer science", so who knows?) with higher slope and so a preference for simpler methods.

 The story continues here

Complexity and Test-first 0

It recently occurred to me to run a Cyclomatic Complexity tool over a codebase I know to have been largely written test-first/code/refactor (and often test-driven). The code is Java, so I used this Eclispe plugin to measure the per-method complexity.

The distribution of complexity per method looked like this:

Note that the count of methods is shown on a logarithmic scale.

There were 19,917 methods in this codebase. The mean complexity per method was 1.46, and the median complexity is 4.5 Not shown on the chart are a few outliers: one with complexity 91, one with 47, and one with 35.

The Extrema

The 91 complexity method turned out to be the doGet of a servlet providing a simple web service, crammed full of if (method.equals("getLocales")) printLocales(out, ids); type dispatching code. Similarly, the 47 complexity method is mainly concerned with calling out to a third-party API and finding which of a small number of equivalence sets a value from a large domain of return codes falls into. It does this by means of a huge switch with many, many fall-throughs. So in these cases we see a disconnect between the arithmatic of cyclomatic complexity and any notion of the code being complicated, in the sense of difficult to undetrstand (and therefore maintain).

Down at the other end of the scale the tens of thousands of complexity 1 and 2 methods are mostly of these sorts:

• constructors
• bean methods
• forwarders

In between are some more interesting methods, which I will deal with in a later post (which is why this is post #0), comparing the amount of testing that was done to write the method test-first with the amount that the Cyclomatic complexity measure would suggest would be required after writing the method.

Interpretation

In one disucssion by McCabe there is the suggestion that 10 is an important threshold for cyclomatic complexity. The SEI treatment gives 11 as the lower bound of the "simple program, without much risk" class. They don't state quite what a "program" is in this sense, I guess they mean "subroutine" in the structured programming sense. As we can see, methods with complexity >= 10 are vanishingly uncommon in the codebase I examined. Evidence that the team working on this code are keeping per-method complexity under good control.

Now, while we can be confident that these methods are overwhelmingly individually very simple the codebase itself is non-the-less considered (by the folks that work on it) highly complex. It does a lot of different things, and interacts with many external systems, and although it is all written in Java it contains several very different technology stacks. So the distribution of cyclomatic complexity isn't the whole story. The total complexity of the whole codebase is about 20,000. It has far fewer that 20,000 test methods (about 7000, in fact), as a simpleminded application of cyclomatic complexity suggests would be required. Although, if you leave out the complexity 1 methods, the total complexity is only 9,000 or so, which paints a different picture.

I don't want to get embroiled in a disucssion of whether or not cyclomatic complexity even makes sense for object-oriented code, not least because the code inside a Java method isn't particularly object-oriented. I do want to examine a mainsteam notion of complexity and testing (the rule is that the complexity equals the smallest number of test cases requied to cover all paths through the code) in the light of code written test-first. Once I've found a suitable candidate method and tests to explore, I'll let you know.

Wait a minute though...

Something about the shape of that chart caught my eye. It looks very much as if it has something close to a power-law distribution. This shows up better on a log-log rendering:

If we switch to a cumulative count of methods we can extract a pretty convincing Pareto distribution:

It so happens that inside the same repository is a bunch of Java that I'm confident was not written test-first (and certianly not test-driven). That doesn't mean that it's bad code, just written differently. What does its complexity chart look like?

Looks like fairly good scale-free beahviour, but let's look at a fitted Pareto distribution:

Not as good a fit. But perhaps more significantly, the slope is about half the slope of the test-first code, 1.39 vs 2.79

Hypotheses

We can imagine all sorts of reasons for these differences (not least, the non-test-first code is an order of magnitude smaller than the test first, which might account for the lower R-squared) but I'm interested in further investigating the tentative hypotheses that the test-code-refactor cycle results in code that has a distribution of complexity closer to Pareto, and with a steeper slope, than traditional approaches.

If that were true, how might we use it? Well, if the complexity distribution is Pareto/Zipf then there is no "preferred" complexity for the codebase. I'd imagine that if there were a preferred complexity then that might point to a (perhaps widely dispersed) collection of methods that could be candidates for refactoring. Question: do the well-known code smells [pdf] cause such a thing?

I'd further guess that the higher level of dupliction expected in an inadequately refactored codebase (not DRY enough, not OAOO enough) would cause a bit of a hump in the complexity distribution. A sag in the distribution I have less of an inution about, although it might point to something along these lines. You'll have to dig around in Prof Salingaros's work to see what I'm getting at, but it's worth it.

Also, if the slope of the Pareto distribution is low then there will be proportionatly more more complex methods in the codebase than less complex ones--that can't be good, can it?

Well, if it wasn't for the day job I'd be looking into this in ernest. But as it is, I'm going to tinker about with this some more as and when I get the time. I'll report back when I do. If anyone else out there does any measurements like this I'd be fascinated to hear about it.

The story continues here.