Yesterday I shipped cvs-fast-export 1.15, with a significant performance improvement produced by replacing a naive O(n**3) sort with a properly tuned O(n log n) version.
In ensuing discussion on G+, one of my followers there asked if I thought this was likely to produce a real performance improvement, as in small inputs the constant setup time of a cleverly tuned algorithm often dominates the nominal savings.
This is one of those cases where an intelligent question elicits knowledge you didn’t know you had. I discovered that I do believe strongly that cvs-fast-export’s workload is dominated by large repositories. The reason is a kind of adverse selection phenomenon that I think is very general to old technologies with high exit costs.
The rest of this blog post will use CVS as an example of the phenomenon, and may thus be of interest even to people who don’t specifically care about high version control systems.
I just had a rather hair-raising experience with a phase-of-moon-dependent bug.
I released GPSD 3.11 this last Saturday (three days ago) to meet a deadline for a Debian freeze. Code tested ninety-six different ways, run through four different static analyzers, the whole works. Because it was a hurried release I deliberately deferred a bunch of cleanups and feature additions in my queue. Got it out on time and it’s pretty much all good – we’ve since turned up two minor build failures in two unusual feature-switch cases, and one problem with the NTP interface code that won’t affect reasonable hardware.
I’ve been having an extremely productive time since chewing through all the stuff I had deferred. New features for gpsmon, improvements for GPSes watching GLONASS birds, a nice space optimization for embedded systems, some code to prevent certain false-match cases in structured AIS Type 6 and Type 8 messages, merging some Android port tweaks, a righteous featurectomy or two. Good clean fun – and of course I was running my regression tests frequently and noting when I’d done so in my change comments.
Everything was going swimmingly until about two hours ago. Then, as I was verifying a perfectly innocent-appearing tweak to the SiRF-binary driver, the regression tests went horribly, horribly wrong. Not just the SiRF binary testloads, all of them.
I shipped point releases of cvs-fast-export and reposurgeon today. Both of them are intended to fix some issues around the translation of ignore patterns in CVS and Subversion repositories. Both releases illustrate, I think, a general point about software engineering: sometimes, it’s better to punt tricky edge cases to a human than to write code that is doomed to be messy, over-complex, and a defect attractor.
Here at Eric Conspiracy Secret Labs, we ship no code before its time. Even if that means letting it stay in beta for, er, nearly twelve years. But at long last I believe my shipper tool is ready for the world.
Since I’ve already described shipper in detail I won’t rehearse its features again. Suffice it to say that if you’re the kind of hacker who ships point releases more often than about once a week, and you’re tired of all the fiddly handwork that implies, you want this more badly than you know.
There’s a recent bug filed against giflib titled giflib has too many unnecessary API changes. For a service library as widely deployed as it is (basically, on everything with a screen and network access – computers, smartphones, game consoles, ATMs) this is a serious complaint. Even minor breaks in API compatibility imply a whole lot of code rebuilds. These are not just expensive (requiring programmer attention) they are places for bugs to creep in.
But “Never change an API” isn’t a good answer either. In this case, the small break that apparently triggered this report was motivated by a problem with writing wrappers for giflib in C# and other languages with automatic memory management. The last round of major changes before this was required to handle GIF animation blocks correctly and make the library thread-safe. Time marches on; service libraries have to change, and APIs with them, even when change is expensive.
How does one properly reconcile these pressures? I use a small set of practice rules I think are simple and effective, and which I think are well illustrated by the way I apply them to giflib. I’m writing about them in public because I think they generalize.
Blogging has been light lately because I’ve been up to my ears in reposurgeon’s most serious challenge ever. Read on for a description of the ugliest heap of version-control rubble you are ever likely to encounter, what I’m doing to fix it, and why you do in fact care – because I’m rescuing the history of one of the defining artifacts of the hacker culture.
I just shipped version 1.10 of cvs-fast-export with a new feature: it now emits fast-import files that contain CVS’s default ignore patterns. This is a request for help from people who know CVS better than I do.
This is a brief heads-up that the reason I’ve been blog silent lately is that I’m concentrating hard on a sprint with what I consider a large payoff: getting the Emacs project fully converted to git. In retrospect, choosing Bazaar as DVCS was a mistake that has presented unnecessary friction costs to a lot of contributors. RMS gets this and we’re moving.
I’m also talking with RMS about the possibility that it’s time to shoot Texinfo through the head and go with a more modern, Web-friendly master format. Oh, and time to abolish info entirely in favor of HTML. He’s not entirely convinced yet of this, but he’s listening.
Here’s a late New Year’s gift for all you repository-editing fiends out there: the long-awaited and perhaps long-dreaded reposurgeon 3.0.
In Heads up: the reposturgeon is mutating! I described the downside of a strategy of incremental small language changes aimed at preserving compatibility: you can wind up trapped by suboptimal early decisions. Sometimes, you have to bust out and do the big redesign, which I did and why there’s a bump in the major version number (the last time that happened was when reposurgeon got the ability to read Subversion dump files directly).
The biggest change is that the command language syntax has mutated from VSO to SVO. What? You’re not up on your comparative linguistic morphology and gave no idea what I’m talking about? That’s Verb-Subject-Object to Subject-Verb-Object.
My first gift of the new year. Read it here.
Not long ago I pulled the plug on one of the two CVS export utilities I was maintaining. One consequence of this is that I decided I needed to get the other one out of beta and into a state I would be willing to ship as 1.0.
And lo, it has come to pass. I just shipped cvs-fast-export 1.0. It has been well field-tested; a couple of weeks ago I used it to rescue the history of Gnu Troff.
There are several CVS exporters out there that suck pretty badly. (To be fair, the perversity of CVS is such that doing an even half-decent job of lifting CVS histories into a modern version-control system is quite difficult.) Now that this one is shipped I know of exactly two that don’t suck. The other one is Michael Haggerty’s cvs2git, which I’m working with him on improving.
Tradeoffs: cvs2git is slow and a bit clunky to use (I’m improving the latter but can’t fix the former). cvs-fast-export is blazingly fast (like, 3.7K commits a minute) but has a hard repository-size limit – above it you run out of core and the OS reaps the process in mid-flight. (Very few projects will hit this limit.)
For each tool there are weird CVS edge cases that it gets wrong. The sets of edge cases are different. cvs2git’s may be smaller, but I’m not sure of that; we haven’t set up head-to-head testing yet. Most projects will not trip over either set of problems.
cvs-fast-export is better documented, especially around error conditions.
Help stamp out CVS in our lifetime!
There are a lot of things people writing software do in the world of bits that don’t have easy analogs in the world of atoms. Sometimes it can be tremendously clarifying when one of those things gets a name, as for example when Martin Fowler invented the term “refactoring” to describe modifying a codebase with the intent to improve its structure or aesthetics without changing its behavior.
There’s a related thing we do a lot when trying to wrap our heads around large, complicated codebases. Often the most fruitful way to explore code to modify it. Because you don’t really know you have understood a piece of code until you can modify it successfully.
Sometimes – often – this can feel like launching an expedition into the untamed jungle of code, from some base camp on the periphery deeper and deeper into trackless wilderness. It is certainly possible to lose your bearings. And large, old codebases can be very jungly, overgrown and organic – full of half-planned and semi-random modifications, dotted with occasional clearings where the light gets in and things locally make sense.
There’s an ancient Unix maxim to the effect that a tool that gets 85% of your job done now is preferable to one that gets 100% done never. Sometimes chasing corner cases is more work than the problem really justifies.
In today’s dharma lesson, I shall illustrate this principle with a real-world and useful example.
I did something unusual today. I pulled the plug on one of my own projects.
In Solving the CVS-lifting problem and Announcing cvs-fast-export I described how I accidentally ended up maintaining two different CVS-to-something-else exporters.
I finally got enough round tuits to put together two-thirds of the head-to-head comparison I’ve been meaning to do – that is, compare the import-stream output of cvs-fast-export to that of cvsps to see how they rate against each other. I wrote both git-stream output stages, so this was really a comparison of the analysis engines.
I wasn’t surprised which program did a better job; I’ve read and modified both pieces of code, after all. Keith Packard’s analysis engine, in cvs-fast-export, is noticeably more elegant and craftsmanlike than the equivalent in cvsps. (Well, duh. Yeah, that Keith Packard, the co-architect of X.)
What did surprise me was the magnitude of the quality difference once I could actually compare them head-to-head. Bletch. Turns out it’s not a case of a good job versus mildly flaky, but of good job versus suckage.
The comparison, and what I discovered when I tried to patch cvsps to behave less badly, was so damning that I did something I don’t remember ever having felt the need to do before. I shot one of my own projects through the head.
A few days ago I released reposurgeon 2.43. Since then I’ve been finishing up yet another conversion of an ancient repository – groff, this time, from CVS to git at the maintainer’s request. In the process, some ugly features and irregularities in the reposurgeon command language annoyed me enough that I began fixing them.
This, then, is a reposurgeon 3.0 release warning. If you’ve been using 2.43 or earlier versions, be aware that there are already significant non-backwards-compatible changes to the language in the repository head version and may be more before I ship. Explanation follows, embedded in more general thoughts about the art of language design.
If you’re a regular at A&D or on my G+ feed, and even possibly if you aren’t, you’ll have noticed that I ship an awful lot of code. I do get questions about this; between GPSD, reposurgeon, giflib, doclifter, and bimpty-bump other projects it is reasonable that other hackers sometimes wonder how I do it.
Here’s part of my answer: be fanatical about automating away every part of your workflow that you can. Every second you don’t spend on mechanical routines is a second you get to use as creative time.
Soon, after an 11-year alpha period, I’m going to ship version 1.0 of one of my main automation tools. This thing would be my secret weapon if I had secrets. The story of how it came to be, and why it took 11 years to mature, should be interesting to other hackers on several different levels.
Though there haven’t been any huge dramatic improvements since Subversion analysis got good enough to use even on horribly gnarly repositories, reposurgeon continues to quietly get better and faster. I shipped 2.43 a few minutes ago.
Blogging has been light recently because I’ve been working very hard on a major GPSD release, which I just shipped. This is mostly new features, not bugfixes, and it’s probably the most new code we’ve shipped in one release since about 2009.
In 30 years of C programming, I thought I’d seen everything. Well, every bizarre trick you could pull with the C preprocessor, anyway. I was wrong. Contemplate this:
#include <stdint .h>
#define IS_BIG_ENDIAN (*(uint16_t *)"\0\xff" < 0x100)
That is magnificently awful. Or awfully magnificent, I'm not sure which. And it pulls off a combination of qualities I've never seen before: