Airs - Ian Lance Taylor

One of the best comic books being produced these days is, of all things, a zombie story. The Walking Dead is written by Robert Kirkman and illustrated by Charlie Adlard. The background is the basic zombie story as reimagined by George Romero: most of the people in the world have turned into zombies, and our heroes have to survive. Kirkman is basically writing a zombie movie that never ends–48 issues so far. It’s gripping because the focus is on how people react to the end of civilization. Kirkman tells a straightforward story, but he doesn’t follow any plot conventions. The resulting story is wholly unpredictable and sometimes horrifying. It’s the most unnerving thing I’ve read in years, but much too good to stop reading. Not recommended for the squeamish.

The FCC spectrum auction is over and the anti-collusion restrictions have been lifted. I’m not going to say anything about what my employer did–I of course was not involved in the auction at all and I don’t know anything about it beyond the public announcements. But I wonder about the whole auction concept in the first place.

Once upon a time, many towns in England had a commons, a shared space for all the inhabitants. The city in which I grew up, Cambridge, Massachusetts, still has a commons, although it is basically indistinguishable from a park. In the old commons, people were allowed to graze their cattle and otherwise use the land. Of course, as we all know commons are subject to tragedy as population grows. What actually happened to the commons in England, though, is that they were enclosed by wealthy land owners who discovered that they could make money raising sheep on what was formerly common land.

This process was described in a little old poem I’ve always been fond of: “They hang the man and flog the woman that steal the goose from off the common, but let the greater criminal loose who steals the common from the goose.”

Anyhow, why is the spectrum not being treated as a commons? In this day and age spectrum is valuable. Selling it as private property, as the FCC just did, does not maximize its value for society. Clearly spectrum requires rules of the road–it can not simply be left to anarchy. But why not simply rent it out for limited, renewable, periods of time? Why not require that low-power use of the spectrum be permitted? Turning it into private property, even at the prices that it drew, is basically giving it away when considered over a fifty year time frame. Why did we do it?

My first real job, at the actual company called AIRS and the original owner of the domain airs.com, was working on what was then called a fourth generation language system. Nowadays we would simply call it a database. It was pretty powerful, and we had customers, but we only ran on a system called the Alpha Micro which ran a proprietary operating system called AMOS. So that’s why you’ve never heard of AIRS, or if not the only reason at least a sufficient one.

Anyhow, what I wanted to say here is, we had a database, but it was not a relational database. It was what then called a network database. Nowadays, we would simply say “huh?” But in fact I thought then and continue to think now that relational databases are basically a mistake.

The idea behind relational databases, as invented back in the ’70s by E.F. Codd at IBM, is that you can access them via a structured query language. We now know that language at SQL. A relational database is conceptually just a set of tables. SQL lets you express a database search by conceptually joining tables together in a few different ways (the most common way being matching some index field) and then describing some condition to be satisfied on the joined table. SQL is nice because you can compose complex queries in a fairly logical manner.

The problem is that data in the real world doesn’t typically come in table format. In order to put it into table format you have to insert all various key fields. That’s not so bad, actually, but when you have one-to-many or many-to-many relationships, SQL requires that you describe them as table joins. When the tables get large, actually joining a table becomes expensive–prohibitively expensive. So instead the database has to figure out an efficient way to do the query which doesn’t involve doing an actual join, but instead involves traversing the tables in some manner collecting the desired results. When the query is at all complicated, that becomes a hard problem. So for practical use relational database implementations require you to define various indexes which they can use, as well as more sophisticated solutions which I won’t go into.

The end result is that when you anticipate a user’s query and create the appropriate indexes, the query is fast. When the user does something you didn’t anticipate, the query is slow–for a large database, prohibitively slow. The user who doesn’t know which indexes you created has no idea which queries will be fast and which will be slow. So SQL gives you this logically powerful query language which is supposed to be simple to use, but in actual practice has traps for the unwary user.

In a network database, you have to express your one-to-many and many-to-many relationships explicitly. And when you do a query, you have to follow the links defined by the database–there are no joins. The result is that an efficient query is easy to write, and an inefficient query is hard to write. This makes it harder to do data mining, but it’s actually not that bad. You can still support a structured query language, even SQL itself, you just use a system which rewrites it into something which can be implemented before it gets to the database rather than after. (At AIRS we had a programming language for queries which we called Logic, but most people used a visual query creator, with saved standard queries, etc.).

I can’t argue that SQL is really nice to use. But I can and do argue that relational databases are not the right way to organize data for efficient access.

gold normally simply mmaps input files and reads the data directly from the mapped memory. In general this requires that all the data structures be properly aligned in the file, which is guaranteed by the ELF standard. The x86, of course, does not require proper alignment for memory loads and stores, so this was never tested. When David Miller tested on a SPARC host, he saw crashes.

It turns out that the problem was object files in archives. Archives only guarantee an alignment to 16-bit boundaries. ELF data structures require 32-bit or 64-bit boundaries (the latter for 64-bit ELF). Thus it is possible for an object file stored in an archive to be misaligned with respect to mmap.

I fixed this in gold in the obvious way. But it suggests that changing the archive format to enforce 64-bit alignment could give better linker performance. Unfortunately the archive format, which dates back the old a.out format, is quite simple. The size of the object file is stored, but not the size that it takes up in the archive. And there is no global table of contents pointing to each object file. So a general archive file reader must walk through the archive file one object file at a time. Archive file readers must align to 16-bit boundaries as they go. There is no provision for recording the amount of required alignment.

The only way I see to get optimal performance would be to actually define a new archive format, with a new magic string. It’s not clear that the compatibility hassles would be worth it.

I’m happy to see that there is a nice new edition of one of my favorite books, The Player of Games by Iain M. Banks. For some reason the book drags me in every time I read it. Much of it amounts to a critique of an exaggerated version of our own society, but the most interesting part for me is just the protrayal of Gurgeh (the protagonist) and his very plausible fascination with games. It’s also interesting to consider whether our society would be as unable to cope with the Culture as the society that Banks describes.

It seems that Orbit is planning to rerelease all of Banks’s SF books. Of course Banks should need no introduction to anybody who follows science fiction, but it’s nice to see some high quality editions sold in the U.S. My copies of his early books were all printed in the UK.

I recently read his latest novel, Matter, also published by Orbit. I was mildly surprised to see that he wrote another Culture novel–it seems to me that he pretty much said everything he had to say about it in Look to Windward. As it turned out Matter doesn’t have much to do with the Culture at all; it amounts to a background element in a reasonably typical Banks space opera. In other words, an interesting book well worth reading, but not the fascinating experience of, say, The Player of Games.

Of course Banks has also written a number of non-SF novels, also well worth reading. My personal favorite of those is The Crow Road.