EASTL and runtime library design

I spent a bunch of time reading through the documentation for EASTL -- the Electronic Arts Standard Template Library. This library is now close to 3 years old, but this is the first I'd heard of it. Of course, I'm somewhat out of touch with the C++ world nowadays; I did most of my C++ programming in the mid-90's, when we were still using Windows 3.1 and the C++ STL was just being created.

Although I no longer work in C++, I still found the overall paper very interesting. I think it's great when somebody takes a really close, detailed, critical look at a large and substantial piece of software, as there is always something to learn. In fact, I think that the best point that the EASTL paper makes is: no matter how good your standard library and your programming infrastructure is, it can always be improved, and it can always benefit from a thorough and detailed critique. There are similar efforts in the Java world which I am familiar with; for example, consider the Google Collections Library, which is a similar attempt to improve on the base JDK collections library.

My favorite part of the EASTL paper was the part where the author itemizes the issues that game programmers encounter, including:

• No matter how powerful any game computer ever gets, it will never have any free memory or CPU cycles.


• Game developers are very concerned about software performance and software development practices.


• Game software often doesn't use conventional synchronous disk IO such as <stdio.h> or <fstream> but uses asynchronous IO.


• Game applications cannot leak memory. If an application leaks even a small amount of memory, it eventually dies.


• Every byte of allocated memory must be accounted for and trackable. This is partly to assist in leak detection but is also to enforce budgeting.


• Game software rarely uses system-provided heaps but uses custom heaps instead. See Appendix item 26.


• A lot of effort is expended in reducing memory fragmentation.


• A lot of effort is expended in creating memory analysis tools and debugging heaps.


• A lot of effort is expended in improving source and data build times.


• Application code and libraries cannot be very slow in debug builds. See Appendix item 9.


• Memory allocation of any type is avoided to the extent possible.


• Operator new overrides (class and global) are the rule and not the exception.


• Use of built-in global operator new is verboten, at least with shareable libraries.


• Any memory a library allocates must be controllable by the user.


• Game software must be savvy to non-default memory alignment requirements.

As I read this list, I was struck by the realization that, really, almost nothing here is specific to game programming. Really, this is just a list of considerations that apply to any software that you care about. This list of concerns is equally important to people writing operating systems, database systems, networking software, etc.

There was a time when people worked really hard on software: slaved over it, deeply considered every line of code, measured and re-measured and tuned every bit of it. This is still important; using great software is just a completely different experience than using sloppy software.

It's nice to see a paper written by some people who obviously care a lot about writing really great software, discussing, in detail, why that's hard to do, and why you really have to constantly focus on every little detail in order to do it.

Even if you aren't a C++ programmer, give the paper a try: I think you'll enjoy it.

Logicomix, by Doxiados and Papadimitriou

I read a rather unusual book: Logicomix, by Apostolos Doxiadis and Christos Papadimitriou.

The book is a graphic novel about mathematicians.

Specifically, the book is about Bertrand Russell, about the writing of Principia Mathematica, about Ludwig Wittgenstein, and about Kurt Godel and the Incompleteness Theorem.

As it turned out, I mostly knew the history-of-philosophy and history-of-mathematics story lines of the book, as I happened to have taken undergraduate classes in this area in college in the 80's. And I was particularly fond of the Incompleteness Theorem so I actually paid attention in that class!

I knew rather less about the social history of Russell's life, about his personal misfortunes, and about his biography. Unfortunately, these are areas in which the book exercises a certain amount of literary privilege; as they note in their afterword:

Also, though our major characters are based as closely as possible on their real-life counterparts, we have on more than one occasion departed from factual detail, in order to give our narrative greater coherence and depth.

It's a tricky business, making history entertaining. The book is pleasantly illustrated, and easy to read; it flows along and I finished it in a few days. But for a book about characters who cared so very, very deeply about truth and accuracy, departing from the facts is a treacherous technique.

If you know little about mathematical logic and the underpinnings of theoretical computer science, you will probably find this an interesting book. But you won't learn much actual mathematics; you'll mostly learn about the history of some fairly interesting and noteworthy individuals of 100 years ago.

Non-empty mount points

Why does Unix allow non-empty directories to be used as mount points?

A few weeks back, I managed to get myself horridly confused, and at the core of the confusion was a directory that I was using as a mount point, and that directory was not empty.

Of course, I didn't know that at the time. Instead, I got a call:

You know that disk we were having trouble with, and you worked on it? Well, something is really weird, because that disk is now showing a 2-year-old backup? Did you somehow restore some ghost files?

Here's the overall sequence of actions that caused my confusion:

• I have some custom backup tools, which back up my system to an external disk, which is mounted as /mnt/backup


• I had some problems with that external disk.


• After a certain amount of investigation, I decided that the external disk had become scrambled irretrievably, and I re-formatted the disk (that is, I ran mkfs on it)


• I rebooted the system, and got ready to run a new backup to verify that my /mnt/backup file system was now happy, and was astonished to see that /mnt/backup was non-empty; moreover, it contained valid backup information from 2007!

It took me a while, but I figured out what was going on: it was due to the iteraction of two behaviors, one which is fairly new (to me), and one which is extremely old:

• My Ubuntu system, and, I think, most modern Linux systems, is now using UUID identification for file systems. I'm not exactly sure when this changed; I don't think that Dapper Drake behaved this way. This particular system was upgraded from Drake, and that's probably when the UUID filesystem identification was switched on, and I didn't notice.


• My Ubuntu system, and, I think, most Linux systems, allowed me to use a non-empty directory as a mount point

Due to the first behavior, the newly-formatted file system was not getting mounted at /mnt/backup, because its UUID had changed, and my /etc/fstab was still specifying the old UUID for my external drive. So Ubuntu had mounted my new disk at something like /media/my-new-uuid.

Due to the second behavior, since I didn't have an external file system mounted at /mnt/backup, my system was happily using the old contents of the directory.

I think that, during the early development of my backup scripts, I had at some point run them without the external filesystem being mounted, so the scripts had happily written a backup into the real /mnt/backup directory. Then, later, I had arranged for the external filesystem to always be mounted, and so all subsequent backups were going to the external filesystem.

I didn't realize that I was mounting the disk on a non-empty directory, so I didn't realize that my system had been operating for several years with all these hidden files, which were present on the root directory, but which were hidden by the mounted file system and thus effectively invisible (yes, the overall disk space usage on the root filesystem was higher than it should have been, but I wasn't paying close enough attention to notice that).

It seems like it would be a nice behavior if the mount command didn't allow mounting an external filesystem onto a non-empty directory mount point, but that's not the sort of thing that Unix systems tend to worry about. The user is always right, they say.

Good Java trivia quiz

This Java trivia quiz is actually quite good.

The first pdf link is to the trivia questions.

The second pdf link is to the answers.

I got about 60% of the answers correct. I completely nailed the JDBC section and the history section, and did OK on the JDK 7 question and the concurrency, IO, and collections questions, but completely bombed the Swing questions.

The Secretary of State on Internet Freedom

Ms. Clinton's speech on Internet Freedom is now online here.

New releases in the web world

Seems like this has been a busy few weeks in the world of web development:

• Firefox 3.6 is out. Here's a nice summary of what's new.


• Firebug 1.5 is out. It's especially nice that the team is managing to keep current with Firefox, as they have sometimes lagged a bit.


• ECMAScript 5 is official. It's a giant spec, but here's a nifty summary of what's been going on. And here's some nice status from the TrollTech guys about the implementation situation in WebKit (one of the major JavaScript engines)


• JQuery 1.4 is out. The JQuery team just continue to impress!


• And lastly, just to blow your mind, here's what claims to be a complete implementation of the Flash runtime written in pure JavaScript.
  

Meanwhile, although it's not really web-related, the proceedings are now online for last fall's LLVM/Clang developer's meeting. LLVM is now used for lots of things, with ActionScript/JavaScript being just one of many worlds that are involved with LLVM. Think you are doing some serious parallelism? Check out this release from a team that has used the LLVM architecture to build a program that runs on 120,000 processor cores! (Actually, according to these notes, they are now 50% higher, passing 180,000 processor cores!!!)

Checking items off the list

I've been spending a lot of time fixing bugs lately.

There's something very satisfying about fixing bugs. It really feels like you're getting something done, accomplishing something.

When I get into these moods, and feel like fixing a bunch of bugs, I get very methodical about it. I start compiling lists of bugs and reading through them. For each bug, I have a fairly rigid discipline:

• Do I understand what the bug writer was describing?


• Can I write a regression test which demonstrates this bug?


• With the test in place, can I see where it's going wrong? Or step through it in the debugger?


• Does my fix make the regression test pass?


• Do the other regression tests reveal any downsides to my fix?


• Is there anybody I should show this fix to?


• Check in the test and fix, mark the bug resolved, and move on.

On the various bodies of software that I work with, there have accumulated a long list of potential bugs to fix. So I can afford to be rather choosy when I get into these moods. If a particular bug report starts to act up; for example, if it's hard to write a regression test, or if the obvious fix doesn't seem to work, or if other tests start to pitch a fit at my change, I just take a pass on this bug, put some notes in the bug report about what I tried and where I got stuck, and move on to the next.

In periods like this, my goal is to make a serious dent on the open bug list. I understand that I'm not necessarily fixing the most important bugs, or even the bugs which are most deserving of my time. I'm just trying to clear away the clutter and keep it from overwhelming me and the people around me.

So many bugs, so little time. It's just the way it is with software.