Joe Ganley

I make software and sometimes other things.

 

Due to Blogger's termination of support for FTP, this blog is no longer active.

It is possible that some links from here, particularly those within the site, are now broken. If you encounter one of those, your best bet is to go to the new front page and hunt for it from there.

Most, but not all, of the blog's posts are on this page; the archives are here.

 

I just ran across a pretty good CACM article on API design. This is a topic I feel very strongly about. In numerous interviews, as I was touting my user-interface design skills, my interviewer has said something along the lines of, "But ours is a batch-mode product; it doesn't have a user interface." My usual response to this is that all programming, especially API design, is user-interface design. The exact same principles that make a good user interface apply to a programming API, and indeed to programming in general. A program is (among other things, obviously) a user interface between programmers, including between you and your future self. A poorly-designed API (or more generally, poorly designed code) is a long-term source of friction, and as with most design work, extra time spent at the beginning to create a usable interface can have a tremendous return on investment.

As that article mentions, a really good API almost disappears. Methods exist to do what you want, they are named what you expect them to be, and they do what you need them to without requiring any gymnastics of the sort described in the article. The only two APIs I've ever seen that come close to what I would consider the gold standard are Qt and OpenAccess (disclaimer: I worked on the latter, so I may be biased there).

A search for API usability guidelines turns up a number of good resources on the topic, such as this one and this one.

Labels: , , ,

Comments (0)
 

I ran into a bug the other day that I've run into enough times in my career that I thought it was worth sharing.

One of the perils of C++ is that it does certain things behind your back, and if you don't understand what those things are, they can bite you. One way this manifests is that apparently meaning-preserving changes can have surprising consequences.

In this recent case, I inherited some code that I was cleaning up. One of the changes was to change this:

SomeClass foo;
foo = factory.getSomeClass();
into this:
SomeClass foo = factory.getSomeClass();
Simple enough, right? But after making this change, a later access to foo segfaulted.

Can you guess why? Here's a hint: SomeClass uses a reference-counted shared-data implementation, similar to std::string.

Here's what happened: SomeClass had defined an assignment operator, but not a copy constructor. The old code used the former, and the new code used the latter. In the absence of a user-defined copy constructor, the compiler generates one that just does a bitwisememberwise copy. As a result, the reference count is copied and not incremented, and so later it becomes 0 before it should, and the data is deleted. A subsequent access to that data produces the segfault.

The solution is simple: Define a correct copy constructor. My own policy is never to rely on the compiler-generated copy constructor and assignment operator. When I write a new class, if I think I don't need these, I immediately add method prototypes for them that are private and have no implementations. Then, if you ever invoke them (deliberately or not), the compile will fail, and you'll know that you have to implement them for real (or change the calling code).

Labels: ,

Comments (0)
 

This is the story of the biggest mistake I've made in my professional career. (I say I; there were other people involved, but it was as much my fault as anyone's.) It was early in my career, and I was tasked with building a new algorithmic optimization system from the ground up. This meant we needed a database; this is a database of geometric objects and connectivity, not the kind people normally think of when they hear the word database. This is exactly what OpenAccess, which I helped develop some years later and which had it existed back then would've allowed me to avoid this whole fiasco, is.

When I came on board, we needed a prototype done, like, yesterday. So I slapped together the quickest, dirtiest database that could possibly work, with the intention that eventually it would be replaced by something more production-worthy. That may have been a mistake too, but it's not the big one that the title refers to.

Fast-forward about a year. The prototype is done, and is producing fantastic results. We've written a real database, and it is time to move the system onto it. Here's the big mistake: I did that as open-heart surgery, completely ripping the system apart and replacing the old database calls with new ones. The data model had changed substantially, so this was a major effort, not just a syntactic change, and calls to the database were woven through the entire codebase; to make another surgical analogy, imagine trying to replace all of a person's nerves. There was a period of a couple of months in which the system did not work at all. Eventually we got it running, and then there were several weeks of debugging - just plain old bug fixes, many of them fixing bugs that had probably already been fixed in the old version but the fixes were lost with the old database calls.

Meanwhile, we weren't able to just freeze the old system in carbonite; we needed to continue improving it, competing in benchmarks, and the like. So it continued to evolve forward from the code base that had been used to begin the conversion. Had the new version ever worked properly, we would have had to make all of the same improvements to it when we were done that we had made to the original system during those months.

Because here is the worst part: The system running on top of this database was mostly Monte Carlo optimization algorithms. Such machinery is highly dependent, in unpredictable and hard-to-debug ways, on such harmless-seeming transformations as changing the units in which a size is expressed, or changing the order in which a graph vertex's edges are enumerated. There were many such differences between the old and new databases, and the new system never did produce results as good as the old one.

After it was all over, it was clear to me that this way of making this conversion was totally wrong-headed. The right way would have been to first write a bunch of regression tests. Then write a facade over the new database that had the old database's API. Move the system onto it (which is nothing more than recompiling against the new library). Then slowly migrate the code, and the facade API, to look more like the new database's API. Run the regression tests frequently, so that if you make a change that breaks things, you know what change is to blame. Eventually the facade API looks just like the new database's API, and at this point the facade is vestigial and can be removed.

This approach has two key features: There is just one version of the system, and it is always working throughout the process. It probably takes substantially more time than the open-heart surgery approach would if everything went smoothly, but how often does that happen?

So imagine how I felt listening to this week's Stack Overflow podcast, in which Jeff talks about facing the same problem with Stack Overflow. Evidently the schemas of his core tables turn out to be really wrong, and force a lot of baroque and complicated over-joining and such in the site's code. Joel suggested something almost identical to what I decided so long ago I should have done: Create a view that looks like what he wants the new table to look like but has the original tables underneath. Then, migrate the code a piece at a time from the underlying tables to the new view. Again, there remains just one, working system the whole time. To my horror, Jeff disagreed quite vehemently and said he planned to go the open-heart surgery route. He went on a bit about the romance and adventure of that sort of swashbuckling. Surprisingly, Joel acquiesced a little and said that might be the right approach for Jeff. I seriously doubt it, and I was disappointed that Joel didn't let Jeff have it with both barrels; after all, this is just a smaller-scale version of the exact same mistake Joel wrote about in Things You Should Never Do, Part I, for pretty much the same reasons. (By the way, that hadn't been written yet when I had my little misadventure.)

Just as Joel says quite unequivocally that you should never do a full rewrite of an application, I'll say just as unequivocally that you shouldn't perform this kind of massive surgery on a working application unless it is simply impossible to do it incrementally. Indeed, in the decade since then I've formed a habit of never having my software be broken for more than a few hours at a time.

Labels: , ,

Comments (0)
 
A couple of months ago, as I was preparing to buy a netbook (which I've since bought), I made myself a note to blog about how just about everything I do on a computer could be done in the cloud these days, except for writing software. Since then, a number of pretty full-fledged IDEs have sprung up in the cloud, including Mozilla's Bespin and a few others.

Labels: , ,

Comments (0)
 
iPod

Recently A List Apart and Rands both covered, from somewhat different angles, the notion that much of great design is about details. As far back as I can remember, seeing a message like this has made me want to scream:

You have 1 new messages.

It would have taken the programmer seconds - literally, seconds - to add the conditional that would omit the plural when the number is 1. When I write such code, I also special-case 0, writing no instead of 0.

Coincidentally, just days before I read that Rands article, I'd added code to this blog to write Today and Yesterday in place of those dates, and to omit the year when the date falls in the current year. That has long been one of my favorite little design details. A couple of my other favorites are how in iTunes, it displays an image of the model and color of iPod that is presently docked (too bad the rest of iTunes is such a mess). And how my TV, in the final seconds before the sleep timer shuts it off, says good night.

Such details sometimes cost extra, especially with physical products. But that cost is often nominal, especially in the software world, as in the 1 message example above. Look for those kinds of opportunities and take advantage of them; they can help make the difference between a product and a thing of beauty.

Labels: , ,

Comments (0)
 
I've long had a good handle on the core JavaScript language, but the other night I set out to understand the DOM and the event-handling model, and the result was this toy sudoku app. If any more seasoned JavaScript programmers see anything stupid in there, please comment.

Labels: , ,

Comments (0)
T
 
Paul Graham just posted a history of the T language written by Olin Shivers, and it got me reminiscing. T was a Lisp/Scheme dialect. I took a compilers class my first year in grad school (ulp - 17 years ago!), and the semester project was to write a compiler for a subset of Pascal (all that was missing, IIRC, was user-defined types) into object code for a hypothetical microprocessor (for which we were provided a virtual machine). At the time, I was ramping up on a master's research track around optimizing the compilation of purely-functional languages like Haskell for doing numerical computations. My C chops were very strong, I figured I wasn't going to learn much more about C programming from this project, and my research would need me to know T, so I got the bright idea of writing the compilers project in T. I brought this idea to my compilers professor; he thought this was a very bad idea, and tried to talk me out of it, but ultimately capitulated with the understanding that I would be free-climbing - if I fell down, he wasn't going to be sympathetic. (This is a man who once said that the only legitimate excuse for turning in an assignment late is your own death.) I'd never really programmed in Lisp before, so learning the language (as any Lisp programmer knows, a major change in mindset) while under the gun on a long, difficult assignment was quite a challenge. However, ultimately I got it done; as far as testing could determine, it worked perfectly, and it had about 30% as many lines of code as my classmates' C implementations. I had fun, I learned a lot about both Lisp programming and writing compilers, and it brought me some small renown in the department (I presented on the project to a number of compilers and programming languages classes). Later, when I told this story in job interviews, my interviewers seemed to appreciate the accomplishment, but especially the attitude involved in bucking the system in this way. Not long thereafter, my would-be advisor left the department, and I ended up doing algorithms research instead; this would end up being a career, and I love it, but I still feel a little wistful about languages/compilers research. Still today, T is my favorite language I've ever written in, though Python is closing fast. BTW, in the unlikely event that anyone is interested, here is the source code for the compiler.

Labels: ,

Comments (0)
 
Via the Beautiful Code blog, a couple of nice sorting results: First, the proportion extend sort, a recursive sort that allegedly outperforms quicksort in both theory and practice. (Warning: Their code is pretty hard to understand, undercommented and obfuscated.) Second, the Python distribution contains a very nice writeup of the sorting routing Tim Peters used to implement listsort. The filename is listsort.txt, and it describes a nicely engineered adaptive mergesort with some elegant tricks to make it perform better on lists that already contain some order.

Labels: ,

Comments (0)
 
Consider the problem of choosing a random element from a linked list whose length you do not know. Obviously, you could count the length of the list, then pick a random number between 1 and length, and then walk to that element, but there is a clever way to do this in one pass.

The algorithm is as follows:

Element choice;
int count = 0;
for (Element e = head; e != NULL; e = e->next) {
   if (rand01() <= (1.0 / ++count)) {
      choice = e;
   }
}

You can easily show that when this finishes, choice is equal to any given element with probability 1/n, where n is the number of elements: The probability of setting the ith element to be the new choice is 1/i. The probability of not selecting any of the subsequent elements to be the new choice is the product as j goes from i+1 to n of (1 - 1/j), which if you work out the math ends up as i/n. Multiply the two probabilities together and you get 1/n.

Labels: ,

Comments (0)
 
A number of times I've been faced with what I call the "Chinese menu enumeration" problem - you know, one from column A, one from column B, etc. Given an array num of N entries where each entry contains the number of items in that column, enumerate [the indices of] all of the possible meals. Equivalently, list every N-digit number in which the i'th digit is less than num[i]. This is not a hard problem, but it's all too easy to write ugly code for it. My latest attempt ended up like this:

int val[N];
for (int i = N - 1; i >= 0; --i) val[i] = 0;
for (int inc = 0; inc >= 0;) {
   // do whatever you need to do with val[]
   inc = N - 1;
   while (inc >= 0 && ++val[inc] == num[inc]) {
      val[inc--] = 0;
   }
}

Pretty succinct, but I can't shake the feeling that it could be obfuscated simplified further. Any takers?

Labels:

Comments (0)
 
One of the more comprehensive collections of bit-twiddling hacks I've seen.

Labels:

Comments (0)
 
Reader Bennet Yee pointed out that my Lisp in JavaScript interpreter failed on his Y-combinator code, as follows:
    ((lambda (x y) (x x y)) (lambda (me n) (cond ((< n 1) 1) (t (* n (me me (- n 1)))))) 4)
Naturally, I suspected a bug in the lambda machinery, but it turned out to be much simpler: The symbol-table lookup code had a conditional that depended on the value of the variable being looked up, and JavaScript (as in C/C++) equates 0 to false. Thus, it failed to find the variable when its value was 0. I hadn't caught this before because I habitually write that terminating condition as the slightly more efficient "< n 2", and thus it terminates before n reaches 0.

This task also led me to revisit the Y combinator, which is really beautiful. For those who don't want to wade through the details, it's a clever mechanism for implementing a recursive call to a lambda (i.e. nameless) function.

Labels: ,

Comments (0)
 
Annoyed at having to look up, yet again, one of the couple of C++ operator precedence rules that I don't have memorized (this time, whether equality or ternary is tighter), I took the C++ precedence rules from here and formatted them into a 3x5 reference card. Here it is in PDF form, or in Word if anyone wants to tweak it. (My graphic-design skills are fairly meager, so if anyone makes substantial improvements, please let me know.)

Labels: ,

Comments (0)
 
Recently I wrote some code in which a templatized class declared one of its template parameters a friend. This worked fine in Visual C++, and I was surprised to find that GCC gave the rather unambiguous error, Template parameters cannot be friends. I was even more surprised to find that, indeed, this is not GCC being overly picky - it is not legal C++! There are extremely crufty workarounds, but in general it's clearly a bad idea to rely on platform-specific violations of the C++ standard in production code.

Labels: ,

Comments (0)
 
Joel Spolsky's latest essay is on coding standards, and in particular why Hungarian notation is good. I've always liked Hungarian and similar notations, but as I read this article I found myself thinking that these classifications could be not only denoted but also enforced by making them classes instead of just variables of the same type with differently-denoted names. This requires a little finesse with simple types such as int, but it can be done. The result not only denotes the same information as Hungarian (and less cryptically) in the class names, but the compiler even enforces the relationships for you. No need to "watch" for types with mismatched notation (as in Spolsky's essay); it's part of the type system. Which is not to say that I no longer find Hungarian notation useful, but that in many situations and in many languages it should be supplemented (or in some cases replaced) by type definitions.

Labels:

Comments (0)
 
Among the entries in Google's recent usenet timeline is the original Tom Duff post describing Duff's Device, a loop unrolling technique that exploits a surprisingly legal C quirk. I remember seeing this for the first time in a job interview in 1990 or so, when my interviewer wrote the code on the board and asked me what it did. I still think it's quite cool; though compiler optimization technology has probably rendered this unnecessary, it's still a great illustration of the sorts of things that are made possible by the "anything goes" design philosophy of C.

Labels:

Comments (0)
 
Ned Batchelder tells a C++ debugging story, the punchline of which is this: If a C++ constructor throws an exception, then that object's destructor is called. I encountered this in my own work, and it turns out exactly the opposite: If the constructor throws, the destructor is not called. These stories have the same moral, though: Constructors really shouldn't throw exceptions. Update May 2005: I reported my findings to Ned, and he wrote an update that describes in detail the precise semantics of what happens when a C++ constructor throws an exception. In short, the destructors of every base class and member whose constructor successfully completed will be called; note that this necessarily precludes the destruction of the class whose constructor threw the exception, since that constructor obviously did not complete execution.

Labels: ,

Comments (0)
 
In last month's C/C++ Users Journal, there was a clever article that described using templates to write loop constructs that are unrolled at compile time. In my last project I wrote some multiobjective optimization code that was full of loops that went from 0 to 2 or 3; this mechanism would've been great for that. On the other hand, five years ago I highly doubt that all the compilers I supported would have processed this kind of fancy template code correctly.

Labels: ,

Comments (0)
 
Michael Abrash has a series of articles appearing in Dr. Dobb's currently. The subject of the articles is code optimization, but the thing I found most interesting is the code being optimized. It is a software-only rasterizer. I wouldn't have thought it possible (even for Michael Abrash) to get DirectX7 performance in software. But most of all, it's noteworthy that state-of-the-art graphics hardware and drivers still have so many bugs and portability problems that Abrash finds it worthwhile to spend a lot of time and sacrifice two generations off the state of the art in order to avoid them. I certainly feel his pain, and I'm jealous that he is able to focus on a single type of processor and thus achieve this level of optimization.

The other thing that caught my eye was an illustration of how on modern processors, optimization can be extremely nonobvious. The example was a subproblem I've solved before: Given a value x between 0 and 1 and an array of ascending values in the same range, figure out which pair of values x falls between. I used a binary search. It turns out that on the x86, binary search is predicted poorly by the processor's branch prediction logic, while in a linear search every compare but the last one is predicted correctly. A mispredicted branch is very expensive. So, for a small number of bins a linear search is 30-50% faster (!), and the problem size has to reach 64 bins before the improved asymptotic efficiency of the binary search actually beats the linear search in real life. My problem had at most a few tens of bins, and the search was deep in an inner loop, so this would have been useful information to have known.

Labels: ,

Comments (0)
 
Ned Batchelder discusses rewriting assert conditions to make them more readable. Since one of the purposes of assertions is as documentation, this is good advice.

Labels:

Comments (0)