Wednesday, October 20, 2010

Test Driven Development

Test Driven Development promises to improve software quality by pushing developers to think hard about requirements, interfaces and corner cases, create tests early in the development cycle, and provide a test framework that enables and encourages re-factoring.

I decided to give it a try myself while working on one of the labs from my son's Computer Science class at RPI. It was a very simple assignment - write a function that returns the maximum of three integers and test the function with some sample data.  Test Driven Development recommends the following:
  1. Write a test.
  2. Run the test and verify it fails.
  3. Write some code.
  4. Run the tests and fix the code until the tests pass.
  5. Re-factor the code.
  6. Repeat.
For some reason I can't yet explain, most software developers like writing functional code but don't like writing test code.  With test driven development, the test code is written in the same language as the functional code, so why is it that we enjoy writing functional code but not test code?  Isn't code code?

I found myself drawn towards the functional code, but forced myself to begin by writing:

int max3(int a, int b, int c) {
  return -1;
}

I then wrote a test harness with the sample data and ran the tests.  As expected, all of the tests failed except one case where -1 was the expected result.  Next, I updated the function to return the maximum value, re-ran the tests, and they all passed!  So far so good...

In class, the TA asked the students a teaser question - write the same function using only a single if statement. My original implementation had two if statements, so I decided to give it a try and I came up with this:

int max3 (int a, int b, int c) {
   int max = a;
   if ( (b>max) && (max=b) && (c>max)) max = c;
}

I ran the tests, and they all passed so I thought I was pretty smart.  Always curious and never satisfied, I decided to add a few more tests.  To my surprise (and disappointment), this test case failed:

a = -2, b = -2, c = -1, expect: -1

Guess I'm better at writing tests than code and I'm not as smart as I first thought.  Given a specific failing test case, it was pretty easy to find the flaw in the code so I updated the function to:

int max3 (int a, int b, int c) {
  int max = a;
  if ( ((b>max) && (max=b)) || ((c>max) && (max=c)));
  return max;
}

I re-ran the tests, and they all passed.  I'm sure a more skilled developer would have recognized the flaw in my first attempt at using a single if statement, but I'm also sure that even the best programmers make mistakes.

[Update 07-Nov-2010:  OK, this code doesn't work either (it has the same type of flaw as my first attempt) and the tests did *not* all pass.  When I ran the tests, I took a quick look at the tests that failed with my first attempt, and those cases passed.  The unit tests worked great - I just made the mistake of rushing and not checking all the results...]

When I started on this exercise, I thought it was too trivial to be of much interest and pursued it solely as a simple way to start exploring test driven development.  To my surprise, this simple example illustrated an important concept - don't write "clever code."

Attempting to be too clever obscures the purpose of the code, making it difficult to understand and maintain, and increases the odds of introducing subtle, hard to detect errors.  Imagine trying to debug the flawed max3 implementation if it was buried deep inside 1,000's of lines of code, with the flaw exposed by some complex system test.  System level tests would work correctly in many cases, but then fail for unexplained reasons in other cases, leading to a long and difficult debugging session.  With a simple failing unit test, it was quick and easy to find the flaw by inspection.

Although this example is far too simple to draw conclusions about the value of Test Driven Development for commercial software development projects, I do feel it's worth exploring the technique in more complex situations.

3 comments:

Anonymous said...

here is an implementation that uses divide and conquer, tail recursion, and no branches at all.

int max2(int a, int b) {
return a > b ? a : b;
}

int max3(int a, int b, int c) {
return max2(a, max2(b, c));
}


gcc compiles it to the following branchless code:


00000000004004e0 :
4004e0: 39 fe cmp %edi,%esi
4004e2: 89 f8 mov %edi,%eax
4004e4: 0f 4d c6 cmovge %esi,%eax
4004e7: 39 d0 cmp %edx,%eax
4004e9: 0f 4c c2 cmovl %edx,%eax
4004ec: c3 retq

Tom Hotchkiss said...

@anonymous - thanks for the post, this is beautiful code. Clear, concise, and high performance!

What gcc version/compile flags did you use to get branchless assembly?

Tom Hotchkiss said...

I was impressed by the results shared by the anonymous commenter, and I wondered if similar results were achievable with a different implementation. First, I copied the max2 and max3 routines posted in the anonymous comment and achieved equivalent results:

$ g++ --version
g++ (GCC) 4.2.2
Copyright (C) 2007 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ g++ -S -fverbose-asm -g -O3 max3.cpp
$ as -alhnd max3-opt.s > max3.lst

From max3.lst (edited for brevity):

0010 39FE cmpl %edi, %esi # a, b
0012 89F8 movl %edi, %eax # a, tmp62
0014 0F4DC6 cmovge %esi, %eax # b,, tmp62
0017 39D0 cmpl %edx, %eax # c, tmp62
0019 0F4CC2 cmovl %edx, %eax # tmp62,, c, tmp62
001c C3 ret

I then tried compiling and analyzing the following source with the same compiler version and flags:

int max3(int a, int b, int c) {
int max = a;
if (b > max) max = b;
if (c > max) max = c;
return max;
}

It produced slightly different, but what looks to be performance equivalent results:

0000 39FE cmpl %edi, %esi # a, b
0002 89D0 movl %edx, %eax # c, c
0004 0F4CF7 cmovl %edi, %esi # b,, a, max
0007 39D6 cmpl %edx, %esi # c, max
0009 0F4DC6 cmovge %esi, %eax # max,, c
000c C3 ret

Post a Comment