Oct 12

A low-performance mystery, part deux

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.

Oct 11

A low-performance mystery

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 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…

Continue reading

Oct 09

Implementing re-entrant parsers in Bison and Flex

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.

Continue reading

Oct 05

In which I have reason to sound like Master Po

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.
> Sincerely,
> 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…

Continue reading

Oct 03

RFC for a better C calendaring library

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.

Continue reading

Oct 03

48-hour release heads-up for Time-Clock-Calendar HOWTO

I’ve been gifted with a lot of help on my draft of Time, Clock, and Calendar Programming In C. I think it’s almost time to ship 1.0, and plan to do so this weekend. Get your last-minute fixes in now!

I will of course continue to accept corrections and additions after 1.0. Thanks to everyone who contributed. My blog and G+ followers were very diligent in spotting typos, helping fill in and correct standards history, and pointing out the more obscure gotchas in the API.

What I’ve discovered is that the Unix calendar-related API is a pretty wretched shambles. Which leads directly to the topic of my next blog entry…

Oct 02

Press silence, black privilege, and unintended consequences

A provocative article at the conservative blog Hot Air comments on a pattern in American coverage of violent interracial crimes. When the perps are white and the victims are black, we can expect the press coverage to be explicit about it, with predictable assumption of racist motivations. On the other hand, when the perps are black and the victims are white, the races of all parties are normally suppressed and no one dares speak the r-word.

If I were a conservative, or a racist, I’d go off on some aggrieved semi-conspiratorial rant here. Instead I’ll observe what Hot Air did not: that the race of violent black criminals is routinely suppressed in news coverage even in the much more common case that their victims are also black. Hot Air is over-focusing here.

That said, Hot Air seems to have a a separate and valid point when it notes that white victims are most likely to have their race suppressed from the reporting when the criminals are black – especially if there was any hint of racist motivation. There is an effective taboo against truthfully reporting incidents in which black criminals yell racial epithets and threats at white victims during the commission of street crimes. If not for webbed security-camera footage we’d have no idea how depressingly common this seems to be – the press certainly won’t cop to it in their print stories.

No conspiracy theory is required to explain the silence here. Reporters and editors are nervous about being thought racist, or (worse) having “anti-racist” pressure groups demonstrating on their doorsteps. The easy route to avoiding this is a bit of suppressio veri – not lying, exactly, but not uttering facts that might be thought racially inflammatory.

The pattern of suppression is neatly explained by the following premises: Any association of black people with criminality is inflammatory. Any suggestion that black criminals are motivated by racism to prey on white victims is super-inflammatory. And above all, we must not inflame. Better to be silent.

I believe this silence is a dangerous mistake with long-term consequences that are bad for everyone, and perhaps worst of all for black people.

Continue reading

Sep 30

Underestimate Terry Pratchett? I never have.

Neil Gaiman writes On Terry Pratchett, he is not a jolly old elf at all.. It’s worth reading.

I know that what Neil Gaiman says here is true, because I’ve known Terry, a little. Not as well as Neil does; we’re not that close, though he has been known to answer my email. But I did have one experience back in 2003 that would have forever dispelled any notion of Terry as a mere jolly elf, assuming I’d been foolish enough to entertain it.

I taught Terry Pratchett how to shoot a pistol.

(We were being co-guests of honor at Penguicon I at the time. This was at the first Penguicon Geeks with Guns event, at a shooting range west of Detroit. It was something Terry had wanted to do for a long time, but opportunities in Britain are quite limited.)

This is actually a very revealing thing to do with anyone. You learn a great deal about how the person handles stress and adrenalin. You learn a lot about their ability to concentrate. If the student has fears about violence, or self-doubt, or masculinity/femininity issues, that stuff is going to tend to come out in the student’s reactions in ways that are not difficult to read.

Terry was rock-steady. He was a good shot from the first three minutes. He listened, he followed directions intelligently, he always played safe, and he developed impressive competence at anything he was shown very quickly. To this day he’s one of the three or four best shooting students I’ve ever had.

That is not the profile of anyone you can safely trivialize as a jolly old elf. I wasn’t inclined to do that anyway; I’d known him on and off since 1991, which was long enough that I believe I got a bit of look-in before he fully developed his Famous Author charm defense.

But it was teaching Terry pistol that brought home to me how natively tough-minded he really is. After that, the realism and courage with which he faced his Alzheimer’s diagnosis came as no surprise to me whatsoever.

Sep 29

Announcing: Time, Clock, and Calendar Programming In C

The C/UNIX library support for time and calendar programming is a nasty mess of historical contingency. I have grown tired of having to re-learn its quirks every time I’ve had to deal with it, so I’m doing something about that.

Announcing Time, Clock, and Calendar Programming In C, a document which attempts to chart the historical clutter (so you can ignore it once you know why it’s there) and explain the mysteries.

What I’ve released is an 0.9 beta version. My hope is that it will rapidly attract some thoroughgoing reviews so I can release a 1.0 in a week or so. More than that, I would welcome a subject matter expert as a collaborator.

Sep 29

Shellshock, Heartbleed, and the Fallacy of False Prominence

In the wake of the Shellshock bug, I guess I need to repeat in public some things I said at the time of the Heartbleed bug.

The first thing to notice here is that these bugs were found – and were findable – because of open-source scrutiny.

There’s a “things seen versus things unseen” fallacy here that gives bugs like Heartbleed and Shellshock false prominence. We don’t know – and can’t know – how many far worse exploits lurk in proprietary code known only to crackers or the NSA.

What we can project based on other measures of differential defect rates suggests that, however imperfect “many eyeballs” scrutiny is, “few eyeballs” or “no eyeballs” is far worse.

I’m not handwaving when I say this; we have statistics from places like Coverity that do defect-rate measurements on both open-source and proprietary closed source products, we have academic research like the UMich fuzz papers, we have CVE lists for Internet-exposed programs, we have multiple lines of evidence.

Everything we know tells us that while open source’s security failures may be conspicuous its successes, though invisible, are far larger.

Sep 28

Commoditization, not open source, killed Sun Microsystems

The patent-troll industry is in full panic over the consequences of the Alice vs. CLS Bank decision. While reading up on the matter, I ran across the following claim by a software patent attorney:

“As Sun Microsystems proved, the quickest way to turn a $5 billion company into a $600 million company is to go open source.”

I’m not going to feed this troll traffic by linking to him, but he’s promulgating a myth that must be dispelled. Trying to go open source didn’t kill Sun; hardware commoditization killed Sun. I know this because I was at ground zero when it killed a company that was aiming to succeed Sun – and, until the dot-com bust, looked about to manage it.

Continue reading

Sep 27

Program Provability and the Rule of Technical Greed

In a recent discussion on G+, a friend of mine made a conservative argument for textual over binary interchange protocols on the grounds that programs always need to be debugged, and thus readability of the protocol streams by humans trumps the minor efficiency gains from binary packing.

I agree with this argument; I’ve made it often enough myself, notably in The Art of Unix Programming. But it was something his opponent said that nudged at me. “Provable programs are the future,” he declaimed, pointing at sel4 and CompCert as recent examples of formal verification of real-world software systems. His implication was clear: we’re soon going to get so much better at turning specifications into provably correct implementations that debuggability will soon cease to be a strong argument for protocols that can be parsed by a Mark I Eyeball.

Oh foolish, foolish child, that wots not of the Rule of Technical Greed.

Continue reading

Sep 26

Halfway up the mountain

Last night, my wife Cathy and I passed our level 5 test in kuntao. That’s a halfway point to level 10, which is the first “guro” level, roughly equivalent to black belt in a Japanese or Korean art. Ranks aren’t the big deal in kuntao that they are in most Americanized martial arts, but this is still a good point to pause for reflection.

Continue reading

Sep 25

Announcing microjson

If you’ve ever wanted a JSON parser that can unpack directly to fixed-extent C storage (look, ma, no malloc!) I’ve got the code for you.

The microjson parser is tiny (less than 700LOC), fast, and very sparing of memory. It is suitable for use in small-memory embedded environments and deployments where malloc() is forbidden in order to prevent leaked-memory issues.

This project is a spin-out of code used heavily in GPSD; thus, the code has been tested on dozens of different platforms in hundreds of millions of deployments.

It has two restrictions relative to standard JSON: the special JSON “null” value is not handled, and object array elements must be homogenous in type.

A programmer’s guide to building parsers with microjson is included in the distribution.

Sep 19

Request for help – I need a statistician

GPSD has a serious bug somewhere in its error modeling. What it effects is position-error estimates GPSD computes for GPSes that don’t compute them internally themselves and report them on the wire. The code produces plausible-looking error estimates, but they lack a symmetry property that they should have to be correct.

I need a couple of hours of help from an applied statistician who can read C and has experience using covariance-matrix methods for error estimation. Direct interest in GPS and geodesy would be a plus.

I don’t think this is a large problem, but it’s just a little beyond my competence. I probably know enough statistics and matrix algebra to understand the fix, but I don’t know enough to find it myself.

Hundreds of millions of Google Maps users might have reason to grateful to anyone who helps out here.

UPDATE: Problem solved, see next post.

Sep 11

Review: Infinite Science Fiction One

Infinite Science Fiction One (edited by Dany G. Zuwen and Joanna Jacksonl Infinite Acacia) starts out rather oddly, with Zuwen’s introducton in which, though he says he’s not religious, he connects his love of SF with having read the Bible as a child. The leap from faith narratives to a literature that celebrates rational knowability seems jarring and a bit implausible.

That said, the selection of stories here is not bad. Higher-profile editors have done worse, sometimes in anthologies I’ve reviewed.

Continue reading