Theodore Ts'o: Does perfect code exist? (Abstractions, Part 1)
Bryan Cantrill recently wrote a blog entry, where among other things, he philosophized on the concept of “perfect code”. He compares software to math, arguing that Euclid’s greatest common denominator algorithm shows no sign of wearing out, and that when code achieves perfection (or gets close to perfection), “it sediments into the information infrastructure” and the abstractions defined by that code becomes “the bedrock that future generations may build upon”. Later, in the comments of his blogs, when pressed to give some examples of such perfection, he cites a clever algorithm coded by his mentor to divide a high resolution timestamp by a billion extremely efficiently, and Solaris’s “cyclic subsystem”, a timer dispatch function.
Watching his talk at Google where his introduction and sidebar book review on Scott Rosenberg’s “On Dreaming in Code”, it’s clear that he very passionately believes that it is possible to write perfect code, and that one should strive for that at all times. Perhaps that’s because he mostly writes code for operating systems, where the requirements change slowly, and for one OS in particular, Solaris, which tries far harder than most software projects to keep published interfaces stable for as long as possible. In contrast, the OS I’ve spent a lot of time hacking around, Linux, quite proudly states that at least inside the kernel, interfaces can not and should not be stable. Greg Kroah-Hart’s “Stable API Nonsense” is perhaps one of the strongly and most passionate expositions of that philosophy.
I can see both sides of the argument, and in their place, both have something to offer. To Bryan’s first point, it is absolutely true that interfaces can become “bedrock” upon which entire ecosystems are built. Perhaps one of the most enduring and impactful example would be the Unix programming interface, which has since become enshrined by POSIX.2 and successor standards. I would argue, though, that it is the interface that is important, and not the code which initially implemented it. If the interface is powerful enough, and if it appears at the right time, and the initial implementation is good enough (not perfect!), then it can establish itself by virtue of the software which uses it becoming large enough that it assumes an important all out of scale with its original intention.
Of course, sometimes such an interface is not perfect. There is an apocryphal story that when S. Feldman at AT&T labs first wrote the ‘make’ utility, that he did so rather quickly, and then put it available for his fellow lab members to use, and then went home to sleep. In some versions of the story he had stayed up late and/or pulled an all-nighter to write it, so he slept a long time. When he came back to work, he had come up with a number of ways to improve the syntax of the Makefile. Unfortunately, (so goes the story) that too many teams were already using the ‘make’ utility, so he didn’t feel he could change the Makefile syntax. I have no evidence that this ever took place, and I suspect it is an urban myth that was invented to explain why Makefiles have a rather ugly and unfortunate syntax that many would call defects, including the use of syntactically significant tab characters which are indistinguishable from other forms of leading whitespace.
Another example which is the bane of filesystem designers everywhere are the Unix readdir(2), telldir(2), and seekdir(2) interfaces. These interfaces fundamentally assume that directories are stored in linear linked lists, and filesystems that wish to use more sophisticated data structures, such as b-trees, have to go to extraordinary lengths in order support these interfaces. Very few programs use telldir(2) and seekdir(2), but some filesystems such as JFS maintain two b-trees instead of one just to cater to telldir/seekdir.
And yet, it is absolutely true that interfaces can be the bedrock for an entire industry. Certainly no matter what its warts, the Unix/Posix interface has proven the test of time, and it has been responsible for the success of many a company and many billions of dollars of market capitalization. But is this the same as perfect code? No, but if billions of dollars of user applications are going to be depending on that code, it’s best if code which implement such an interface be high quality, and should attempt to achieve perfection.
But what does it mean for code to be perfect? For a particular environment, if the requirements can be articulated clearly, I can accept that code can reach perfection, in that it becomes as fast as possible (for the given computer platform), and it handles all exception cases, etc., etc. Unfortunately, in the real world, the environment and the requirements inevitably change over time. For example, Bryan’s cyclic subsystem, which he proudly touts as being if not perfect, almost so, and which executes at least 100 times a second on every Solaris system in the world. I haven’t looked at the cyclic system in any detail, since I don’t want to get myself contaminated (the CDDL and GPLv2 licenses are intentionally incompatible, and given that companies — including Sun — have sued over IPR issues, well, one can’t be too careful), but waking up the CPU from its low-power state 100 times a second isn’t a good thing at all if you are worried about energy conservation in data centers — or in laptops.
For example, on my laptop, it is possible to keep wakeups down to no more than 30-35 times a second and it would be possible to do more but for an abstraction limitation. Suppose for example an process wants to be sleep and then receive a wakeup 1 milliseconds later, and so requests this via usleep(). At the same time, another application wants to sleep until some file descriptor activity takes place, or after 1.2 milliseconds takes place. 0.3 milliseconds later, a third process requests a sleep, this time for 0.8 milliseconds. Now, it could be that in all of the above cases, the applications don’t actually need exact timing; if they all get their wakeups plus or minus some fraction of a millisecond, they would be quite cool with that. Unfortunately, the standard timer interfaces have no way of expressing this, and so the OS can’t combine the three wakeups at T+1.0, T+1.1, and T+1.2 milliseconds into one wakeup at T+1.1ms.
So this is where Greg K-H’s “Stable API Nonsense” comes into play. We may not be able to solve this problem at the userspace level, but we darn well can solve this problem inside the kernel. Inside the kernel, we can change the timer abstraction to allow device drivers and kernel routines to provide a timer delta plus a notion of how much accuracy is required for a particular timer request. Doing so might change a timer structure that previously external device drivers had depended upon — but too bad, that’s why stable ABI/API’s are not supported for internal kernel interfaces. Is this that the interface could have been extended? Well, perhaps, and perhaps not; if an interface is well designed, it is possible it can be extended in an API and/or ABI compatible way. There usually is a performance cost to doing so, and sometimes it may make sense to pay that that cost, and sometimes it may not. I’ll talk more about that in a future essay.
Yet note what happened to the timer implementation. We have a pretty sophisticated timer implementation inside Linux, that uses heap data structures and buckets of timers for efficiency. So while I might not call it perfect, it is pretty good. But, oops! Thanks to this new requirement of energy efficiency, it will likely need to get changed to support variable levels of accuracy and the ability to fire multiple timers that are (more or less) coming due in a single CPU wakeup cycle. Does that make it no longer perfect, or no longer pretty good? Well, it just had a new requirement impact the code, and if criteria for perfection is for the abstraction defined by the code to be “bedrock” and never-changing, and no need to make any changes in said code over multiple years, I would argue that little to no code, even OS code, can ever achieve perfection by that definition — unless that code is no longer being used.
(This is the first of a multi-part series of essays on abstractions that I have planned. The next essay which I plan to write will be entitled “Layer surfing, or jumping between layers”, and will be coming soon to a blog near you….)
…BECAUSE I DON’T THINK YOU ARE!
This is probably the funniest image I have ever seen on Wikipedia:
Inspired by a certain blog/foo post, I want to announce that I've seen my first snow of this winter last night, too. Not enough to really cover the ground, but a bit to at least give the impression the ground ist covered. 
Is anyone else getting pingbacks
from sites consisting entirely
of formulaic posts like
So, our country is again in one of its recurrent strike
madness. Yesterday (Wednesday), unions of the public transportation
companies (mostly SNCF for trains all over the country, RATP for Paris
and suburbs metros/bus system and maybe a few transport companies in
other cities) called for an unlimited strike.
The point is protesting against the project of harmonizing the retirement systems of these companies with the system used in private companies (AND many public ones such as Onera who I work for).
The French retirement financing system is facing the challenge of all participative systems (where the current workers pay for the current retired people, contrary to cpitalization systems where one spares one's own retirement money during one's work life....I hope this is clear with my broken English). As there are less and less workers and more and more retired peoplen the load on workers is becoming harder and harder while the retirement 'salaries' (what's the word for 'pension'?) can only be lower.
As a consequence, in the standard retirment system in France, ppl now have to work for 42 years to get a full pension when they retire (theoretically we can at 60....but practically, this happens at 65). In the same time, workers at SNCF, RATP and a few others still have a special retirement system with only 37 years to work and the possibility to retire when reaching 55 for some of them (good ol' days of steam trains justify the work being "hard").
All attempts to change this have failed up to now because of the power of unions at SNCF/RATP/others and the power they have to screw out the entire country. Attempts in 1999 lead to huge strike with, at that time, a strong support by the general public (who feared for their own retirement system.....the strike also being a good way to protest against the general policitcs of the government at that time...as usual).
Things changed now and the majority of ppl no longer support so-called privileged people to try hanging to their special retirement system....but of course, unions still have to show their power and, anyway, very few strikers may break things a lot.....and here we are with huge strikes.
Yesterday, I managed to do it well with a good train coverage on my line (1 all-stops train per 30minutes) and running at both ends (good for health!).
Today was a little bit jerkier with the scheduled train being cancelled and the next one 30 minutes later...and well packed..:-)
Hopefully, for tomorrow, the situation should improve as negotiations between government and unions are planned (they were already but I guess that unions had to show their strength....and check whether the average people support them like it happened in 1999....which is actually a complete failure as the general feeling over French population is "enough!").
That's good as I'm not completely sure I can sustain running 12km every day.:)
Today, when walking through some Wammu/Gammu bugs, I came to conclusion that
the spam changed some people to behave insane. The email field in bug tracker
is there to allow developer to contact you, for example when he makes a fix
for issue you reported and wants you to test it. Entering addresses as ones at
TrashMail which will vanish soon (the bug I'm talking about is two days old,
what I feel is good enough reaction time from my side), will not help anybody.
Thank you firebird76 (whatever your real name is) for realizing how people are
stupid.
PS: I use Mantis bug tracker, which I believe does not expose email addresses
to anyone besides privileged users.
Oath of Gold rounds up this excellent fantasy series
from Elizabeth Moon. It is a pity that she never came back to this
character (though she wrote a couple of prequels), despite the fact
that the ending paragraph leaves ample room for sequels when the
call of Gird came, Paksenarrion left for other lands.
This is high fantasy in true Tolkien manner, but faster paced,
more gritty, and with characters one could relate to. I am already
looking forward to my next re-read of the series.
