It’s all about context

The C# using directive and implicitly typed local variables (i.e. using var) are Good Things whose use should be encouraged in C# programs, not prohibited or severely limited. Used correctly (and it’s nearly impossible to use them incorrectly), they reduce noise and improve understanding, leading to better, more maintainable code. Limiting or prohibiting their use causes clutter, wastes programmers’ time, and leads to programmer dissatisfaction.

I’m actually surprised that I find it necessary to write the above as though it’s some new revelation, when in fact the vast majority of the C# development community agrees with it. Alas, there is at least one shop–the only one I’ve ever encountered, and I’ve worked with a lot of C# development houses–that severely limits the use of those two essential language features.

Consider this small C# program that generates a randomized list of numbers from 0 through 99, and then does something with those numbers:

    namespace MyProgram
    {
        public class Program
        {
            static public void Main()
            {
                System.Collections.Generic.List<int> myList = new System.Collections.Generic.List<int>();
                System.Random rnd = new System.Random();
                for (int i = 0; i < 100; ++i)
                {
                    myList.Add(rnd.Next(100));
                }
                System.Collections.Generic.List<int> newList = RandomizeList(myList, rnd);

                // now do something with the randomized list
            }
            
            static private System.Collections.Generic.List<int> RandomizeList(
                System.Collections.Generic.List<int> theList,
                System.Random rnd)
            {
                System.Collections.Generic.List<int> newList = new System.Collections.Generic.List<int>(theList);
                for (int i = theList.Count-1; i > 0; --i)
                {
                    int r = rnd.Next(i+1);
                    int temp = newList[r];
                    newList[r] = newList[i];
                    newList[i] = temp;
                }
                return newList;
            }
        }
    }

I know that’s not the most efficient code, but runtime efficiency is not really the point here. Bear with me.

Now imagine if I were telling you a story about an experience I shared with my friends Joe Green and Bob Smith:

Yesterday, I went to Jose’s Mexican Restaurant with my friends Joe Green and Bob Smith. After the hostess seated us, Joe Green ordered a Mexican Martini, Bob Smith ordered a Margarita, and I ordered a Negra Modelo. For dinner, Joe Green had the enchilada special, Bob Smith had Jose’s Taco Platter . . .

Wouldn’t you get annoyed if, throughout the story, I kept referring to my friends by their full names? How about if I referred to the restaurant multiple times as “Jose’s Mexican Restaurant” rather than shortening it to “Jose’s” after the first mention?

The first sentence establishes context: who I was with and where we were. If I then referred to my friends as “Joe” and “Bob,” there would be no ambiguity. If I were to write 50 pages about our experience at the restaurant, nobody would get confused if I never mentioned my friends’ last names after the first sentence. There could be ambiguity if my friends were Joe Smith and Joe Green, but even then I could finesse it so that I didn’t always have to supply their full names.

Establishing context is a requirement for effective communication. But once established, there is no need to re-establish it if nothing changes. If there’s only one Joe, then I don’t have to keep telling you which Joe I’m referring to. Doing so interferes with communication because it introduces noise into the system, reducing the signal-to-noise ratio.

If you’re familiar with C#, most likely the first thing that jumps out at you in the code sample above is the excessive use of full namespace qualification: all those repetitions of System.Collections.Generic.List that clutter the code and make it more difficult to read and understand.

Fortunately, the C# using directive allows us to establish context, thereby reducing the amount of noise in the signal:

    using System;
    using System.Collections.Generic;
    namespace MyProgram
    {
        public class Program
        {
            static public void Main()
            {
                List<int> myList = new List<int>();
                Random rnd = new Random();
                for (int i = 0; i < 100; ++i)
                {
                    myList.Add(rnd.Next(100));
                }
                List<int> newList = RandomizeList(myList, rnd);

                // now do something with the randomized list
            }
            
            static private List<int> RandomizeList(
                List<int> theList,
                Random rnd)
            {
                List<int> newList = new List<int>(theList);
                for (int i = theList.Count-1; i > 0; --i)
                {
                    int r = rnd.Next(i+1);
                    int temp = newList[r];
                    newList[r] = newList[i];
                    newList[i] = temp;
                }
                return newList;
            }
        }
    }

That’s a whole easier to read because you don’t have to parse the full type name to find the part that’s important. Although it might not make much of a difference in this small program, it makes a huge difference when you’re looking at code that uses a lot of objects, all of whose type names begin with MyCompany.MyApplication.MySubsystem.MyArea.

The use of using is ubiquitous in C# code. Every significant Microsoft example uses it. Every bit of open source code I’ve ever seen uses it. Every C# project I’ve ever worked on uses it. I wouldn’t think of not using it. Nearly every C# programmer I’ve ever met, traded email with, or seen post on StackOverflow and other programming forums uses it. Even the very few who don’t generally use it, do bend the rules, usually when LINQ is involved, and for extension methods in general.

I find it curious that extension methods are excepted from this rule. I’ve seen extension methods cause a whole lot more programmer confusion than the using directive ever has. Eliminating most in-house created extension methods would actually improve the code I’ve seen in most C# development shops.

The arguments against employing the using directive mostly boil down to, “but I can’t look at a code snippet and know immediately what the fully qualified name is.” And I agree: somebody who is unfamiliar with the C# base class library or with the libraries being used in the current project will not have the context. But it’s pretty unlikely that a company will hire an inexperienced C# programmer for a mid-level job, and anybody the company hires will be unfamiliar with the project’s class layout. In either case, a new guy might find the full qualification useful for a week or two. After that, he’s going to be annoyed by all the extra typing, and having to wade through noise in order to find what he’s looking for.

As with having friends named Joe Green and Joe Smith, there is potential for ambiguity if you have identically named classes in separate namespaces. For example, you might have an Employee class in your business layer and an Employee class in your persistence layer. But if your code is written rationally, there will be very few source files in which you refer to both. And in those, you can either revert to fully-qualified type names, or you can use namespace aliases:

    using BusinessEmployee = MyCompany.MyProject.BusinessLogic.Employee;
    using PersistenceEmployee = MyCompany.MyProject.Persistence.Employee;

Neither is perfect, but either one is preferable to mandating full type name specification in the entire project.

The code example still has unnecessary redundancy in it that impedes understanding. Consider this declaration:

    List<int> myList = new List<int>();

That’s like saying, “This variable called ‘myList’ is a list of integers, and I’m going to initialize it as an empty list of integers.” You can say the same thing more succinctly:

    var myList = new List<int>();

That eliminates the redundancy without reducing understanding.

There is some minor debate in the community about using var (i.e. implicit typing) in other situations, such as:

    var newList = RandomizeList(myList, rnd);

Here, it’s not plainly obvious what newList is, because we don’t know what RandomizeList returns. The compiler knows, of course, so the code isn’t ambiguous, but we mere humans can’t see it immediately. However, if you’re using Visual Studio or any other modern IDE, you can hover your mouse over the call to RandomizeList, and a tooltip will appear, showing you the return type. And if you’re not using a modern IDE to write your C# code, you have a whole host of other problems that are way more pressing than whether or not a quick glance at the code will reveal a function’s return type.

I’ve heard people say, “I use var whenever the type is obvious, or when it’s necessary.” The “necessary” part is a smokescreen. What they really mean is, “whenever I call a LINQ method.” That is:

    var oddNumbers = myList.Select(i => (i%2) != 0);

The truth is, they could easily have written:

    IEnumerable<int> oddNumbers = . . .

The only time var is absolutely necessary is when you’re working with anonymous types. For example, this code that creates a type that contains the index and the value:

    var oddNumbers = myList.Select((i, val) => new {Index = i, Value = val});

I used to be in the “only with LINQ” camp, by the way. But after a while I realized that most of the time the return type was perfectly obvious from how the result was used, and in the few times it wasn’t, a quick mouse hover revealed it. I’m now firmly in the “use implicit typing wherever it’s allowed” camp, and my coding has improved as a result. With the occasional exception of code snippets taken out of context, I’ve never encountered a case in which using type inference made code harder to understand.

If you find yourself working in one of the hopefully very few shops that restricts the use of these features, you should actively encourage debate and attempt to change the policy. Or start looking for a new place to work. There’s no reason to suffer through this kind of idiocy just because some “senior developer” doesn’t want to learn a new and better way to do things.

If you’re one of the hopefully very few people attempting to enforce such a policy (and I say “attempting” because I’ve yet to see such a policy successfully enforced), you should re-examine your reasoning. I think you’ll find that the improvements in code quality and programmer effectiveness that result from the use of these features far outweigh the rare minor inconveniences you encounter.

How to waste a developer’s time

A company I won’t name recently instituted a policy that has their two senior developers spending a few hours per week–half hour to an hour every day–examining code pushed to the source repository by other programmers. At first I thought it was a good idea, if a bit excessive. Then I learned what they’re concentrating on.

Would you believe they’re concentrating on things like indentation, naming conventions, and other such mostly lexical constructs? That’s right, they’re paying senior developers to spend something like 10% of their time doing a job that can be done more accurately, more completely, and much faster by an inexpensive tool that is triggered with every check-in.

And they wonder why they can’t meet ship dates.

Style issues are important, but you don’t pay your best developers to play StyleCop. If they’re going to review others’ code, they should be concentrating on system architecture issues, correctness, testability, maintainability, critical performance areas, and a whole host of high-level issues that it takes actual human intelligence to evaluate.

Having your best developers spend time acting like mindless automatons is not only a huge waste of money and talent, it’s almost guaranteed to cost you a senior developer or two. I hope, anyway. Forcing any developer to play static analyzer on a regular basis is one of the fastest ways to crush his spirit. And any developer who’s worth the money you’re paying him will be working for your competitor in no time flat rather than waste his time doing monkey work.

The drawbacks of having your senior developers spend their time examining code for style issues:

  • They can’t do as good a job as StyleCop and other tools.
  • They can’t do it as fast as StyleCop and other tools.
  • They can’t do it on every check-in.
  • There are much more important things for them to spend their time on.
  • They hate doing it.
  • They will find somewhere else to work. Some place that values their knowledge and experience, and gives them interesting problems to solve.

Benefits of having your senior developers spend their time examining code for style issues:

  • ??

Solving the right problem

As programmers, we sometimes lose sight of the problem we’re supposed to solve because we’re focused on the problem we want to solve. Or perhaps on the problem we think we need to solve. Today’s lesson is a case in point.

Imagine you have a very large collection (many thousands) of records that contain individuals’ names and their skills. The data consists of a name followed by a comma-separated list of skills. Something like:

Jim Mischel, programming, wood carving, brewing, curmudgeon

The problem is that some of the skills are misspelled or abbreviated: “mgmt” for “Management,” for example, or “hadup” instead of “Hadoop,” etc.

Your job is to go through the records and fix the misspellings.

Seems easy enough, right? Just go through the skills, look up each word in a dictionary, and correct the entry if the word isn’t in the dictionary. But there are two problems:

  1. A lot of common terms used in describing skills are domain specific and won’t be in any dictionary.
  2. Even if there were such a dictionary, how would you determine that “mgmt” is supposed to be “Management,” or that “hadup” should be “Hadoop?”

It’s at this point that we lose sight of the real problem we’re trying to solve. Being programmers, we start thinking about figuring out edit distances, machine learning, support vector machines, etc. In no time at all we’re shaving a yak.

Writing a computer program that will detect and correct misspellings like this is hard. I’m talking Ph.D. research project hard. I guarantee that the person who asked you to solve the problem isn’t willing to let you embark on a multi-year research project.

Fortunately, you don’t have to. You can solve it in a day or two with two simple programs and a little bit of manual effort.

First, write a program that builds a dictionary of all the terms used, along with how often they’re used. You’ll end up with a very large list that looks something like:

    Management,200
    Mgmt,3
    Hadoop,10
    Hadup,1
    Mamagement,1
    ...

If you make the assumption that if a term appears very often, it’s probably spelled correctly, then all you’re really concerned about are those terms that occur infrequently. You can decide on a threshold of, say, three or five, and have your program output only those terms. You’ll probably end up with a list of a few hundred infrequently used terms.

That’s where the manual work comes in. You have to look at each word, determine if it’s a misspelling, and if so find out what the correct spelling is. You manually create a file that contains the misspelled term along with the correct term. For example:

    mgmt, Management
    mamagement, Management
    hadup, Hadoop
    wood craving, wood carving
    etc.

The second program is even easier. All it does is load the replacements file into a dictionary with the key being the misspelled term, and then reads each name record. For each name record, the program checks each term against the dictionary. If it finds a misspelling that’s in the dictionary, it writes the replacement. Otherwise, it writes the original text. The algorithm looks like this:

    dict = LoadDictionary();
    create output file
    for each record in file
        output name
        for each skill in record.skills
            if skill in dict
                output replacement text
            else
                output original skill text

This approach won’t be perfect, but it will be very good. You’ll have to tinker with the threshold value a bit to get the right balance between detecting real misspellings and “false positives”: terms that are used infrequently but aren’t actual misspellings.

You’ll also have to accept that common misspellings will not be detected. Fortunately, common misspellings will be … common. So you can add them to the replacements dictionary as they’re detected, and subsequent passes over the file will catch them. You could do some work with edit distance algorithms to catch the more common misspellings, but it would be a huge amount of work for relatively little gain.

I’ll admit that it’s somewhat dissatisfying having to manually create the replacements file, but it’s hard to argue with the result. Especially if I can get somebody else to do that work. Then all I have to do is create the list of terms and their counts, and write the program that will make the replacements once the manual work is done.

It’s not sexy, but it solves the problem quickly and effectively.

Hash codes are not unique

It’s surprising how often I hear (or see written) a programmer saying, “…and then I’ll compute a unique hash code that I can use for a key.”

The term “unique hash code” is a red flag indicating that the programmer who uttered it does not understand hash codes and is about to do something incredibly stupid. Let me provide a simple example.

In .NET, every object has a GetHashCode method that computes a 32-bit number that can serve as a key in a dictionary or hash table. Used properly, the hash code lets you create very efficient data structures for looking things up by name. But there’s no magic involved, really.

Used as intended–as the keys in a dictionary or hash table–hash codes work very well. If you try to use them for something else, it’s not going to work.

Let’s say you foolishly decide to use a hash code for a “unique key” when indexing some strings.

The number of strings is essentially infinite. The number of unique values that a 32-bit hash code can represent is a little more than four billion. So it’s a certainty that two or more strings will produce the same hash code. You might think, if you’re only storing 100,000 values, that the chance of collision (two strings hashing to the same value) is so small as not to matter. You’d be wrong.

If you’re familiar with the Birthday Paradox you know that, in any group of 25 people selected at random, the chance of two having the same birthday (month and day) are better than 50%. In a group of 60 people, it’s almost a certainty. If you don’t believe the math, you can do some empirical research of your own.

Hash codes are a lot like birthdays in this regard. A good rule of thumb is that the chance of collision (two items hashing to the same value) is 50% when the number of items hashed is equal to the square root of the number of possible values. So with a 32-bit hash code, the chance of two items hashing to the same value will be 50% when you’ve hashed 2^16, or 65,536 items. Again, if you don’t believe me just write a program that generates random strings and try it.

Another rule of thumb is that you’re almost certain to get a collision when the number of items is four times the square root. So with a 32-bit hash code, the chance of getting a collision when adding 256,000 items is almost 100%.

This is second year Computer Science stuff. Maybe even first year? And yet I hear the term “unique hash code” thrown around distressingly often by experienced programmers who should know better. It’s frightening.

If you’re interested in a bit more discussion and some sample programs that illustrate this point better, see Birthdays, Random Numbers, and Hash Keys.

In praise of technical debt

The term “technical debt“, as commonly used, refers to the eventual consequences of poor software design decisions or development practices. The Wikipedia article and most other references consider technical debt to be a Very Bad Thing. The literature is filled with examples of development projects whose combined technical debt eventually killed or seriously hampered the company.

There is a huge amount of literature about techniques that claim to reduce or eliminate technical debt, and there are countless design patterns and development practices to go along with all that talk. Those patterns and practices are usually ways of paying up front in order to avoid having to pay more later. And to the extent that they actually meet that standard, using them to avoid technical debt is a Good Thing.

Unfortunately, those techniques intended to avoid technical debt often cause more problems than they solve, and end up costing more than it would have cost to incur the debt.

It seems every software development pundit preaches a “no technical debt” sermon with the fervor that some misguided financial advisors preach a debt-free lifestyle. And, unsurprisingly, they all have their books, articles, software packages, and training programs that will teach you how to avoid technical debt.

Yes, there’s a lot of hype and snake oil in the software development “Best Practices” business.

Just as there are sound financial reasons to incure financial debt, there are sound business and technical reasons to incur technical debt. In fact, I think technical debt is more often a Good Thing. It takes a very strong argument to convince me not to incur many kinds of technical debt.

The comparison of technical debt to financial debt isn’t perfect. When you take out a loan at a bank or other lending institution, you agree unconditionally to repay the money you borrowed, with interest. I know of only two ways you can avoid paying: bankruptcy and death. In bankruptcy, you might have to pay back some of the debt, and if you die you might leave somebody else with the obligation. And, of course, there are the ongoing interest payments. Financial debt is never free.

Technical debt, on the other hand, often doesn’t need to be repaid, and often has no interest payments. It’s a “free loan.” Not always, but in my experience more often than not. And when it does have to be repaid, the cost is usually quite reasonable.

A good example of technical debt causing a problem is in the development of a Web site. Imagine that you have an idea for a new site. You slap something together in a few days or weeks, post it on your site, and it’s immediately a hit. Within weeks you’re getting more traffic than your poor server can handle. It’s pretty easy to expand your site to use more Web servers, but then your back end database server melts down under the load. That, too, is easily expanded, but eventually you reach a point where some critical component of your system is the bottleneck and there’s no easy way to scale it. Adding a faster server with more memory and a faster hard disk just postpones the problem.

You incurred the technical debt when you slapped together a simple Web site without taking into account the possibility of massive scaling, and now it’s time to repay that debt. And it’s painful. You also have to do it pretty quickly or all your customers will move over to your competitor who spent six months developing a copycat site. You might find yourself, as you crawl in bed at 9 A.M. after another sleepless night trying to retrofit your program, lamenting the decision to ignore the scaling problem in favor of getting something working. And you vow never to do that again.

That’s the wrong attitude to have.

To hear the “no technical debt” preachers tell it, the world is full of failures who would have succeeded had they not taken on the technical debt. And they’ll show you the successes who refused to incur technical debt, opting instead to spend the extra time required to “do it right” up front. What they won’t tell you about, because they don’t know of or choose not to mention, are the many successes who just “slap things together” and deal with the consequences successfully, and the many projects that fail despite “doing it right.” Most sites fail, not because they didn’t develop their software correctly, but because their product idea just didn’t fly. It doesn’t matter how well your code base is constructed if your business idea just doesn’t work.

The “no technical debt” preachers are wrong, plain and simple. They’ll have you believe that any technical debt will crater your project. Even those who say that you should repay technical debt as soon as possible are wrong. As with financial debt, the secret to managing technical debt is to examine each case and make an informed decision. You have to balance the likelihood of having to repay the debt against the cost of repaying it. It’s a simple (in concept, sometimes not in implementation) risk / reward calculation. What is the risk of incuring the debt, and what is the potential reward?

In the case of our hypothetical Web startup, the risk is that your server melts down before you can modify the code to be more scalable. But the likelihood of that risk is pretty darned small. First, you have to build something that people actually care about. The truth is that most Web startups turn on their servers and hear crickets. A few people will come to check it out, yawn, and move on to the next cool new thing. If that happens, you’ll be really happy that you didn’t waste a bunch of time writing your code to support massive scaling.

Even if your site starts getting traffic, it’s not like you’ll get a million dedicated users the first month. You’ll see traffic growing, and you’ll have time to refactor or rewrite your code to meet the increased demand. It might be painful–rewrites often are–but it’s unlikely that traffic will increase so quickly that you can’t keep up with it.

Some developers attempt to design for scalability to start, and in doing so end up making everything scalable. They spend a lot of time building a scalability framework so that every component can be scaled easily. Every component is split into smaller pieces, and each of those pieces is built to be scaled. That sounds like a good idea, but there are huge drawbacks to doing things that way.

The first problem is that not all components need to support massive scaling. In most software systems, there are one or two, or at most a small handful of, components that are bottlenecks. Designing those to be scalable is a Good Thing. Time spent making anything else scalable is a waste of resources. Even the time spent on those things you think will be bottlenecks is often a waste, because it’s incredibly difficult to tell where the bottlenecks will be before you have customers banging on your site. In all too many cases, designing for scalability is like attempting to optimize a program as you’re writing it–before you do a performance analysis to determine where the bottlenecks are.

Designing for scalability makes the code more complicated. Techniques like dependency injection and inversion of control are very effective ways to create more flexible systems, but they make the code more complicated by inserting levels of indirection that often are difficult to follow. Taken to their extremes, these and similar techniques create a bloated code base that is less maintainable and harder to change than the “old style” code they replace. This is especially true when a development team loses sight of the objective (make something that works) in favor of the process. When you see a system that has a nearly one-to-one mapping between interface and implementation, you know that the people who designed and wrote it lost sight of the forest because they were too busy examining the trees.

Those who preach these techniques for reducing or eliminating technical debt assume that you know what you want to build and how you want to build it, and that you have the time and resources to become fully buzzword compliant. In the case of a startup business, none of those three things is true. Startups typically have a few guys, an idea, and lots of enthusiasm. They’re going to try things, quickly building a prototype, making it available for others to look at, and then discarding it to try something else when that idea fails. Eventually, if they’re lucky, they’ll hit on something that seems to resonate, and they’ll start concentrating on that idea. That’s the nature of a startup. Those guys are living on ramen noodles and little sleep, hoping that one of their ideas strikes a nerve before the savings runs out. They don’t have time to waste worrying about things like technical debt.

Fred Brooks, in his 1975 book The Mythical Man Month, famously said:

The management question, therefore, is not whether to build a pilot system and throw it away. You will do that. […] Hence plan to throw one away; you will, anyhow.

That’s as true today as it was back then. Time spent making your first prototype scalable is wasted. You’re going to throw it away. If you’re lucky, you’ll reuse some of your underlying technology. But most of what you write in your first attempt will be gone by the time you finish the project.

As an aside, there are those who say that The Mythical Man Month is outdated and that many of its lessons are irrelevant today because we have faster, more powerful, and less expensive computers, better tools, and smarter programmers. I’ve seen studies showing that programmer productivity is five to ten times what it was 35 years ago. Whereas programmers can do more in less time today, we’re also trying to build systems that are two or more orders of magnitude larger and more complex than the systems being built back then. Brooks’ cautions are more pertinent today than they were in 1975 because teams are larger and the problems we’re trying to solve are more difficult.

Avoiding technical debt is like paying for flood insurance and building a dike around your house when you live on the top of a mountain in the desert. Sure, it’s possible that your house will flood, but it’s highly unlikely. And if the water does get that high, you have much more pressing problems that make the insurance policy and the dike irrelevant. You’ve wasted time, money, and other resources to handle an event that almost certainly won’t ever occur, and if it does occur, your solution won’t matter one bit.

So go ahead and incur that technical debt, but do so intelligently, with full knowledge of what it will cost you if it comes due. But know also that in many, perhaps most, cases, you’ll never have to pay it.

Bloom Filters in C#

As I’ve mentioned before, writing a Web crawler is conceptually simple: read a page, extract the links, and then go visit those links. Lather, rinse, repeat. But it gets complicated in a hurry.

The first thing that comes to mind is the problem of duplicate URLs. If you don’t have a way to discard URLs that you’ve already seen, you’ll spend most of your time revisiting pages. The naive approach of keeping an in-memory list of visited URLs breaks down pretty quickly when the number of visited sites moves into the tens of millions. Overflowing that list to disk also has problems: maintaining a sorted index and searching that index quickly are very difficult problems. Databases can handle many billions of records fairly quickly, but I don’t know of a database that can keep up with a distributed crawler that’s processing almost 1,000 documents per second, each of which has an average of 100. [As an aside, I was very surprised to find that the average number of links per HTML page–this is based on examining several million documents–is about 130. I would have guessed 15 or 20.]

I ran across a mention of Bloom filters while reading about a different Web crawler. I’ll let you get the detail from the linked Wikipedia article, and just say that a Bloom filter is a space-efficient way of allowing you to test for inclusion in a set. It uses hashing, but has a much lower false positive rate than a simple hash table. The cost is slightly more processing time, but the memory savings and decreased false positive rate are well worth the cost. Besides, my crawler is not at all processor bound.

I coded up a C# class to experiment with Bloom filters, and compared it with a simple hash table. The code along with more detailed explanation is available in my new article, Bloom Filters in C#.

A new file system primitive?

A problem I was working on recently got me to wishing that I could lop off the front of a file. Kind of like a “truncate at front,” if you will. Truncating a file at the back end is a common operation–something we do without even thinking much about it. But lopping off the front of a file? Sounds ridiculous at first, but only because we’ve been trained to think that it’s impossible. But a lop operation could be useful in some situations.

A simple example (certainly not the only or necessarily the best example) is a queue. You’re adding new items to the end of the file and pulling items out of the file from the front. The file grows over time and there’s a huge empty space at the front. With current file systems, there are several ways around this problem:

  • As each item is removed, copy the remaining items up to replace it, and truncate the file. Although it works, this solution is very expensive time-wise.
  • Monitor the size of the empty space at the front, and when it reaches a particular size or percentage of the entire file size, move everything up and truncate the file. This is much more efficient than the previous solution, but still costs time when items are moved in the file.
  • Implement a circular queue in the file, adding new items to the hole at the front of the file as items are removed. This can be quite efficient, especially if you don’t mind the possibility of things getting out of order in the queue. If you do care about order, there’s the potential of having to move items around. But in general, a circular queue is pretty easy to implement and manages disk space well.

But if there was a lop operation, removing an item from the queue would be as easy as adding one. As easy, in fact, as truncating a file. Why, then, is there no such operation?

Disk files are typically allocated in fixed-size blocks: four kilobytes, for example. If you create a file and only put one character in it, the file system will allocate an entire block for that file. The file allocation table (or equivalent structure) associates the file name with that particular block, and also stores either the length of the file, or the offset in the block of the last used byte.

If a file exceeds the block allocation size, the file system allocates another block, links it to the previous block, and updates the file size or last byte pointer. In this way, files of arbitrary size can be allocated and disk fragmentation is kept, if not to a minimum, at least manageable.

Truncating a file is a very simple and quick operation. If the truncation is within the last allocated block, all the file system has to do is adjust the file size. If truncating removes allocated blocks, the file system adjusts the file size pointer into the final used block and then frees any following blocks that were used by the file.

A lop operation (chopping off the front of the file) would be similarly easy to implement if the file allocation table maintained an “offset to first byte” pointer similar to the file size pointer. If you wanted to lop the file off at position 10, for example, the file system would just have to update the pointer. If a lop occurred in something other than the first block of the file, the file system would have to adjust the pointer into that block, make that block the first block of the file, and then free the previous blocks. Simple and neat.

The only real cost is a few extra bytes for each directory entry in the file allocation table. In the past, when disk space was expensive and precious, the idea of even one extra byte per directory entry was unthinkable. But with terabyte hard drives appearing on the market for $400 (yeah, 40 cents per gigabyte), the idea of saving a few bytes per directory entry is just silly. Even if we allocated four bytes per directory entry (which is overkill, considering that most file systems use block sizes that are less than 64K, which would require only two bytes), we’re only talking one megabyte for every 250,000 files. On my laptop, where I have about 140,000 files occupying 30 gigabytes, that works out a little less than one megabyte per 50 gigabytes, or 0.002% of disk space. Seems like a win to me.

Are there other reasons why file systems don’t implement a lop operation? What other operations could file systems implement if designers started worrying less about using a few extra megabytes here and there?

Multithreaded programming

I’ve been head-down here working on the Web crawler and haven’t had much occasion to sit down and write blog entries. It’s been a very busy but interesting and rewarding time. A high performance distributed Web crawler is a rather complex piece of work. I knew that it would be involved, but there’s a lot more to it than I originally thought. Managing hundreds of concurrent socket connections on a single machine and coordinating multiple machines gets complicated in a hurry.

It’s been a long time since I did any serious multithreaded programming, and I’m re-learning some lessons:

  • When there are multiple threads, everything is subject to concurrency issues.
  • Unless you can guarantee that a data structure cannot possibly be accessed by more than one thread of execution at a time, you will eventually experience a problem if you don’t protect it with some kind of synchronization lock.
  • You’ll find that guarantee very difficult to make.
  • It can take hours or days before your program crashes inexplicably.
  • It can take just as long to find that one place where you forgot to protect a global data structure with a mutual exclusion lock.
  • If you’re developing a multithreaded application on a single processor machine, you’ll invariably end up finding more bugs when you move to a dual processor machine where the computer really can do more than one thing at a time.
  • Learn how to use trace logging and prepare to spend a lot of time examining the log files for problems.
  • Race conditions and deadlocks are facts of life, difficult to predict, and painfully obvious in retrospect.

It’s really good to be programming again.

Tales from the Trenches: The Forth Incident

In my first games programming job, I took over development of a game that the original designer had started.  He had written a “first playable” version that included basic game play and graphics.  My task was to work with the publisher to complete the design, and then implement that design.  The contract called for a Windows version and a version for the Macintosh.  Since we didn’t have any in-house Macintosh experience, we contracted with another development firm to complete the Mac version.

The entire project was written in C.  We wrote all of the internal game logic to be platform independent so that it could compile without change on either platform.  I put all of the Windows-specific user interface code in separate modules, and had a very strict separation between platform-specific and platform-independent code.  Such was common practice, and it had worked well for us in other projects that we had developed for multiple platforms.  All the other programmer had to do was develop the Mac-specific user interface and attach it to the base game logic.  Simple, right?

The first few milestones in the Mac port came and went, with the programmer showing good progress on the port.  One day, however, we got a call from the owner of the other development house.  He had to fire the programmer who had been working on the game.  Why?  Because the programmer–a very junior developer who was working at his first job–had decided that it would be easier to throw out the 20,000 lines of fully-tested platform-independent C code and replace it with entirely new code written in Forth.  Let’s just say that none of us involved in the project was very happy about that.

I don’t have anything against Forth as a programming language, and I’ll be the first to admit that my C code didn’t present the best possible interface, but discarding a large body of existing and proven code in favor of something new is almost always a bad idea.

This “throw it away and start over” mentality is very common among junior developers who don’t understand that things are usually much more difficult than they appear.  They think that it’s easier and faster to rewrite code from scratch than to take the time to study and understand the existing interfaces.  Besides, implementing user interface code isn’t nearly as cool or interesting as developing core game logic.  And we all know how programmers will favor cool and interesting over tedious UI hacking.

Ultimately, of course, the blame lies squarely on the project manager who let several milestones go by before performing even a cursory inspection of the code.  Had he examined the programmer’s work at the first milestone, it would have saved him a whole lot of time, money, and heartache.  He had to pull a programmer from another project so that they could finish our contract in time.

The moral of the story is twofold.  First, a complete rewrite takes longer than you think, especially if you don’t fully understand what you’re rewriting.  Not only that, the new code probably has a large number of non-obvious bugs that probably existed in the old code, but were fixed over time.  The old code, as clunky as it might appear, contains a whole bunch of hard-won knowledge that will almost certainly be lost in a rewrite.

Secondly, programmers need supervision, especially junior programmers at the beginning of a product development cycle.  You have to live with your early decisions throughout the product cycle, and any mistake you make early on will be very expensive to fix as time goes by.  It’s imperative that managers keep an eye on the development team’s early decisions.

Attitude matters!

The following is the final paragraph of an email that I received from the lead developer on a large enterprise software system.  He was debugging a performance monitoring application and that lead him to problems in all parts of the system.

I’ve uncovered many more problems in the last 80 or 90 hours of debugging, too many to list or bother to discuss at length.  Error handlers were completely missing or completely wrong, logging was incomplete or missing, copy and paste errors were propagated over and over again instead of using proper sub-classing.  Some of these problems were simple defects, and others were the side effects of code entropy and general complexity weighing in our team.  To be fair, many of the bugs had my own handwriting on them.  But many of them were the product of laziness and general indifference on the part of the developers.  Every time I embark on one of these marathon debugging efforts, I’m always surprised at how much we have, and how much of the code is poorly written or never traced.  But it’s the indifference to the problem that’s really troubling.  Please be sensitive to the fact that the code you write impacts the other people on your team, and if you fail to take ownership of it and do a good job, somebody else might be forced to do so, at tremendous personal expense.  Your work impacts the product, the people, our productivity and more generally our revenue, directly.  That being said, I’m tired and frustrated, but not discouraged.  I’m hopeful that our recently expanded team will lead us to improved productivity and allow us to focus more on quality than we have been able to in the past.

The the product in question will remain anonymous, although I will say that it is not a project that I am personally involved with.  The particular product isn’t relevant anyway as this kind of thing is common, especially in mature software systems that have undergone several generations of enhancements.  Developers who have been on the project for a long time get bored and lazy, and younger developers often don’t understand the finer details of the coding standards (error checking and usage patterns, especially) that have become almost automatic for those who have been with the product since its inception.  The result is inconsistent and often buggy code that is difficult to debug and maintain.

There’s not much else I can add beyond what my friend wrote.  Attitude matters in programming, perhaps more even than aptitude.