Reflections on Programming

My perspective on programming has changed quite a bit over the years. Even in the few years since I started this blog I've noticed that I look at programming differently than I used to. If there's anything people who work with technology need to get used to, it's change, and I expect that my perspective will continue to evolve in the years to come. This is an attempt to take a snapshot of how I look at programming right now and how it's different from the recent past. As for the future, I'm not capable of speculating. We'll have to see what I think when it gets here.

Don't Fool Yourself

The first principle is that you must not fool yourself and you are the easiest person to fool. -Richard P. Feynman

Have you ever fooled yourself? Maybe a better question is, do you remember the last time you fooled yourself? You've worked all day or all week on a problem, and you think you've come up with a reasonable, if not elegant, solution. You show it to someone you trust—a coworker or a friend maybe—and she immediately sees the flaw in your logic or proposes a dead simple alternative that you never thought of. Face-palm.

I fool myself all the time, and I'm not ashamed to admit it. Those face-palms are the times when real learning happens, if you're willing to examine where you went off track and why the better solution works. Then you can generalize it to other problems. I came across one fascinating post by Ivan Yurchenko a few months back that perfectly illustrates how you can fool yourself on multiple levels when you're excited about something and want it to be more than it is.

The post is about calculating the Nth Fibonacci Number in O(log n) time, and it caught my attention because I thought that was impossible. To be clear, I don't want anyone to think I'm trying to take down Ivan or his post in any way. That's not the intent here. I enjoyed reading his post, and it made me think hard about algorithms, benchmarking, and optimization. It's a great post to learn from, and I'm sharing some of the insights I had. Getting back to Fibonacci Numbers, why did the claim of O(log n) time bother me?

Question Your Assumptions

The Fibonacci Numbers are a common sequence of numbers that are generated by starting with 0 and 1 (or 1 and 1, depending on context and personal preference) and continually adding the last two numbers to get the next number in the sequence. The first 10 Fibonacci Numbers are

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Using a loop, we can write a simple program that calculates the Nth Fibonacci Number. Ivan does this, and here is his version in Python:

class IterationFibonacci:
  def __init__(self):
    pass
 
  def get_number(self, n):
  """Get nth Fibonacci number (n is int, non-negative)."""
 
    if n == 0:
      return 0
    a = 0
    b = 1
    c = 1
    for i in range(n-1):
      c = a + b
      a = b
      b = c
    return c

By inspection of the for loop, this algorithm runs in O(n) time, but that's already making an assumption that we'll get back to in a minute. First, can we improve on this naive algorithm at all? A quick search of Wikipedia shows that there is actually a closed-form expression for the Nth Fibonacci Number:

where

is the golden ratio, and

Normally, a closed form expression signals that we can compute a result in constant time, but take a closer look at that expression. The n for the Nth Fibonacci Number that we're trying to find is an exponent in two places, and φ and ψ are irrational numbers. Taking the nth power of a number requires n-1 multiplications. That makes the time complexity of this closed-form expression O(n). We could be smarter about the multiplications and split them up into a binary tree of multiplications. That would make the time complexity O(log n).

Can we do better? How about using a power function provided by a standard library? It turns out that the run time complexity of a power function is dependent on the precision that you need in the result, and once you start looking at the precision that you need for Fibonacci Numbers, you start to see the real problem that we're dealing with. The Nth Fibonacci Number will have on the order of n bits in binary form. The 100th number has 69 bits. The 1,000th number has 694 bits. the 10,000th number has 6,942 bits.

It takes a little while for the series to get going, but after a while every subsequent number requires another bit to calculate and store it. That growth means that a power function needs n bits of precision to compute the Nth Fibonacci Number exactly, so it will have O(n) time complexity, assuming you already know the golden ratio to the required number of bits outright. That's the best we can do. Returning to the simple iterative algorithm above, the addition inside the for loop doesn't take constant time. It takes O(n) time because there are O(n) bits to add together. That was the incorrect assumption we were making, and the algorithm actually has O(n^2) time complexity.

That brings us to the matrix multiplication algorithm that Ivan presented from The Art of Computer Programming. It only has O(log n) complexity if you assume that all multiplies can be done in constant time, but the numbers being multiplied are on the order of O(n) bits long so the complexity is actually O(n log n). Knowing that calculating Fibonacci Numbers means working with ginormous numbers is a good thing to keep in mind when figuring out the complexity of a real implementation. The theory may be making assumptions that can't be met on a physical computer.

Pay Attention to What You're Testing

Moving on from complexity theory to benchmarking, Ivan compared the simple iterative algorithm above to the matrix multiplication algorithm, and the results showed that the run time of the iterative algorithm grew linearly and the matrix multiplication algorithm run time appeared to stay constant. There were a couple wrinkles in his tests, though.

The test procedure consisted of doing test runs of each algorithm, calculating 10,000 Fibonacci Numbers around n where n was chosen pseudo-randomly in the range n±5. He did these 10,000-iteration runs over the range of n from 10 to 1010 in increments of 10. Here's the code:

def benchmark():
  random.seed()
 
  for around in range(10, 1010, 10):
    ifib = IterationFibonacci()
    mfib = MatrixFibonacci()
    ti = 0
    tm = 0
    count = 10000
    for _ in range(count):
      n = random.randint(around-5, around+5)
      t = time.time()
      ifib.get_number(n)
      t1 = time.time() - t
      ti += t1
 
      t = time.time()
      mfib.get_number(n)
      t2 = time.time() - t
      tm += t2
 
    print("{0}\t{1}\t{2}".format(around, ti, tm))

In other words, he started with n=10, calculated 10,000 Nth Fibonacci Numbers in the range of 5 to 15, moved to n=20, calculated 10,000 Nth Fibonacci Numbers in the range of 15 to 25, and so on up to n=1000. Right away, one issue is that the benchmark is only calculating relatively small Fibonacci Numbers where the linear time complexity of the additions and multiplications don't come into play too much. Maybe the application that would use these algorithms doesn't need to calculate larger numbers, but in that case, why not calculate all of the numbers in the required range once and store them in a look-up table? It wouldn't take too much time or space unless the application had limited memory requirements.

The second issue arises when we look at how the matrix algorithm is implemented. Another optimization was added to the matrix algorithm to speed it up more. In the part of the algorithm that decomposes n into powers of 2 and calculates the matrices for those powers of 2, the matrices are calculated once and saved in a hash table so that they can be recalled the next time they're needed instead of calculating them again. This optimization is called memoization, and it muddies the waters a bit because we're no longer comparing two algorithms, we're comparing one algorithm without an optimization and another one with an optimization. Here's the matrix algorithm with memoization:

class MatrixFibonacci:
    A = [[1, 1],
         [1, 0]]

    def __init__(self):
        self.__memo = {}

    def __multiply_matrices(self, M1, M2):
        """2x2 matrices multiplication"""

        a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
        a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
        a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
        a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
        r = [[a11, a12], [a21, a22]]
        return r

    def __get_matrix_power(self, M, p):
        """Calculate matrix power (p is a power of 2)"""

        if p == 1:
            return M
        if p in self.__memo:
            return self.__memo[p]
        K = self.__get_matrix_power(M, int(p/2))
        R = self.__multiply_matrices(K, K)
        self.__memo[p] = R
        return R

    def get_number(self, n):
        """Get nth Fibonacci number (n is int, non-negative)."""

        if n == 0:
            return 0
        if n == 1:
            return 1
        # Decompose to powers of 2,
        # i.e. 62 = 2^5 + 2^4 + 2^3 + 2^2 + 2^0 = 32 + 16 + 8 + 4 + 1.
        powers = [int(pow(2, b))
                  for (b, d) in enumerate(reversed(bin(n-1)[2:])) if d == '1']
        # Less pythonic: http://pastebin.com/h8cKDkHX

        matrices = [self.__get_matrix_power(MatrixFibonacci.A, p)
                    for p in powers]
        while len(matrices) > 1:
            M1 = matrices.pop()
            M2 = matrices.pop()
            R = self.__multiply_matrices(M1, M2)
            matrices.append(R)
        return matrices[0][0][0]

Notice that in the benchmark code the memoization hash is initialized when a MatrixFibonacci object is initialized, and it's maintained for the life of the object. Because the objects are created before each run of 10,000 Fibonacci Numbers, this optimization gives the matrix algorithm a big advantage. We could apply this same memoization technique to the iterative algorithm, and it would give the iterative algorithm an even bigger advantage because instead of only saving parts of the calculating, it would be saving every Fibonacci Number as it was calculated, basically building the look-up table that I described earlier on the fly. If we ran this benchmark on the iterative algorithm with memoization, it would be orders of magnitude faster than the matrix algorithm.

To compare the two algorithms directly, we can remove the memoization from the matrix algorithm. Even so, running up to n=1,000 doesn't show a substantial difference between the two algorithms. To get a better sense of their difference, we can run out to n=10,000, which results in run times like this:

This chart clearly shows the O(n^2) behavior of the iterative algorithm. It's not quite as clear that the matrix algorithm is O(n log n), but it looks like it's at least linear and not sub-linear. It's important to know what you want to test when creating benchmarks, and make sure that you are indeed testing what you think you're testing.

Keep Looking for a Simpler Way

If a solution seems complicated, it probably is. There is often a simpler approach that will accomplish the same goal more clearly and in less code. The above matrix algorithm is pretty complicated, and a few of the commenters on the original post came up with some nice improvements. One that I particularly liked from Juan Lopes was dramatically shorter, and it's reproduced here with a few edits to put it in the same format as the previous algorithms for running in the test bench:

class MatrixFibonacciShort:
  def __init__(self):
    pass

  def mul(self, A, B):
    return (A[0]*B[0] + A[1]*B[2], A[0]*B[1] + A[1]*B[3], 
            A[2]*B[0] + A[3]*B[2], A[2]*B[1] + A[3]*B[3])
    
  def fib(self, n):
    if n==1: return (1, 1, 1, 0)
    A = self.fib(n>>1)
    A = self.mul(A, A)
    if n&1: A = self.mul(A, self.fib(1))
    return A

  def get_number(self, n):
    if n==0: return 0
    return self.fib(n)[1]

The matrix was simplified from a 2-dimensional to a 1-dimensional array that compresses the multiplication code, and the core of the algorithm in fib() is now five lines long. It's a very elegant way to dynamically decompose the matrix multiplications into powers of 2 because the binary 1s in n mark where the powers of 2 are, and the algorithm uses that information to build the multiplication tree on the stack as it shifts through the binary bits. It's also about twice as fast as the original matrix algorithm:

I run into this problem all the time where I think long and hard about the best way to express some algorithm only to have someone else (or a Google search) show me a much more elegant solution. It's always great to learn about another clever way to solve a problem, and over time these solutions build up your repertoire. But every time I'm attacking a new problem—and it's good practice to always spend some time reasoning about solutions yourself—I basically assume that whatever solution I come up with, I'll find something better on the internet.

It is so true that the easiest person to fool is yourself, and these mindsets are a good way to prevent at least some foolishness. First, always question your assumptions. Assumptions are the blind spots that hide obvious mistakes. Second, make sure that when you're comparing ideas, you know exactly what you're comparing and you are comparing exactly what you should to reach a valid conclusion. Finally, assume that whatever solution you come up with, a better one exists, especially if your current solution seems too complicated. Then you have to decide if further optimizations are worth pursuing, or if your current solution is good enough.

Tech Book Face Off: Growing Object-Oriented Software, Guided by Tests Vs. Agile Testing

It's been nearly eight months since I've done a Tech Book Face Off. That is way too long. Granted, I had been reading plenty of other stuff—math books, physics books, and econ books—but it's high time that I got back to some software development books. One area where I thought there was still somewhat of a hole in my understanding was automated testing, so I picked out a couple books on testing that I thought would be good: Growing Object-Oriented Software, Guided by Tests by Steve Freeman and Nat Pryce and Agile Testing: A Practical Guide for Testers and Agile Teams by Lisa Crispin and Janet Gregory.

VS.

I'm not going to lie. Getting through these books was kind of a slog. I had hoped to learn lots of great new insights on how to go about automating tests and working testing into the software development process without going crazy. I found out that pretty much everything I needed to know was already covered in other books I had read, especially Clean Code and Agile Principles, Patterns, and Practices in C#, two books I've reviewed previously.

While I have some misgivings about panning anyone's work because these authors obviously put tons of time and effort into their books, I don't want to mislead any readers about the value that I got out of these books. After all, these reviews are supposed to give my assessment of whether a pair of books is helpful or not. Sometimes both books are good and complement each other nicely, sometimes one is clearly better than the other, and sometimes I don't find either one very useful. I try to describe those opinions as respectfully and honestly as I can while providing some of the reasoning behind those opinions. With that in mind, let's take a look at these two books on agile testing.

Growing Object-Oriented Software, Guided by Tests

The premise of this book is something I totally agree with. In many ways software grows and evolves over time. Freeman and Pryce nicely described three distinct ways that a code base grows and changes through refactoring:

Breaking out: When we find that the code in an object is becoming complex, that’s often a sign that it’s implementing multiple concerns and that we can break out coherent units of behavior into helper types. … Budding off: When we want to mark a new domain concept in the code, we often introduce a placeholder type that wraps a single field, or maybe has no fields at all. As the code grows, we fill in more detail in the new type by adding fields and methods. With each type that we add, we’re raising the level of abstraction of the code. Bundling up: When we notice that a group of values are always used together, we take that as a suggestion that there’s a missing construct. A first step might be to create a new type with fixed public fields—just giving the group a name highlights the missing concept. Later we can migrate behavior to the new type, which might eventually allow us to hide its fields behind a clean interface, satisfying the “composite simpler than the sum of its parts” rule.

I find that a lot of my software design progresses in these ways. The architecture of a system emerges over many iterations, step by step. This constant flux is a characteristic of Agile development in particular, and it can be an issue for teams and management that are new to it. The authors make some good points about that initial discomfort as well:

[I]ncremental development can be disconcerting for teams and management who aren’t used to it because it front-loads the stress in a project. Projects with late integration start calmly but generally turn difficult towards the end as the team tries to pull the system together for the first time. Late integration is unpredictable because the team has to assemble a great many moving parts with limited time and budget to fix any failures. The result is that experienced stakeholders react badly to the instability at the start of an incremental project because they expect that the end of the project will be much worse.

The goal with Agile development is to not end up in crunch time at the end of the project, but instead spread the chaotic stuff more evenly over the full length of the project, making it more consistent and manageable in the long run.

The first part of the book was much like these excerpts with clear, well thought out discussions of TDD (Test-Driven Development). The second part of the book was an extended example of developing an internet auction bidding program with Agile testing principles, and that is what I had a hard time with. It became increasingly difficult to stay interested as the example went on.




There is something to be said for working through a non-trivial example to better show how a process would work in a more realistic project, but the example that they used seemed too complicated to me. Maybe it was because I haven't written in Java since college and I'm not familiar with any Java frameworks. However, I hadn't done much programming in C# before reading Agile Principles, Patterns, and Practices in C#, and I didn't have any problems with the examples used in that book. In this Java example, the authors seemed to pick a bunch of graphics and networking frameworks that required some prior familiarity to understand what was really going on. For all I know, they are common Java frameworks, but using them served to narrow the audience that could follow along. The complexity of the example and the prior knowledge required obscured the message that the authors were trying to get across.

Once the complexity of the application increased, the big ideas tended to get buried in the details of working through the code. The main point that the authors kept coming back to was that encapsulating related functionality enabled programmers to understand the code quickly and change it easily in one place. This is programming nirvana, but it was hard to see how that encapsulation developed through all of the details of their code samples.

Another issue that came up was that after a couple of tasks were completed, it wasn't clear that it was useful to continue with the example. New concepts and benefits of TDD were no longer being demonstrated; we were just plowing through the rest of the example using the same process we already know about. The danger with a long example is that the focus changes from teaching concepts using a demonstration to completing the example for its own sake. It's a difficult balance that I'm well aware of. You start off with good intentions, but as you get further into the example, it takes on a life of its own. After a while you pull back and wonder how you got where you are, and are you really saying what you mean to say anymore. The overarching ideas have gotten lost in the details of the example. In this case, the goal should have been to show how software can grow efficiently while using TDD, not the gritty details of how to implement an auction sniper.

Even though the extended example was a drag, the authors still had some nice insights into practical testing:

Some TDD practitioners suggest that each test should only contain one expectation or assertion. This is useful as a training rule when learning TDD, to avoid asserting everything the developer can think of, but we don’t find it practical. A better rule is to think of one coherent feature per test, which might be represented by up to a handful of assertions. If a single test seems to be making assertions about different features of a target object, it might be worth splitting up.

I like the pragmatic nature of this recommendation. Dogmatically splitting up tests so that each has a single assertion only serves to extend your test time and bloat your test code. When a set of assertions focus on one feature and have the exact same setup and tear down, they should be combined into one test.

Overall, Growing Object-Oriented Software, Guided by Tests was okay, but I can't recommend it. There are much better books out there, and this one didn't add much to my understanding of TDD. If you're an experienced Java programmer that happens to work with OpenFire, Smack, Swing, and the other libraries that they used in their example, you may get more out of it. Otherwise, I would pass this one by.

Agile Testing: A Practical Guide for Testers and Agile Teams

After getting through the last book, I was hoping for something a little more engaging with Agile Testing. This book was written by a couple of testers who have worked on a number of Agile teams and gave their perspective on how testers could fit into the Agile process after the programmers on the team have adopted TDD. Crispin and Gregory make the case that there are many other types of testing that still have a place in improving software quality, and I strongly agree. Automation with unit and functional testing only scratches the surface of the testing that needs to be done for a product, and having dedicated testers on the team that offer their unique perspective and talents is invaluable.

I did find some insights that resonated well:

If you’ve worked in the software industry long, you’ve probably had the opportunity to feel like Lisa’s friend. Working harder and longer doesn’t help when your task is impossible to achieve. Agile development acknowledges the reality that we only have so many good productive hours in a day or week, and that we can’t plan away the inevitability of change.

This is, of course, one of the key arguments for adopting an Agile process, and you'll see similar statements in any Agile book you read. Most of the book was much like this quote—reasonable and well thought-out—when taken in isolation, but taken as a whole, it was excessively verbose and redundant. The authors were constantly discussing the benefits of automated testing, the use of this or that tool during the testing process, or how you really don't want to make an iteration a mini-waterfall process. I felt like they could have easily covered the same amount of material in less than half of the 576 pages they took to do it.

The book was organized into five parts:

• Introduction to Agile Testing
• Organizational Challenges in moving to Agile Testing
• The Agile Testing Quadrants and the different types of testing that makes up each quadrant
• Automation of any testing that warrants it
• An Iteration in the Life of a Tester and how testers fit into an Agile development environment

At a high level it seems well organized, but there was so much overlap between these sections that much of every chapter was repetition and cross referencing. After a while the periodic tidbits of wisdom didn't seem worth the trouble of wading through pages and pages of generalities. Even the beginning of each chapter had an extra repetition of the rest of the chapter with a mind map that exactly duplicated the chapter's section headings. Maybe that's useful to some, but it just added pages to the book for me.

Some of their points were surprising as well. For example:

“AADD,” Agile Attention Deficit Disorder. Anything not learned quickly might be deemed useless. Agile team members look for return on investment, and if they don’t see it quickly, they move on. This isn’t a negative characteristic when you’re delivering production-ready software every two weeks or even more often.

I wrote one small note on my Kindle when I highlighted this quote, "definitely sounds like a flaw to me." This attitude struck me as having a cavalier disregard for deeper thought and more exploratory learning, especially for difficult problems. Maybe it works when you're implementing yet another CRUD app, but some software requires careful research and design to make something that's going to have a big impact. My interpretation of this statement is that I shouldn't be doing Agile Testing if I'm developing ground-breaking software, but I don't think that's really true. I think Agile promotes examining the trade-offs before making a decision on how to proceed, and sometimes the right decision is research and learning. AADD isn't really defensible.

Later in the book the authors talk about the difficulties of bringing new testers up to speed on a project, and they make this recommendation:

This conversation sparked the idea of a FAQ page, an outstanding issues list, or something along that line that would provide new testers a place to find all of the issues that had been identified but for which the decision had been made not to address them.

Ideas like this should be questioned as to whether or not they scale and if they add unnecessary complexity to the process with too many tools. I can't imagine such a thing scaling well at all, and anytime you create documentation that you'll never use personally, it will not be adequately maintained. I find that keeping these kinds of lists up-to-date is nearly impossible when they're not part of some other process that the maintainer does find useful.

The book did contain a few pleasantly surprising nuggets, though. Near the end when the authors were discussing defect tracking software, they claimed:

If your team is working closely with the programmers and is practicing pair testing as soon as a story is completed, we strongly recommend that you don’t log those bugs as long as the programmer addresses them right away.

It's an interesting difference from bug tracking software proponents, and such pragmatic practices can eliminate a lot of tedious bookkeeping.

All in all, I can't recommend this book either. I pretty much heard it all before and it has been presented much better in the other books I've already mentioned. Maybe if you're a tester that's completely new to the Agile process, you'd find Agile Testing much more useful, but I'd hope you could find a more concise resource. As for programmers, The Pragmatic Programmer and Robert Martin's books are more engaging and are all you're going to need.

More Than Enough Testing

I set out to fill what I thought was a gap in my understanding, and found out that other books I read had already covered what I needed to know. I probably didn't need to read either of these books. It was too much reading about testing and not enough practicing. You only need to read a little bit about testing to understand the benefits and how to go about it, and then it's best to spend the time experimenting with it. Clean Code and Agile Principles, Patterns, and Practices in C# are more than enough on the subject of testing for developers.

Test in Moderation

Software testing is a huge topic, and intense debates are going on all the time about what is the best way to do software testing. Test Driven-Development (TDD) has built up a strong following over the past 15 years, and with good reason. TDD can have a lot of benefits if done well. It also has its downsides, and if taken to an extreme, TDD can cause more harm than good. Programmers are justified in pushing back on the more extreme forms of TDD, but we don't want to go to the other extreme, either. Testing is a necessary part of a high-quality development process that increases the odds of releasing highly-functional software. We need to do testing in some form. The real questions are, how should we test and how much?

The intention here is not to focus solely on TDD, although that will be difficult because it's something most programmers are familiar with. What I really want to talk about is testing in general, and TDD is but one piece of the complete testing picture. The rest of the picture includes things like usability testing, code reviews, and quality assurance (QA) testing. Proponents of TDD, when at their most extreme, claim that TDD subsumes and encompasses all other types of testing. They take every possible type of testing, define and categorize them, and put them all under the banner of TDD. It may be a convenient title, but in practice most programmers think of TDD as focusing on unit and integration testing because those are the tests that are most easily automated.

When referring to TDD, the concept I'm thinking of is essentially the same as the one used by Steve Freeman and Nat Pryce in Growing Object-Oriented Software, Guided by Tests:

When we’re implementing a feature, we start by writing an acceptance test, which exercises the functionality we want to build. While it’s failing, an acceptance test demonstrates that the system does not yet implement that feature; when it passes, we’re done. When working on a feature, we use its acceptance test to guide us as to whether we actually need the code we’re about to write—we only write code that’s directly relevant. Underneath the acceptance test, we follow the unit level test/implement/refactor cycle to develop the feature[.]

I'm using 'integration' whereas they use 'acceptance,' but they're pretty interchangeable. It's clear from this explanation of the TDD process that acceptance tests do not include getting the user interface in front of actual users, getting the code in front of coworkers, and getting the product in front of physical, human testers. That's okay. The definition of TDD should be focused, but we shouldn't forget about the rest of the testing picture.

In the Grand Scheme of Things

One great way to step back and see the bigger picture is to do a postmortem on a project (referred to as a retrospective in agile development). Despite the name, don't wait until the project is finished (or dead) to do a postmortem. You can learn a lot from looking back on a project after certain milestones are reached, like major releases, and many software projects are never truly finished anyway.

When I was working for an ASIC design company, we sometimes did a postmortem right before we would release the second revision of silicon for prototyping. This was a perfect time to take a look back at what happened during the previous cycle of silicon evaluation because we were about to send off the design for fabrication again. It would be 6-8 weeks before we'd see the results, and it would be very unlikely that we could fix any mistakes we found after pulling the trigger.

I remember one postmortem in particular that was for a project with a high profile customer. We were aiming to complete the design in two and a half spins—that means the third revision would only change the metal interconnect layers of the design—and as always, we were schedule constrained to get it right. Before releasing the design for the second spin we took a look back at all of the bugs that we discovered during the first silicon evaluation. We had found 35 bugs (pretty respectable for first silicon), and they had varying degrees of severity and scope.

While we didn't discover anything that caused us to delay the next release, we did learn some interesting things about the source of the bugs. Part of the postmortem exercise involved figuring out how we could prevent those bugs that we found in the future. I can't remember the exact numbers, but we found that a significant number of those bugs, like more than half, could not have been prevented with better automated testing and simulations.

Some bugs we definitely should have caught. They were obvious after we had gotten silicon back, the fixes were obvious, and the simulations required to catch the bugs were obviously missing. It's your standard face-palm kind of stuff.

Other bugs had a root cause that didn't originate in the implementation, but in the specification. These were the inevitable misunderstandings of how the product should work, either on our part, the customer's part, or the communication between us. We continually strove to reduce these kinds of mistakes, but there's always room for improvement when it comes to product specifications and customer communication.

Then there were bugs that we could not have predicted would be an issue until we had physical silicon in our hands to test. Similar to most software development, we were doing something that had never been done before, at least by the collection of engineers participating in this project. We knew going in that there would be issues with the design, but we couldn't know what all of them would be. We did try to mitigate the risk by making the design as flexible as possible in the areas where we thought there would be trouble, and we planned for the inevitable bugs with the two and a half spin schedule. It's actually a tribute to the design team that there were so few bugs in first silicon and most of them were of this unpredictable variety.

We ended up shipping revision B2 as planned, and it was one of the most well-executed projects I've had the pleasure of working on. However, the take-away for this discussion is that in spite of our quite rigorous automated testing, we didn't catch every bug that we needed to, nor did we have any hope of doing so even if we devoted ten times the effort to testing simulations.

Imperfections in Testing

The equivalent automated testing in the software world is integration and unit testing, whether it's TDD or not, and Steve McConnell has some interesting statistics on the effectiveness of different types of testing in Code Complete 2:

.. software testing has limited effectiveness when used alone—the average defect detection rate is only about 30 percent for unit testing, 35 percent for integration testing, and 35 percent for low-volume beta testing. In contrast, the average effectiveness of design and code inspections are 55 and 60 percent.

The defect detection rates for unit and integration testing are amazingly low. Similar rates are probably applicable for ASIC simulation testing, and that is why we would have had to put in so much more effort to catch the obvious bugs that got through. During development those bugs are not obvious, and you have to write a ton of extra tests and cover cases that aren't broken to find the few remaining cases that are hiding the bugs. Other types of testing can make those bugs more obvious.

One argument against TDD is based on this issue of missing obvious bugs. The argument goes something like this. If you write the minimum amount of test code to produce a failing test and then write the minimum amount of production code to make the failing test pass, what you’re actually doing is minimizing the amount of production code you write. In the end, you’ll probably write much less error checking code, and you’ll forget to write error checking code for certain conditions or in certain circumstances, letting bugs get through the development process.

I don't think this argument only applies to TDD. You have to think of the error condition where a bug might exist whether or not you're practising TDD. The TDD approach just changes the way you handle error checking during development. If you think of a possible error condition in your code, you write a test for it first to make the failure a reality, and then write code to fix it. Humans are notoriously bad at predicting failure so it may be better to make sure the bug is real before trying to protect against it. TDD doesn't alleviate developers from needing to be diligent about error checking. Although it may help eliminate unnecessary error checking code.

Another argument against TDD came up in a discussion on the Stackoverflow podcast #38. (I know it's old, but history can still be relevant.) Joel and Jeff talk about unit testing, TDD, and the SOLID principles. Joel questions whether TDD and SOLID are agile or not. It's an interesting thought, and I can see how he would come to that conclusion if these practices were taken to their extreme: 100% unit testing, TDD for every single line of production code, and all the SOLID principles applied to every class in the system. Such a code base would be an incredible, unmanageable mess. Especially the interaction of unit testing every single little thing about every class while separating classes into thousands of tiny single-function elements causes the entire design to be very rigid and fragile to change. I shudder at the thought of it.

While it is useful to have an automated test to check code that you've written so that you don't have to keep checking it manually all the time, that does not always trump other factors. Sometimes it is a piece of code that will never break again, and writing the test is way more complicated than the actual code. In some cases it makes sense to not write the test and instead write the code, check it manually, and be done with it. As a general rule, if a test is hard to write—much harder than writing the actual code—think about whether or not to actually write the test. It would have to provide some benefit, like if the code is especially risky, before it's valuable to write and verify a complicated test.

I like the balance that Michael Hartl strikes in his Ruby on Rails Tutorial. Sometimes he uses TDD, sometimes he writes integration tests or unit tests after coding the functionality, and his assertions have a light touch that leaves enough room for the code to be flexible

Expanding the Testing Repertoire

When writing tests, it's best to KISS. If you get too wrapped up in testing it's easy to go overboard, and that can waste a lot of time. There is some intersection of tests that catch bugs and code that is the source of bugs (or code changes that create bugs). That sounds like a venn diagram to me.

 

If you write tests for 100% code coverage, you're creating a huge number of tests and spending the corresponding huge amount of time writing those tests when some percentage of tests will never ever fail, and are thus useless.

Another way to think about this problem is to consider how many bugs are caught as you ramp up the amount of time you spend using a given testing style. For unit testing, as you write more tests it gets harder and harder to find more bugs, and tests start to overlap in the bugs that they catch. This is why 100% code coverage doesn't mean 100% of bugs caught; it only means about 30% of bugs caught. Over time, testing efficiency tends to look like this:

At some point, putting in more effort doesn't give you any more progress. This trend is true of all types of testing. Whether it's unit testing, usability testing, code reviews, or QA testing, testing efficiency is going to saturate at some level below 100% bug-free because different testing styles will catch different classes of bugs. Instead of taking one testing style to the extreme, it's better to mix different testing styles together so that you're hitting your software from multiple angles. If you have a fixed amount of effort that you can dedicate to testing, different mixes of testing styles will result in varying degrees of quality in the final product.

This chart represents what the space of testing efficiency might look like if you could spread out all variations in the mix of testing styles on one axis. Somewhere in that curve would be a point where you did 30% automated testing, 20% code reviews, 10% usability testing, 20% QA testing, and 20% other miscellaneous testing. Maybe 100% automated testing is near that valley on the left. It's really representing a multi-dimensional space on a single axis, and it's purposefully vague because the maximum testing efficiency is going to heavily depend on everything—the product, the problem domain, the experience and skill of the team, the schedule, the customer, and the list goes on. Experience is probably the best remedy for this dilemma because with experience you'll learn what a good mix of testing is for the contexts that you generally develop in.

One thing's for sure. It's not worth hammering on one testing style to the detriment of all others. That's a terrible waste of time. It's better to back off the 100% code coverage goal—trust me, it's a mirage because you're still far from 100% input coverage—and look for other ways to test more effectively. Automated tests are great, but they should be used judiciously where they give you the most benefit by making sure your stuff isn't fundamentally broken. Then, spending some time getting your product in front of real users or having another developer look over your code and talking them through it will provide much more value for your testing time than writing another test that verifies that, yes, your getters and setters do indeed work. Like all things, testing is best done in moderation.