Cyclomatic complexity: why long methods are bad

You might have heard it many times, and there are many disputes on what is the maximum limit of code lines per function or method. In fact, for a long time I was writing huge functions myself and I couldn't understand what can possibly be wrong with a class method containing 50 lines of code if this method does exactly what it is supposed to do - like building an array from data fetched from an external data source. I wasn't convinced neither by a "one screen" rule (because it depends on the size of your monitor and the font you use in your code editor), nor by alleged bigger bug density in larger code modules (in fact, research by Les Hatton shows that bug density is lowest in modules containing from 200 to 400 lines of code).

It wasn't until I realized that there is one true reason to write small methods: low cyclomatic complexity. Cyclomatic complexity shows how complicated your code is by using a very simple metric: number of branching instructions, all of which increase the number of possible execution paths through the code. Why is it so important? Because every branch increases the number of execution paths not linearly, but exponentially. When you put an "if" into your method, you can traverse through it in two possible ways. When you add another "if", you increase this number to four. Another "if" makes it eight, and so on. Now imagine you have a function in a big financial system, calculating invoice value, containing ten branching instructions. To make sure it works correctly for every possible case you would need to write over a thousand (2 power 10) test scenarios. Sounds scary? Now divide this method into five smaller methods, with each of them containing only two branching instructions. How many tests do you need now? Two paths power two branching instructions times five methods: 2^2 * 5 = 20. Twenty. Impressive improvement, isn't it?

Let me give you some example code to show how it works in practice. Imagine you write a simple game, in which you have a player moving around a map in four directions: north, east, south and west. The Player object has two methods to get its current coordinates on the map and four public boolean properties: canMoveNorth, canMoveSouth, canMoveEast and canMoveWest. The Map object has a method returning information whether a field with given coordinates is free (and the Player can move to this field) or not (because it contains another player or an obstacle for example). Now let's write a function which sets the Player properties according to the information returned by the Map:

void setPossibleMovementsForPlayer(Player *player, Map *map) {
    int x = player->getPositionX();
    int y = player->getPositionY();

    if (map->getFieldValueForXY(x + 1, y) == FREE) {
        player->canMoveEast = true;
    } else {
        player->canMoveEast = false;
    }
    if (map->getFieldValueForXY(x - 1, y) == FREE) {
        player->canMoveWest = true;
    } else {
        player->canMoveWest = false;
    }
    if (map->getFieldValueForXY(x, y + 1) == FREE) {
        player->canMoveNorth = true;
    } else {
        player->canMoveNorth = false;
    }
    if (map->getFieldValueForXY(x, y - 1) == FREE) {
        player->canMoveSouth = true;
    } else {
        player->canMoveSouth = false;
    }
}

It is easy to calculate that there are sixteen different combinations of the field values around the player - you can also read it from the cyclomatic complexity of the function. So to properly check the player state after executing this method you need to create exactly sixteen unit tests covering it.

But we can make this function much shorter by splitting its logic into four independent ones:

getPositionX();
    int y = player->getPositionY();

    setCanMoveEast(player, map, x + 1, y);
    setCanMoveWest(player, map, x - 1, y);
    setCanMoveNorth(player, map, x, y + 1);
    setCanMoveSouth(player, map, x, y - 1);
}

void setCanPlayerMoveEast(player *player, Map *map, int x, int y) {
    if (map->getFieldValueForXY(x, y) == FREE) {
        player->canMoveEast = true;
    } else {
        player->canMoveEast = false;
    }
}

void setCanPlayerMoveWest(player *player, Map *map, int x, int y) {
    if (map->getFieldValueForXY(x, y) == FREE) {
        player->canMoveWest = true;
    } else {
        player->canMoveWest = false;
    }
}

void setCanPlayerMoveNorth(player *player, Map *map, int x, int y) {
    if (map->getFieldValueForXY(x, y) == FREE) {
        player->canMoveNorth = true;
    } else {
        player->canMoveNorth = false;
    }
}

void setCanPlayerMoveSouth(player *player, Map *map, int x, int y) {
    if (map->getFieldValueForXY(x, y) == FREE) {
        player->canMoveSouth = true;
    } else {
        player->canMoveSouth = false;
    }
}

Now you only need to test player behaviour against these four small methods, and for each of them you only need two test cases. It reduces the overall number of necessary unit tests by half: from sixteen to eight.

But wait, all four methods do the same thing: they set a public property of the Player object. So why not merge them into one method?

void setPossibleMovementsForPlayer(Player *player, Map *map) {
    int x = player->getPositionX();
    int y = player->getPositionY();

    setCanPlayerMoveInDirection(&player->canMoveEast, map, x + 1, y);
    setCanPlayerMoveInDirection(&player->canMoveWest, map, x - 1, y);
    setCanPlayerMoveInDirection(&player->canMoveNorth, map, x, y + 1);
    setCanPlayerMoveInDirection(&player->canMoveSouth, map, x, y - 1);
}

void setCanPlayerMoveInDirection(bool *property, Map *map, int x, int y) {
    if (map->getFieldValueForXY(x, y) == FREE) {
        property = true;
    } else {
        property = false;
    }
}

Now you need only two unit tests to make sure the setCanPlayerMoveInDirection() method is correct, and possibly four more for setPossibleMovementsForPlayer() to make sure that the right player properties are being set.

As a side effect, the code is now also smaller and more readable than the original version.

Dependency Injection in C++

One of the most fundamental rules of good programming is the single responsibility principle, a term coined by Robert C. Martin. In object oriented programming a similar concept is often referred to as encapsulation. Unfortunately, programmers usually get these two rules wrong. Separating responsibilities is not only about wrapping code into separate classes and methods, but also about decoupling dependencies. Consider the following code:

class Logger {
  public:
    void log(std::string s) {
        /* implementation here */
    }
}

class Foo {
  private:
    Logger *logger;
  public:
    Foo() {
        logger = new Logger();
    }
    void doSomethig() {
        /* does something */
        this->logger->log("done");
    }
}

There is one big problem with this implementation: class Foo is strongly tied to the specific instance of the class Logger, which has the following implications:
1) If you ever need to write a new logger and make your application use it, you will have to browse through all the classes depending on the logger and refactor them.
2) There is no way to write good unit tests for class Foo, since it requires the environment setup expected by Logger (like syslog, database, log directory on the filesystem, etc.).

A solution to this problem is to turn Logger into an abstract interface and inject its specific implementation (hence term "dependency injection") into class Foo through a constructor. Because C++ implements multiple inheritance instead of interfaces, let's just use an abstract class ILogger:

class ILogger() {
    virtual void log(std::string s) = 0;
};

class Logger : public ILogger() {
    void log(std::string s) {
        /* implementation goes here */
    }
};

class Foo {
  private:
    ILogger *logger;
  public:
    Foo(ILogger *l) {
        logger = l;
    }
    void doSomethig() {
        /* does something */
        this->logger->log("done");
    }
}

With this implementation it is now possible to create different loggers inheriting from ILogger and use them with class Foo without any modification of the Foo itself (it follows so called open/closed principle, which means that you can modify object's behaviour without changing its source code). It is also possible to write unit tests to cover doSomething(), using a fake logger having an empty log() method, or even doing some assertions inside. The classes are loosely coupled, which means that you can use them like independent building blocks, and make changes to the application architecture much more easily.

However, if you have a lot of classes, it is tedious to instantiate all of them with proper dependencies, like this:

Foo *foo1 = new Foo(new FileLogger());
...
Foo *foo2 = new Foo(new FileLogger());
...
Foo *foo3 = new Foo(new FileLogger());

A common pattern that solves this problem is called a dependency injection container. It's a mechanism that helps you managing application through registering and resolving dependencies. More advanced containers (like Google Guice for Java or Symfony Framework Container for PHP) provide additional services, like support for injecting dependencies through setters or defining dependencies in separate configuration files (XML or YAML for example). However, these features rely heavily on reflection and cannot be easily used in C++, so let's just create a simple dependency resolver:

class Resolver {
  public:
    static std::map<std::string, void *> registeredTypes;
    template<class T> static void Register(const T*);
    template<class T> static T* Resolve();
};

std::map<std::string, void *> Resolver::registeredTypes;

template<class T> void Resolver::Register(const T* object) {
    registeredTypes[typeid(T).name()] = (void *)object;
}

template<class T> T* Resolver::Resolve() {
    return (T *)registeredTypes[typeid(T).name()];
}

The resolver implements two methods: Register() and Resolve(), which store and retrieve data from a map holding associations between type name and a pointer to a specific object of that type. You can now use it to simplify dependency management of the initial Foo class:

/* Bootstrap code */
Resolver::Register<ILogger>(new FileLogger());
/* Application code */
Foo *foo1 = new Foo(Resolver::Resolve<ILogger>());
...
Foo *foo2 = new Foo(Resolver::Resolve<ILogger>());
...
Foo *foo3 = new Foo(Resolver::Resolve<ILogger>());

The resolver can also be used as a service locator, which means that a class uses a resolver instance to retrieve the dependencies itself, instead of relying on injection through a constructor or setter:

class Foo {
  private:
    ILogger *logger;
  public:
    Foo() {
        logger = Resolver::Resolve<ILogger>();
    }
    void doSomethig() {
        /* does something */
        this->logger->log("done");
    }
}

/* Bootstrap code */
Resolver::Register<ILogger>(new FileLogger());
/* Application code */
Foo *foo1 = new Foo();
...
Foo *foo2 = new Foo();
...
Foo *foo3 = new Foo();

Using a resolver or a full-blown dependency container to inject class dependencies is generally considered better practice than using service locators within classes, because it forces you to initialize dependencies before injecting them (with service locator you may forget to register all dependencies required by a class before trying to make an object).
The resolver is publicly available for download on Github. It's super simple (around 30 lines of code, not including unit tests and comments) and uses a simplified BSD license, which means that you can use and distribute it with any project (free or commercial) without any restrictions, provided that you keep the original copyright notice.

Simple ANSI C formatter for JSON streams

Recently I needed to debug a JSON document coming from a REST service. The problem I encountered was that it was not a single file, but a stream dripping from a fairly slow network connection. Besides the fact that I didn't want to wait for the whole document to finish downloading, I couldn't find a tool which could properly parse only partially available (and hence formally invalid) JSON document. So I wrote my own simple parser, which reads data line by line from the input stream and formats it without validation. You can use it to parse single files, or pipe through it data coming from a web service, like this:

wget -O - http://staff.tumblr.com/api/read/json | jsonformat | less

It is written in portable ANSI C, so it should compile on any platform providing C89 compatible compiler. You can get it from the project page on Github.

Tiny TCP proxy server development continues

Two months ago I published a tiny TCP proxy server which helped me to proxy network traffic on hosts where I didn't have access to firewall configuration. Recently it turned out that it would be nice if it had at least some basic debugging capabilities. Because I'm not a big fan of reinventing the wheel, I decided I would just add an ability to cooperate with external tools through pipes and let them do the job. Thus the latest version of the proxy can pass all incoming and outgoing data through any command which can read it from the standard input and write it back to the standard output. For example if you want to log all incoming http data to in.txt file and outgoing data to out.txt you can use tee command for this purpose. It echoes all input and additionally writes it to a file:

proxy -l 8080 -h 192.168.1.2 -p 80 -i "tee -a in.txt" -o "tee -a out.txt"

The software is LGPL v3 licensed and can be downloaded from Github. On Linux you can compile it with standard development tools, on Windows you will need Cygwin with gcc package installed first.

Software industry gone mad

Recently I was looking for an alternative to Javascript and a friend of mine recommended Dart, a new programming language announced last year by Google. At first I was very keen to give it a try until I saw a post at Stackoverflow showing the output of Dart to Javascript compiler - it produced 730 lines of Javascript code out of 3-line Dart "Hello world" source.
For me it's just pure madness. Writing code in a scripting language, which than gets translated to a 243 times bigger code in another scripting language, which than gets run by a Javascript engine embedded in a web browser working on top of an operating system... Dart official page strongly emphasizes that it increases programming productivity. Actually I can't figure out how adding more and more layers of software on top of existing ones can increase productivity. And I don't mean logic layers within one application or framework, but using one technology on top of another.
In fact, it's just the opposite. Tracking down non-trivial bugs becomes more problematic, because their source can be located deep below in one of existing layers. Also spawning software layers makes its overall performance drop dramatically. I remember laughing out loud back in 1997 when I read in PC Magazine that a 200 MHz Intel Pentium CPU with 32 MB RAM is recommended to surf the web comfortably, while I could do just fine on Intel Pentium 133 with 16 MB RAM. Now such computer wouldn't probably even boot any modern operating system, not to mention that I can barely open more than a few tabs with Firefox 13 on a computer with 2-core 1.6 GHz CPU and 4 GB RAM. Insane rush to release software more often and more quickly makes it require more and more efficient hardware. In the long rong run, the company may pay less to the developers (because they will produce new applications faster), but it will pay more for hardware infrastructure. Latest power outages in India, one of the world's largest IT centers, clearly show that "productivity" comes at a cost, and that this cost can be huge. To make things worse, hardware performance cannot be increased infinitely: CPU speed became more or less stale since 2005 (further increase in clock frequency became impossible due to amount of heat it produces) and now the processing power is being increased by adding more and more cores. However, there are many algorithms which cannot be parallelized, so they will run equally fast (or slow) on a one-core as well as on a multi-core CPU. Modern processors provide many mechanisms which are designed to help programs run faster, like L1 and L2 cache, but what benefit do you get from a few megabytes of cache if your application requires a virtual machine which does not event fit into the cache itself, not to mention that it needs to be shared among all running applications?
Many of my fellow programmers say that "it has to be like that". No, it hasn't. A computer which helped Apollo 11 land on the Moon was a 2 MHz 16-bit unit, something that modern programmers cannot even imagine. I remember when Kevlin Henney showed at GeeCON a complete chess software written in 672 bytes of 8-bit assembly code someone from the audience screamed: "But that's impossible!". And yet, you can find a web server running on bare Commodore64 with 1 MHz CPU and 64 KB RAM - hell, there is even Unix clone dedicated for it! Another example is a quadcopter controlled by a 16 MHz ATmega 8-bit CPU with 32 KB Flash RAM and 2 KB SRAM (it's based on modified Harvard architecture). If it was programmed by an average software developer, it would probably require the latest Intel Pentium hardware and of course would be much too heavy to fly, even if it run a single floppy MenuetOS...

Streaming Internet radio from Raspberry Pi to Samsung TV

Not much related to programming, but I spent almost a week trying to make it work, so I decided to share my experience in hope someone may find it useful. You've probably heard already about Raspberry Pi - I think it's a great project and I admire thousands of people from all over the world who contribute to its development, but it's still in its experimental stage and has some quirks which sometimes make it very hard to use. One of them is using it as a DLNA server for streaming media straight from the Internet right to your home theater.

I have a Samsung TV with DLNA client on board, which works well with Serviio installed on my laptop, but I didn't feel like turning on a computer just to listen to my favourite online radio station, once I got my hands on Raspberry Pi. So I installed SqueezePlug on an SD card and started to play with it. Unfortunately, it turned out that none of the four pre-installed media servers could provide me with what I needed: MiniDLNA did not support transcoding of live streams (it needed some patches that were not applied), TVMobili was not recognized by my TV, Twonky said that its license expired before I even managed to configure it, and Logitech Media Server simply didn't work (it had some problems with the GUI - it called an AJAX script which always responded with an empty contents).

The only option I was left with was MediaTomb, which fortunately has a very good documentation and a lot of supportive users across different forums. The first thing I learned was that Samsung needs some special headers to be sent by MediaTomb, otherwise it always responds with "file format not recognized" message. Very informative from Samsung I must say - it took me a lot of time just to discover that it was the response header from DLNA server that was not recognized, not the data itself. Next step was to read the radio stream from the Internet and pass it to the TV. I spent next few evenings analyzing why I can stream media from a laptop and I can't from Raspberry Pi using ffmpeg for transcoding, despite using exactly the same version of MediaTomb and the same configuration file. As it turned out, my TV has issues with streams encoded by ffmpeg on ARM CPU (they differ substantially from those produced by ffmpeg on Intel), and it seems that ffmpeg compilation for ARM is simply broken. If you try ffmpeg on different distributions of Debian for Raspberry Pi you will learn that it either crashes with core dump or "illegal instruction" message or produces mpeg audio streams full of bad bytes, which can be corrected by PC players like vlc or foobar, but apparently not by a TV built-in software. So I tried other transcoders, like mencoder (provided by mplayer), until I realized that I need no transcoding at all - it's enough just to pass the original http stream to the output file just as it is, and wget is actually everything that I needed.

Still, one problem remained. After a few seconds of playing the connection between the TV and MediaTomb was breaking up. It was driving me nuts and it took another few hours to discover that MediaTomb sends "Connection: close" header to the client, while the online radio streams use "Connection: keep-alive", which prevents client from disconnecting when there is no data in the stream for a while. I found out that the solution is to use apropriate buffer size for the radio stream - it should be fairly small so that it never stops serving data even for a while and thus prevents the TV from disconnecting, but not too small because it will make the ARM to choke.

So, if you have a Samsung TV and want to listen to Internet radio stations served by a Raspberry Pi, here is my recommended configuration:

1. Install Debian Squeeze following the instructions on Raspberry Pi download page. Then log in to it and install MediaTomb server:

sudo apt-get update
sudo apt-get install mediatomb

2. Modifiy the /etc/mediatomb/config.xml file: Enable web user interface by modifying <ui> entry in the <server> section:

<ui enabled="yes" show-tooltips="yes">
  <accounts enabled="yes" session-timeout="300">
    <account user="mediatomb" password="mediatomb"/>
  </accounts>
</ui>

Add the following entry to the <server> section (as described here):

<custom-http-headers>
   <add header="transferMode.dlna.org: Streaming"/>
   <add header="contentFeatures.dlna.org: 
DLNA.ORG_OP=01;DLNA.ORG_CI=0;DLNA.ORG_FLAGS=017000 
00000000000000000000000000"/>
</custom-http-headers>

Change:

<transcoding enabled="no">

to:

<transcoding enabled="yes">

Just below it, in <mimetype-profile-mappings> section add the following entry:

<transcode mimetype="audio/x-shoutcast" using="streaming"/>

Also, add the following section to <profiles>:

<profile name="streaming" enabled="yes" type="external">
  <mimetype>audio/mpeg</mimetype>
  <accept-url>yes</accept-url>
  <first-resource>yes</first-resource>
  <use-chunked-encoding>no</use-chunked-encoding>
  <agent command="wget" arguments="%in -O %out"/>
  <buffer size="8192" chunk-size="1024" fill-size="2048"/>
</profile>

3. Restart MediaTomb server:

sudo service mediatomb restart

Now log in to MediaTomb interface using a web browser (it will be listening at port 49152, so assuming that your Raspberry Pi has IP address 192.168.1.10 you should go to http://192.168.1.10:49152/) with user and password defined in beforementioned <accounts> section (in my example it's mediatomb/mediatomb) and add a new stream:

Type: External Link (URL)
Title: Your radio station title
URL: Radio URL (for example http://nl2.ah.fm:9000)
Protocol: http-get
Class: object.item.audioItem
Mimetype: audio/x-shoutcast

Choose DLNA (MediaTomb) as input source on your TV and enjoy listening to your favourite radio.

Short introduction to TDD

Test-driven development (or TDD in short) is a coding technique that makes creating unit tests a crucial element of the software development process. Using TDD is benefitial in several ways: research by IBM showed that it substantially decreases the ratio of bugs by single line of code (up to 40%) and positively affects code design, leading for example to lower cyclomatic complexity. Also, very high code coverage with unit tests, implied by TDD, allows safe code refactoring and effectively eliminates "do not touch a working code" syndrome. A great book to learn TDD is Kent Beck's "Test Driven Development: By Example".

One of the main principles of TDD is a Red-Green-Refactor cycle. "Red" is a phase when you write a test that checks your code for a desired condition, but it obviously fails, because no code is ready, yet. Then you move to the "green" phase, which is a state when your code passes the test. The important thing about this step is to move from red to green as quickly as possible - the code doesn't need to work, it just needs to pass the test. Now you can start the last phase: refactoring. In this step you can implement the full functionality, restructure your code or optimize it for performance, because the unit test protects you from bugs during code modifications.

Now let me show you how TDD works on a short example of Project Euler problem number one:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

The first sentence of the task is already a test case, so we are ready to dive into a red phase. Let's write a C++ code skeleton with a simple assertion: for the input value of 10 the expected result should be 23.

#include <cassert>

int main()
{
    Problem p;
    assert(p.Solve(10) == 23);
    return 0;
}

Obviously, the code won't even compile, because there is no class Problem, yet.

Important note: You should write your tests while you implement your solution, not before you start writing code or before you design it. This is a very common misunderstanding about TDD: many people think that TDD enforces you to create tests before you write any code, which is plain wrong. In this example I just assume I need a class I call Problem with one public method Solve() and only then I write a test to verify this method's output. And, in fact, this is the only test I need, because I only want the final solution to be correct.

Now the crucial step is to move to the green phase as fast as possible, so we can make sure that the test passes. So let's create the required class:

class Problem
{
    public:
        int Solve(int n);
};

int Problem::Solve(int n)
{
    return 23;
}

This is so called "fake it" solution, which means that you put some dummy code in your class just to make it pass the test. Now your program should compile and the assertion should not fail. You are ready for the next step: refactoring. Let's implement some obvious solution to Problem 1:

int Problem::Solve(int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }
    return sum;
}

The modified Solve method still passes the test, which means that we can assume that the code above is correct. Now you can modifiy the main method to get the result for input value of 1000 and the final code should look more or less like this:

#include <cassert>
#include <iostream>

using namespace std;

class Problem
{
    public:
        int Solve(int n);
};

int Problem::Solve(int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }
    return sum;
}

int main()
{
    Problem p;
    assert(p.Solve(10) == 23);
    cout << p.Solve(1000) << endl;
    return 0;
}

After solving each Project Euler problem you get access to the forum, where you can find solutions provided by other people. Sometimes you can also get access to a paper describing the most efficient algorithms used to find the correct answer. The solutions are different, but they all should pass the test assertion and give the same result. If you already have the correct solution you can write the second assertion for p.Solve(1000) and try to implement different algorithms to make your code smaller or faster - the TDD approach will prevent you from implementing an incorrect solution.

On the other hand, no unit test will make you sure that your code will work correctly for each possible case. For such purposes much more suitable is design by contract approach, which allows you to define constraints imposed on software modules.
Another interesting technique is fuzz testing, which randomizes input data and monitors the code for unexpected behaviour. However, unlike unit tests, fuzz tests are usually more complicated and not always necessary - they are used mainly for security tests or early identification of problems such as crashes or memory leaks.