price.mit.edu/blog

Last month, we decided at Ksplice that it was time to redesign our website. We had a very clean website that we had developed in-house, but we’re finally selling our Linux security product directly on the Web, we’re beginning to seek greater publicity, and it was time to make a website focused completely on selling Ksplice-Uptrack-the-product rather than explaining Ksplice-the-company and Ksplice-the-technology. This time, we also wanted to get the design from a professional web designer, to see what they do differently.

In the olden days, I gather the way a company might have done this is to find a web design firm in SoHo (or maybe Beacon Hill or Brookline for us) and pay them $20K to make an array of gorgeous mockups on their 30″ Apple Cinema Displays in their loft offices, display them in a presentation for our admiration and our selection, and then turn out perfect XHTML.

I’m not sure it ever worked quite like that in the real world. But in any case it turns out that’s not the world we live in anymore—a good thing, too, because as a bootstrapped startup it’d be hard for us to justify spending $20K on a website at this stage. Instead of a firm, we hired a freelancer. Instead of SoHo, he lives in Sri Lanka. Instead of $20K, we paid on the order of $1K all told—and it would have been under $1K if we had started with a clear sense of how much things should cost in this market. And instead of a theatrically delivered client presentation in our office, the mockups were delivered in a string of emails as I communicated with our designer—let’s call him “Sajith”—over Google Talk to iterate through designs while North America was deep in the night. It’s not hard to see the logic that drives this new way of doing things: $1K is six months’ worth of per capita income in Sri Lanka. Sajith is making a nice living for himself on fees that even a cash-conserving startup like us can easily pay.

Here’s how it works:

1. Post a project on a freelance job board—I used getafreelancer.com.
2. Wait for bids. We were running on our characteristic tight schedule, so I set a 24-hour deadline, and in that interval 26 people and firms offered to do the project.
3. Pick someone. Most of the bidders’ portfolios were terrible, some qualified as mediocre. I went for the only one whose portfolio looked good.
4. Get mockups and iterate. This was the next-to-longest stage of the process. I spent many late hours with Sajith as he presented a mockup image of the page, I made comments, he went off for a few minutes to implement them and I half-worked on something else until he came back, etc. One of the pitfalls: English language skills may not be what you hope for. I learned to give instructions in short sentences, and gave up on trying to get text right in favor of us correcting it later.
5. Slice. This is apparently the word for taking a mockup and producing an HTML document, CSS, etc, that implements it. More on this step below.
6. Integrate and polish. Our sites comprised a Django application with a handful of distinct pages, and our mostly-static main website with a large number of pages, of which we were only redesigning/adding a few of the most critical for selling our product. Taking Sajith’s static HTML and turning it into Django templates that behave in all the right ways, getting all the right text in place, and dealing with final improvements to the HTML and the CSS to the point where we were happy, consumed about three person-weeks of engineering time on our end. I knew there would be work to do here, but we were completely unprepared for how much work it was.

I’ll close with the episode in this process that really made me feel I was living inside a Tom Friedman book. We were humming along on our aggressive schedule, and one day Sajith failed to deliver on a deadline: he was to get a page of sliced HTML to me that morning, his evening. I pressed him as the hours passed—OK, I understand some details aren’t finished, can you get me what you have? We want to start on integrating it. Eventually he confessed that he wasn’t doing this work himself; rather, he had himself gone out and found a subcontractor, somewhere else in the world, who had promised to do the slicing, and the subcontractor had failed to come through. (Apparently he had done the job and then accidentally deleted it—someone needs to learn about source control.) After another failed subcontract attempt the next day, Sajith gave up and did the slicing himself. Maybe the outcome of Sajith’s experiment suggests we don’t live in Friedman-flattopia just yet.

This January, Ksplice swelled from 8 people to 20 people. You can imagine what that did to the office—it’s a good thing that Tim and Jeff have been practicing the art of rearranging a space to fit more people than ever thought possible since their days in the SIPB office. Fortunately, because we have at our disposal a computer-systems training and recruitment machine of awesome effectiveness, our interns defied Fred Brooks and produced a great deal of useful code.

The problem: how to keep track of all that new code and get it all reviewed smoothly? Our ad hoc practices relying on one-on-one exchanges clearly were not going to scale. The solution: on the first day the new interns showed up, I took a couple of hours and threw together a script to request code reviews. The key design considerations were

• Public visibility. The script sends mail, and CCs a list going to the whole team.
• Non-diffusion of responsibility. The user must identify someone to be the reviewer, and the request is addressed to them.
• Git friendliness. Being a kernel shop, we use Git for everything, so the script assumes a basic Git workflow: you make some commits, and then you request a whole series of commits to be reviewed at once.

We looked at some existing code review tools like Gerrit and Rietveld, but we weren’t happy with any of them because the ones we found don’t work on branches—they work on individual commits—and we have drunk too deeply of Git to be satisfied working that way.

On the other hand, being the product of a few hours’ work, there’s several things that could be made better. The interaction with the user could be better to prevent mis-sends. The script could do better at detecting what the repository in question is called, it could take advantage of commit messages for better subject lines, and it could try to give the reviewer a command line that will show the commits in question. (Until then: it’s usually git log -p --reverse origin/master..origin/branchname.) Someday we may also want a system that tracks what commits have been reviewed by whom and blocks commits from going in without review; that will be a bigger project.

Apparently we did something right with this script, because I heard a couple of people say they’d like to use it outside of Ksplice. So the other day we decided we were happy to release it as free software. As of last night you can get it from Github—enjoy.

Let me know if you use it, and patches welcome, of course.

My favorite moments with free software are when I get annoyed with some manual task that a tool leaves me to do for myself, and then invent a feature that the tool should have to handle the task for me.

With any software free or proprietary, if I’m lucky the tool might have a configuration system powerful enough to let me effectively add the feature from the outside. But with free software, I don’t need the authors to have anticipated my needs—I can reach into the guts of the software itself and change it to work the way I want. If it’s a friendly codebase or if I’ve hacked on it before, I may be able to add my change in a few minutes. And hey presto: software that does exactly what I wanted. It’s a lot more fun than praying to the vendor and waiting a few years, and it’s faster and more reliable too.

So it went with Git one night last October. I was repeatedly revising a branch with git rebase -i. A couple of points along the branch were marked as branches of their own, so every time I changed something I would have to either

• rebase the full branch, then do a dance with checkout and reset to update the sub-branches, carefully typing the correct new commit IDs;
• rebase the full branch, then muck with update-ref with the same care about getting commit IDs right; or
• rebase the first sub-branch, then use rebase --onto to move the next sub-branch on top of it, then rebase --onto again for the main branch

What I really wanted to do was just

• rebase the full branch, and tell the sub-branches to come along for
  the ride.

Fortunately I’d worked on the code for Git’s interactive rebase before—at Ksplice we push Git to its limits in six different directions, and rebase -i we push beyond the limits of stock Git—so I knew where to find the moving parts that could do what I needed. Four minutes after having the idea, I was happily using the new feature.

If you want the feature too, it’s up on my Git git repo. Or you can wait until I get it upstream. Why haven’t I done that already? That’s another old story about software. My 4-minute, 4-line patch turned into 29 lines with documentation and with proper error handling, then 147 lines to make the feature easy to invoke, and then 231 lines with test cases. So I just finished all that work today. Maybe you’ll see the feature in Git 1.7.1 this spring.

At Ksplice, we put a lot of effort and discussion into how we manage projects, in part because we know we aren’t as good at it yet as we’d like to be. Books by managers and books for managers lie scattered around the office and employees’ rooms. So imagine my surprise and delight the day after Christmas when I opened The Soul of a New Machine, Tracy Kidder’s 1981 classic about the machines that made the computer age and the geeks who built them, and discovered it was about project management.

Keith sometimes remarks that Ksplice needs a documentarian. The Soul of a New Machine is the result of a project that had a documentarian, one who produced prose. The Eagle project at Data General set out to build a new computer, a 32-bit version of the existing 16-bit Eclipse line, just as DEC raced into the lead in the minicomputer market with the 32-bit VAX. Tracy Kidder, a writer for The Atlantic looking to write a story about technology, connected with his editor’s old college roommate, the leader of the Eagle project, Tom West.

The story that Kidder tells is full of implicit lessons that look as current today as they were in the computing projects of thirty years ago.

Schedules. Everyone knows that computing projects run slow. When the Eagle project started in July of 1978, it set an insanely fast timeline to have the whole computer architected, designed, built, and debugged by April 1979. They didn’t make it, of course, and many team members expected that from the start. But at every stage West, the engineer in charge, insisted on treating the schedule seriously—”come on, this schedule’s real”—setting intermediate deadlines as if the April date would be met. And though April slipped, the project was done in October, just fifteen months after it started and still a rapid turnaround by anyone’s count.

Delegation. On a big project, the person in charge can’t do everything themselves, or even keep a close eye on all of the work. They have to rely on others to do it right. Good managers know this, but it’s nerve-wracking to actually put it into practice. West itched to get into the lab and start debugging the prototype himself, telling Kidder, “Rocking back here in my chair and talking about doing it is one thing, but it makes me worry. It gives me a nauseous feeling, because I’m not doing it.” Eventually, as one lieutenant puts it, he “gripped the arms of his chair and decided to trust” the engineer leading the hardware team.

Perfect vs. done. Before Eagle, some of the same engineers had worked on projects to build a 32-bit machine from scratch. None of these projects were completed. Eagle would be tied by backward compatibility to the 16-bit Eclipse, and at the outset some engineers saw the idea as “a kludge on a kludge on a kludge”, or “a paper bag on the side of the Eclipse”, and wanted nothing to do with it. Yet West convinced them all to sign on to the project anyway, and in the end it was the compatible computer that was completed, sold well, and rescued Data General.

It’s not only the lessons that seem not to have changed. Some of the engineers on the Eagle project recall how as undergraduates they would “stay up all night and experience … the game of programming”, and we can all think of people thirty years later who, like a few of them, “started sleeping days and missed all their classes, thereby ruining their grades.” One comforting thought: Carl Alsing, the engineer in charge of the microcode team, was one of those who actually flunked out of school.

Finally, a word about the writing. The technical exposition is incredible. On the one hand, the reviewer for the New York Times heaped praise on the prose that enabled him to “follow every step” despite knowing nothing about computers (and a reviewer writing in 1981 could mean that in a much stronger sense than any reviewer typing into their laptop today.). From my very different perspective, I was fascinated to learn details about the faraway architectures and design constraints of a different era. And in 291 pages delving frequently into technical aspects of computer architecture, digital logic, and software, I never felt condescended to and I found not one mistake.

Maybe Ksplice should get a documentarian after all.

This week I got myself eaten by a math problem. Fortunately the problem is solved now, and I’ve escaped. Let me explain.

Two years ago, I was in Erik Demaine’s class about computational geometry, and heard about a problem that I wanted to solve. Suppose you have a convex polyhedron in ordinary 3-space. Then there is an intrinsic metric on the surface points of the polyhedron: the distance between two points is the length of the shortest path between them that runs along the surface. You can describe this metric to me without mentioning the embedding in 3-space, for instance by giving the shapes of a bunch of triangles and telling me which sides connect to which. The metric will certainly have these three properties:

1. it’s homeomorphic to a 2-sphere: I can put the triangles all on a sphere preserving their interconnections, if I’m willing to stretch and bend them
2. it’s a polyhedral metric: every point has a neighborhood with the same metric as a Euclidean disk (for most points) or cone (for the vertices)
3. it’s locally convex: every circle of radius r has circumference at most 2πr

Now suppose you hand me a metric in the form of a bunch of triangles and notes on which edges to connect to which, and I confirm that they satisfy properties 1, 2, and 3. The great thing is that this is actually enough to guarantee that the triangles can be put together in 3-space to form some convex polyhedron, and this polyhedron is unique. (Here it’s crucial that I be allowed to bend the triangles, but without stretching — like paper.) Soviet mathematician A. D. Alexandrov proved this theorem in the 1940s. But Alexandrov’s proof doesn’t say how I can actually go and construct this embedding, so it opens up an algorithmic problem: given a metric satisfying properties 1, 2, and 3, how can we construct the unique convex polyhedron with this metric that Alexandrov’s theorem guarantees us?

Just the previous year, mathematicians Alexander Bobenko and Ivan Izmestiev had shown how to build the polyhedron by solving a rather involved differential equation. I figured it should be possible to get an explicit algorithm by discretizing their differential equation, and put a time bound on it by showing that the discrete steps don’t have to be too small. I cornered math problem-solver extraordinaire Daniel Kane, we sat down for a couple of hours with the Bobenko-Izmestiev paper, and he agreed—this shouldn’t be too hard.

Well, we were half right. Our approach worked, and we obtained an algorithm with an explicit time bound, a polynomial in the size of the input and its geometric ratios. Voilà:

Theorem. Given a convex polyhedral metric M homeomorphic to a sphere with n vertices, ratio S between the largest and smallest distance between vertices, and defect (discrete Gaussian curvature) between ε₁ and 2π−ε₈ at each vertex, an ε₆-accurate ε₉-convex embedding of M can be found in time

Õ(n^915/2 S⁸³² / (ε¹²¹ ε₁⁴⁴⁵ ε₈⁶¹⁷) )
where ε = min(ε₆/nS, ε₉ ε₁²/nS⁶).

Now, that bound with its enormous exponents was great for getting people’s attention in talks. You don’t often see a time bound like that, and the reason is that to get that bound we had to pursue the problem and hammer it out piece by piece, assembling a diverse array of geometric lemmas, long past the point where sane people might have stopped. Daniel and I probably spent close to 100 hours meeting and working on the problem, some of it together with Erik, and I spent something like two or three times as long nailing all the details down in writing. The work became my master’s thesis, I presented it at the WADS conference this summer, and we submitted the paper to a journal. We breathed easy for a while.

Then we heard back from the reviewers. Turns out peer review is a good idea. One reviewer grabbed onto a particular subproblem that he apparently thought was more interesting than the whole rest of the paper. At each iteration we need to find an appropriate retriangulation of the surface. What we need is described by a well-understood concept, a “weighted Delaunay triangulation“. In the familiar Euclidean setting a Delaunay triangulation is equivalent to a “Voronoi diagram“, so we originally thought that some existing papers that described how to compute a Voronoi diagram on a polyhedral surface were enough to give us the weighted Delaunay triangulation we needed.

This reviewer demanded we give more attention to the issue, and he was right—the problem was harder than we realized. On a polyhedral surface things are more complicated than in the plane; for one thing, there can be infinitely many straight lines between two points, and to make a Delaunay triangulation you need to use the right ones. But in two marathon sessions this week and 2000 words of writing, Daniel and I worked out how to get an unweighted Delaunay triangulation from a Voronoi diagram, and then how to adjust the triangulation to handle weights. So the reviewer was right to think the problem more interesting than we had treated it, and now we’ve solved it. Since our new algorithm for Delaunay triangulation is straightforward and is known to run in a practical amount of time, it may prove to be the most reusable part of the paper.

Anyone interested can read more in the paper (pdf). The new Delaunay triangulation algorithm is in the last section.

So that was my vacation. How was yours?

And I intend to post here from time to time.  In general I plan to write more of an “ideas” blog than a “cool thing I saw today” blog; I post my fill of the latter on Twitter and on Zephyr.

But I found less time this week to write than I planned on, and I told people I’d make a post by tonight, so here is one lazy post.  More-interesting posts are in a draft state.