Variants of CompareAndSwap

I ran across an interesting issue the other day while trying to make a cross-platform atomics header work on Mac OS X.

Compare-and-Swap (hereafter, CAS) is one of the fundamental atomic primitives: given a working CAS you can implement any other atomic operation.

But there are in fact two common variants of CAS:

    // Returns the old value from *ptr
    int ValueCAS(volatile int *ptr, int compare, int swap);

    // Returns true if a swap occurred
    bool BoolCAS(volatile int *ptr, int compare, int swap);

That's OK, though, because it's theoretically possible to convert either one into the other.

It's trivial to implement BoolCAS in terms of ValueCAS. Here's how you do it:

    // GOOD: this works correctly.
    bool BoolCAS(volatile int *ptr, int compare, int swap) {
        return compare == ValueCAS(ptr,compare,swap);
    }

But for what I was doing, I needed to go the other way around. Mac OS X provides BoolCAS functions in <libkern/OSAtomic.h>, and I needed to convert those to ValueCAS functions.

It turns out to be subtly difficult to go the other way around, and I thought I'd share the reasons why.

First attempt

My first attempt was fairly simple, using just an extra load and branch:

    // BAD: do not use! Broken!
    int ValueCAS(volatile int *ptr, int compare, int swap) {
        if (BoolCAS(ptr,compare,swap))
            return compare;
        else
            return *ptr;
    }

The idea is that if the CAS worked, then the old value of *ptr must have been the same as compare, so we can just return that. That's absolutely correct.

However, if the CAS failed, what was the previous value? I was naïvely re-reading *ptr. But my unit tests (oh yes, this is the kind of thing you unit-test thoroughly) showed that very rarely — once per several million iterations — it would fail to do the right thing.

What was going wrong?

The problem comes down to how callers detect success and failure from ValueCAS. If ValueCAS returns compare, the CAS is assumed to have succeeded. If ValueCAS returns any other value, the CAS is assumed to have failed.

Once we recognize this, we can see that the naïve implementation above has not one, but two failure cases:

1. Spurious CAS failure. This can happen on nearly any system, for a variety of reasons. I'd rather not get too deep into explanations of CPU behavior here, but the typical example might be if an interrupt occurred at exactly the wrong moment. Even if *ptr == compare when the CAS runs, a spurious failure might exit the CAS without changing the value of *ptr. This would cause ValueCAS to incorrectly report success!
2. Race between CAS and reload. If more than one thread is atomically modifying *ptr, then there's a window between the CAS and the reload where *ptr could be changed to anything at all — including getting set back to compare. Again, this would cause ValueCAS to incorrectly report success!

Another approach

One tempting way to fix it is to simply lie about the old value of *ptr. I didn't actually try this, but I'll admit I considered it for a moment:

    // BAD: do not use! Semantically incorrect!
    int ValueCAS(volatile int *ptr, int compare, int swap) {
        if (BoolCAS(ptr,compare,swap))
            return compare;
        else
            return (compare-1); // or any value other than compare
    }

But this is wrong! It breaks the semantics of the CAS. CAS is supposed to return the old value. But the value this function returns is totally bogus, and may never have existed at *ptr. To help imagine why this is bad, consider what might happen if the caller is using the value as a bitmask. We might wind up returning an illegal mask with bits that had never been set. This could have unintended, ugly, subtle side-effects.

Third time's the charm

As far as I can tell, the best way to fix it is by adding both an extra load and two branches:

    // GOOD: works correctly
    int ValueCAS(volatile int *ptr, int compare, int swap) {
        int old;
        do {
            if (BoolCAS(ptr,compare,swap))
                return compare;
            old = *ptr;
        } while (old == compare); // never return compare if CAS failed
        return old;
    }

And sure enough, it's a little heavy-handed, but it works. Proper branch hinting will help, but I'm still a bit surprised that it's so expensive (relatively speaking) to do this conversion.

Can anyone come up with a better way?

MarsEdit Markdown Scripts updated to 1.0.3

No piece of software, however simple, is bug-free.

Daniel Jalkut was kind enough to point out to me that my Markdown scripts for MarsEdit didn't deal properly with Unicode text.

Silly me. I'd forgotten that AppleScript (with its very early-1990s roots) still needs to be explicitly told not to lose data when writing out files. He offered a fix — a few «class utf8» coercions in the right place and all was well again. That was 1.0.1.

However, just immediately after release, I discovered that the scripts needed to do some more aggressive transcoding of UTF8 into ASCII in order to get Python to read the file in html2text. So I've added support for that. This slows down the HTML-to-Markdown reverse conversion a little bit, but at least it's correct now. That was 1.0.2.

Finally, later in the evening I realized it was pretty stupid to write AppleScript code to transcode the UTF8 into ASCII, because AppleScript's support for Unicode is so horribly primitive and I was doing it character by character. So I rewrote that whole section as a one-line Perl script. Now it's blazing fast. And that's 1.0.3.

I've updated the scripts. Download them now!

Markdown Scripts for MarsEdit

I've created a few AppleScripts for MarsEdit to simplify the process of using Markdown to post to any weblog (like, say, Blogger) that doesn't natively support it.

Translate Markdown to HTML

This script takes text written in Markdown syntax and translates it into HTML. Extraneous line breaks are eliminated, because many blog hosts like to translate them into <br /> tags.

This works particularly well because MarsEdit has native support for previewing content written in Markdown. I normally use the Markdown preview mode while composing a post, then convert it to HTML just before posting.

But wait, you say: what if you need to edit a post?

No problem, says me. Then you use the other script.

Translate HTML to Markdown

This script uses Aaron Swartz's html2text to translate the post from HTML back into Markdown. It works on any HTML post, not just ones that you've created with the other script. Then you're free to edit the post, convert it back to HTML, and repost it.

Updated: Now with Unicode support

Update, Oct 4 2007: MarsEdit's author, Daniel Jalkut, alerted me to the fact that these scripts had problems with non-Roman text and offered a fix. Sure enough, I'd forgotten that AppleScript needs special care to do the right thing and handle text files as UTF-8. I've updated them appropriately.

Get them now!

Interested? Download the scripts now!

MarsEdit Markdown Scripts

Better Food, Just as Fast

Do you find yourself going out to dinner a lot, or bringing home takeout food more often than you should?

We sure do. Even though we've been making an effort to eat lighter meals at healthier places -- our faves from around here include Panera, Chipotle, Zoup!, and our local Heinen's grocery store -- it's just not the same as cooking and eating at home. There's a real difference in quality, quantity, and healthiness. And it's expensive, too!

Worse yet, it's a slippery slope. Once you get into the habit of getting takeout for dinner, it's easy to slip and start eating less healthy fast food too. (cough KFC's beautiful-but-deadly mashed potato bowls, I'm looking at you.)

My wife Nancy recently came up with a solution. She'd heard about this place nearby called Simply Done Dinners. Apparently -- and I had no idea this even existed -- places like this are a growing trend around the country. It's basically a place where you can come in, put together homemade dinners, bring them home, and toss them in the freezer to cook later.

Simply Done Dinners is local to the Cleveland area, and they have only four stores right now: Parma, North Olmsted, Twinsburg, and Medina. If you're not from around here, don't worry. There's probably a similar store near you. Take a look at this HUGE directory of easy meal-prep stores. See? I told you it was a growing trend. :-)

Our First Taste

The first time we tried it out, Nancy simply ordered six dinners online ($109) and had the store in Twinsburg assemble them ($29) so that all she had to do was pick it up. There was no preparation involved: she simply walked in and grabbed the prepared dinner packages. We got one of each of the following:

• Apple Pork Chops with Sweet Potatoes
• Cheeseburger Noodle Casserole
• Cod Provencal
• Lemon Garlic Chicken
• Pasta Broccoli Bake
• Southwestern Meatloaf

Each dinner package is designed for 4-6 people. For our family of three -- papa bear, mama bear, and baby bear, with proportional appetites -- we found that we got just under two meals per person out of each. Either two dinners from each, or dinner plus a tasty lunch of leftovers the next day. The meatloaf actually lasted much longer: I used it for lunch sandwiches for almost a week, but that was balanced out by the pork chops which got left out for too long and had to be thrown away. All in all, I figure that we got roughly 30 meals from the order.

If you do the math, that works out to $4.60 per meal per person: a little more expensive than buying all the ingredients yourself, but without any of the hassle. It's also about what you'd pay for a fast food "value meal", and maybe 50 cents to a dollar more than a frozen TV dinner at the grocery store. Really, a surprisingly good value for the kind of quality that you get.

Of course, these are just main courses and don't come with sides. (Some other chains do provide sides, but they also charge a little more.) So we'd add rolls, or a salad, or some veggies as needed. That adds a bit to the cost-per-meal, strictly speaking, but we already had all that stuff around the house anyway so we didn't factor it in.

The dinners come in a big disposable pan, the kind that you can just toss in the oven. There's a sticker with cooking directions on the side. Some needed baking, some needed broiling, and other stuff could be done in a crock-pot. (We avoided the crock-pot ones the first time, since we didn't have one.) In all cases it's pretty much drop-it-in-and-wait; no skills required. A bachelor could do it with one hand tied behind his back. :-) They're all designed to be stored in the freezer, but you have to remember to pull them out into the fridge to thaw 48 hours before you want them. We pulled out one or two a week, and eventually started a rotation where every time we used one we'd move another into the fridge so that it would be ready in a couple of days.

What about the taste? Well, we have a diverse set of tastebuds in our family: I'll eat anything, but Nancy can be a picky eater (to put it mildly). And even though Olivia's pretty darn adventurous for a 10-year-old kid, eating sushi and cow tongue among other things, she doesn't like everything. Sometimes she opts out of dinner and just gets a veggie burger instead.

But even in our divided household everyone unanimously agreed: the food was delicious! I guess that's the benefit of having a professional chef selecting the recipes.

Better still, it was all stuff that we either wouldn't have made, or something that was a unique flavor that we probably wouldn't have thought of. So it didn't actually conflict with any regular cooking -- we still made our simple family-friendly foods like nachos, pizza, salads, burgers, soup, sandwiches, pasta, etc. It was more like a supplement to our regular meals which pushed the fast food out of our diet for a while.

Cooking Too: Electric Boogaloo

Today we received our second order. Nancy is now nine months pregnant (!) and we're anticipating that eating will be a little bit hectic for a while once the baby comes, so we wanted to stock up on easy and nutritious food. This time instead of ordering 6, we ordered 12. And we figured we'd skip the "pick it up" option and try preparing it ourselves. Here's what we chose:

• Balsamic Thyme Chicken
• 2 x Apricot Chicken (Heart Healthy)
• Crabmeat and Swiss Cheese Bake
• 2 x Creamy Potato Soup
• 2 x Down Under Chicken
• Rice Vegetable Cheese Casserole
• 2 x Tropical Pork Chops
• Onion Bacon Crusted Cod

Preparation was really a lot of fun. Nancy and I went together, and we both agreed: it was all the fun parts of cooking without any of the hard stuff! No chopping, no searching for bowls, no scavenging ingredients or trying to work out what you can substitute because you forgot to buy something, and of course the best part -- NO DISHES!!

Working together we finished making our twelve dinners in just over an hour -- that's about five minutes each. Here's how it works:

Each store has a fixed menu which changes every month. There are different recipe stations around the room, one station per recipe. Each station has containers of the ingredients you need at waist level, with the appropriate measuring cup for the recipe already in it. Cheese, mayo, chopped onions, chili sauce, apricot jelly, cooked bacon, etc. (If you want a visual, think of the scene behind the counter at a Subway restaurant, but one that is customized for just a single sandwich.) Some ingredients are pre-packaged in containers that are just the right size for the recipe: for example, one casserole had a bag of exactly the right number of bread squares ready to go. Herbs and spices, sugar, oil, seasoning salts, etc for the recipe are all at shoulder height, and each one has the appropriate measuring spoon next to it. The meat is in a big refrigerator on one wall: thawed, pre-cut, and also ready to go. Along the side there's a sink for washing your hands, and a big rack full of all the utensils you could want and all the pans you need. Oh, and there's yet another station with ziploc bags and a big roll of plastic wrap.

To make your order, you simply find an open station (there was only one other couple there, so this wasn't hard) and start working. Since everything is already prepped for you, you basically wind up dumping stuff together. It's not hard at all. You're free to tweak the proportions if you want; we only did this a little bit since the recipes seem to have a good mix to begin with.

I'll admit that our very first one (the Down Under Chicken) was a little intimidating simpy because it was a new experience. We took it pretty slowly to make sure we were doing everything right. But once we figured out how it worked, we got into a groove and it couldn't have been easier -- we banged out the rest without a hitch.

When you're making it yourself you can also split the orders, so that instead of one meal that serves 4-6 you can make two meals of 2-3 each. We did that on many of the orders, in an attempt to reduce the amount of leftovers. We'll see how that works out.

At one point Nancy commented, "Geez, I feel like we're on a TV show!" You know how in cooking shows they just describe what you'd do, and then whip it out already done? And dirty dishes aren't even discussed? It was exactly like that. Almost a magical experience.

Net cost: $197 for twelve dinners, plus about two hours of our time on a Saturday morning. If the previous ratio holds and we get 60 meals out of it, that will come out to $3.28 per meal.

I'd love to tell you how the food tastes, but since we just made it this morning I can't say yet. But boy, did it ever did look good when we made it!

By the way, in case you were wondering: I'm not affiliated with these folks in any way, nor do I know the guy who runs the store. (Although we chatted afterward and he seemed pretty cool.) I just think it's a great service. And it's the kind of place that's just awesome for families, and which I even kind of wish I'd had access to as a bachelor -- because sometimes you just want a nice dinner without a lot of effort.

The verdict? Two thumbs way up. The dinners are cheap, fun to make, delicious, and easy ... and we're back to eating at a table, instead of from a paper bag.

Changing the DNS query timeout in Windows XP

I've been having some networking trouble lately. When my PC laptop is busy downloading a file, Windows XP starts failing to resolve DNS queries. So even simple lookups that I know must be cached at multiple levels, like www.google.com, start failing to resolve. Windows just times out after fifteen seconds and gives up.

Needless to say, this makes web browsing while downloading a file insanely frustrating.

My Mac laptops don't seem to have the same problem. I have no idea whether this is a problem with my ISP, my wireless router, Windows itself, or some combination of the three. And frankly, as an end user I don't care and shouldn't have to care. I just want it to stop sucking.

I set out to see if I could increase the client-side DNS timeout so that Windows would be a little more forgiving about slow DNS responses. It turns out there is a way to do that, though it's nearly impossible to find via a web search. (Even Windows experts, which I make no claim to be, seem to have trouble with this one because it's so obscure.)

Here's the registry setting to increase the DNS client-side timeout in Windows 2000 and XP:

HKEY_LOCAL_MACHINE \ SYSTEM \ CurrentControlSet \ Services \ Tcpip \ Parameters \ DNSQueryTimeouts

[Update Nov 3, 2006: Fixed the above link. It used to point here, but that link now redirects you to the main page for the Windows 2000 resource kit. Remember, kids, cool URLs don't change.]

Read the above link for details. The registry entry does not exist by default; you have to create it. I don't suggest you do this lightly unless you're familiar with using regedit to tweak parameters.

The default value when the property isn't present is documented to be "1 2 2 4 8 0", which appears to represent that 15-second total timeout. (15 = 1 + 2 + 4 + 8. It's not clear to me exactly what the other 2 is for; it may be redundant.)

I wanted something a little longer, so I quadrupled all the numbers to "4 8 8 16 32 0".

Now I have a 60-second total timeout, with the final query given 32 seconds to get through. In practice this has proven to be a long enough timeout that Windows can continue to resolve DNS names even when my network connection is busy.

And that's good news. I'm much happier again, and I can continue to use my PC laptop without wanting to chuck it out the window every time I download a file.