Threading Again

Ned Batchelder posted about another single- vs. multi-threading discussion, which has been a regular feature here as well. This time it cropped up in the context of using SQLite (an awesome embedded database as Ned says) from within a multi-threaded program. The first round is from SQLite’s author, D. Richard Hipp, and my response is on the next page:

Actually, this seems like a good opportunity to repeat my oft-ignored advice to not use more than one thread in a single address space. If you need multiple threads, create multiple processes. This has nothing to do with SQLite = it is just good programming advice. I have worked on countless multi- threaded programs over the years, and I have yet to see a single one that didn’t contain subtle, hard to reproduce, and very hard to troubleshoot bugs related to threading issues.

Amy’s Favorites

Here’s the latest batch of Amy pictures, showing some of Amy’s favorite places/things/activities.

Timeouts

OK, enough of the politics and philosophy; back to the techie stuff. Today’s topic is timeouts, and why they should not be used to detect failures except when absolutely necessary. The first reason is that you just never know how long a timeout should be. If you set it too long, your code will sit around longer than it should after an operation has already failed (and you’ll get very little information about why it failed. If you set it too short, you risk timing out for an operation that did in fact succeed. That can be even worse, if the operation is not truly idempotent – i.e. if the effect of retrying an operation that already succeeded is not exactly zero. It can be very frustrating to debug problems that occur when a request that’s retried after a timeout leaves you in a state that’s almost but not quite the same as if the operation had succeeded (and been known to succeed) the first time. Explicit failure notification is vastly superior to reliance on timeouts, and should be preferred wherever possible.

There’s a second problem with timeouts that’s even more pernicious, and that has to do with their proliferation. As I’ve written before, it’s important to minimize the number of states a system can be in, which is a product of the states its components can be in. If you have multiple components all relying on separate timeouts to detect failures, most often communications failures or failures of remote nodes, then it’s highly likely that you’ll have many states where some components have detected and are responding to a failure while others remain oblivious. Specifically, you’ll have O(n!) recovery scenarios, where n is the number of components (or instances of components, or sometimes even requests). That’s unacceptable. It’s far, far better to have one piece of the system responsible for detecting such failures and providing some sort of notification to all of the others – all of which will just keep on trying until they get either a normal response or a notification that whoever they’re talking to has died. Such notification should be considered an essential feature of the communications paradigm in any serious distributed system, freeing all components but one from the need to guess how long to wait before concluding that something’s wrong. Because notifications can be serialized, such an approach also ensures that components will always detect the failure and do their recovery in a deterministic order. Limiting timeouts to that one “heartbeat” component and relying on explicit failure notification everywhere else is one of the best ways to make a system more debuggable and maintainable.

In conclusion, then, timeouts are a necessary evil but they are still evil. Using them to implement periodic maintenance or tuning functions is fine, but using them in more places than absolutely necessary to detect failures is a sure way to make an unmaintainable mess of your system.

Game Theory

There’s an interesting article at Crooked Timber about Hiring and Firing and the relationships between owners, managers, and workers. To me, the most interesting part was this:

managers, if they are to get workers to deliver their full effort, need to be able to make credible commitments to them that their efforts will be rewarded over the longer term. Itâ??s thus a good idea to keep a strict separation between management and owners. Efforts to make the interests of stockholders and managers coincide with each other are going to weaken managementâ??s ability to credibly commit to workers

This claim is supposedly backed up by game theory:

Another condition for the achievement of cooperative equilibria in a repeated game is the mutual expectation that the relationship will go on long enough to justify the investment in cooperation.

Unfortunately, there’s another bit of game theory involved here: the Stag Hunt. It certainly would be nice if companies operated the way Miller suggests, but as long as a significant number of companies do not it’s just a dream. Owners who want the best managers will lure them with promises of massive stock options etc. which bind them more to owners than to workers, expecting that their other advantages will outweigh any disadvantage in worker loyalty. Meanwhile, companies that believe in keeping managers closer to workers will be stuck (for the most part) with the non-elite managers and will be at a competitive disadvantage. The state represented by Miller’s proposal would not be stable, and would almost inevitably devolve into something much like what we have now. One way to change the relationship between owners, managers and workers would be for workers to unite and work within the market by refusing to work at places where managers were too “complicit” with owners. Besides the fact that such unionization creates its own share of problems, it’s not very practical in the modern world where most people’s jobs can be moved elsewhere (e.g. overseas) with relative ease. Another way for such a thing to happen would be for government to mandate a certain relationship, and even I don’t think such a mandate would be a good thing overall. There are certain cases (e.g. Costco) where the overall separation between all three groups is smaller and the owners can draw from the relatively small pool of managers who truly believe in doing what’s right as well as what’s profitable, but I don’t think the “managers closer to workers” approach could ever become the dominant paradigm.

Ideological Freeloaders

Apparently some folks are pushing an Open Source Amendment in response to the recent Kelo decision on eminent domain. Don’t ask me why they use the term “open source” for this because it doesn’t seem applicable to me either Here’s the proposed text.

The right to ownership of property being the cornerstone of liberty, no government, or agency thereof, within these United States shall have the authority to take property from any person, corporation, or organization through exercise of eminent domain for other than a public use without just compensation.

Public use shall be understood to be property the government owns or retains the paramount interest in, and the public has a legal right to use. Public use shall be understood to include property the government owns and maintains as a secure facility. Public use shall not be construed to include economic development or increased tax revenue. Public use of such property shall be maintained for a period of not less than 25 years.

Just compensation shall be the higher of twice the average of the price paid for similar property in the preceding six months, or twice the average of the previous 10 recorded similar property transactions. Compensation paid shall be exempt from taxation in any form by any government within these United States.

The price-doubling in the last paragraph is probably what will kill this, since it’s pretty obviously just gouging for the sake of discouraging the government from doing even things that are beneficial. The thing I find really odd, though, is the part requiring that the government own or retain the “paramount interest” in seized property. I find it odd because of something that’s actually incorporated into the text of the Kelo decision, quoting from the earlier Berman case:

The public end may be as well or better served through an agency of private enterprise than through a department of government—or so the Congress might conclude. We cannot say that public ownership is the sole method of promoting the public purposes of community redevelopment projects.

That seems like a statement that would appeal to any True Believer in markets, or hater of big government. The Supreme Court of the United States, saying that sometimes the private sector can do something better than the government itself? Cool, huh? And yet, this Open Source Amendment would destroy that benefit by making it impossible to use the power of the market for the public good.

I’m no fan of Kelo, of course. I think it was a terrible decision, but this amendment seems like an equally terrible response. It doesn’t matter whether the government owns a seized property but whether the public benefits from it. The amendment is wrong on two points: government vs. the public, and ownership vs. benefit. I’ve argued before that the standard by which an exercise of eminent domain should be measured is whether it primarily benefits the public, but that’s not at all the same as whether the government retains ownership of the property. The amendment seems like no more than an attempt to take advantage of outrage over Kelo to push measures that have little to do with that decision’s faults, as part of a preexisting absolutist-property-rights agenda. Those pushing it should learn to present their views honestly and have them judged on their own merits instead of trying to hitch their wagon to someone else’s horse.

Argh!

A while back I wrote about my problems with Akregator (an RSS news reader) and I’ve been using Thunderbird’s built-in RSS support ever since. Now it seems that Thunderbird has an even worse problem: today, for the third time, I discovered that it had quietly dropped half of my feeds. All three times it has been an entire folder worth of feeds that just silently disappeared, and it’s a major pain to clean it up. Can’t anybody get this very simple kind of programming right? Not throwing away information is hardly rocket science, and yet every Linux RSS aggregator I’ve tried either does that or crashes regularly. It’s enough to make me go back to Windows, where at least there were such programs that actually worked.

Zuma Redux

After finishing the last level in Zuma, I’ve tried playing a few similar games – Tumblebugs, Luxor, and Bubblefish Bob (which I have already finished). Doing so has given me a new appreciation for Zuma, and how its design affects strategy. Here are some observations on the alternatives, followed by a few more about strategy.

Tumblebugs
Two words: ugly ripoff. The graphics are chunky, with very few colors, and almost put me off the game right away, but it’s the play that matters, right? TB is more similar to Zuma than the other two are. The bonuses and level completion work the same way, and the powerups are mostly the same. You can rotate between three “ready” balls instead of just two as in Zuma, which seemed more of a pain than anything else. There’s an additional “penetrating” ball that can go through multiple segments of a convoluted track triggering multiple kills. There’s a “wild card” ball that matches any other color; I never quite got used to anticipating what would happen when I shot it between two different-colored balls, but I’m sure I would with time. The most interesting extra powerup is the “ballistic ball” which you can fire over one segment of the track to reach another. While it might seem handy to reach something that’s shielded from your firing position, it also means you must aim by range as well as direction. Since choosing a direction and firing quickly is the key play element in all of these games most of the time, having to deal with range was actually quite a pain – especially since the cursor tracking in the game is also sloppy. The one thing I did think was kind of cool in TB was the way that some levels had multiple firing positions that you could switch between. With better level design that could be cool, forcing the player to switch to deal with odd angles etc. As it is, though, “let’s do Zuma with some extra stuff” seems to have been the TB design. Without more attention to how people actually play and what actually makes Zuma so addictive, the result is just a shoddy-feeling rework.
Luxor
Much more polished than TB, maybe even a little better than Zuma, but fundamentally different in some ways. For one thing the motion is linear (move left/right, shoot up) instead of circular, which feels very different. Powerups do not take effect immediately but fall after being shot and must be caught. Gaps close almost instantaneously, eliminating one of the best strategic aspects of Zuma, and they fall fast. Between the fact that it was hard to tell which balls represented powerups and the fact that they fell so fast, they effectively seemed to occur at random. There’s nothing in Luxor similar to the level midpoint (when the colored bar fills up and new balls stop appearing) in Zuma, which removes another strategic element. There also seemed to be a serious lack of creativity in the level design relying too much on simple zig-zags. If I hadn’t already played Zuma I might find Luxor more appealing, but I have so it just seemed kind of ho-hum.
Bubblefish Bob
By far the most visually appealing; it’s worth checking out just to see the transparent bubbles jiggle across the screen. Play is very similar to Luxor in that motion is linear and you have to catch powerups. Like Luxor the powerups seem to appear a bit randomly, but they fall quite slowly so you can see what they are and prepare accordingly. This is especially important because there are also “powerdowns” that cause bad things to happen – balls speed up, you lose a life, or (most creatively of all) the colors get scrambled into the worst possible order. The level design is quite good, though the linear rather than circular format seems limiting; the closest equivalent to some of the convoluted Zuma levels is levels with up to four parallel streams so you have to cut back the lower ones to get to the higher ones. It’s challenging, but not as interesting. There’s no level midpoint, and overall the game just seems too easy. Yes, I know, I have a lot of practice from playing Zuma, but I completed BB – a whole different game – in my second try after only a few hours of play. I’d probably require many more tries and much more time to complete Zuma again even though it’s more familiar.

Obviously I liked BB the best, even though TB was more similar. Nothing more to say there; read on for the strategy portion.

Explicit State

There are many ways to design programs. Two of the best known represent opposite extremes: flowcharts tend to represent only control flow with little regard for data, and notations like UML (in its most common usage) tend to represent only data with little regard for flow. Flowcharters are a dying breed, but the industry is awash with UML weenies who develop frighteningly detailed models of their data without being able to conceptualize any non-trivial control flow which affects that data. Personally, I’ve found that the most important pieces of any workable design usually have to do with the space in between – in how control flows affect data, in particular with regard to state information. Typically a system has objects to represent various resources, requests, and components. Each of these has some actual data associated with it, plus links to other objects, plus some state information in the form of enumerated states and/or flags. The amount of state information directly affects the predictability and maintainability of a system, since every state or combination of states has to be handled and tested. Worse, the state of the system is the product of its component states, potentially leading to an exponential explosion, so one of the design rules I’ve learned is to keep states to a minimum. Another important rule is to make state explicit rather than implicit. In what follows I’ll cover some examples of implicit state, why they’re bad, and how explicit state is preferable.

Random Science Link

Why don’t trees grow on the Great Plains?

Congrats, Barry!

Congratulations to Barry Smith, of Angst Technology fame, on the birth of a beautiful daughter.