Ex Bibliotheca

The life and times of Zack Weinberg.

Saturday, 31 May 2003

# 6 AM

Tired after the week to date of running around, so I decided to take it easy today. Attempted to sort out Jo's email setup, so she wouldn't have to use dodgy web-mail all the time. This was only partially successful, because the exim MTA was written to be used on a machine with a permanent network connection. Jo wants to download all her mail over her modem line, disconnect, write responses at leisure, then reconnect and send everything in a batch. I don't know what MTA you want for that kind of operation. However, I believe I at least made things better than they were.

In the afternoon we browsed round a few bookstores in search of plane reading for my return flight tomorrow, and then we met Sasha and Emmet for dinner at a Peruvian restaurant in the southwest of the city. There was a street fair going on down the road the restaurant is on, with various live musicians (singing what sounded like sappy love songs, but in French so I don't know for sure), people selling clothes, that sort of thing. Sasha wanted to buy computer parts, and was loudly disbelieving when Jo and I told him better stuff could be had for about half what the street merchants wanted. For example, there was an $80 computer case which looked really spiffy but would have collapsed into flinders if poked too hard. The food at the Peruvian restaurant was a bit disappointing — I ordered what proved to be cold fish in sour milk, for instance.

Friday, 30 May 2003

# 6 AM

Went up to McGill University to have a look round. This seems like a fine place. Their CS department developed the McCAT experimental compiler, whose internal representation inspired GIMPLE (discussed previously). Also, they have one of the oldest departments of meteorology and oceanology (now renamed "atmospheric and oceanic science" in the world. And the rare books collection in the Redpath library is open-stack.

After that I went to the Musée des Beaux-Arts since Jo said that they had a larger collection of Inuit art than the museum in Ottawa. This may be true, but I didn't get to see it because that entire floor, and in fact most of the museum, were closed for exhibit rearrangement. They did have one small Inuit gallery open, but it wasn't very impressive. Also there was a collection of Art Deco furniture, which was nifty indeed.

And then I was meaning to visit Concordia, the other Anglophone university in Montreal, but I got confused about which bus stop I wanted and wound up back near Jo's flat so I gave up.

In the evening we went out to eat at a Greek restaurant in the old French part of town. They had delicious spanokopita and decent shishkebab.

Thursday, 29 May 2003

# 6 AM

Once again, up far too early, this time to catch the train to Montreal, where I am visiting friends. Canada, unlike the states, has a functional passenger railroad system. This means the trains are not nearly as posh as Amtrak, but on the other hand they run on time. In Ottawa there was a certain amount of casual use of French, but in Montreal they are dead serious about it; half the people on the Metro were chattering at each other in French, for instance, and warning signs tend to be French only. Interestingly I remember enough Spanish, and there is enough commonality, that I have no trouble reading signs and the like. Conversations, however, are just sound.

There's an island in the middle of the St. Lawrence, and on this island is a geodesic dome, and in the dome is the Biosphère Museum. Sasha, who is twelve, is very much fond of the dome, so he and I and Emmet trooped out there to show it to me. Unfortunately the museum was closed.

Wednesday, 28 May 2003

# 6 AM

The first talk this morning was Naveen Sharma describing his stack frame optimizer. This delays committing to a precise layout of the stack frame until after register allocation; previously stack slots were assigned as necessary during RTL generation, and never changed again later. A lot of really nice optimizations fall out of this patch. Naveen did it in order to improve code generation on architectures like the SH that have limited base+offset addressing modes. In addition, it gives more accurate aliasing information between stack slots, which lets the generic optimizers do a better job. We will no longer allocate space for stack slots whose use has been optimized away. There is hope of being able to share stack space among variables with disjoint lifetimes, which the kernel people like. All in all, a nifty optimization and well presented.

Again, Mark and I skipped the rest of the morning's talks to tour Ottawa. We went to the National Gallery of Canada which was a short walk from the hotel. They have a modest, but growing, collection of contemporary and historical Inuit art; the primary medium is small sculptures carved into stone or whalebone. Their imagery comes from their strong shamanic tradition, so for instance animal/human hybrid forms are common. One gets a vivid sense of the harsh polar environment and their determination to survive in it.

We also walked through their exhibit of paintings by Canadian artists. The strong point of this collection is the landscapes, which capture the wildness and variety of this part of the continent. The portraiture and modern art selections are not unlike other such things that one may see elsewhere. There is also an entire Catholic chapel interior which was transplanted from a convent that had to be demolished; a good representative of the modified French style that developed in the Quebecois territories.

In the afternoon there was some informal discussion about the best way to make C++ exception handling interoperate with POSIX threads. Everyone agrees that the pthread_cleanup_push mechanism needs to talk to the exception handling runtime, but that requires an extension to the C and C++ languages. The exact semantics of this extension are in debate. The simplest and most general thing unfortunately risks conflict with future revisions to the standard; it might also be seen as confusing in the context of C++. Furthermore, the natural semantics permit a cleanup block to abort thread cancellation, but the pthreads library maintainer (who did not attend this conference) insists that this cannot be permitted. We all disagree, but there may be no hope of convincing him to change his mind. The next talk started in the middle of this discussion so I didn't hear what conclusion, if any, was reached.

That next talk was Per Bothner's "compile server" concept. This is an alternative to precompiled headers, where the bulk of the compiler runs as a persistent semi-detached process, accepting compile requests from the driver program. It remembers the parse trees it constructed from header files on each invocation, and can reuse them for subsequent invocations. He's seeing speedups from 30% to 300% depending on the input. However, at present the design does not handle all the nasty corner cases, and it's not clear that he can augment it to get everything right without losing all the benefits. There are some secondary improvements to the compiler that we can use even if the main idea doesn't pan out; for instance, disentangling the initialization process, which is a prerequisite, would be great all by itself.

Paul Brook of the G95 project presented a report on the present state of that effort, which will give GCC a front end for modern versions of the Fortran language. The current Fortran front end is limited to the 1977 language revision plus a number of extensions; also, its internal design is incomprehensible to anyone other than its original author, who is no longer working on GCC at all. G95 will, when complete, replace it entirely; they hope this can be achieved in time to be incorporated into the 3.5 release along with the tree-ssa optimizers. Paul's talk focused on the "scalarization" process. Fortran 95 includes "array expressions" that specify a mathematical operation to be carried out on all the elements of an array; these have to be converted to loops in the front end. It is desirable to make use of vector arithmetic operations if the hardware provides them, but presumably that's best dealt with later, in a language-independent loop optimizer.

Mark gave a closing keynote in which he proposed a somewhat more formalized development process for GCC, rather like Python with its PEP procedure. That went over well. He also proposed the formation of a non-profit consortium to pool resources for long-term development. That didn't go over as well; Jon Hall pointed out that such things have not historically worked. On the other hand, perhaps we can learn from their mistakes.

Then there was the PGP keysigning party. As I suspected, there were rather a lot of keys to get through; we all stood around in a circle and read off our key signatures (which are lengthy hexadecimal numbers) and then frantically ran around the room looking at each others' passports. Several people who originally had wanted to participate had already left, alas.

And finally, as is the custom with such conferences, we all went to a bar and got drunk. Someone dared Stephanie (one of the organizers) to ask Jeff Law for his autograph, whereupon he turned bright red and there was much snickering.

Tuesday, 27 May 2003

# 6 AM

Everyone seems to have gotten sick of verifying PGP keys; there's a timeslot set aside at the end of the conference for this, so they're probably assuming they'll get everyone then.

Diego Novillo picked up where Jason Merrill left off with GIMPLE, describing how SSA form works and introducing some of the optimizations it enables. As Richard predicted, this is almost all of the interesting high-level optimizations one could want. The exceptions involve cross-module optimization, which is difficult mainly for political reasons that I don't care to go into.

Mark and Nathan and I skipped out on the rest of the morning's talks to go wander around Ottawa. We saw the Canadian Houses of Parliament, which Nathan says looks very much like the British prototype, except built with a different kind of stone. Around the back of these, we found the staircase lock connecting the Ottawa River to the Rideau Canal, which goes all over the place but eventually connects to the St. Lawrence Seaway. This was built in the sixteenth century, and was an important shipping route at the time, but it is now used primarily by people out for boating trips. I do mean trips; you wouldn't go up this lock for a short excursion, it takes at least an hour to get from one end to the other. There are at least eight individual steps, and they're operated by hand, using period windlasses and chains.

For lunch we went to the Marché Mövenpick in the mall next to the hotel. This is an extremely upscale cafeteria. You get a tray and a card, and you wander around the place, which is full of faux pushcarts manned by perky teenagers. Each pushcart has a different kind of food, you ask for what you want, they give it to you, and then they put a stamp on your card. When you've got enough you go find a table. After you're done eating you give your card to the cashier, and they tell you how much money they want.

In the afternoon, Michael Matz gave a talk about register allocation. The right approach is to treat it as a graph coloring problem; unfortunately this is NP-complete. There are various clever heuristics that do an OK job, but they're messy and unintuitive. Then you throw in all the weird details of real processors (no one has ever made a CPU where all the registers are exactly the same, alas) and it gets really messy. The good news is it's nearly done, and works well; the bad news is we won't be able to get rid of the infamous "reload" pass entirely. But, it will hopefully shrink quite a bit.

After that, Chris Lattner took the stage to describe his spiffy new intermediate representation, LLVM. LLVM solves more or less the same problem that GIMPLE does, but isn't GIMPLE. He's mostly interested in intermodule optimization, which is unfortunate, because of the aforementioned political problems with that. It is also unfortunate that he's put in a great deal of effort on his IR, and the GIMPLE folks have put in a great deal of effort on their IR, and they aren't compatible. And we don't want two mid-level IRs. I anticipate lots of nasty fallout from this one.

In the evening I hosted a BOF session in which I tried to get about fifty of the core developers to agree on solutions to a handful of the most immediately pressing problems with GCC. It got really heated at times. However, we seem to have come out of it with consensus on all the issues, and we may even get them fixed. After that I went to dinner with Mark, Nathan, and a random collection of people from Red Hat and ACT Europe.

Monday, 26 May 2003

# 6 AM

In between talks, people were wandering around verifying each other's PGP keys. This is a process not unlike notarization. If you sign someone's PGP key it means that you met the person whose key it is, face to face, and checked that (a) they are who they claim to be, (b) that really is their key. Assuming that you've never met the person off the net before, part (a) involves looking at government-issued ID; I saw a lot of passports. Surprising to me, although it makes perfect logistic sense in retrospect, is that you do this completely offline. The actual operation of signing someone's key is of course done on a computer, but there's no need to do that immediately after one has checked it. I have a list, on a piece of paper, of people whose identities and key fingerprints I've verified, and I can sign the keys when I get home.

I attended all of the talks today, which was a mistake; several of them were boring. I'm going to summarize only the interesting ones.

Richard Henderson's keynote got the conference off to a solid start. He hadn't given any hint of what he might say beforehand, and many of us were wondering if he'd just make something up the night before. In fact, for all I know, he did, but no one noticed.

He focused on better intermediate representations for GCC and the improvements which they could make possible. It's been known for some time that the current intermediate representation, RTL, is too low-level. It throws away information which modern optimizer algorithms would like to use. There's a project underway at Red Hat to produce a new intermediate representation, called GIMPLE, which is higher-level and easier to work with. Richard pointed out that almost all the interesting optimizations can be done on GIMPLE, which makes the existing code that does them on RTL unnecessary. That's a good thing; that code is old, buggy, slow, and no one wants to work on it.

In Richard's plan, only the very lowest level optimizations would be left to RTL: instruction combination, register allocation, scheduling, basic-block reordering. These passes are either okay as is, or other projects are underway to replace them. He also outlined a clever scheme for reducing the memory consumption of RTL form. Right now RTL is an expansive representation that carries a lot of detail about each instruction:

(insn 12 5 16 0 (nil) (parallel [
            (set (reg:SI 61)
                (plus:SI (mem/f:SI (reg/f:SI 16 argp) [2 a+0 S4 A32])
                    (reg/v:SI 60)))
            (clobber (reg:CC 17 flags))
        ]) {*addsi_1})

Most of this information is redundant with the {*addsi_1} annotation at the end. It could be compressed down to

(insn 12 5 16 0 (nil) {*addsi_1} [
     (reg:SI 61)
     (mem/f:SI (reg/f:SI 16 argp) [2 a+0 S4 A32])
     (reg/v:SI 60)
     (reg:CC 17 flags)
  ])

Probably some of the numbers at the beginning would become unnecessary, too.

Reaction to this scheme was generally positive. People worried about the loop optimizer, which ideally works at a high level, but needs to know about certain low-level characteristics of the target machine. The best approach seems to be providing that information to the high-level optimizers as needed.

My talk (paper) was immediately after Richard's. I talked about the maintenance issues which hinder contributors to GCC. This was generally well received. One thing I hadn't anticipated was the depth of loathing people have for the build process. I concentrated on issues with the code itself, but lots of people wanted to talk about the Makefiles. Which are horrid, it has to be said.

After that we broke for lunch, and then there were several more talks. The most interesting of these was Jason Merrill's detailed introduction to GIMPLE. It uses the same data structures as the very high level "tree" representation that we already have, but imposes constraints which make life easier for optimizers. For instance, an arithmetic expression like y = m*x + b will be broken in half so that there are only two operands on the right hand of each subexpression: T1 = m * x; y = T1 + b.

In the evening there was a reception with dubious cheese and crackers, and decent alcoholic beverages.

Sunday, 25 May 2003

# 6 AM

Up far too early to catch my 8AM flight to Ottawa. (Mad props to Michael and Julia for letting me sleep on their couch, halving the distance that had to be covered at the crack of dawn.) SFO Airport was packed...no surprise, it being Memorial Day weekend. Better yet, they were making everyone take off their shoes and have them X-rayed at the security checkpoint, slowing things down dramatically.

I had a stopover in Detroit; the second leg of the flight was on an itty bitty plane with propellers. Now I know why propellers are not used on most modern airplanes; not only are they noisy, but they make the whole airplane vibrate. Oddly, the gate attendant on the second leg required five volunteers to wait until the next day for their flight, but the plane was only about half full.

Arrived at the hotel at 8pm, then headed out to join the majority of summit attendees at the Earl of Sussex pub down the road, for a badly-needed proper meal. I talked to Dan Jacobowitz for a long time about debugging multi-threaded programs in general, and improvements to be made to GDB in specific. We also touched on generation of DWARF2 debug information, which GCC is not very good at.

Saturday, 24 May 2003

# 5:45 AM

Oh, and ... I got my hands on a cleaning tape. For roughly HALF WHAT I PAID FOR THE DRIVE ITSELF, furrfu, but still. And, once I applied the cleaning tape to the tape drive, it (the drive) started working. Yay.

It's unpleasantly slow — takes about an hour to back up 15GB of data — but I can live with that. Backups are something you start before going to bed, anyway.

# 5:40 AM

My grandmother turned 80 last week. Congratulations, Mia!

My mother came up for the occasion, and we all went down to Stanford to see the 2003 Student Film Festival. Two of the films on the bill — "The Making of Elliot Weisenheimer's Wuthering Hearts" and "The Misfortunes of an Arrogant Child" — were directed by my sister Dara. All good stuff. Well, I was not impressed with "to be".

For the next week Ex Bibliotheca will be coming to you live from Ottawa and Montreal, where I am attending the 2003 GCC Summit and visiting my friends Emmet and Jo, respectively. Connectivity permitting, I plan to post a summary of the day's activities for each of the three days of the conference. I probably won't do that while visiting friends though.

Friday, 16 May 2003

# 7:10 AM

the backup blues

About three weeks ago I bought a whole bunch of gadgets on E-bay. When hooked together properly, they were supposed to become a tape backup system for my computer. I have had far too much fun getting all of these (see the previous discussion of package delivery annoyances for one such incident) but now I have everything I need: a working SCSI controller, a tape drive, the cable to connect them, and tapes to feed the drive.

So today I plugged everything together and turned it on. The tape drive made an odd flapping noise and started flashing half of its many blinkenlights. This, according to the manual, indicates a hardware fault. The only documented way to find out what kind of hardware fault is to use a special utility to read detailed error reports over the SCSI bus. But when I actually did that I get "BugCheck Error: A209" followed by several lines of hex dump. Gee, really helpful. No, code A209 does not appear in the manual.

Having suspicions about the flapping noise, I took the drive apart, and they were confirmed. For you to understand what was wrong with it, I have to explain the guts of a DLT drive in a bit of detail. DLT is a good design, except for one detail that leaves me wondering what the hell they were thinking? That detail is, the tape cartridges have only one spool apiece. The other spool is permanently fixed inside the drive. The designers did this for a noble reason: it saves storage space. The cartridges would have to be twice as big if they had two spools.

However, the implications of that decision are nasty. Since the cartridge only has one spool, the tape has a free end. Somehow the tape must get threaded through the drive and onto the other spool. The mechanism that does this is extremely clever. The free end of the tape has a hole in it. The takeup spool has a springy metal strip attached to it, with a hook on the end. This strip is threaded through the tape path. When you insert a cartridge, the hook is supposed to grab the hole in the end of the tape and and pull the tape through the drive, onto the takeup spool.

It gets more complicated. The hook is held in the right place by another hook, which catches a hole in the end of the strip. That hook is on a plastic swing arm. I can't see all the little pieces because part of the case is in the way, but I think the idea is the tape cartridge pushes the swing arm back, freeing the strip from its hook, just as the hook on the strip catches the end of the tape. In my drive, the strip had come unhooked from the arm without any tape involved. When I turned on the drive, it tested the motor on the takeup spool; since there was nothing stopping it, the strip got dragged through the drive and wound round the spool. The flapping noise was the end of the strip banging on the inside of the case.

The drive was designed to make this fairly easy to fix. You have to take off one cover panel, which is held down only by snap-on hooks (notice a trend?) Then you unwind the strip from the spool and feed it back through the tape path. Getting the strip onto its hook is a little fiddly but not impossible. I did all this...and it still doesn't work. Now what happens is, it powers up just fine, but when I load a tape it scans the tape back and forth for a long time, the "use cleaning tape" light comes on, and when I try to write files to the tape I get I/O errors.

A cleaning tape, of course, is the one thing I didn't buy.

Tuesday, 13 May 2003

# 5:40 AM

not dead yet

However, I have been head down in work, hence the dead air for two weeks in this here weblog. Most of the time I was writing a paper for the 2003 GCC Developer's Summit, which is titled A Maintenance Programmer's View of GCC. The final edition is 6400 words; considering how much text got ripped out and rewritten, I probably wrote closer to ten thousand. In seven days.

Despite this, I did manage to make it to a They Might Be Giants concert on April 29th. Ran into Benjy again there; he has the set list and a review of the concert. Being a rabid fan, he went all three days they played San Francisco; it sounds like the Tuesday show was the weakest of the lot, but I was delighted to hear them play Turn Around and See the Constellation. Not to mention In the Middle with vocals by Robyn Goldwasser, who is John Flansburgh's wife and apparently has a following, judging by the cheers when she took the stage.

The show was at the Great American Music Hall, which is smaller than the Fillmore, and I think it suits TMBG better. Unlike last time, I had earplugs (purchased for 50¢ at the bar)... and my giant sunglasses, which solved the 1000-watt-stage-lights-shone-directly-into-my-eyes issue nicely.

Still haven't heard them do Ana Ng nor Spiraling Shape. Grumble.

correspondence

Tkil suggests a number of notational tricks for making Emacs regexps easier to deal with -- an example:

  (let ((abbrev "[a-z][a-z][a-z]")
        (ws     "[ \t\n]*")
        (wsd    "[ \t\n---]*"))
    (concat
     "^"
     "\\(\\(" abbrev "\\),\\)?" ws
     "\\([0-9][0-9]?\\)" wsd
     "\\(" abbrev "\\)" wsd
     "\\([0-9]*[0-9][0-9]\\)" ws
     "\\([0-9:]+\\)" ws
     "\\([a-z][a-z]?[a-z]?"
        "\\|"
        "[+---][01][0-9][0-9][0-9]\\)"
     "$"))

This is a way to get the effect of perl's /x modifier. Personally, I find all the appearances of \\ detract from readability more than having it on one line with no whitespace, but that's just me.

Kevin Maples reveals himself as the creator of the goddamned internet sticker, and says it isn't supposed to be a M*A*S*H reference, but a "got milk?" reference. Indeed, it did come to me via Sumana, who didn't remember where she got it, but the Leonard connection is the obvious explanation.

misc

The archive links are now up to date. One of these days I'm going to automate that. One of these days I'm going to make an RSS feed for this blog, too, like someone asked me six freaking months ago. Upgrading to a newer version of Blosxom is not really an option, as I would have to repeat the substantial effort of grokking Rael's code (sorry, it's just not written in a style I can cope with) and figuring out what bits needed chainsawing. I suspect I would have to do the performance tuning I did for 2+4i all over again.