Strangelove

I bought a copy of Dr. Strangelove last weekend. I hadn't seen it in years, so I had the joy, once again, of discovering all the the little gems buried in the movie.

"You can't fight here! This is a War Room!"

To really appreciate the movie, you have to understand it in the context of the early '60s with the commie scare, the bomb scare, and, yes, the floridated water scare.

So where is the moviemaker today who'll do a comedy about terrorism, Al Queda, homeland security -- with a side jab or two at intellegent design? Yes, we really do need to laugh while we watch the World Trade Centers burn -- otherwise the terrorists win.

Remember at the end of Strangelove the doomsday device was triggered while George C. Scott was warning the president about the "mine shaft gap."


Dale

We've come a long way...

I just stumbled over this code deep down in ACE -- a C++ library/framework that prides itself on its portability:

ACE_OS::sprintf (date_and_time,
ACE_LIB_TEXT ("%3s %3s %2d %04d %02d:%02d:%02d.%06d"),
day_of_week_name[local.wDayOfWeek],
month_name[local.wMonth - 1],
(int) local.wDay,
(int) local.wYear,
(int) local.wHour,
(int) local.wMinute,
(int) local.wSecond,
(int) (local.wMilliseconds * 1000));
return &date_and_time[15 + (return_pointer_to_first_digit != 0)];

A word of explanation. For a long time the ACE community didn't believe in bool, so "return_pointer_to_first_digit" is a bool-like substance that when equal to zero means false. Thus (return_pointer_to_first_digit != 0) converts the pseudobool to a genuine bool.

Question: What value does *your* favorite C++ compiler use to represent true?

Dale

Coming soon to a cell phone near you...

Just a reminder: In a month, cell phone numbers are being released to
telemarketing companies and you will start to receive sale calls.
YOU WILL BE CHARGED FOR THESE CALLS
To prevent this, call the following number from your cell phone:
888/382-1222. It is the National DO NOT CALL list. It will only take a
minute of your time. It blocks your number for five (5) years.

You can also use the following web link:

https://www.donotcall.gov/default.aspx

The opposite of in...

Quick, what's the opposite of login?

The answer, of course, is logout.

And the opposite of logon?

Logoff!

So why do some systems want you to login, then logoff; while others prefer that you logon and logout?

I must be developing another pet peeve.

Why I worry about Ruby

In the FAQ on the official Ruby site, Matz (author of Ruby) is quoted as saying:

Well, Ruby was born on February 24 1993. I was talking with my colleague about the possibility of an object-oriented scripting language. I knew Perl (Perl4, not Perl5), but I didn’t like it really, because it had smell of toy language (it still has). The object-oriented scripting language seemed very promising.

I knew Python then. But I didn’t like it, because I didn’t think it was a true object-oriented language—OO features appeared to be add-on to the language. As a language manic and OO fan for 15 years, I really wanted a genuine object-oriented, easy-to-use scripting language. I looked for, but couldn’t find one.

Let's see: In 1993 he had been an OO fan for fifteen years. He must have been using Simula in 1978. I'll give him the benefit of the doubt on that one, but...

Python is not object-oriented enough? OO features tacked on?

Apparently Matz doesn't quite get it. In Python *everything* is an object Witness the following interactive session:

>>> type(1)
<type 'int'>
>>> dir(1)

['__abs__', '__add__', '__and__', '__class__', '__cmp__', '__coerce__', '__delattr__', '__div__', '__divmod__', '__doc__', '__float__', '__floordiv__', '__getattribute__', '__getnewargs__', '__hash__', '__hex__', '__init__', '__int__', '__invert__', '__long__', '__lshift__', '__mod__', '__mul__', '__neg__', '__new__', '__nonzero__', '__oct__', '__or__', '__pos__', '__pow__', '__radd__', '__rand__', '__rdiv__', '__rdivmod__', '__reduce__', '__reduce_ex__', '__repr__', '__rfloordiv__', '__rlshift__', '__rmod__', '__rmul__', '__ror__', '__rpow__', '__rrshift__', '__rshift__', '__rsub__', '__rtruediv__', '__rxor__', '__setattr__', '__str__', '__sub__', '__truediv__', '__xor__']

As you can see an integer, like all the other native data types, is an object with a value, a type, methods -- the whole shebag.

Not only that, but!

>>> def spam():
... """This is the spam function"""
... print "Peanut butter and Spam sandwich"
...
>>> spam()
Peanut butter and Spam sandwich
>>> type(spam)
<type function >
>>> dir(spam)
['__call__', '__class__', '__delattr__', '__dict__', '__doc__', '__get__',
'__getattribute__', '__hash__', '__init__', '__module__', '__name__', '__new__', '__reduce__', '__reduce_ex__',
'__repr__', '__setattr__', '__str__', 'func_closure', 'func_code', 'func_defaults', 'func_dict', 'func_doc',
'func_globals', 'func_name']

A function is an object. It can be manipulated just like any other object in Python. It just happens to support the __call__ method. Yes, of course you can create your own class of object that supports the __call__ method and use it anywhere a "normal" function is expected.

Other types objects in Python include modules (in Java they're called packages); chunks of compiled code (that's the func_code property of the method above); "None"; "NotImplemented"; and "Ellipsis"; and more, all of which are available to be manipulated by the programmer as objects (if your into that kind of thing), or to just quietly do their job if you'd rather concentrate on the important stuff.

Of course, Python supports user defined classes from which instances (i.e. objects) can be created. Like the rest of Python, class defintions are syntactically and conceptually clean. And yes, the class itself is just as much an object as its instantiations are.

About the only OO feature I can think of that Python doesn't support is function overloading -- it's kind of hard to do in a dynamically typed language (grin).

Back in '93 Python was still a bit young (it was originally released in '91) but even then it was obvious that "Guido knows Objects."

I guess Matz was mislead because Python's OO nature is not constantly in-your-face. You can code in Python without thinking about objects (unless, of course, you want to). Instead you get to think about the problem you're trying to solve. Hello world in Python is:

print "Hello, World!"

The objects are there doing their job, so you don't have to worry about them.

Maybe Matz did a better job of designing Ruby than he did of understanding Python.

Simulating a loom. UI vs creativity.

I bought another weaving design program last week at the Midwest Weavers' Conference. Both Tina and I use our"old" program regularly to design cloth. Why would I pay $100 for a new program when I have a perfectly good program that obviously works? The answer says something about the impact of user interface design on creativity.

Since I can't assume that everyone who reads this understands how a loom works, I have to digress. I'm going to describe the design issues faced by a weaver using a jack loom. There are many other types of looms that have their own design issues, but jack looms are very common among handweavers so it's a good place to start.

The purpose of a loom is to interleave two sets of threads that run at right angles to each other -- thereby creating cloth. (All you people with triangular looms, hush -- I'm trying to keep this simple.) One set of threads, the warp, is installed on the loom before the actual weaving begins in a process known as dressing the loom. The second set, the weft, is added to the cloth one thread at a time by running a shuttle containing a bobbin full of weft thread between the warp threads in a preplanned pattern. (and I'm not even going to *mention* how many details and variations I just omitted.)

When you ask a weaver to describe his or her loom, you can be sure that one of the first things they mention is how many shafts the loom has (unless, of course, they've been weaving for a long time in which case they'll tell you how many harnesses the loom has. I'm sure there's a really good reason for the terminology change -- other than to confuse the innocent.) That's because the number of harnesses (oops, I mean shafts) has a strong influence on the complexity of the cloth that can be produced. So what's a shaft?

Part of dressing the loom is threading. Each of several hundred threads in the warp goes through through the eye of a heddle (Imagine a large (12" long) needle with the eye in the middle rather than near one end.) The heddle is attached to a shaft, so that when you lift the shaft, all of the heddles attached to that shaft, and therefore all the threads in the eyes of those heddles are lifted. The the remaining warp threads -- the ones that are attached to shafts that do not get lifted -- remain down and a triangular space is opened up between the two sets of threads. This space, called a shed, is where the shuttle is thrown -- trailing its warp thread behind it.

Once the shuttle is through the shed, the shed is closed, the warp thread is pressed into place at the edge of the newly woven cloth using part of the loom called the beater, and a different shed is opened for the next warp thread. Thus each warp goes under the set of lifted warp threads, and over the remaining ones and cloth happens.

Since each warp thread is associated with a single shaft, the warp is divided into independantly controllable sets of threads. The number of shafts on the loom defines an upper limit on the number of sets of warp threads. More than one shaft can be lifted to produce any particular shed so the number of potential sheds (aka lifts) goes up dramatically as the number of shafts increases. In fact, a loom that has n shafts can produce 2**n - 2 meaningful lifts. (The -2 is there because it doesn't make sense to lift 0, or n shafts.) Some of the common cases are:
2 shafts -> 2 lifts
4 shafts -> 14 lifts
8 shafts -> 254 lifts.
16 shafts -> 65534 lifts.

Thus motivating a common malady among weavers: shaft envy [ no questionable jokes allowed here.] and it's converse: shaft pride [note 1].

There is another limitation, however, that shows up when I describe a previously unmentioned part of the loom -- the treadles. In order to lift the shafts, the weaver presses down a foot treadle. Each treadle is tied to one or more shafts so that the shafts are lifted as the treadle is pressed. The number of treadles imposes an additional upper bound on the number of lifts. For example, most 8 shaft looms have 10 treadles, so part of the design process is select which of the 254 possible lifts will be used during the weaving process. Of course it is possible to press more than one treadle at the same time (two feet can produce 100 possible lifts on a 10 treadle loom), and of course the tie up between treadles and shafts can be changed during the weaving process, but that's a slow and awkward proposition. Most handweavers using treadle-operated looms end up restricting the number of distinct lifts to the number of treadles.

...unless....

Unless the loom has a dobby instead of treadles and a tie-up. For computer history buffs, dobbies are the thing that Joseph Jacquard invented that led via Herman Hollerith to punched cards (which no one under 30 remembers, anyway.) A mechanical dobby uses holes punched in a wooden board, or more commonly nowdays pegs screwed into a wooden board to indicate which shafts should be lifted to form a shed. These cards are chained together so when the weaver is ready to move to the next weft thred, the chain is advanced to the card containing next lift pattern.[note 2]

A dobby provides two benefits. First the number of possible sheds is no longer limited by the number of treadles -- the weaver can design to the full capability of the loom, and second the weaver no longer has to remember the treadling sequence. No longer is the complexity of the pattern limited by the capacity of the weaver's memory, or the speed of weaving limited by the need to carefully follow a treadling sequence.

An electronic dobby takes this one step further. Rather than pegs in a wooden card to select a lift pattern, an electronic dobby uses solenoids to select the shafts to be lifted. These solenoids can be computer activated, so the chain of dobby cards can be relplaced with a lift plan stored in the computer. This removes yet another limitation in that the length of a woven pattern is no longer limited by the number of dobby cards in a chain. Instead it is limited only by the capacity of the computer and the ability of the weaver to design the pattern. Suddenly those 65 thousand possible lift patterns are accessable -- if only the weaver can figure out how to actually use them.

Which brings us back, finally, to the issues of user interface design for the computer assisted design programs used by weavers -- a topic for the next entry since this has gotten way to long.

[note 1] Tina and I have looms with 4, 8, 16, and 24 shafts. The 16 and 24 shaft looms are computer controlled.

[note 2] A dobby controlled jack loom described here is not the same as a modern Jaquard loom. A Jaquard loom provides individual control of each thread. It could be (but isn't) described as a loom with several hundred shafts. Jaquard looms typically cost 10 to 100 times as much as dobby controlled jack looms, and wouldn't fit in a handweaver's studio anyway.

When worlds collide

I love it when two separate parts of my life collide. Ruth Blau just posted this on the WeaveTech List

This past weekend, I attended a wonderful knitting workshop with Debbie New. One of her approaches to designing is based on the Sierpinksy triangle fractal. You can do it with color (either two colors, or better yet, with dark & light and then use any colors you want), with stitches (knit vs. purl) or w/ broader design concepts, e.g, cables. She calls it "rule-based knitting." At any given time, the stitch (or color or whatever) you use is determined by the stitch's surroundings. Here's an example. Assume you're ready to knit a stitch. Look at the three stitches below it (one directly below and the two on each side of it). Your rule is this: if one (and only one) of the stitches below is purl, then you purl. Otherwise you knit. It could also be this: if one and only one of the stitches below is light then use light yarn, otherwise use dark. You make this decision for every stitch in the row (yes, it's slow going).

If you happen to have Debbie's book "Unexpected Knitting," this is in the section called Cellular Automaton Knitting.

Intel Exudes Confidence

Headline and lead-in from an InformationWeek article

Intel Business PCs Won't Include Dual-Core Processors
The business-PC platform includes only technologies that have been validated, and the chipmaker promises it will remain stable and unchanged for the next 12 months.
By Darrell Dunn

Are you getting a warm fuzzy feeling about the Intel dual core chips?

Pauli Exclusion Principle applied to Airlines

Pauli Exclusion Principle

No two people on any particular airplane shall have paid the same amount for their ticket.

Oops. My mistake...

In a previous post on threading I gave a high-level pseudocode description of a multithreaded MPEG decoder.

It was wrong.

A revised (and, I hope, more correct) version is:

The new high level design for video looks like:

• Accept input, and separate into VOBs
• Hold VOBs for processing [MT]
• Pick a VOB and demux its content into substreams
• Queue packets for decoder(s)[MT]
• Decode stream into buffer in decoded VOB
• Wait for VOB completion [MT]
• Hold completely decoded VOBs[MT]
• Get next VOB and deliver decoded substreams to presentation engine.
• Hold decoded, substreams for presentation [MT]
• Mix and present decoded content.

* * *
My first instinct was to simply edit the original post and replace the incorrect "code" with the corrected version.

Then I remembered the programmer's diary, I mentioned in another post.

One of the hardest parts of becomming a good programmer is learning how to deal with mistakes. First you have to accept that you and the people you work with are going to make mistakes. Then you have to train yourself to react positively to your own and other peoples' mistakes.

Reacting positively to your own mistakes means you fix your mistakes. You don't hide them. You don't defend them. You just fix them -- and clean up any consequences resulting from the mistake.

Reacting positively to other peoples' mistakes means you bring them to their attention in a non-threatening way. You don't fix their mistakes for them (at least not silently.) You don't help them hide their mistakes. You don't gloat over their mistakes (although it's hard to avoid a certain level of "boy, I'm glad I didn't make that mistake.) What's important is that the person who makes the mistake learns that it happened, and that the mistake gets fixed.

And finally, when someone brings one of your own mistakes to your attention, the only proper response is "Thank you." After saying that then you can proceed to analyze the report to see if it's correct, but first you must reward the person who respected you enough to tell you about your (possible) mistake.

A lot of this comes from another landmark book about software development: The Psychology of Computer Programming, by Gerald Weinberg.

* * *
I predict that we will never have a good programmer as president of the United States (and vice versa.)

* * *
So why did I make this mistake? Because I was thinking about multithreading on a frame-by-frame basis. Then when I switched to thinking about it on a VOB-by-VOB basis I didn't completely reset my mental model of the problem.

How can I avoid making this kind of mistake in the future? (Or how can I make it less likely to happen?) Tough question -- maybe awarness of the potential pitfall will help.

Baby Geese and Parrots

The eggs in the goose nest right outside the door to our building here hatched the other day. Within hours after they hatched, they were cute bundles of fuzzy yellow feathers running around on their own -- much to their mother's dismay. A day later the parents marched their goslings over to a near-by lake.

How come baby geese are so competent and cute when baby parrots are totally helpless and look like something from a grade C SF flick?

For example

My theory is that baby parrots are too busy growing an intellegent brain to have any energy left over for cute. Geese seem to make-do without benefit of brain.

Parallel by force

Suppose you've created the multithreaded MPEG decoder as outlined in the previous entry. Remember the good reason for multithreading the MPEG decoder was:

• The task is inherently multithreaded so a multithreaded solution results in simpler code.

In fact the MPEG decoder almost begs to be multithreaded.

So one day your multithreaded MPEG decoder is happily zipping thru an MPEG stream that contains just video and one audio track. The following threads are running:

#1 Accept and demux input
#2 Decode video substream
#3 Decode audio substream
#4 Mix and present substreams.

Then your boss shows up and says, "I spent all this money on a 16 CPU superserver and your application is only keeping it 25% busy. I want you to increase the parallellism so all the CPU's will be kept busy. NOW!"

* * *
Now what do you do (other than looking for a new job with a new boss.)

You've already added the "natural" multithreading that is inherent in the problem. How can you increase parallelism even further?

It's time to try to apply the other good reason.

• The task can be cleanly decomposed into multiple sub-tasks that are highly independent; the independent tasks can use resources in parallel; and the benefits of this parallel usage outweigh the overhead of multithreading. (All three conditions must be true.)

Hmmm....

A video stream is a series frames. Maybe we can create multiple threads and have each thread decode a separate frame. So we add component that separates the stream into a series of, undecoded frames (yes this is fairly easy to do without actually decoding the frames) and a pool of threads that processes these frames. Each thread from the pool picks up the next un-decoded frame, decodes it, and adds the result to a collection of decoded frames. Since frame-decode time varies as a function of the complexity of the image, we also need component to shuffle the decoded frames back into the correct order.

Voila, we can keep as many CPU's busy as we want to by looking forward far enough. Makes sense, right?

Nice theory, anyway. When you start coding the frame decoder, you'll quickly run into a major stumbling block. One of the techniques MPEG uses to compress the video image is to send most frames as a diff from the previous frame. This is very effective -- especially when the movie is showing relatively static scenery (it doesn't work so well during explosions.) Thus as you decode frame #n you regularly have to refer back to frame #n-1 to apply the diff and thereby create the final result. Even more interesting, sometimes you have to look *forward* to frame #n+1! (Don't ask, the MPEG folks are a twisted bunch.)

So the thread-per-frame solution sounds plausable (you can probably sell it to your boss) but fails the "independance" test. Back to the drawing board.

Fortunately for DVDs there's another approach. In order to support fast forward, slow motion, jump to scene, etc, the video on a DVD is carved up into chunks called video objects (VOBs) A VOB contains about half a second worth of video, audio, subtitles, etc. and what's more important each VOB is independant of the VOBs that preceed it and follow it. So, although the thread-per-frame idea was a bust, a thread-per-VOB approach will work nicely. You may need a priority scheme to insure that the thread that's decoding the VOB scheduled to show up next on the screen gets all the resources it needs, but other than that you've found a clean division of the main task into subtasks that can take advantage of the available CPU's by running in parallel.

The new high level design for video looks like:

1. Accept and demux input
   
2. Queue packets for decoder(s)[MT]
   
3. Separate into VOBs
   
4. Hold VOBs for processing[MT]
   
5. Decode VOB
   
6. Hold decoded VOBs for reordering[MT]
   
7. Reorder decoded VOBs into decode stream
   
8. Queue decoded streams for mixer.[MT]
   
9. Mix and present substreams.

This approach has added some more synchronization spots -- one to hold the separated VOBs waiting to be decoded, and one to hold the decoded VOBs until they can be placed in the correct sequence and passed on to the mixer. It might be tempting to try to merge demuxer with the VOB separator or the decoded VOB holder with the decoded stream queue, but don't give in to temptation. Solve one problem at a time and let the inherent parallelism take care of improving performance. [or at least get it working correctly and profile it before optimizing.]

The moral of the story:

• Finding the right decomposition into independant subtasks needs to be done carefully based on detailed understanding of the domain. An obvious solution may not be the right solution.

Multithreading: Why bother?

So multithreading synchronization is hard and requires hardware support. How do all those existing multithreaded programs manage to work?

Answer #1 Someone got lucky. Doesn't it comfort you to know that the software flying your airplane might be working by accident?

Answer #2: To write thread-safe code you have to follow a different set of rules. Actually an additonal set of rules, because all the old rules for writing good programs still apply.

Since single threaded code runs faster, is easier to write, and is easier to test than multithreaded code, why anyone would willingly go to all the effort necessary to write multithreaded code? Good question. The first decision that needs to be made when designing a multithreaded program is, "is this necessary?" If you can't come up with a compelling benefit for multithreading, go for the simple solution.

There are lots of bad reasons for multithreading, and only a couple of good ones. The good reasons I know of:

1. The task is inherently multithreaded so a multithreaded solution results in simpler code; or
   
2. The task can be cleanly decomposed into multiple sub-tasks that are highly independent; the independent tasks can use resources in parallel; and the benefits of this parallel usage outweigh the overhead of multithreading. (All three conditions must be true.)
   

Let me provide an example of the first case.

MPEG is a standard for encoding audio-video information. A stream of MPEG encoded data can contain many substreams. For example: an MPEG encoded movie recorded on a DVD might contain a single stream of video, two or three streams of video overlay (the subtitles in various languages); several streams of audio (the main audio track in different languages, etc. and the director's comments); and DVD navigation information to support fast forward, fast reverse, etc.

These substreams are multiplexed at a packet level. The overall data stream consists of a set of fixed-sized packets and each packet is part of a a particular substream. You could have a navigation packet, two video packets, and audio packet, another video packet, a subtitle packet, and so on.

The substreams themselves have a rich internal structure. For example the video stream contains sequences of variable bit-length, huffman encoded data fields. Suppose the video stream decoder has extracted the first five bits of an eleven bit field when it hits a packet boundary, it would be a nightmare to attempt to save the video-decoding state including the partially extracted field, and switch to a completely different context in order to be able to properly decode the audio packet that comes next.

Splitting the MPEG decoder into a main demultiplexing thread and independent decoding threads for each substream, and a mixing thread to manage the simultaneous presentation of the decoded threads dramatically simplifies design.

It is interesting to note that there are two synchronization hot-spots in the multithreaded version of the MPEG decoder. One is the point at which the demultiplexer passes a packet is passed to the specific stream decoder for this type of packet, and the other is the point at which the mixer accepts the decoded substreams for integration and presentation. Everything between these two points can and should be coded as if the program were single threaded.


These synchronization hot spots should be separate components. A possible high level design would be:

• Accept and demux input
  
• Queue packets for decoder(s)[MT]
  
• Decode substream
  
• Queue decoded streams for mixer.[MT]
  
• Mix and present substreams.
  

Multithreading issues should addressed only in the two components marked [MT]. Everything else should be written as if it were single threaded (and protected accordingly.)

The moral equivalent of a mutex

In yesterday's post I used the phrase "The moral equivalent of a mutex." I claimed that it was not possible to write code that shares data between threads safely without one.

This prompted an anonymous response which cited Dekker's algorithm as an example of a software-only synchronization mechanism. I appreciate the response (even though I immediately rebutted it) because it prompted a train of thought about what the "moral equivalent..." is and why multithreaded code is so falupin' hard.

Mutex equivalents on Win32 include: CriticalSection, Event, Mutex, Semaphore, InterlockedIncrement, InterlockedDecrement, InterlockedExchange, and so on... Other OS's support some of these and have their own, unique variants with various degrees of arcanity (SYSV Semaphores, for example.) The point is that all of these objects are designed specifically to address thread synchronization.

Dekker's algorithm is interesting because it is an algorithm for implementing a critical section. I'd count it as the moral equivalent... with one caveat. It doesn't work unless there is an underlying hardware synchronization mechanism.

The algorithm contains the following code:

 
  flags[i] = BUSY;
  while(flags[j] == BUSY)
    <SNIP>
  <if you get here you have access to the resource>

The problem shows up in the following sequence of events:

  Thread 0: flags[0] = BUSY;
  Thread 0: while(flags[1] == BUSY) // false so thread 0 has access
  Thread 1: flags[1] = BUSY;
  Thread 1: while(flags[0] == BUSY) // flags[0] from cache is still FREE
                                    // so the condition is false and thread 1
                                    // also has access to the resource

I'm not saying that Dekker's algorithm is wrong. I'm saying that it contains an underlying and invisible assumption about how things are executed in the computer. In particular it assumes that operations on shared memory are atomic and immediately visible to other threads. If that assumption is correct then the algorithm works. Thus the algorithm reduces the problem of providing CriticalSection behavior to the problem of implementing the shared property.

* * *

A programmer reading code, has a mental model of how the machine works. Most of the time we use a very simple model -- things in our mental model happen sequentially in the order that they appear in the source code we are reading. Having this simple model is A Good Thing[TM] because it allows us to concentrate on what the program is supposed to be achieving rather than how it goes about achieving it.

The problem with this simple model is performance. The code may say:

for(int i = 0; i < 10; ++i)
{
  someFunction(i * k);
}

but the compiler may generate code that looks more like:

int j = 0;
do
{
  someFunction(j);
  j += 10;
} while (j < 100);

on many processors a literal translation of the second version will be faster than a literal translation of the first version -- so the language standards committees have given compiler writers freedom to provide the second version as a legal compilation of the first code.

If you observe the state of the system before this code executes, and after it completes, you can't tell the difference between the two versions. The only observable difference is that one version runs a bit faster.

The programmer gets to write code in a way that describes the algorithm most clearly (in his mind, anyway), and the processor gets to execute code that generates the desired result faster. Everybody is happy.

* * *

Multithreading changes the rules. Rather than observing the before and after states of the system, you now have to be concerned about every intermediate state that might be visible to another thread. A lot of discussions of multithreading present C source code and discuss the implications of an interruption occurring between each statement. The discussion of the incorrect algorithms that precedes the presentation of Dekker's algorithm uses this technique to identify the points of failure. This is a step in the right direction, but it's still not good enough.

Consider the following statement:

  volatile i;
  a[i] = b[i] + c[i];

and what happens if "i" is potentially changeable by an outside agency (another thread, a memory mapped I/O, etc.) For example, suppose that before executing this statement i has the value 0, but sometime during the execution of the statement i takes on a value of 1. How many possible outcomes are there for this statement?

The answer surprises many people. There are 8 possible outcomes because the compiler is free to evaluate the three instances of i in any order it chooses to. To analyze an algorithm containing the above statement in a multithreaded environment you must consider all eight of these cases.

So all we need to do is break each statement down into phrases that can occur in arbitrary order and analyze the effect of an interrupt between any two phrases. Are we there yet?

Well, it depends on how many phrases you see in the following statement:

    ++j;

Assuming int j;, this probably compiles into a single machine language statement: inc [j] -- hence one phrase, right?

Nope. At this microcode level, this statment says: retrieve the value of j from memory; add one to it; store the new value back into memory location j. That's two phrases (why not three? because "add one to it" is internal to the processor and therefore invisible to other threads.)

So, we've gotten to the microcode level. We must be at the right level of analysis by now.

Sorry, to truly understand you have to throw in instruction pipelining, and cache (remember cache.) Once you take them into account, then you model of what really happens in the machine is complete enough to analyze the thread-safeness of the probram.

Alas, pipelining and caching issues are truly beyond the control of the programmer, so the problem of ensuring thread-safeness appears to be unsolvable.

Except!

Thank goodness there's a way to tell the hardware to switch momentarily from its default anything-for-speed mode into a safe-for-the-silly-programmer mode. Every processor has at least one synchronization operation that does things like flushing and/or updating cache, locking the bus for a read/alter/rewrite cycle, etc. These operations tend to produce a dramatic slow down because they defeat all the work that went into designing a cache and a pipeline, etc to speed things up. The other problem is on many CPU's the hardware guys decided that these operations should be reserved for kernel mode, so enlisting the hardware's help may involve an OS call with the corresponding high-overhead context switch.

In any case, I think this justifies Rule #1: Multithreading is hard.

Multithreading considered

Peter said I should post this, so....

Hi Peter,

On 4/14/05, Peter Wilson wrote:
> Do you know of any books on threading in software design written at
> the level of Design Patterns?

Sounds like a great book. I want a copy! 8-)

There have been some interesting articles recently in C++ journal, but I haven't seen any of the "newer thinking on threads" gathered into a book.

This is going to become more critical RSN as the multi-core chips hit the market. Maybe I should write a book!

Rule #1: Multithreading code is hard.
Corollary: If you don't think it's hard, your code is wrong! (witness Java synchronized)

Rule #2: If the hardware isn't involved at some point, it's wrong.
There are no software-only synchronization methods. This doesn't mean you have to lock a mutex every time you touch shared data. It just means that somewhere in any thread safe technique there has to be a mutex (or the moral equivalent.)

Rule #3: Don't try to cheat -- particularly not for performance sake.
Multithreading buys you performance through parallelism, not
through shoddy coding techniques. (remember the Double Checked
Locking Pattern? (and see my blog for TCLP))

Rule #4: You need a model.
If you wing it, or play it by ear, you'll get it wrong (I'll put money on it.) Separate the thread-safeness from everything else and get it right in isolation. Then use encapsulation to keep "the next guy" from cheating.

Rule #5: Testing multithreading code is harder (and more important) than writing it in the first place.

how'm I doing?

Dale

Joel on Hungarian

I just got around to reading the third installment of Joel On Software's essays on the new FogBugz release.

In it he extolls the virtues of Hungarian notation. I was somewhat taken aback, since Joel usually makes so much sense and Hungarian is such an abomination, but then I noticed the context.

Hungarian notation was originally developed to overcome a deficiency in the C language and in C compilers -- weak type checking. Using HN you could do the "type checking" by eyeball rather than relying on the compiler. Once the language and compilers got smart enough to complain when you tried to assign the address of a SnaggleWhomp to a pointer to DeedleBlang then the justification for Hungarian disappeared -- leaving only it's significant drawbacks. artThe adjMost advImportant prepOf adjithinkThese nounsubjDrawbacks verbWas adjUnreadable nounobjCode.

However, the reason Joel gives for valuing Hungarian is that the home-grown Thistle compiler they use at Fog Creek has trouble compiling VB Net without it. Aha-- once again you have a defective language and a deficient compiler to compensate for and Hungarian rides again!

Supercomputers and tapestry weaving

There's always been a strong link between computers and weaving, but a recent New Yorker article looks at the relationship from a different perspective.

It's a long article so don't worry that the computers don't show up for a while.

Hybrid User Interface

I really like my new Escape Hybrid, but I've started to notice some interesting UI issues:

I was stopping at a traffic light yesterday. I'd been driving a while so everything was warmed up. The gas engine turned off as I dropped below 20MPH -- as expected.

If the radio's not on it gets eerily quiet when you stop. Cool.

Then I took my foot off the brake. I noticed something unexpected. The car started to creep forward, just like "normal."

Hmmm...

In a normal car, the creep happens because the gasoline engine has to keep running. The torque "leaks" through the automatic transmission's torque converter. But for a hybrid the gas engine is off, and an electrical engine doesn't really need to keep spinning. In fact I'll bet the electrical engine was at a dead stop, too, when my foot was on the brake. Where is the creep coming from?

I'm betting that it's designed into the system to comfort those of us used to an automatic transmission. It reinforces the concept that a hybrid is "just like a normal car, only more efficient."

I wonder how much time Ford wasted getting this behavior to feel right. Personally I'd just as soon my car stayed where I put it unless I explicitly tell it otherwise.

Cross-Programmer Code

A lot of my programming work is intended to be portable across platforms where a platform is defined as a combination of operating system, computer architecture, and development tool set (compiler, etc.). ACE is a prime example of what it takes to achieve this goal.

However,

Even more important that platform portability is programmer portability. It is highly unlikely that any significant programming project will be developed and maintained by a single programmer for the life of the project. Every time a new programmer gets involved in a project the source code has to be "ported" into that programmer's model of the language.

Every programmer carries around a lot of mental baggage. Some of us are fresh-out-of-school apprentices -- lacking the pragmatic experience of a seasoned pro. Some of us are old fogies with fond memories of FORTRAN COMMON (who strive to recapture the glory using the Singleton pattern (chuckle.)) Some of us have been programming in C++ so long that we forget how arcane some of the "obvious" idioms are.

Fortunately, unlike computer architectures, compilers, etc. the port can work both ways. The code can be adapted to the understanding of the new programmer, or the new programmer's understanding can be adapted to the code. In fact there is usually much more of the latter adaptation than the former, although I have certainly been involved in situations in which it was easier to rewrite the code than to attempt understand it.

Recognizing how often programmers must adapt to unfamiliar code, and vice versa, we should make an effort to write programmer-portable code. With that in mind, I propose the "five programmer test."

Given a language feature or coding idiom, create a sample of code using that technique.

Select five programmers with skills ranging from average to superstar (below average programmers should be dumped on someone else's project.) Ask each of them to explain in English what the code does and to describe any limitations, consequences, etc. that need to be considered when using the technique.

If all five of them agree, then it's ok to use the technique.

If at least three of the five agree (and one of them is the superstar) then it's ok to use the technique, but it requires a comment to clarify the usage.

If fewer than three programmers understand the technique, or if any programmer "understands" the technique, but her explanation of what it does is way off base -- find another way to achieve the same goal that does pass the five-programmer test.

Another Interview Question

Another good interview question is, "Once you fix all the syntax errors and get a clean compile, what type of errors are most likely to still be in your code?"

Wrong answer: "None." End of interview. Have a nice life.

Most common answer: "I don't know."

Followup question: "So how could you find out?"

When I first asked myself this question (shortly after reading Writing Solid Code) my solution was to create a "programmer's diary." This was a background program that I could pop up with a hot key. It opened up an edit window into which I could paste or type information. It date/time stamped the entry then appended it to a sequential file and disappeared.

To use it, I'd select/copy code containing an error, pop open the edit box and paste it, then annotate it to explain the error. I did not do any further analysis in-line. Instead I went back to whatever I was doing -- fixing the problem or running more tests or whatever...

After capturing data for about a month, I analyzed the file. I categorized the types of errors into classes like:

• uninitialized or improperly initialized variable;
  
• sense of a condition is backwards;
  
• failure to release resource when returning from a function;
  
• difficult to use, difficult to understand, or easy to break feature of the language (think "goto" although I'd already stopped using those.)
  

Then for each class of mistakes I asked myself:

• What can I change can I make to my coding style or work habits to prevent this type of error?
  
• What can I change can I make to detect this type of error sooner?
  
• What type of test would detect this type of error?
  

In some cases this resulted in changes in my coding style. For some cases I added new types of tests to my set of tools. In others, just the increased awareness of my error-of-choice was enough to help me avoid the error.

I continued to use the diary for a couple of months afterwards, and yes, there was a noticable reduction in the types of errors I had specifically targeted. Without benefit of statistical analysis, I also think there was a significant overall reduction in uncaught-by-the-compiler errors.

The downside of all of this is when I get into an argument (oops, I mean a reasoned discussion) about programming style issues I tend to be dogmatic about my style. That's because I think it's based on emperical evidence rather than aesthetics or arbitrary preferences. This would be a lot more valid if I had used the diary recently. My emperical evidence is from sometime before 1995 -- and of course it is specific to one programmer. Programming has advanced considerably since then -- in particular exceptions and patterns like RAII have changed the way I program. I wonder if it's time to fire up the old diary program.