Sunday, March 23, 2008

Implications of the Power Law

I’m trying to capture all the thoughts triggered by the SPA conference before the ACCU conference in a couple of weeks time. One of the topics that resurfaced at SPA was the Power Law. Or rather, the fact that software source code and program execution follows a Power Law distribution. If you’ve not come across this before it is worth knowing.

Most (educated) people are familiar with the standard distribution, or bell curve. And the idea that most values cluster around a mean with most data falling inside a standard deviation. It looks something like this:

(Thanks to Petter Strandmark and Wikipedia for this image.)

Well there is another distribution which is called a Power Law distribution. It looks something like this:

In other words there are a few very large numbers and lots of very small ones. Most values are small, if you calculate the average its going to be small because there are so many small values the few large ones get averaged away.

As a result you get the long tail that seems to get so publicity. The 80-20 rule, also called the Pareto Principle is an example of a Power Law but this is a relatively mild form. Some distributions may be 90-10, 99-1 or even higher.

Well it turns out that software follows this distribution. If you take a source code base and count the length of each function you will find a few long functions and lots of small functions. Perhaps not every time but in general this is the case. (I’ve been told this several times and believe it, but I can’t put my hands on an reference to prove it, if anyone can please let me know, more importantly if its been disproved please tell me!)

It also turns out that program execution proceeds in a similar fashion. A few functions account for most of the execution time. Not necessarily the long functions I just mentioned, they could be short.

And it turns out that object graphs in OO systems follow the same pattern. James Noble has some work on the power law in Java systems - systems which conform to the power law are said to be scale free. As this paper points out the web itself conforms to this law.

I’ve been thinking about this for a few years - every since Kevlin Henney and James Noble explained it to me in fact! - and SPA gave me another boost when Michael Feathers mentioned it again. This actually has some quite important implications for software development.

Obviously this law has implications for performance optimisation: find and optimise those few functions where the time is spent.

It explains why major bugs can remain hidden for years and years. Because they exist in a function which is very very rarely used. The program crashes very occasionally. Of course if way the program is used, or the data changes, you might start triggering the bug far more often.

Most changes to a system will occur in a few places. Most of the system will remain stable and unchanging. Therefore it makes sense to refactor those parts of the system that do change and leave the rest.

Perhaps most importantly this law also completely demolishes the argument that you can’t retrofit unit tests to a legacy system. I regularly meet teams who say: “We agree that automated unit testing is good. But our system has 1 million lines of existing code and we can’t cover it with unit tests.” They then usually continue: “Therefore we can’t refactor or apply any of the other principles of Agile development.”

But when I have worked with teams that start to add unit tests to a legacy system they quickly find the tests pay for themselves. Even with a few tests in place there is a pay back. The power law explains this: because most changes happen in a small amount of code, putting tests around that code now will benefit you very soon. Most of the system is not changing so it doesn’t need tests. Of the 1 million lines perhaps only 10,000 changes regularly. As soon as you have 1,000 covered you see the pay back.

It is difficult to know in advance which parts of the system need tests so you might as well add them to anything you are working on. Just because this code hasn’t changed in the last year doesn’t mean it won’t change again soon. The fact that you are working on it shows it is more likely to change than most code. Save your time guessing what will change, just test it.

I’m also starting to see the Power Law elsewhere. It has long been noted that some developers are far more productive than others. 10, 20 or more times productive depending on who you read. Is this another Power Law at work?

I looked over the blogs (of individuals) I subscribe to on Bloglines this morning and made this graph:

This is the number of readers subscribed through Bloglines to the blogs I subscribe too. Joel Spolsky leads with 43,000, Robert Cringely weight in at 19,000 and Guy Kawasaki is a distant third at 3,300. Most of the blogs (including this one) are in the long tail with less than 10 readers.

I think I also see the Power Law at work in employment of IT people. A few people stay with a company years and years and years. Most other people average 18 months or so. Apparently once you’ve been somewhere for 7 years your chances of changing employer drop to near zero.

Some features in a program are used so much more but at the requirements stage it is difficult to know which these are and which are in the long tail. So the Power Law is at work in requirements too. The trick is to work with the law rather than against it: us a little-bit-and-often development and release strategy. Don’t front load your projects with requirements. Do a little, release a little.

It seems the Power Law runs throughout IT, unfortunately many people have internalised the standard distribution and use this as the, sometimes unconscious, basis for making decisions. Decisions made on a standard distribution are wrong. We need to learn to think in Power Law distributions.

1 comment:

  1. An interesting thing would be to take this Scale Free structure normatively and set it as a goal when structuring your libraries. In a way this is close to what Christopher Alexander called living structure.


Note: only a member of this blog may post a comment.