Andrew Birkett’s blog

I find performance work quite relaxing and satisfying. I think there are several reasons for this. Firstly, it is very methodical work. It goes like this:

1. Establish which particular aspects of your application are too slow
2. Establish what would consistute “fast enough”.
3. Create easy-to-run test cases for each area that needs speeding up (eg. application startup time).
4. Run a profiler to see where your application is actually doing during that time.
5. Based on that evidence, make changes to the application.
6. Repeat until things are fast enough.

It is very methodical, but enjoyable too. When you are identifying the performance bottlenecks, you have powerful tools (such as Intel’s Vtune) at your disposal and they do most of the hard work for you. It is always very satifying to use good tools.

These tools produce a large amount of data, and you have to put on your “investigation” hat to intepret the raw data. I enjoy this phase, partly because I know that all the relevant information is available to me, and partly because it lets you see your application from a different angle. It’s like exploring a landscape, building up a map of an area that you only vaguely knew before. I am always very familiar with the static structure of the applications I work on (what each bit of the code does, and how they fit together), but it’s only when I am doing performance work that I look at the big-picture dynamic structure of the application.

During this investigation phase, some of the facts which reveal themselves are expected and familiar - for example, you would expect a game would spend a lot of its time drawing graphics. These points act as signposts to me - known markers in the large mass of information. But then when you continue drilling down, you often hit surprises. Beforehand, you probably had suspicions as to where the time was being spend. I have to say that my suspicions have always been consistently wrong - to the point that I no longer bother thinking about them too much .. I just run the profiler. During performance work, I find myself alternating between thinking “yup, that all seems reasonable” and “oh gosh, what’s going on there?”. It’s like some kind of crazy jigsaw puzzle. Sometimes weird stuff shows up; people accidentally leave bits of code in the application which shouldn’t be there. Mostly however, the code is basically fine, but with your performance-tuning goggles on (and the benefit of hindsight) you can see how things can be restructured to make them more efficient.

Once you’ve explored around for a while (a fine opportunity to drink some tea) you end up with probably a few areas which you think could be improved. Now comes the creative side of performance work, because at this stage you have lots of choices. You could make the program do the same amount of work, but faster. You could make the program avoid having to do so much work. You could delay the work until later, waiting for a time where a delay wouldn’t be so important, and possibly never having to do the work at all! There are other angles to approach this. It is often not the absolute performance of your application which is critical - it is the user’s _perception_ of the performance which matter. This is why an application will display a progress bars during a long operation. This is why we have splash screens during application startup. This is why lift engineers put mirrors in lobbys near to the lifts. People hate having to wait, and they perceive and application which makes them wait as being slow.

So, the “make things appear less slow” stage can involve a huge range of techniques, from low-level assembler optimizations, through design changes, right up to HCI tricks. You have a real opportunity to pull out your toolbox and go to work. But at all stages, you can always go back and test how well you’ve solved the problem. It’s a lot easier than, for example, choosing which new features to add to an application.

Right, that’s nearly the end. This turned out not to be so much about profiling itself, but more about my reaction to the task. I’m not sure why I’ve recently turned my attention away from technology towards my reaction to technology. Partly it is triggered by the title of a famous paper by Dijkstra, “Programming considered a human activity”. Yes, I am still strongly interested in technology and I think there are great gains still to be made by improving our technology. But at the same time, it is we human beings who use the technology, and we who are affected by its results. Software projects are carried out by humans who get bored sometimes, excited sometimes, and are most definitely not robots. A software methodology which treated team members as interchangable automata is doomed to failure, because it would crush the spirit of each team member. But on the flip side, you need some structure in order to harness the team’s energy and coordinate their efforts. I think the best gains are to be made by adopting methods which amplify and harmonize the efforts of individuals, rather than focusing on process and expecting individuals to execute that process. I think a useful first step is to be aware nof your own rational, emotional and physical reactions to the work you do, and try to avoid the nasty “distraction field” which seems to operate around computer. Oh look, another superficially interesting article on slashdot! There goes another few minutes of my life!

Who says you can’t fix things any more? (more photos here).

Sitting at work waiting for our C++ application to link reminds me that just because your language can do lots of stuff at compile time doesn’t mean you necessarily want it to do so. Usually with a C++, the linker goes through your code figuring out what address each function will live at, and making each function-call jump to that address. You do almost all the linking work upfront. In contrast, other languages are lazier - they don’t bother doing any work until it’s actually needed, which makes for faster edit/compile cycles because you’re not doing the work upfront. Actually, often these languages forced into being lazy because the information isn’t available at compile time. But contrapositive doesn’t apply: if you have the information you don’t have to be eager. A C++ compiler could delay figuring out which function to call until the first time the function was called. You’d also need to keep all the type information around until runtime, but you’re probably already doing that for debugging purposes anyway. You’d be moving one phase of the compiler from compile-time to run-time.

You might think it would all be much easier to do this stuff by starting with a more dynamic language. but then with “dynamic-C++” you still maintain the benefit of having static typing checking for silly mistakes. Which brings me full circle to a paper which was on LtU recently which discusses this very topic (and which I have yet to read!).

Ah, dynamic languages vs. static languages. Here I am again.

I got a Creative Labs NX Pro webcam, but unfortunately there aren’t linux drivers for it yet. I did find a project which is developing a driver for zc030x-based webcams. They’ve managed to grab a still image from a webcam, so that’s hopeful. However, the driver only builds under linux 2.4 at the moment and I’m using 2.6.

First of all, I did a bit of reading about the kernel usb support.

• There’s a skeleton usb driver (in drivers/usb/usb-skeleton.c). Under Documentation/DocBook there’s an article about the USB system.
• drivers/usb/media/dabusb.c is quite a clean looking driver
• USB programmers guide
• Loads of great articles about porting drivers to the 2.6 kernel

I read through the existing code for the zc030x driver, and used Freemind to organise my notes about it.

Since then, I’ve crashed my computer more times that I can remember. Writing kernel code is very unforgiving. If you make a mistake, the whole computer will probably hang. I’ve ended up adopting a very different, even-more-paranoid-than-usual coding style, and have aliased insmod/rmmod to automatically run sync beforehand! But I’ve been making progress - the driver compiles, loads, creates the /dev file correctly, and responds to incoming data .. but I don’t think the webcam is being initialised properly yet. I need to do more snooping of the datastream under Windows to understand what needs to be sent when.

USB itself has been really nicely designed. The designers have obviously considered real use-cases and designed for these. For example, there are four different modes of data transfer, including isochronous (regular time interval, eg. for a webcam running at 15fps) and bulk transfer (eg. for a usb disk, which wants to use as much bandwidth as is available). When there are multiple devices plugged in to your PC, the USB system itself is responsible for arbitrating who is allowed to use how much bandwidth. The usb system knows that it’s better to drop a webcam frame entirely than to deliver it really late. On the other hand, it knows that it should stop files being copied to my usb storage stick if the webcam wants to send a frame. All of this happens behind the scenes, as far as a programmer is concerned. USB is not just an end-to-end pipe, like rs232 was. There’s a whole bandwidth/device management layer on top of that.

Oh, finally .. learning a new code always takes a bit of effort, but it can be made easier by using decent tools. Xref is a refactoring/navigation tool for C. If you’re working on a C program with emacs, and you’re not using this already then you must enjoy pain. Note that you don’t want to be browsing the kernel headers in /usr/include - you need to use the ones under /lib/modules/version/build. Here’s the options for xref to set this up.

[webcam]
  //  input files and directories (processed recursively)
  ~/Projects/zc0302/
  -D__KERNEL__
  -resetIncludeDirs
  -I /lib/modules/2.6.5-gentoo/build/include/linux
  -I /lib/modules/2.6.5-gentoo/build/include
  -I /lib/modules/2.6.5-gentoo/build/
  //  directory where tag files are stored
  -refs ~/Xrefs/webcam
  //  number of tag files
  -refnum=10

Backyard DNA computing? Yeah, baby. Doesn’t seem too hard.

First of all, what is DNA computing. Aren’t computers made from metal with CPUs and memory? Yes, they commonly are, but that doesn’t mean that all computers must take that form. After all, a computer is just a compute-r, something which computes answers to problems.

I remember my grandad, who worked in the police, telling me how they used to keep details of criminals on filing cards. On the edge of each card there were a number of punched holes, some punched right the way to the edge. Each punched hole corresponded to some fact about the person - whether they were a burglar or a mugger or things like that. So, if you wanted to pick out all the burglars, you’d take a metal skewer and slide it in through the appropriate hole and lift it up. All the cards whose hole had been punched right to the edge (non-burglars) would stay behind, whilst all the relevant ones would get lifted up. Now, while that a million miles away from how modern “computers” work, it still has some flavour of “computing” a solution to a problem.

Now let’s flip to DNA. It’s a long polymer (poly=many, mer=parts) made up from monomers called nucleotides. Nucleotides come in four flavours (called A, T, C and G) and have two neat properties. Firstly, they can join together into big long chains. Secondly, these chains can get zipped together if there are matching nucleotides on each side (A matches with T, G matches with C). It’s the fact that these nucleotides are fussy about who they zip up next to which makes them interesting as computing devices.

If we’re going to try to solve some “computing” problem using DNA, we’ll have to pick a problem which doesn’t require a keyboard or a monitor, since test-tubes don’t come with them attached. The first problem to be solved in this way was what’s called the Hamiltonian Path problem which, despite the formidable name, is really simple. Imagine a small group of islands, connected by bridges. You start on Starting Island, and your aim is to get to Finish Island by crossing bridges, visiting each island exactly once. Now, depending on how many bridges there are, there may be several ways to do this or there may be no way to do it. So, to play the Hamiltonian Path game, someone describes the islands and bridges to you, and you have to either say “here’s a solution” or “there are no solutions”. When there’s lots of islands, it gets really quite Hard.

Fortunately for us, a bright chap called Leonard Adleman figured out how we can cheat at this game by messing around with DNA in testtubes until we find the answer. He’s a pretty bright guy, famous for being the “A” in the RSA encryption system among other things.

The trick goes like this. For each island, we choose a different 20-mer strand of nucleotides (ie. literally “20 parts”; molecular chemists like to pretend they know greek). It doesn’t really matter too much whether you choose ATCGGCTACTGCATGCTGAA or GGGGAAAATTTTCCCCAAAA for a given island, as long as they are different. You do need quite a lot of each strand though - billions and billions of them. And where do you get them from? Well, you can just buy them. They’re called oligonucleotides (more greek, oligos means “few”). Phone them up, say “hey, can you knock me up some GGAACCTT’s and a few billion ATCCGAT’s please?” and they’ll send you out a little white lump.

Here comes the clever bit. We’re going to build strands of nucleotides which represent the bridges. Let’s assume there’s a bridge from Starting Island to Fire Island. Remember how A and T will stick together, and G and C will stick together? These are called complementary pairs. Our bridge-strand is going to be carefully chosen so that its first half will be complementary to the second half of Starting Island’s nucleotide strand, and the second half of the bridge strand will be complementary to the first half of Fire Island’s strand. That means it can act like sticky tape to join the two together. That’s pretty cool, and it’s the first hint that something a bit like “computation” is going on here. We’ll need strands which correspond to each bridge, and we’ll need quite a lot of copies of them - Adleman used about 30,000,000,000,000,

So we take our island-strands and our bridge-strands and we put them into a test-tube. We give it a bit of a shake and we’re done. Problem solved!

Ahem, well, the problem has been solved but we need to do a bit of work to reveal the answer. What has happened in the test-tube is that bridge strands have joined the island strand together into big chains, each corresponding to a possible route through the islands. And because we started with so many billion copies of each, and we gave the test-tube a pretty good shake, we can be reasonably sure we’ll have plenty of example of each possible route through the islands in our test tube. Unfortunately, most of these routes will not honour the “only visit each island once” rule. However, it’s not hard to get rid of a lot of the wrong answers by selecting only those DNA strands with the right length. If we had 14 islands (like Adleman did) then we can pick out the DNA strands which are 14*20 = 280 nucleotides long. For this, we can use gel electrophoresis which amounts to blasting the DNA strands down through gel using an electric field to persuade them to move. (As an aside, I had an interesting conversation with someone I’d just met in the pub about why you can’t easily use mass spectroscopy for this).

We’re still not quite finished though. Just because our route visited 14 islands doesn’t mean we visited all 14 islands. Maybe we just spun around in a loop between Starting Island and Fire Island. And also, there’s no guarantee that the routes all started and finished in the right place. Again, biochemistry comes to our rescue. It’s not too difficult to pick out these DNA strands which start with Starting Island’s sequence and end with Finish Island’s sequence, thanks to a rather “special” guy called Kary Mullis. He won a Nobel Prize for inventing the PCR reaction, which is a way of selecting particular strands of DNA and making loads of copies of them. As with a lot of great inventions, it’s blindingly obvious with hindsight, but Kary was the first person to conceive of it - largely due to his background in both computer science and chemistry. People had been doing the polymerase reaction for ages (well, we humans had been doing it for millions of years, but we only noticed in the past few decades). The polymerase reaction builds up a (complementary) copy of an exiting DNA strand, so you end up effectively with twice as much. Mr Mullis’s stroke of genius was to do it again. And again. And again. And again, until you disappeared under a mountain of rice and you can’t find your chessboard any more. You should try and borrow a copy of his book, “Surfing Naked in the Mind Field” for a mind-altering view of the world. I think I left my copy in Miami somewhere, but I’m left with the memory of a very unique person. Oh, yeah. Special.

Once we’ve picked out all the strands which start and end in the right place, we go through the remaining pile firstly discarding those which never visited Fire Island, then those which missed out on the delights of Infinite Chocolate Island, and so on until we are left with a somewhat reduced pile of routes/strands. This selection process is done with some glass beads and some molecular glue. If you want to pick out strands containing the sequence AAAA, you can “glue” some TTTT strands (the complement) to some glass beads. Then you pour the solution containg your DNA over the beads, and the AAAA-containing strands will stick to them. Then you scrape them off with a spoon. Well, that’s close enough.

All of the remaining strands represent a route which visited all the islands exactly once. If you had microscopic fingers, you could pick up a strand of DNA and shout “Eureka, I finally have the answer!”. But, if your fingers are human-sized like mine, you will need a final bit of biochemistry to reveal the answer. There’s several different ways to read out the sequence of nucleotides which are left - Adleman used Graduated PCR. But at the end of the day (seven days in Adleman’s case) you end up with answer. Either there was a path through all the islands in which case you’ll have almost certainly found it (as in, really really almost certainly), or there wasn’t in which case you ended up with a sad empty test-tube.

So that’s it. That’s how you can perform a computation in a test-tube using DNA. There’s so much interesting stuff in this area. For a start, just because we can solve an island-hopping problem doesn’t neccesarily mean we can use DNA to solve every conceivable computing problem. It turns out, however, that DNA is that powerful. And, for certain types of problems, it may be a lot quicker than existing electronic computers. After all, you don’t need to buy a faster processor - you just use a bigger testtube! You can’t really use C++ to write DNA programs, so how do you encode an arbitary problem onto strands of DNA? It’s also interesting to look at how the imperfect nature of a biochemical reaction affects the usefulness of the results we get. Our electronic computers aren’t perfect theoretical beasts either - they get hit by alpha particles and have to endure power supply fluctuations. Finally, and this is where my interest really kicks in, can I coin the phrase “backyard dna computing” (cf. bymc) to describe what I’m going to try Real Soon Now -…

Emergency Mental Health or a guide for survivng a typical software project?