A&D regular Mike Swanson did such a nice job on this that I want you all to see it.
My low-power, low-overhead version control system, SRC, is no longer just a stake in the ground. It is still a determinedly file-oriented wrapper around RCS (and will stay that way) but every major feature except branching is implemented and it has probably crossed the border into being useful for production.
The adventurous can and should try it. You’re safe if it blows up because the histories are plain RCS files. But, as previously noted, it’s RCS behind an interface that’s actually pleasant to use. (You Emacs VC-mode users pipe down; I’m going to explain why you care in a bit.)
The main developments today include a fairly complete regression-test suite (already paying large dividends in speeding up progress) and a “src status” command that will look very familiar to Subversion/git/hg users. There’s a hack behind that status command I’m rather proud of; I’ll talk about that, too.
I wrote a version-control system today. Yes, an entire VCS. Took me 14 hours.
Yeah, you’re looking at me like I’m crazy. “Why,” you ask, quite reasonably, “would you want to do a thing like that? We’re not short of powerful VCSes these days.
That is true. But I got to thinking, early this morning, about the fact that I haven’t been able to settle on just one VCS. I use git for most things, but there’s a use case git doesn’t cover. I have some document directories in which I have piles of things like HOWTOs which have separate histories from each other. Changes in them are not correlated, and I want to be able to move them around because I sometimes do that to reorganize them.
What have I been using for this? Why, RCS. The ancient Revision Control System, second oldest VCS in existence and clinging tenaciously to this particular niche. It does single-file change histories pretty well, but its UI is horrible. Worse than git’s, which is a pretty damning comparison.
Then I got to thinking. If I were going to design a VCS to do this particular single-file, single-user job, what would it look like? Hm. Sequential integer revision numbers, like Subversion and Mercurial used locally. Lockless operation. Modern CLI design. Built-in command help. Interchange with other VCSes via git import streams. This sounds like it could be nice…
Then, the idea that made it inevitable. “I bet.” I thought, “I could write this thing as a Python wrapper around RCS tools. Use them for delta storage but hide all the ugly parts.”
Thus, SRC. Simple Revision Control, v0.1.
I’ve just shipped a new version of cvs-fast-export, 1.26. It speeds the tool up more, more, more – cranking through 25 years and 113300 commits of Emacs CVS history, for example in 2:48. That’s 672 commits a second, for those of you in the cheap seats.
But the real news this time is a Python wrapper called ‘cvsconvert’ that takes a CVS repository, runs a conversion to Git using cvs-fast-export, and then – using CVS for checkouts – examines the CVS and git repositories side by side looking for translation glitches. It checks every branch tip and every tag.
Running this on several of my test repos I’ve discovered some interesting things. One such discovery is of a bug in CVS. (Yeah, I know, what a shock…)
Here’s an interesting article with a stupid and misleading title on the role of what the author calls “cognitive disinhibition” – a fancy term for “allowing oneself to notice what others miss” – in enabling creative genius.
While in many ways I could be a poster child for Simonton’s thesis (and I’ll get to those) I also think there are some important things missing from his discussion, which is why I’m blogging about it. The most crucial problem is that his category of “madness” is not sharp enough. I know how to fine it down in a way that I think sheds considerable light on what he is trying to analyze.
Lately I’ve been wrestling with various members of an ancient and venerable open-source development group which I am not going to name, though people who regularly follow my adventures will probably guess which one it is by the time I’m done venting.
Why it so freaking hard to drag some people into the 21st century? Sigh…
I’m almost 56, an age at which a lot of younger people expect me to issue semi-regular salvos of get-off-my-lawn ranting at them. But no – I find, that, especially in technical contexts, I am far more likely to become impatient with my age peers.
A lot of them really have become grouchy, hidebound old farts. And, alas, it not infrequently falls to me to be the person who barges in and points out that practices well-adapted for 1995 (or, in the particular case I’m thinking of, 1985) are … not good things to hold on to decades later.
Why me? Because the kids have little or no cred with a lot of my age peers. If anyone’s going to get them to change, it has to be someone who is their peer in their own perception. Even so, I spend a lot more time than seems just or right fighting inertia.
Young people can be forgiven for lacking a clue. They’re young. Young means little experience, which often leads to unsound judgment. It’s more difficult for me to forgive people who have been around the track often enough that they should have a clue, but are so attached to The Way It’s Always Been Done that they can’t see what is in front of their freaking noses.
Some people on the NetBSD tech-repository list have wondered why I’ve been working on a full NetBSD repository conversion without a formal request from NetBSD’s maintainers that I do so.
It’s a fair question. An answer to it involves both historical contingency and some general issues about moving and mirroring large repositories. Because of the accident that a lot of people have recently dropped money on me in part to support an attack on this problem, I’m going to explain both in public.
Wendell Wilson over at TekSyndicate had a good idea – run the NetBSD repo conversion on a machine roughly comparable to the Great Beast design. The objective was (a) to find out if it freakin’ worked, and (b) to get a handle on expected conversion time and maximum working set for a really large conversion.
The news is pretty happy on all fronts.
I’ve attempted to summarize the discussion of build options for the repository-surgery machine. You should see a link at the top of the page: if not, it’s here
I invite all the commenters who have shown an interest to critique these build proposals. Naturally, I’d like to make sure we have a solid parts list with no spec conflicts before we start spending money and time to build this thing.
Something of significance to the design discussion for the Great Beast occurred today.
I have finally – finally! – achieved significant insight into the core merge code, the “black magic” section of cvs-fast-export. If you look in merge.c in the repo head version you’ll see a bunch of detailed comments that weren’t there before. I feel rather as Speke and Burton must have when after weeks of hacking their way through the torrid jungles of darkest Africa they finally glimpsed the source of the Nile…
I just shipped cvs-fast-export 1.21 much improved and immensely faster than it was two weeks ago. Thus ends one of the most intense sieges of down-and-dirty frenzied hacking that I’ve enjoyed in years.
Now it comes time to think about what to do with the Help Stamp Out CVS In Your Lifetime fund, which started with John D. Bell snarking epically about my (admittedly) rather antiquated desktop machine and mushroomed into an unexpected pile of donations.
I said I intend to use this machine wandering around the net and hunting CVS repositories to extinction, and I meant it. If not for the demands of the large data sets this involves (like the 11 gigabytes of NetBSD CVS I just rsynced) I could have poked along with my existing machine for a good while longer.
For several reasons, including wanting those who generously donated to be in on the fun, I’m now going to open a discussion on how to best spend that money. A&D regular Susan Sons (aka HedgeMage) built herself a super-powerful machine this last February, and I think her hardware configuration is sound in essentials, so that build (“Tyro”) will be a starting point. But that was eight months ago – it might be some of the choices could be improved now, and if so I trust the regulars here will have clues to that.
I’ll start by talking about design goals and budget.
This series of posts is increasingly misnamed, as there is not much mystery left about cvs-fast-export’s performance issues and it is now blazingly, screamingly, bat-out-of-hell fast. As in both threaded and unthreaded version convert the entire history of groff (15593 CVS deltas in 1549 files in 13 seconds flat. That would be about 10K CVS commits per minute, sustained; in practice the throughput will probably fall off a bit on very large repositories.
I achieved the latest doubling in speed by not succumbing to the temptation to overengineer – a trap that lays in wait for all clever hackers. Case study follows.
The mystery I described two posts back has actually been mostly solved (I think) but I’m having a great deal of fun trying to make cvs-fast-export run even faster, and my regulars are not only kibitzing with glee but have even thrown money at me so I can upgrade my PC and run tests on a machine that doesn’t resemble (as one of them put it) a slack-jawed yokel at a hot-dog-eating contest.
Hey, a 2.66Ghz Intel Core 2 Duo with 4GB was hot shit when I bought it, and because I avoid bloatware (my window manager is i3) it has been sufficient unto my needs up to now. I’m a cheap bastard when it comes to hardware; tend to hold onto it until I actually need to upgrade. This is me loftily ignoring the snarking from the peanut gallery, except from the people who actually donated money to the Help Stamp Out CVS In Your Lifetime hardware fund.
(For the rest of you, the PayPal and Gratipay buttons should be clearly visible to your immediate right. Just sayin’…)
Ahem. Where was I? Yes. The major mystery – the unexplained slowdown in stage 3 of the threaded version – appears to have been solved. It appears this was due to a glibc feature, which is that if you link with threads support it tries to detect use of threads and use thread locks in stdio to make it safe. Which slows it down.
Well, the good news is, I get to feel wizardly this morning. Following sensible advice from a couple of my regulars, I rebuilt my dispatcher to use threads allocated at start time and looping until the list of masters is exhausted.
78 LOC. Fewer mutexes. And it worked correctly first time I ran it. W00t – looks like I’ve got the
hang non-hang of this threads thing.
The bad news is, threaded performance is still atrocious in exactly the same way. Looks like thread-spawn overhead wasn’t a significant contributor.
In truth, I was expecting this result. I think my regulars were right to attribute this problem to cache- and locality-busting on every level from processor L1 down to the disks. I believe I’m starting to get a feel for this problem from watching the performance variations over many runs.
I’ll profile, but I’m sure I’m going to see cache misses go way up in the threaded version, and if I can find a way to meter the degree of disk thrashing I won’t be even a bit surprised to see that either.
The bottom line here seems to be that if I want better threaded performance out of this puppy I’m going to have to at least reduce its working set a lot. Trouble is, I’m highly doubtful – given what it has to do during delta assembly – that this is actually possible. The CVS snapshots and deltas it has to snarf into memory to do the job are intrinsically both large and of unpredictably variable size.
Maybe I’ll have an inspiration, but…Keith Packard, who originally wrote that code, is a damn fine systems hacker who is very aware of performance issues; if he couldn’t write it with a low footprint in the first place, I don’t judge my odds of second-guessing him successfully are very good.
Ah well. It’s been a learning experience. At least now I can say of multi-threaded application designs “Run! Flee! Save yourselves!” from a position of having demonstrated a bit of wizardry at them myself.
UPDATE: One of my regulars found a minor bug in the mutex handling that cost some performance. Alas, fixing this didn’t have any impact above the noise level of my profiling. Also, I managed to unify the threaded and non-threaded dispatchers; the LOC specific to threading is now down to about 30.
OK, I’ll admit it. I’m stumped by a software-engineering problem.
This is not a thing that happens often, but I’m in waters relatively unknown to me. I’ve been assiduously avoiding multi-threaded programming for a long time, because solving deadlock, starvation, and insidious data-corruption-by-concurrency problems isn’t really my idea of fun. Other than one minor brush with it handling PPS signals in GPSD I’ve managed before this to avoid any thread-entanglement at all.
But I’m still trying to make cvs-fast-export run faster. About a week ago an Aussie hacker named David Leonard landed a brilliant patch series in my mailbox. Familiar story: has a huge, gnarly CVS repo that needs converting, got tired of watching it grind for days, went in to speed it up, found a way. In fact he applied a technique I’d never heard of (Bloom filtering) to flatten the worst hot spot in the code, an O(n**3) pass used to compute parent/child links in the export code. But it still needed to be faster.
After some discussion we decided to tackle parallelizing the code in the first stage of analysis. This works – separately – on each of the input CVS masters, digesting them into in-core revision lists and generating whole-file snapshots for each CVS delta; later these will become the blobs in the fast-export stream. Then there’s a second stage that merges these per-file revision lists, and a third stage that exports the merged result.
Here’s more detail, because you’ll need it to understand the rest. Each CVS master consists of a sequence of deltas (sequences of add-line and delete-line operations) summing up to a sequence of whole-file states (snapshots – eventually these will become blobs in the translated fast-import-stream). Each delta has an author, a revision date, and a revision number (like 1.3 or 22.214.171.124). Implicitly they form a tree. At the top of the file is a tag table mapping names to revision numbers, and some other relatively unimportant metadata.
The goal of stage 1 is to digest each CVS master into an in-core tree of metadata and a sequence of whole-file snapshots, with unique IDs in the tree indexing the snapshots. The entire collection of masters is made into a linked list of these trees; this is passed to stage 2, where black magic that nobody understands happens.
This first stage seems like a good target for parallelization because the analysis of each master consists of lumps of I/O separated by irregular stretches of compute-intensive data-shuffling in core. In theory, if the program were properly parallelized, it would seldom actually block on an I/O operation; instead while any one thread was waiting on I/O, the data shuffling for other masters would continue. The program would get faster – possibly much faster, depending on the time distribution of I/O demand.
Well, that’s the theory, anyway. Here’s what actually happened…
I made a finger error. Full version of A Low Performance Mystery to follow shortly.
In days of yore, Yacc and Lex were two of the most useful tools in a Unix hacker’s kit. The way they interfaced to client code was, however, pretty ugly – global variables and magic macros hanging out all over the place. Their modern descendants, Bison and Flex, have preserved that ugliness in order to be backward-compatible.
That rebarbative old interface generally broke a lot of rules about program structure and information hiding that we now accept as givens (to be fair, most of those had barely been invented at the time it was written in 1970 and were still pretty novel). It becomes a particular problem if you want to run multiple instances of your generated parser (or, heaven forfend, multiple parsers with different grammars) in the same binary without having them interfere with each other.
But it can be done. I’m going to describe how because (a) it’s difficult to extract from the documentation, and (b) right now (that is, using Bison 3.0.2 and Flex 2.5.35) the interface is in fact slightly broken and there’s a workaround you need to know.
A bit late, because I’ve been hammering on some code the last several days. But here it is: Time, Clock, and Calendar Programming In C.
Suggestions for 1.1 revisions and improvements will of course be cheerfully accepted. Comments here or email will be fine.
This landed in my mailbox yesterday. I reproduce it verbatim except for the sender’s name.
> Dear authors of the RFC 3092,
> I am writing this email on behalf of your Request For Comment “Etymology of
> ‘Foo’.” We are currently learning about the internet organizations that set
> the standards of the internet and our teacher tasked us with finding an RFC
> that was humorous. Me and my two friends have found the “Etymology of
> ‘Foo'” and have found it to be almost as ridiculous as the RFC about
> infinite monkeys; however, we then became quite curious as to why you wrote
> this. Obviously, it is wrote for humor as not everything in life can be
> serious, but did your manager task you to write this? Are you a part of an
> organization in charge of writing humorous RFC’s? Are you getting paid to
> write those? If so, where do you work, and how may we apply? Any comments
> on these inquiries would be greatly appreciated and thank you in advance.
> XXXXXXXXXXXXXX, confused Networking student
I felt as though this seriously demanded a ha-ha-only-serious answer – and next thing you know I was channeling Master Po from the old Kung Fu TV series. Reply follows…
In the process of working on my Time, Clock, and Calendar Programming In C document, I have learned something sad but important: the standard Unix calendar API is irremediably broken.
The document list a lot of consequences of the breakage, but here I want to zero in on what I think is the primary causes. That is: the standard struct tm (a) fails to be an unambiguous representation of time, and (b) violates the SPOT (Single Point of Truth) design rule. It has some other more historically contingent problems as well, but these problems (and especially (a)) are the core of its numerous failure modes.
These problems cannot be solved in a backwards-compatible way. I think it’s time for a clean-sheet redesign. In the remainder of this post I’ll develop what I think the premises of the design ought to be, and some consequences.