Reliable Systems

As part of the product set that my company develops we are being very aggressive about automated unit testing and validation. Our product is used primarily by companies that operate custom developed software systems to monitor and ensure they have reliable systems, and accordingly they expect it to do no harm and essentially be lean, mean, and bulletproof. One of our set of unit tests was designed to ferret out problems by varying numeric inputs by their smallest increment and checking the output for discontinuities. This technique had proven surprisingly effective at discovering a range of existing defects in everything from the Intel and AMD processors through the .NET runtime. When we would find an issue, we’d verify it and then put a workaround in our calculation routines so that our users wouldn’t have to worry about them.

Recently we were introducing a new set of 64-bit specific tests and ran into a challenge: It wasn’t possible to exhaustively validate the routines. Our automated build system can run around 500,000 tests per second, meaning it takes about 2.5 hours to process all possible 32-bit values. But, to cover all 64-bit values we’d need to run that 2.5 hour test about 4 billion times. This works out to be well over a million years, give or take a rounding error of all recorded history. We intuitively knew the test would take a while, and had bandied about a range of possible times, but in the end we failed to comprehend that 64-bits is the square of 32-bits.

That’s A Big Twinkie

Think about it. In your life you often have to deal with linear approximation and even multiplicative approximation, but never exponential. About the biggest effect we can intuitively get our head around is an order of magnitude - 10 times a value. If you see one car, you can visualize 10, possibly then mentally extend that to 100 (two orders of magnitude) by mentally creating ten rows of ten cars. Now go one more order of magnitude to 1000 by say visualizing a 10 story parking garage with each floor having 100 cars. By going an order of magnitude at a time, you can get through around three before it becomes meaningless. That is roughly the difference between one megabyte and one gigabyte. This is a ratio we’ve developed some familiarity with: Memory has (until very recently) generally been thought of in megabytes and hard drives in gigabytes. Only in the past year or two has it become commonplace to talk about memory in gigabytes and hard disk space in terabytes, each around 1000 times greater than their predecessor.

But what we’re talking about with the difference between 32 and 64 bits isn’t about orders of magnitude. A 64-bit value can contain over 4 billion sets of 4 billion values each - nearly 100 orders of magnitude greater. In traditional Big-O notation for understanding algorithmic complexity you drop out purely additive or multiplicative affects as inconsequential and focus on exponential effects. Despite having been both trained in this and working around complex software for nearly two decades, with the incredible increase of processing power in the last 10 years it has become very easy to forget that things can still take real time to calculate, sometimes nearly infinite time.

The Last of My Lifetime?

We have also become conditioned that every doubling in bit width is only a temporary reprieve: In my career we’ve gone from 8 to 16 bit, 16 to 32, and now are starting 32 to 64. It’s natural to project forward and assume that we’ll similarly need to move to 128 bit within a decade, but these doublings in bit widths are exponential increases in size, and the step from 32 to 64 is vast in the amount of area it opens up. When Windows NT shipped with 32 bit support, it was possible to buy a computer with 1 GB of RAM or one quarter the entire 32 bit address space. That would require approximately one billion gigabytes of memory to equal for 64 bit. Just to purchase that would require around 25 billion dollars today, and would nearly consume the entire world production of DRAM for one year. It isn’t the same game anymore, we aren’t going to see 128-bit memory spaces any time soon, at least not for the traditional reasons we’ve upped bit width. To a certain degree that’s a shame - Having gone through the other transitions before which were the cause of years of trauma to hardware and software developers alike I’ve been amazed at how our entire .NET product just worked the first time on 64-bit. That’s progress.