Books that all Programmers Should Read

I read a lot of programming books. However, I haven't read many that all programmers should read. Programmers do a lot of different things, and it's pretty darn hard to write something for all of them.

In fact, I can only think of two books. If you know of another, I'd love to hear about it.

How to Write Code

All programmers write code. Furthermore, writing code is a skill that transcends language. If someone can write really good JavaScript code, then they probably understand most of the principles in writing Scheme code. The skill does not depend on language.

Steve McConnell does a great job of explaining this in Code Complete. This is a classic, and everyone should read it. The first edition had examples from a lot of different languages. Between 1991 and 2004, a lot of languages died out. The second edition doesn't try as hard to be language independent. It's still good, and the points he makes are still language neutral.

It talks about how to write code at the very lowest level: How to name variables. How to format argument lists. When to write comments. Et cetera. McConnell found a large number of obscure studies that prove some of his points, too. It's a great book.

User Interface Design

Sooner or later, every programmer has to write an interface of some sort. Yes, even library authors are creating an API. Even authors of tools that run only on servers have users. If it doesn't have a user, then there's really no point in writing it.

To write a UI design book that can apply to any of that and also apply to a web site requires a fundamentally different approach. Again, I'm going to bring up a classic.

Donald Norman wrote the Design of Everyday Things almost 20 years ago. It's not about which widget to put in the upper left corner of your web page. It's about human psychology and how people learn to use something they've never seen before. Humans are the same no matter what kind of tool they're using. This is the important part of UI design.

American culture does change, and you'll have to keep reading new articles to learn what users are capable of at any given point in time. Norman's book is about the stuff that will remain true forever.

It's also a fun book to read. After you read it, you'll never open a door to an art gallery the same way again.

That's it?

That's all I could come up with. There might be some room for a book on project management since all projects need to be managed. However, project management goes through the same series of fads that programming goes through. To add a book to this list, I'd like it to be timeless. I suspect a book like that exists, but I don't have it.

This originally appeared on PC-Doctor's blog.

What's that Data Structures Class for?

I assume that when computer science students go through college, they all take a required course in data structures. If I were designing a course like this, I'd make them learn how a variety of useful data structures worked. Certainly if you read a book on data structures you'll learn this sort of thing.

How many programmers actually need this information? In today's world, there are a lot of libraries out there that have a reasonable implementation of AVL tree, hash table, and B tree. Certainly some people need to learn to write these things. Why does your typical student programmer care about different ways to handle collisions when inserting into a hash table?

Okay, I'll admit that programming without this knowledge for me would feel a bit like skiing naked. It'd be a bit too weird to choose an algorithm because someone told me that I should always use AVL trees because their worst case performance and therefore their predictability in the face of ignorance is better. For me, I'd rather be able to use a sorted array to improve locality of reference even if I don't know that there's a problem anywhere. I'm sure that at least 95% of the time that I've used an immutable sorted array it hasn't made a difference. I certainly don't check with a profiler unless a real problem exists.

Every so often performance does matter, though. It sometimes matters a lot. In that case, you might say that you need a programmer who knows to check the hash tables to make sure they aren't behaving horribly. However, a decent profiler is likely to tell you a lot of useful information without having any knowledge of data structures. Since these cases are rare for typical programmers, wouldn't they be just fine if they knew a collection of data structures that they could swap in until they got something that worked better?

I can't remember many times when I've had to swap out a data structure because of performance issues. The last time was inserting into the end of a very large STL vector. The copies were too expensive due to C++'s tendency to copy things too often. (Even this case will be fixed with the next C++ standard.) Anyway, STL has some other data structures that can be used. I was able to replace my data structure and things immediately improved. I can't remember enough details to know what knowledge I needed. It's also possible that I guess correctly more often than an ignorant programmer would. Who knows how many times they might need to swap things randomly?

A C# programmer would have it even easier. The System.Collection namespace in .NET doesn't have a lot of different options. It'd be pretty easy to try all the possibilities pretty quickly. If none of the options solves the problem, it's entirely possible that there's something that could be done elsewhere.

Memory and speed performance are pretty much the only times you might care about the differences between a hash table and an AVL tree. A few years from now, application programmers may just add a bit of concurrency if they want more speed. Few web applications run low on memory. Are data structures classes useful anymore for typical programmers?

I've left a lot of unanswered questions in this post. I'm really curious about the answers. I'd love to hear from you.

This originally appeared in PC-Doctor's blog.

Model View Controller and Beautiful Code

I've been reading Beautiful Code. It's a fun book with chapters written by a few well-known programmers about some beautiful code that they've written or seen. They all have wildly different views on what makes code beautiful, so it's pretty entertaining. It's fun seeing what programmers I've heard of think is beautiful. Brian Kernighan, for example, wrote about some string processing code. I found that extremely entertaining and ironic. Yukihiro Matsumoto had an impressively concise description of what it takes to make beautiful code. It was refreshingly in character with the Ruby philosophy.

Most of the authors were completely unknown to me. However, even though the most obscure is more famous than me, I'm still going to tell you about some beautiful code that I run into frequently.

The Model View Controller (MVC) design pattern is, perhaps, one of the oldest out there. It's been used for almost 30 years now, and it is still an extremely clean way to divide up the responsibilities of a user interface. When I see it implemented well, it's extremely satisfying.

For those of you who grew up using Microsoft's GUI frameworks, you may have never seen this done well. .NET Forms and MFC make it difficult to implement it correctly. (In fact, this topic was inspired by me working simultaneously on a Rails and a MFC project.) Ruby on Rails, by the way, revolves around the MVC design pattern.

What's so beautiful about the pattern?

It cleanly separates three different activities. The separation is clean enough that the pattern is relatively easy to use. It's usually easy to figure out whether some functionality should go in the model, the view, or the controller.

Furthermore, even in a highly interactive GUI, the program becomes easily testable. The view is the only part that interacts directly with the user, and, other than interacting with the user, the models and controllers have all of the functionality. (This statement becomes less true if you're writing custom controls such as a text editor.) If you test the models and controllers, then you've tested a large fraction of the code.

I always smile when I see some MVC code that works well.

This originally appeared on PC-Doctor's blog.

Futexes are Fun

Futexes are a synchronization primitive that is new to the 2.6 Linux kernel. If you're like me and had never heard of them before a few days ago, then I recommend reading Ulrich Drepper's article, Futexes are Tricky. To a Windows programmer like myself, futexes are a wonderful idea that would be lots of fun to play with. Essentially, they're the antithesis of Window's synchronization model.

Hmmm. I guess I'm showing how much I dislike Window's synchronization model...

Let's start there. In Windows, if you want to use a synchronization object, you go to the Micrsoft-approved zoo of Win32/.NET synchronization objects, and you find one that's close to what you need. You then modify your problem to fit this synchronization object.

Okay, the zoo of synchronization objects that Microsoft gives you isn't bad. There are some extremely useful ones in there. If you're using .NET, you even get to use a monitor, which was missing from Win32.

In fact, if you're doing relatively normal programming in Windows, you'll never even realize that you're missing futexes. However, if you're trying to build an application that has to have optimal performance, then you may want something unusual.

You may want to do a WaitForMultipleObjects on 65 mutexes. You may want to optimize a mutex implementation as much as possible, and you're willing to give up features like re-entrance. There are a lot of things you might need, and Microsoft deliberately doesn't give you all of them. Thomas Becker has tried to implement something that's not in Microsoft's zoo, and the difficulties that he ran into are instructive.

POSIX doesn't have a universal solution, either. However, it does have a monitor, and, assuming performance isn't an issue, you can solve any problem using this.

Futexes are all that and more. They let a programmer write their own synchronization object in user mode. They do this by avoiding doing anything that's unnecessary. A futex lets you have a thread join a wait list and sleep until it is woken. The user mode code decides when a thread will enter the wait list, and when threads in the wait list will get woken up. They're still a bit new, and they don't let you control which thread gets woken up with much precision. Even if it's missing some features, however, it's still an exciting idea. It allows user mode libraries almost complete control over the performance and features of a synchronization object.

That's pretty darn clever. My next goal is to find an application at PC-Doctor that needs a futex. It sounds like a lot of fun, but it won't work on Windows.

This originally appeared on PC-Doctor's blog.

Bonus Day at PC-Doctor: They Gave Me a Coffin!

This morning was PC-Doctor's 14^th anniversary! To celebrate, the management team at PC-Doctor put in overtime and bought a lot of goodies to give away to employees.

Wow. That's pretty cool.

Maybe I'll win a 50" TV or some Raiders tickets or the massage chair.

The management team picks names, ostensibly at random, and when someone's name comes up, they run over to a pile of stuff they choose and claim it. Sounds great! I don't own a TV, and they've got a bunch of them here. Maybe I can get one?

It's Andy's turn! I work a lot with Andy, but his kids were sick today, so I got to pick for him. He sounded pretty happy about his plasma TV on the phone.

There aren't many choices left, but there are still a few good options remaining.

When's it going to be my turn?

Okay, now it's really hard to find anything left. What's still around?

Uh, oh. It turns out that I'm the last person.

What's still there?

Woot! I get a Lady of Guadalupe Casket! Rob says that it'll get delivered next week.

While I'm not a coffin expert, it's at least got a long list of features. It's pretty long, too, so my legs would only be slightly bent!

I'd told my wife that I might win a TV. Somehow, I'd forgotten to mention that I might win a casket. In retrospect, this seems like poor planning on my part.

One question remains: Is there enough space in my cubical for my new coffin?

This originally appeared on PC-Doctor's blog.

RTL Languages and International Usability

When you localize a product into a right to left language such as Hebrew or Arabic, how much do you have to change the position of UI elements?

It's a pretty simple question, and I think the answer is also pretty simple. If you have to have your eye on the right side of the page to start reading a sentence, then your eye is going to start on the right side of the page.

As far as I can tell, that's the extent of the problem. What are the implications?

You can't assume that users will start in the upper left corner and scan down to the bottom right of a page. Important navigation tools should be on the right or the top. Tab order should go from the right to left.

Is that the whole story? As someone who knows absolutely nothing about the subject, it's tempting to say yes. Unfortunately, Saleh, a Persian blogger, knows better. I recommend reading his blog.

This originally appeared on PC-Doctor's blog.

Fairness in Win32 Lock Objects

Windows Vista has given up fairness in their synchronization objects. In fact, Windows XP isn't guaranteed to be fair, but Vista goes quite a bit further.

The issue and the solution is explained pretty well by Joe Duffy over here. At first glance, it looks as though this could cause some really bad thread starvation in some circumstances.

The change to unfair locks clearly has the risk of leading to starvation. But, statistically speaking, timing in concurrent systems tends to be so volatile that each thread will eventually get its turn to run, probabilistically speaking. Many more programs would suffer from the convoy problems resulting from fair locks than would notice starvation happening in production systems as a result of unfair locks.

The problem they're trying to solve and the problem that I'm worried about are pretty similar, so it's worth explaining it carefully. If you have a mutex that protects a small chunk of code, and you have a large number of threads trying to get that mutex, then you have the potential to have a lock convoy. You can get this easily if you wake up a large number of threads with the same priority and have them all immediately try to get another lock.

Here's what happens. A bunch of threads are waiting for a mutex. A thread releases the mutex. Under Windows XP, the next thread in line to get the mutex now owns the mutex and gets a temporary priority boost. Windows does a context switch to the new thread, and it performs a short operation and releases the mutex. (Note that this will also boost the priority of the next thread in line, but that thread will have the same priority, so no context switch is performed.)

These context switches are expensive. Joe Duffy claims that it's about 1000 cycles. Avoiding these switches would be a good thing, so Vista changes the way mutexes work. When a thread releases a mutex under Vista, the mutex does not become owned by the next thread in the queue. Instead, it becomes unowned. This allows a third thread that's already in the running state to grab the mutex and keep going without any context switches at all. That's much cheaper, much less fair, and has the potential to starve the waiting threads.

One problem with this is that you're giving priority to running threads over waiting threads. As the number of cores in your CPU goes up, then the number of running threads gets higher. Eventually, isn't there going to be some starvation of the waiting threads?

I tried for a while to construct an artificial scenario where a thread could be starved for a long period of time. I've got to admit that I couldn't do it. The reason is that there is always some randomness in the scheduling. In order to make it so that there is a problem, I had to increase the fraction of time that a thread holds the synchronization object. Once you do that, you're going to limit the number of threads that can run without having to run into problems with a lack of fairness. It feels as though that might be true of all problems where this change becomes bad, but I couldn't prove it.

In short, Vista gives up the pretense of fairness in synchronization objects, and it does so without guaranteeing that it doesn't starve a thread. However, it looks to me as though thread starvation will never be a huge issue.

This originally appeared on PC-Doctor's blog.