Dale Wilson

Tardis

2009-01-28T11:37:00.000-08:00

Someday my Tardis is going to have been on backorder by now, but apparently some people have their's already.

I say this because I have a new netbook on order.

I was an early adopter on this one. It went on sale the 20th and I ordered that morning.

The original scheduled ship date was 1/27 (yesterday as I write this) but instead I got an email that said:

Dear WILSON DALE

Due to a delay in fulfilling your order # xxxxx placed on 1/20/2009, it may miss the estimated ship date that was on your original order confirmation. We sincerely apologize for this inconvenience.

However there are already five "customer reviews" of this computer out on the HP web site, so either these folks have their Tardis up and running or they are reviewing a computer that they haven't even seen yet.

For what it's worth: 3 of 5 (60%) customers recommend this product.

[Oh, alright, maybe they got advanced copies for review, or are basing their review on what they saw at CES, but I doubt it, and in either case that doesn't qualify as a "customer review" in my book.]

My Contra Dance

2008-08-10T13:00:00.000-07:00

I've been doing a lot of contra dancing recently, and have tried my hand at writing some dances. I've also been experimenting with Google Docs as a way to publish them.
For example:

Fly Around My Pretty Little Miss

Contra Dancing

2008-06-21T18:55:00.000-07:00

As I mention in my profile, I have a new obsession -- contra dancing with occasional forays into English Country Dancing. Obsessions come; obsessions go; sometimes they stick around. I'm hoping this one will stick. It s great fun, great exercise, and I've met some really wonderful people at dances.

Any good obsession should fit in with my previous obsessions. The connection to folk music and upright bass is obvious. Computers are a bit more of a stretch, but in my (ahem) spare time, I have started working on a program to help design dances and/or catalog existing dances. Then there's the weaving.

A contra dance is all about patterns fitting in a fairly constrained framework. Weaver's will feel right at home. The question is can there be cross-over. Could one weave a contra dance, or dance a weave structure. Hmmmm.....

If you're in the St. Louis area check the Childgrove site linked above, and come to a dance (usually Sunday night.) You'll be glad you did.

Oh, and the link to parrots? Well, Willow went to a flash dance recently. She was a big hit.

Artificial Inscrutability vs Human Pattern Recognition: A Challenge

2008-01-16T13:23:00.000-08:00

I was messing with the automatic language translation sites on the Internet. I started with the lyrics of a song, translated them from English to French to German, back to French, then back to English, and came up with:

The scandal is currently sufficient
May with the sun them on you
that supplements expensive you;
And the pure light with you
to lead your house in the kind.

Anyone recognize the original song?

Hints:

The song came from an album released in 1968 so there's an age bias in this challenge.
The album has been reissued on CD -- I was pleased.
I believe the lyrics were actually borrowed from a traditional folk song.
Somewhere along the line the translation acquired an extra line (and some extra concepts!) The original verse was four lines long.
The original lyrics were comprehensible, although I've got to admit you could probably substitute the translated version into the song and few people would notice.

Simplicity

2007-11-29T07:49:00.000-08:00

My previous rant was in response the frustration that built up while I was reading various standards documents and also using some ACE code [1]. In the interests of simplicity, however I should have just quoted Stephen Dewhurst from his book C++ Common Knowledge:

It's surprising how much of advanced object-oriented programming is basic common sense surrounded by impenetrable syntax.

Dale

[1] Pop quiz: An ACE_Map_Manager does not "manage" maps, it is a map. A map is a useful container for data. There are a couple of ways to describe the function it provides:

As a map: Given a key, map that into a corresponding value.
As a dictionary: Given a word, provide a definition.
As an associative array: Given an index of arbitrary type, return the associated value.

These points of view are equivalent (although the dictionary view implies that keys and values are text which is too restrictive). They describe useful ways to think about ACE_Map as a tool for solving a real programming problems. In each case there are two interesting values: The key (or word, or index), and the associated value (or definition).

In ACE, these are called int_id and ext_id (not necessarily in that order).

Question: Which one is the key and which one is the value?

Hint: int stands for internal (not the C++ data type int); and ext stands for external.

So int_id must be the data that is stored inside the map and ext_id is name the external world uses to get to that data.

No, now that I think of it int_id is the name used internally to identify the data and ext_id is the data that is of interest to the external world.

Hmmmm..

Answer: I have no idea. I have to look it up (in the code because the documentation doesn't help!) every time I use an ACE_Map or else find some existing code that uses it and copy/paste it into the code I am writing.

Extra Credit Question: ACE has been around well over ten years now and is used in thousands of applications. How many programmer-years have been wasted trying to remember which "id" is which?

'Tis a gift to be simple

2007-11-26T15:13:00.000-08:00

This used to be a long rambling blog entry in which I complained about the tendency of technical folks, to oversimplify complex problems, then add the complexity back in by using obscure terminology accessible only to the in-crowd.

The next entry, which in the topsy-turvy world of blogs is up ^^^ there, and which you've probably already read, quoted Stephen Dewherst who said it much more clearly and concisely.

So I rewrote this entry.

Hey if I can't change history in my own blog, where can I change it?

Getting better all the time

2007-11-14T13:29:00.000-08:00

As always this works better if you read the blog in reverse order -- going back to "An out-of-box experience." I've been recording the impressions of a brand new iMac user.

Several people recommended Quicksilver for my new Mac. I finally got it installed and running yesterday, and you know what? I don't miss the start menu any more! Quicksilver is truly the missing link in MacOS.

And, since the Logitech keyboard has a real, live delete key, I'm running out of things to complain about.

Let the record show that Spaces combined with Windows Remote Desktop Client (RDC) running in full screen mode makes working remotely on a windows machine a pleasure. Take some time to configure RDC, though, it's defaults are silly, and because I grabbed the beta version it's documentation is all stubs. Unfortunately most of the Fn keys are interpreted locally rather than being sent to the windows machine. Maybe I'll have to get the non-beta version just to read the doc. There--I found something to complain about anyway -- even if it was Microsoft software.

MacOS is exactly like Windows except everything is different.

2007-11-08T09:01:00.000-08:00

A couple of days of silence is good news.

The iMac up and running. I'm finding my way around. Just about everything I have tried so far is a lot harder on Mac then it would be on Windows, but of course that's because I'm try to do Windows stuff.

Dear Mac folks, keep that in mind when you say Windows is harder to use than Mac. If you try to do Mac stuff on Windows, well D'oh!

I haven't run into any more BSOF level issues, just a continuous, low-level state of frustration. Typical issues include:

Right click doesn't work to bring up menus. Of course, once I figured out that you had to actually turn the right click on in system preferences, it works. But for heavens sake, why have such a stupid default. Two buttons on the mouse that do exactly the same thing is silly -- unless of course you are a true believer that one button should be enough for anyone (and 640K RAM is good enough for anything you'd ever want to do on a personal computer, right?) [Note: a two hand/two finger click is *NOT* and acceptable substitute for a right click]

Speaking of two hands and two fingers, where's the @#$%^&* delete key! Please don't tell me I don't need it. I know I don't need it -- I want it 'cause it makes life MUCH easier.

I can't get back to my home page in Safari. I went through ALL the menus, looking for a "go to home" option. You can't do it through menus. You can't do it through a toobar button[*]. I can't find a keyboard shortcut to do it. For a while I simply used "open a new Safari window" but that's an unpleasant mini-hack. [*]Finally someone told me I needed to customize my toolbar to put the "go to home page" button on it. For heaven's sake, why have such a stupid default. Going "home" is such a common thing to want to do, why should I have to turn it on -- and why didn't Safari's help tell me how to do it!

I miss the Start menu. For all the flack it's taken over the years, the Start menu works really well. It caches recently used applications so it adapts to your normal usage patterns, yet for unusual situations the "All Programs" option lets you enter a nicely hierarchical organized list of the applications on this system.

Sure I could double click on the hard drive, then double click on applications to get to the equivalent of "All Programs", but Start menu is a lot more convenient -- it tends to "do-the-right-thing[TM]" automatically, and when it doesn't it listens politely when you explain things to it.

PS: I've started rolling my own start menu by putting a shortcut to the Application folder on the dock. For some reason it wouldn't let me put it where I wanted it -- with the other frequently used applications. Instead it insisted that it had to be over on the right side of the dock. I'm sure there's a lame excuse (er. I mean a perfectly valid and logical reason) for this restriction, but the motivation escapes me.

And there's more. You get the idea. Once I have adapted to the differences, I'm sure that MacOS will blend into the background and I can concentrate on doing the stuff that interests me rather than playing with the (admittedly pretty) operating system controls, just like I do on Windows where CTRL-ALT-= pops open the calculator; CTRL-ALT-T gets me notepad; CTRL-ALT-D opens a new DOS window, etc. [And don't tell me about the dashboard -- I know about it -- it's just like Windows except completely different (grin)]

Speaking of missing keys, and strange keyboards. The Logitech wireless keyboard & mouse came last night. O Frabjous Day, Calloo, Callay, I can type again! [Anyone wanna buy a Apple Wireless keyboard -- barely used.]

And to end on a positive note. I was able to read recordings I made with my digital recorder in and edit them with an open source audio editor then play them back on my "home theater" speakers with no grief. That's what I'm talking about when I mean the OS should disappear into the background and let me focus on the work I want to do.

How I spent the last 12 hours

2007-11-03T06:19:00.000-07:00

Read the previous two blog entries first.

Let's see --

Retrying the install didn't fix the problem.
Booting in single user mode and hiding my preferences didn't fix the problem (got that idea from the this article in the apple knowledge base)
Booting in single user mode and running dscl as described in this article didn't work at all -- the "launchctl" command failed -- never mind actually running dscl.
Various other attempts happened. I was starting to get seriously worried, or at least to think I'd have to bundle the thing back into the box and tote it over to the nearest Apple store for help.

<humor> One of the joys of Windows is how *many* times you get to install it on the same machine. Yet another feature Apple has copied from Microsoft</humor>

Finally I found this thread on the Leopard install discussion page that suggested using the "Archive and Install" w/o saving user settings during the upgrade. That worked (although I got to play twenty questions again)

It's up!

-------

And to respond to some of the comments to previous posts.

When I went into this my good friends who use Macs all told me -- you'll be up and running within minutes of opening the box. It's not like Windows. This is Macintosh!

I'm not really criticising them (or Apple). I'm just reporting what really happened and how it make me as a new Mac owner feel about the experience. That means I don't have to be "fair" If it pisses me off, it pisses me off even if there is a perfectly good excuse (er, I mean reason) for the problem.

In response to the comment "most mac users are waiting for the ".1" release." How Microsoftian of them! But seriously, if an experienced computer user who is trying hard to play it straight [except for the phone number thing] using a brand new, all-Apple, out-of-the-box machine encounters this troubles, how is good ol' Aunt Tilly gonna feel? If I had a lot invested in existing work on the machine, I might wait for .1, too. I'm still waiting on Vista --- although since I need to buy a copy of Windows to run on this machine under VMWare, I'll probably end up running Vista on THIS machine. Strange, but true.

Oh yeah, one of the "brags" of the Mac crowd is they don't stuff your machine with cripple-ware. Um--guys--there's a hobbled copy of Office on this machine! Admittedly its not as cluttered as a new Dell would be but...

Anyway, I have a new wireless-Mac keyboard on order from Logitech. It comes with a wireless mouse, too, which is good cause the mighty mouse, although functional, doesn't feel especially good when I use it.

In retrospect I should have taken the stock system from the Apple store, ordered a 2gig memory module and installed it myself (to get to 3G rather than the 2x1G I have now) and shopped for a wireless keyboard/mouse.

Now, let's have some fun!

Dale

Look, it's a Tiger; no, it's a Leopard; no, it's a paperweight, NO.....

2007-11-02T07:18:00.000-07:00

Blog entry #2 about my brand new iMac. See the previous entry for background:

Aha, I found where they told me they hadn't installed Leopard on my new iMac. All I had to do is find the Leopard CD -- break the shrink-wrap license announcement thereby revealing the news obscured by the seal that even though Leopard had shipped, they hadn't installed in my new machine so I get to do the upgrade myself.

Gee Apple, you know how to show a geek a good time. Now Aunt Tilly who bought the iMac cause she heard it was a good system for a novice, is not going to be quite so thrilled. (-0 for Apple 'cause I already dinged 'em for this)

Reminds me of an old joke about a college professor who walked into the classroom and wrote on the board, "CS 150 will be meeting here rather than in Foster Hall room 35."

Anyway, I followed instructions.

The first thing I found out was that the Leopard update couldn't find my wireless mouse and keyboard. I had to boot back into Tiger, start the boot process, then quick turn off the mouse and keyboard so I could turn them back on when prompted to.

---oookay----

[Here passeth two hours.]

Finally the upgrade completes and automatically reboots my system. Wow, look there's the Leopard star-field background. I'm almost getting excited. Oops. Can't find the mouse. Turn off the mouse; turn off the keyboard; turn off the computer; turn on the computer; turn on the mouse when prompted; turn on the keyboard when prompted. Aha. It's up and asking me for my password.

So I entered the password. The screen goes pale blue. It's not nearly as attractive as the BSOD, but it will do. Then the Leopard background reappears and look there's a password prompt. Er...

I repeated the cycle many times just to be sure that I was really trapped in a loop. I was even able to verify that I was entering the password correctly because when I intentionally got it wrong, the dialog box did this cute little shake (I could almost hear it saying tsk, tsk..) and didn't cycle through the BSOF (that's "Frustration" rather than "Death") -10 for Apple.

Of course I tried variations on the theme, but it always ended back at the BSOF cycle. A visit to apple's web site(via my windows machine) yielded a couple of ideas [Look the "insert link" worked in Firefox on Windows -- take *that* safari]

When last seen, I held the 'C' down while restarting. This booted from the CD which started the upgrade process all over. I waited until it estimated 2 hours and 15 minutes, then headed for work where I'm entering this blog entry from a Windows machine using Firefox.

If that doesn't work the next step is to boot into single user mode and try to fix things from the command prompt.

Is Aunt Tilly having fun, yet?

An out-of-box experience

2007-11-01T22:46:00.000-07:00

My iMac arrived today. The box says it's a 24 inch, widescreen computer. When did we start selling computers by the inch?

In fact, I'm typing this blog entry in using it. When I told my macophile friends at work that I'd finally succumed to the lure-of-Apple, one of them asked me to report my experieces as a long time user of many other systems.

It seems like a worthy blog topic.

To capture the essence of my very first exposure to Mac: Mixed bordering on unpleasant.

[Sorry macomaniacs, but it's true.]

Issues (so far).

The first shock was the keyboard. This is one's my own fault.

When I was shopping I looked at the iMac at the Apple store where, of course they had wired keyboards. I am rather opinionated about my keyboards -- I use my own Das Keyboard (I would make this a hot-link to http://www.daskeyboard.com/ but blogger doesn't recognize control-shift-a when I type it on the Apple keyboard -- strke n+1
) (Thanks to Peter and Avani for gifting me the Das Keyboard.)

Where was I. O yeah. I tried the new mac keyboard in the store -- it wasn't great, but it was acceptable. However, I didn't want to be tethered -- I wanted a wireless keyboard and mouse,

When I told the guy at the Apple store that I wanted the wireless keyboard and mouse, he said that made it a custom system so they couldn't sell it at the store. I'd have to order it thru the web site (which I did.) -1 Apple for an annoy-your-customers-when-they're-ready-to-buy policy

Silly me, I assumed the wireless keyboard would be just the Mac keyboard with the cord chopped off. Wrong. Not only did they chop the cord off, they also chopped of half the keyboard -- in particular the number pad and navigation keys disappeard leaing only a whimpy set of arrow keys tucked down in the corner. To be fair, if I use this keyboard for a while I may like having the arrows nestled under my right pinkie, but I'll still miss the num pad, home, pgUp, and friends.

-1 Apple for producing a brain-dead keyboard. -1 to me for not shopping better.

A word here about the enclosed documentation. I think Apple got this one right. There was enough information written in clear English with illustrations. Other languages were available, too. No making up your own iconographic language to achieve equal-opportunity miscommunication. +1 for Apple

So I turned it on. It figured out that there was no mouse attached and showed me a picture of the wireless mouse with a clear animation showing the mouse's power switch being turned on. I obeyed, and it synched-up nicely with the bluetooth mighty mouse. +1 for Apple

Likewise it automatically detected the keybaord. Another +1.

It found my wireless network and painlessly established the connection. A definate +3. In fact I'm on line now (obviously!) without answering any questions about the wireless network except which of the networks it found I wanted to use.

It asked for my Apple ID & password for the account I had to set up to place the order at the Apple store. It used that to retrieve my name, address, etc (a nice touch), and went so far as to propose a user ID for me on this machine based on my name -- letting me override it, of course, if I wished to. Ok that gets yet another +1.

Then it started playing 20 questions. In particular it want to know my phone number -- which I hadn't supplied to the Apple store and didn't want to supply now! I'm not that kind of guy -- I don't give out my phone number to just anyone! (I HATE HATE HAtE phone spam -- and no, I don't trust Apple.) It insisted! It would not let me use the computer unless I told it my phone number. You had to enter a phone number that conformed to US phone number conventions to proceed (ok--they already knew I lived in the US. I assume the validation was locale specific.)

Gee, I sure hope they don't try to call me at 911-555-5555 You meet interesting people that way.

-5 for Apple, +3 for me.

And then it wanted to take my picture. It didn't explain why, but it wouldn't proceed until I let it. Now I'm feeling testy. -5 Apple; -2 for me (I'm not looking my best in the middle of the night when I did this!)

Next it produce a list of software for which upgrades were available. After asking nicely for my permission it download the upgrades, installed them and asked me to let it reboot. +2 for this seamless process.

Finally, we made it thru that and I ran into the biggest shock. I waited for Leopard to come out before I bought the iMac, but after surviving the install process I discovered I was now running on Tiger. Grrrrrrr -10 for Apple

There's a Leopard CD in the box (no Tiget CD), but I thought by going directly to Apple to buy the machine I would bypass the need to upgrade immediately. -3 for Apple. Other than including the CD, there's nothing that lets me know that I should upgrade. If I was a typical novice computer user I might well run Tiger for a long time before discovering that THEY PUT ThE WRONG OS ON THE MACHINE. -3 for Apple.

So that's the story so far. I'm still on Tiger, but Safari is working (oops -- I just tried to spell check this document using the blogger built-in spell checker and ended up with a massive javascript error message. -1 for Apple The cool thing is the javascript error message contains a list of my misspelled words. +1 for me ;-)

(and where's the @#$%^&*( delete key!)

Dale

Obvious Icons

2007-08-07T07:51:00.000-07:00

There's a theory that an icon is more recognizable than a word. <humor> That explains why you have to have tool tips so you can hover the mouse over the icon to find out what it does</humor>.

How many programs let you hover over a word to generate a little picture of what the word means?[1]

What brought this to mind was 3.5" floppy disk icon that means "save this file" in a lot of windows programs. How long do you think it will be before new computer users have no idea what a 3.5" disk used to look like even though they know that a bluish square with a whitish rectangle on it means "save this file?"

It is said that icons are more locale-independent than English words. I think we're just inventing a new pictographic [2] language.

----------------
[1] ok, gmail shows you the person's picture when you hover over their name.
[2]The first time I posted this, I spell checked it and absentmindedly let it "correct" pictographic to photographic. I guess I should have just used an icon ;-)

If I wrote a mail client....

2007-07-02T08:42:00.000-07:00

If I wrote a email client, it would do a sanity check on dates before sending messages. I had the date time set wrong on my machine recently and sent a message out on July 18th (it's presently July 2nd) Now everyone who received that message is going to be annoyed by having it sort to the top (or bottom) of their inbox until July 18th actually rolls around (unless, of course they actually keep a clean inbox ;-) )

And while I'm at it, my mail client would scan the text for the words "attachment," "attached," "attaching," etc. If any of these appeared but there was no attachment, my client would prompt me: "Did you forget to attach a file?"

2007-06-29T08:30:00.000-07:00

OK, this brought back some memories:

http://www.wired.com/culture/art/news/2007/07/IBM1401_Musical

That's why there was an AM radio sitting on top of the CPU box on the 1401 at KU.

One could also play music on the chain printer. The chain spun at a constant speed and a hammer hit the character as it came by, so by modifying the sequence of characters to be printed....

Program Language Hamming Space

2007-06-13T15:18:00.000-07:00

A couple of computer language related events came together in the last few days to form a train of thought.

One was reading Justin's blog discussing strongly typed vs loosely typed variables with side trips into compiler-detected/assigned types for variables. Along the way Justin also discussed case sensitive languages (he's ag'in' 'em)

Another was a question Rich (who doesn't have a blog) asked me about a Python program.

The Python programmer, who obviously came from a C++ or Java background had was hoping for some function overloading. To paraphrase:


 class Widget:
     def tweak(filbert):
          print "tweak with one argument\n"

     def tweak(pecan, almond):
          print "tweak with two arguments\n"

It didn't work. That makes sense because Python is a duck typed language that gives you incredibly flexible argument passing support so you really can't overload functions based on signature.

What concerned Rich is that it not only didn't work, it also didn't generate a "compiler" error. Python just blithely and silently replaced the first definition of tweak with the second one.

My first response to Rich was to explain why Python worked the way it did. That's fine, but a better discussion might be how can Python be improved to allow this type of error to be detected while not eliminating the possibility of replacing an class's methods at runtime.

Of course you might think (with some merit) that replacing an class's methods at runtime is an evil, bad, nasty, cruel thing to do and should be forbidden altogether, but I disagree. There are occasions, in which it's the right thing to do. One example is my "Aspect Oriented Python" demonstration program that I include in my "Power Python" talk. It shouldn't be impossible to replace a method; it should just be a little bit harder than it was in Rich's example: maybe a "redef" keyword.

But this is not about Python (or VB). It's about a programming language's Hamming space.

Hamming space, and Hamming distance is a concept that helps design error detecting and correcting codes. The goal is to detect and/or correct mistakes as long as they aren't too bad. A typical encoding scheme can correct any single bit error and detect all double bit errors. Errors involving three or more bits lead to unpredictable results -- the encoded value just might be "corrected" into to the wrong value.

Now consider the difference between a valid and correct program and a program that is wrong. One could imagine a programming language in which any statement containing a single error could be corrected and any statement containing more than one error could be detected as being wrong. You might notice, however, that I'm not defining "error" here. In a case sensitive language, an error might consist of a single character of the wrong case (widget when I meant Widget) or we might consider "case mismatch" to be a single error no matter how many letters are involved (newwidget when I mean NewWidget). Or how about this error: int pi = 3.14159;

I'm not advocating error correcting languages (Justin is!). I'd just as soon correct my own mistakes, thank you, but I would like a language that could detect many more of my errors than today's languages do. One of the reasons I don't especially like perl is that it has a very low Hamming distance between syntactically valid programs. I can put a perl statement together in all sorts of strange and mysterious ways and perl kindly tries to make sense of it. That's OK as long as it guesses right. What really annoys me, however, is that *you* can put together a perl statement in strange ways and if I want to understand and/or maintain the program I have to out guess the compiler to figure out what's really going on.

But this is not about perl. It's about a programming language's Hamming space.

One measure of "goodness" for a programming language should be the "distance" between valid programs. Making a minor coding mistake should produce a compiler/interpreter error message. It should not produce a syntactically correct, but semantically flawed running program. The only way to achieve this is to have a larger Hamming distance between syntactically valid programs.

Alas, none of the programming languages commonly in use lives up to this standard.

At least it's job security for programmers.

I've been blog tagged: 5 things

2007-04-10T08:55:00.000-07:00

Weiqi Gao blog tagged me. That means he demanded that I post in my blog five things that most people don't know about me.

Five things you might not know about me.

1) Divorce

There has been a fairly long gap in this blog. That's because last October my wife Tina announced that she was moving out and she wanted a divorce. It's not final yet -- we're trying to negotiate a settlement before we get the lawyers involved. In the light of this, a lot of things -- like blogs -- seem less important.

Thanks Weiqi for breaking me out of the slump.

2) Diving

From the time I was 9, until I graduated from High School, I was a competitive springboard diver. Highlights of my diving career include, Ohio AAU Age Group state champion 12 & under, top twelve (meaning I made the finals, but didn't win) in the Southeast Regional AAU Age Group Championship when I was 15, and a three (out of a possible three) athletic letters at Wichita High School West.

I never won the Kansas high school state championship, though, because Tom Pettit who went to Wichita High School North could always beat me. His front 1 1/2 somersault with 2 twists had a degree of difficulty of 2.6 while my best dive, a front 1 somersault with 2 twists was only worth 2.3.

For several years I coached the diving team for my local subdivision pool. It was a wonderful experience for me and I got to watch some great kids grow into twenty somethings (so far.)

You learn a lot in diving beyond the physical skills. Probably the most important lesson for me was controlled risk taking (or courage if you want to think of it that way.) A lot of time when I was diving I was deeply scared -- I have a very good imagination and I could think of all sorts of ways to get hurt if things went wrong! I still remember watching a friend break most of his toes hitting the board. In fact I hit the board painfully several times myself. Nonetheless when you dive you learn to have confidence in your skills and perform in public in spite of the risks.

This doesn't mean all my risk taking was reasonable or controlled My extracurricular diving activities included cliff diving and bridge diving -- probably the less said about these the better. I didn't kill myself.

3) White Water Canoing

Speaking of risk taking. In my late twenties (before the kids were born) my wife and I got involved in whitewater canoing. Have you ever seen the movie Deliverance? It was filmed on the Chattahoochee river in Georgia. I've been down that river in an open canoe. No banjo's, though when I was there.

4) Music

And speaking of banjos...

A lot of my friends know I and trying to learn to play the guitar -- I'm not very good, yet. Not many people know that I have been playing harmonica and flute (all sorts) for many years. That's because I mostly play for my own enjoyment.

Sometimes I play harmonica in public -- blues, traditional folk, or improvization, but I haven't played recorder (wooden flute) in public since Jeff Dearinger made me join his recorder quartet back in Lawrence, KS. I played tenor in the quartet, but I also own an alto, and a soprano (like the ones they make unsuspecting elementary kids play.)

Most mornings I greet the day by playing something on my Native American Flute. I have never played it in public except one time last summer when I went down to Elephant Rocks State Park in southeast Missouri. I hid in the rocks and played for a while. I hope some passers by were mystified and entertained.

And recently I acquired a tin whistle -- possibly the most annoying instrument known to mankind when it's in the wrong hands. I like to think that my playing, though not great, yet, is not painful.

5) Road Trip

And finally, back in 1969 I was planning to go to a concert in with a bunch of friends. We didn't have tickets, but we'd heard that you could get in without them. Even if you couldn't get in there would be a great gathering outside the concert. Unfortunately I broke my glasses right before we left. Since I'm pretty useless without glasses (although I managed to dive blind for many years!) I stayed in Lawrence long enough to get a new pair. That's why I didn't make it to Woodstock.

The Software Crisis Solved (yet again)

2006-05-23T16:04:00.000-07:00

Thirty five years ago someone offered to pay me for writing a computer program. "What a great way to make a living," I thought.

When the program was working, I proudly showed the result to my customer. He had the sheer audaucity to check the results by hand. When the numbers didn't add up, I was, shall we say, chagrined.

Since that time I have written a lot more programs for money, but I've never forgotten the lesson learned on that first assignment. Writing programs that are not only "done" but are also demonstratably correct has been an important goal in my professional life.

Thus when I see the teaser "How to Prevent Software Disasters" on the front of the June 2006 "Scientific American," and an article "Dependable Software by Design" by Daniel Jackson, you can be sure it had my attention.

After the usual scare stories -- in this case the ones involving the Denver Airport, the IRS, the FBI, and the FAA -- along with cautionary scenarios of out-of-control computers running planes, trains, and automobiles, financial markets, and machine tools (the author forgot medical equipment, oh, never mind,that showed up in a sidebar a couple of pages later) the article got down to business.

My first warning that this was going to be yet another silver-bullet article came when I read, "Almost all grave software problems can be traced to conceptual mistakes made before programming started."

Um, excuse me, out here in the field it turns out that the overwhelming majority of mistakes have to do with the little fiddly bits, not the grand scheme of things. For every Denver Airport Baggage system that couldn't possibly work due to faulty analysis of the problem to be solved, there are hundreds or thousands of "little problems" like the Mars Observer missing the planet because someone used the wrong measurement system, or the software viruses that were able to cripple the internet because some programmer neglected to include a simple check for the length of an incoming message.

"Ok," I thought. "We'll ignore that one and move on. There's often a pony to be found in this type of article." And then I came to the statement: "The idea is to simulate every state that the software can take to determine that none leads to a failure." I must admit I broke out laughing at that point.

Consider the climate control system in my car. It's not very complicated, A rough estimate of the "possible states" for the heater and air conditioning controls on the dashboard is around 2000. The estimate is rough because the temperature control is analog so I'm estimating about ten possible settings. Factoring in the radio gets the number of possible states for the dashboard controls well into the millions, and we haven't even handled half of the dashboard. I daresay generating all possible states for my single automobile would take modern computers (all of them!) more time than has passed since the automobile was invented.

Yes, it turns out the author is aware of the state explosion problem, and he didn't really mean "simulate every state..." He really meant "use some heuristics to search for possible pathological states..." Apparently those states that are identified by the developer as being pathological (unreachable files in his example.) Once again, referring to my experience in "the real world" it's not the pathological cases that you can think up ahead of time that get you. It's the ones that come as a surprise. "Gosh, I never imagined that a trader would enter the price in the quantity field and vice versa. There goes the company."

Simulating a model is just another form of testing in which a negative result (we found a failure case) is important and significant, but a positive result (no problems found here!) can be used, along with $5.00 to buy a fancy cup of coffee at Starbucks. The authors are describing an automated testing tool that is driven from a model of the program behavior.

To make this system work, the author has invented a new language to describe the design of the program, Alloy. Presumably Alloy expresses the design at a higher more abstract level than the typical languages (Java, Ruby, C++, Python, ...) used by programmers, and therefore allows a higher level of validation (aka testing) to be applied to the design. The question not answered by the author is what relationship exists (if any) between the Alloy model of the program design and the actual program as executed by the computer?

Some possibilities include automatically generating the "low level" computer code from the high level model, automatically verifying the correspondence between the model and the actual implementation, or depending on the intellegence and understanding of the software analysts and developers involved in the project to be sure that the relationship holds as expected. Each of these possibilities has corresponding problems.

If the actual code is auto-generated what you have is an executable model. In fact you've invented a new programming language. Now rather than programming in Java, the software developers will be programming in Alloy. This is not necessarily a bad thing, but it means the Alloy modeling language needs to be rich enough to address all the issues that software developers must worry about when writing programs. And, just as mistakes are often made by programmers writing in Java or Python, mistakes will be made in Alloy. If it turns out that Alloy is a good language and can hide more of the complexity of programming that can traditional languages, then progammers will make fewer mistakes. However if Alloy is not seen as a programming language and analyzed as such, we'll never know how expressive and safe it is.

Suppose we try the approach of automatically verifying the equivalence between the Alloy model and the "real" program. Once again Alloy is a programming language, but this time it does not need to handle all the low level details. They can be addressed in the "actual" programming language (goodness, I hope the programmer gets the details right.) All that needs to happen is that the high level abstraction expressed in Alloy must be compared to the abstraction expressed in Java or Python. To put this another way, we need a tool that can examine a Java program and understand what it is supposed to do.

Making this comparison is an interesting, and quite difficult problem to solve. One wonders, we had a way to extract the higher level meaning of a program from the lower level C# or VB or Java source, why we can't just validate this representation of what the program means directly using the same techniques that are used to validate an Alloy program (er... model.)

This does, however, raise and interesting possibility. Rather than inventing a new higher level language in which to express the program, maybe it would be more productive to have two teams writing the same program and an automated comparison of the results of the two team's work. Surely it is easier to compare two C++ programs to each other than it is to compare a program written in an abstract modelling language to one written in a low level implementation language.

As an aside, let me mention the stiff resistance such a plan will encounter in the "real world" of managers and business people who already think that it takes too long to develop software so don't even think of using two people to do one job! I happen to know this because many developers would like to spend half their time writing code that tests to be sure the other half of our code behaves the way we expect it to. We call it "unit testing" and it's mighty difficult to get the funding to do it from some short sighted organizations.

The remaining approach for verifying the correspondence between the Alloy model and the actual code is to depend on the native intelligence and experience of the software developers. This is a good thing to the extent that it helps the developers involved analyze and understand the program at a higher level than the one at which they normally work. In fact I speculate that a great deal of the benefit claimed for Alloy comes because of just this effect. In order to create an Alloy model the developers must come to a deeper understanding of the basic design of the program, and in doing so, they end up creating a better system.

So, I congratulate the author on addressing a difficult topic and bringing some new ideas to the table (or at least some interesting new variants of the old ideas that have been around for a while) but I do wish he had done a better job of understanding the meaning of this work. I cringe when he suggests that "governments may even establish inspection and licensing regulations that enforce high-quality program construction techniques" implying that modeling the program in Alloy is such a good thing that it should be imposed by fiat.

Functional Programming Observation Continues...

2006-01-05T09:33:00.000-08:00

A follow-up to my previous post on functional programming in C++.
Compare


    size_t total = 0;
    for(size_t i = 0; i < elements_size(), ++i)
       total += elements_[i].bytes();


    size_t total = 0;
    std::for_each(elements_.begin(), elements_.end(), count_bytes(total));
    return total;

Neither one is "right."

What I want is to hide the details of iterating through a collection while revealing what is actually being done. In fact, I want to say:


   size_t total = 0;
   for (each element in elements_)
        total += element.bytes();

(Python anyone?)

The "for-loop" approach fails on the "hide the iteration" criteria [although I've been using for loops for so long that for(size_t i = 0; i < elements_size(), ++i) is a single conceptual chunk for me.]

The "for-each" approach also fails to hide the iteration {although familiarity with STL makes begin() ... end() into a single conceptual chunk, also.]

The "for_each" approach also hides what's actually being done -- it depends on a descriptive name (count_bytes is not bad) to provide a hint.

The "for-loop" approach shows the actual work (which is good, but clutters it up with a leftover detail from the indexing process ("elements_[i]" rather than simply "element")

I wonder if there's some way to convince the compiler to recognize:


 size_t total = 0;
 while(each(element, elements_))
        total += element.bytes();

for any arbitrary collection (elements_) of data type (element). This would of course require that the collection obey STL rules.

An observation concerning functional programming in C++

2005-12-29T14:47:00.000-08:00

The following code was extracted from a live program.


   namespace
   {
     class count_bytes
     {
     public:
       count_bytes(size_t& total)
         : total_(total)
       {
       }
       void operator()(
         const Element& element
         )
       {
         total_ += element.bytes();
       }
     private:
       size_t& total_;
     };
   }
   size_t
   ElementSet::bytes() const
   {
     size_t total = 0;
     std::for_each(elements_.begin(), elements_.end(), count_bytes(total));
     return total;
   }

By my count that's 26 lines of code. To be fair I should admit that I tightened it up a bit. The original was well over 30 lines.

Compare that to:


   size_t
   ElementSet::bytes() const
   {
     size_t total = 0;
     for(size_t i = 0; i < elements_.size; ++i)
     {
       total += elements_[i].bytes();
     }
     return total;
   }

Ten lines (And yes, you could use an iterator rather than an index.)

Functional Programming Motto: You may have to type a whole lot more, but at least your code will be harder to understand.

Actually functional programming is just fine when you need it. The problem happens when it's the "Wrong Tool For The Job[TM]." There seems to be a lot of that goin' 'round [sigh].

Thread return value/threadID/ handle/ join/detach vs C++

2005-12-10T14:24:00.000-08:00

Two entries ago, I opined that in a C++ program there should be an object that represents every thread. One interesting consequence of this statement is that many of the "features" of the OS-supplied multithreading support become unnecesary and even counterproductive.

For example, on almost all platforms, start_thread (by whatever name) calls a function with a void* argument. That's ok. Amost all thread functions begin life with a cast. However the thread function is expected to return a value: usually an int but maybe a DWORD or even a void * or whatever depending on your platform. In C++ the proper return value from this function should be 0 -- always! (Actually it should be void, but it seems a shame to disappoint the OS that's eagerly awating the zero. (And besides the compiler won't let me get away with it.))

Why?

Because if there is an object associated with the thread, the thread has a much richer channel through which to return information -- the members of the object.

And speaking of return values, many times no one cares what the thread has to say as it exits. [No death-bed epigrams for you, Thread, you're outta here. ] The joinable vs detached concept in many OSs accomodates this desire on the part of the thread to get the last word in.

However, since the thread now has a whole object available through which to return values, and since anyone who cares can keep a smart pointer to the object (remember the purpose of smart pointers is to manage object lifetimes.) the whole joinable vs. detached issue becomes moot.

Threads in C++ should ALWAYS run detached. Rather than joining a thread, you can wait on a condition in the thread's object (safely because you have a smart ptr to guarantee the condition will be around to be waited on.)

This approach might be much kinder to your system resources. Many OS's hang on to lots of information about a terminated thread -- possibly even it's entire stack, register safe storage, open FDs, etc. waiting for someone to join in and tell them the resources can be freed. Using an object can be a considerable savings.

Which brings up the issue of thread ID's If your interaction with the thread is via the object, you don't need a thread ID to join the thread -- and you certainly don't need a thread ID to kill the thread (see blog entry n-1) so the thread ID becomes much less valuable. It still has some value in identifying the thread in log messages (Ever tried to follow a log that didn't include thread ID's in a message? Me too, and I still regret it.) And the thread ID might also be involved in managing thread specific storage -- although many uses of TSS could be handled better by storing the data (or pointers thereto) in the thread's object.

Speaking of TSS. Think of it as FORTRAN COMMON for the thread-wielding-crowd. There's usually a better way, but sometimes the better way requires some thought <insert cynical comment here.>

Foot shooting

2005-12-10T14:08:00.000-08:00

In my previous post I criticized ACE for allowing the programmer to shoot himself in the foot. I was wrong. The problem is not that ACE allows you to do dangerous things. The problem is it doesn't provide enough incentive to convince a lot of programmers NOT to do the dangerous things.

If I work really hard I can imagine a situation in which the only way to save my life would be to shoot myself in the foot. Witness the hiker a couple of years ago who cut off his trapped arm so he could hike out of the wilderness with the rest of his body parts still functioning. That doesn't mean that everyone who ventures into the wilderness should pack an amputation kit just in case, or if the do, it should be in a package that is clearly labled: "For emergency use only." Once you open the package, you should find another package that says, "No, this is not an emergency, do it the right way." Only after opening THAT package should you find the Acme self-amputation, foot-targeting, and dangerous OS functions kit. [Pat. Pending]

So, if you want thread A to kill thread B, all you need to do is call the:
I_AM_A_BLINKING_IDIOT_FOR_USING_THIS::kill_thread() method.

Practical Threading

2005-12-05T23:14:00.000-08:00

A while ago, I started to talk about multithreaded programs in this blog. Alas, I distracted myself into talking about "Why Thread" -- an important topic and one that is often misunderstood-- when I should have been talking about "How to thread" because "How" is done badly even more often than "Why".

My recent work with multithreading has been with ACE and boost threads, so I'll use them as examples (no offense, guys.)

So, "How to thread in C++"

C++ is an object oriented language (or at least it can be used to write object oriented programs which is not quite the same thing but is close enough for now.) An object oriented should have an object representing/corresponding to each entity the program is dealing with.

A thread is an entity that needs to be dealt with by a multi-threaded program.

Rule #1: There should be a one-to-one relationship between threads and thread-related objects in a C++ program.

This does not mean an application programmer (a programmer who is dealing with objects that represent "real-world" entities) should be thinking about thread objects. On the contrary the thread objects should be hidden so well that they do their job without distracting the application programmer from the real work to be done.

"But wait!" you say, "isn't that a lot of overhead? Expecially," you add -- looking ahead in this entry -- "when you have to allocate the object on the heap."

"Don't be ridiculous." I calmly reply. "You're planning to start a thread with it's own stack, register storage, and who knows what resources tied up in the OS and you worried about a simple malloc!"

But I digress (so what else is new)

Where was I? Oh, yeah. "There should be a one-to-one relationship between threads an thread-related objects." But many thread-support libraries (ACE) don't always do this. Instead they have objects like a thread group that represents some number of threads. As soon as you do this, you lose control of individual threads and that's a problem.

I'm not saying that there shouldn't be objects like thread pools, just that a thread pool should never interact directly with an OS thread. Instead it should interact with the C++ object that represents the thread -- of which there will be as many as there are threads.

Oh, didn't I mention rule 2: All interaction with a thread should be through its object. I guess that seems obvious to me, but again it's often not obvious enough to the authors of thread libraries [ACE] that they actually do it that way (sigh). I guess they think the programmers would object to having a gun that wouldn't fire when pointed directly at your foot (or more vital parts of your anatomy.)

Ok, its time for rule three: The lifetime of the thread-related object must be longer than the lifetime of the thread. It should exist (however briefly) before the thread is started, and should continue to exist (however briefly) after the thread exits.

Again, this is something that many existing libraries (ACE, boost, et. al.) get wrong.

Oh, dear. We've entered the hazardous realm of object lifetime management [sometimes misrepresented as an issue of object ownership, but thinking in terms of ownership muddles the issue.]

Fortunately object lifetime management is an area in which the *SILVER* *BULLET* solution has emerged -- reference counted pointers! Unfortunately, C++ does not provide the tools to do reference counted pointers well, but it is possible to come close. boost::shared_ptr and ACE_Strong_Ptr are examples of refcount pointers done pretty darn good if not perfectly.
[ACE_Refcounted_Autoptr on the other hand is a disaster waiting to happen -- please don't use it (at least not in an airplane I might fly in!)]

So, we're going to use boost::shared_ptr to manage the lifetime of the ThreadRelatedObject. Cool!

class ThreadRelatedObject;
// alias TRO
typedef boost::shared_ptr ThreadRelatedObjectPtr;
// alias TROPtr

That leads to the next rule (4 I think): The TRO must be the one to start the thread (deftly satisfying half of rule three by guaranteeing that the TRO exists before the thread does.) The other half of rule three is handled by rule 5: The TRO must have its own, private, TROPtr so that it can be involved in its own lifetime management. We'll call this the self pointer. The last thing the thread does before exiting will be to reset it's self pointer -- allowing the TRO to be deleted if no one else remembers it. [So if you're thinking object ownership you might not understand why an object needs to own itself, but it seems perfectly reasonable to think that an object might want to manage its own lifetime.]

And then of course, there's rule 6: Any object outside the TRO that wishes to interact with the thread must do so via a TROPtr. Otherwise it can't guarantee that the TRO still exists.

A point of information: boost::shared_ptr to the same object must touch each other. I.e.
Widget * w = new Widget;
WidgetPtr p1(w);
WidgetPtr p2(w);
and you have a disaster because p1 didn't touch p2.
No one would code the above, but they might code:
WidgetPtr p3(new Widget);
which looks perfectly reasonable, and in fact is the preferred technique up 'till the point that the Widget does
class Widget
{
Widget()
:self_(this)
{
}
WidgetPtr self_;
};
Kaboom.

Anyway, it's time for a very-import-point-that-*everybody*-gets-wrong. Rule 7: The TRO must not -- repeat must not -- start the thread in the constructor. Why?
Suppose the constructor:
1) creates the self pointer
2) starts the thread
3) returns the self pointer to the creator of the TRO (oops, see above!)

Nevermind that point 3 doesn't work because the constructor can't return anything other than this which is not a ThisPtr -- that's just a deficiency in the C+++ language, and there are ways[hack] around that problem -- like private constructors with static create() methods [hack] and my favorite: passing to the constructor a reference to a TROPtr which the constructor initializes[hack].

The real reason for rule 7 shows up somewhere between step 2 and step 3 of the constructor when the thread started by step 2, does what needs to be done, and exits(!) before step 3 is executed. The static create method can't handle this. The pass-a-ref-to-ptr-to-the-constructor hack mentioned above, can cope if done very carefully (a very careful hack, eh?) but it gets ugly --especially when layers of inheritance happen. Actually its kind of fun to get it wrong, then watch one of your coworkers try to figure out why the pointer returned from new points to an object that's already been deleted -- but only if you have a coworker who deserves it . To bad at this job I don't have any candidates.

Why do ugly when there is a simple solution.

Rule 7a: There should be a start method on the TRO that actually starts the thread.

One of the fun things about programming that when you find the right solution, stuff works! Separating object construction from thread initiation is one of those right solutions. The calling object gets the luxury continuing to initialize the TRO after creating it and before starting it. Some things are best not done in a constructor.

Separating construction from thread initiation also make it considerably easier to create a generic base class for handling thread related issues. The ugly create and or pass-a-pointer hacks aren't necessary (go ahead, try to figure out how to do a static create method in a base class). This means that we can get the solution right once and never worry about it again.

So that's what I did.

My solution that's actually being used is based on ACE thread support (ACE does provide good platform independent thread support [as long as you don't use Thread Specific Storage (grin) I just don't like the way its packaged.) Unfortunatly ACE tends to be a bit intrusive -- it's a shame to take on all that baggage just to get a few platform-neutral thread-related functions.

That's why I went looking at boost threads. Most of boost is truly high-class work. Boost threads, alas, is not. Although it passes the "use conditions rather than events" test [an altogether different topic.], it fails the object-lifetime management test.

So I guess I won't be publishing my "universal thread support the right way" base class quite yet. Maybe I'll just publish the ACE-based version and someone will point me to a platform independent thread library that separates object construction from thread initiation and supports condition rather then event, and does not come with tons of baggage.

Just remember, the multicores are coming. Do you know what your threads are doing?

Strangelove

2005-10-20T08:30:00.000-07:00

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

2005-10-13T13:52:00.000-07:00

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

2005-08-29T07:10:00.000-07:00

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

2005-08-26T13:13:00.000-07:00

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

2005-08-19T15:34:00.000-07:00

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.

2005-06-21T13:52:00.000-07:00

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

2005-05-19T08:24:00.000-07:00

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

2005-05-19T07:42:00.000-07:00

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

2005-05-16T14:20:00.000-07:00

Pauli Exclusion Principle

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

Oops. My mistake...

2005-04-27T07:40:00.000-07:00

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

2005-04-21T07:55:00.000-07:00

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

2005-04-19T15:00:00.000-07:00

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:

Accept and demux input
Queue packets for decoder(s)[MT]
Separate into VOBs
Hold VOBs for processing[MT]
Decode VOB
Hold decoded VOBs for reordering[MT]
Reorder decoded VOBs into decode stream
Queue decoded streams for mixer.[MT]
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?

2005-04-18T11:53:00.000-07:00

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:

The task is inherently multithreaded so a multithreaded solution results in simpler code; or
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

2005-04-15T07:23:00.000-07:00

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

2005-04-14T12:05:00.000-07:00

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

2005-04-06T10:28:00.000-07:00

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

2005-04-05T09:22:00.000-07:00

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

2005-03-31T14:31:00.000-08:00

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

2005-03-22T07:45:00.000-08:00

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

2005-03-15T08:55:00.000-08:00

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.

This one's for Jonathan

2005-03-12T18:17:00.000-08:00

In the lobby where visitors sign in at Google, there's a Naked Juice vending machine.

The Computer History Museum

2005-03-12T10:49:00.000-08:00

We visited the Computer History Museum yesterday. Lots of interesting artifacts including an Enigma machine, a Cray 1, etc. The item that captured my attention, though, was a white teapot. In fact, THE white teapot. If you've seen the test images from any 3D graphics program, you already know what the teapot looks like. And it does.

Do you know the way to San Jose?

2005-03-10T06:09:00.000-08:00

Do airplane trips ever just work? I mean have you ever gotten to the airport on time, sailed through security, found a comfortable seat next to a pleasant companion, arrived at your destination feeling refreshed and rested, and had your luggage make it, too?

Well...

Tina and I just flew to San Jose to visit Peter, and the perfect plane trip didn't happen (one more time.)

Let’s see,

My computer fell out of the back of Dave's van as he dropped us off at the airport (nothing damaged, apparently.)
When we checked our bags, they took my picture ID and wandered off with it. When I asked what was going on, they told me my name was on a "watch list." This must be the same evil Dale Wilson who is behind on his alimony payments and stiffed an eye-care place somewhere in Illinois. Kind of spooky knowing I have an evil twin.
Next was Tina's turn with security. "Is this your bag, ma'am?" said the TSA guy. "Yes," replied Tina. "I'm going to have to ask you to open it up." By then I was through security myself, so I didn't hear the details, but after I stood around for quite a while, Tina finally made it through. Apparently they confiscated a vicious looking nail file and were deeply suspicious about the dangerous drugs that were Not In Their Original Ibuprofen Bottles!
So the plane was a little bit late taking off.
And we landed in Tulsa. Most of the passengers go off, but those of us who were heading on to Phoenix on the same flight rearranged ourselves and got comfortable for the next leg. One of the stewardesses stopped by to admire my beard. She said her husband also had a long beard, and was giving Tina some really unfortunate suggestions involving braids and tiny lights, when the PA system announced we all had to get off the plane and go to another gate. There was vague mention of a "maintenance issue."

When we got to the new gate, there was an enormous crowd. Much more than a planeful. It seems that they were putting us on a plane that was supposed to go to Dallas. Since the plane was going to Phoenix instead, now, the Dallas people were being sent to yet-another-gate where presumably they would eventually be put on their own replacement plane to replace the one we had just borrowed from them.

This being Southwest, we were given new boarding passes that let us board first -- even before "families traveling with small children." If you want to get on a Southwest airplane first, get yourself a mauve boarding pass (honest they called it mauve!)
So that got us on the plane in Tulsa. We were 45 minutes late, but we were on our way. Nothing much went wrong during the flight to Phoenix (unless you count peanuts, but they're normal for a Southwest flight.) As we made our final approach into Phoenix they announced that Southwest was holding all connecting flights, and would anyone going to San Jose go directly to gate C2. Of course, our plane docked at the far end of the D concourse, but it coulda been worse. We hiked on over to C2 in time to walk right onto the plane shortly before they closed the doors. Things were looking up -- this plane was half empty so we had no problems finding seats.
Oops. Spoke too soon. As we arranged ourselves I realized that I had left the book I was reading on the other plane. "Do you think they'll let me go back and get it?" I asked Tina. Right.
So on to San Jose. We made up the time somehow and actually got to San Jose on time! The only unfortunate part of this leg was when the stewardess decided to sing as we taxied in to the airport. I guess it was endearing. A personal touch sort of like the early episodes of American Idol. "A bit pitchy," said Randy, "but not too bad." "I don't think this was a good song selection for you," said Paula, "but you've got a, um, loud voice." "I've heard better performances from the taxi driver that brought us to the hotel." said Simon.
Home free, eh? Our baggage made it! Calloo, Callay!
Then we got to Peter's car, and I said -- where's my computer? The brief case containing my computer--which I had carried on, so I couldn't blame the airline--wasn't there! In near panic I headed back to the baggage claim area. Fortunately it was sitting on a chair waiting for me. Airport security hadn't confiscated it as an unaccompanied bag -- probably because there was a woman there watching it. She said she saw us leave it and couldn't figure out what to do, so
she was waiting a bit to see if we came back before calling security. Thank you, thank you, thank you.

Guidance toward the-one-true-path.

2005-03-08T07:17:00.000-08:00

Paul Colton wrote an interesting article for Byte about XAML. Once sentence in the article was a real attention grabber:

XAML has many strengths, and Microsoft's ability to educate the marketplace and guide the .NET developer community may ultimately tip the balance to XAML.

Wow. I'm *SO* glad Microsoft is willing and able to educate and guide me. ;->

Thoughts Meandering From Interview Questions to Semantic Compilers.

2005-03-07T14:51:00.000-08:00

I used to do a lot of interviews for programming positions. One of my favorite interview questions is:

What's the best book about programming you've ever read? What book should every programmer read?

(I know, that's two questions --- but hey, it's my interview (and my blog) so I make up the rules.)

There is no "right" aswer to this question, but there are a couple of wrong ones.

The worst answer is "I haven't read any programming books recently." The applicant can recover from this if she goes on to explain that she reads programming blogs, and magazines instead because the informaion is more current, but barring such a last-minute save, a negative answer is an interview stopper.

The next worst answer is a textbook required by a college course. If the interviewee is more than a couple of months out of college and hasn't learned anything since, well....

Responding with something like "How to write [fill-in-the specific-application] programs in [fill in the language] on [fill in the platform]" earns a barely passing grade. The interviewee is on the bubble and better come up with a reason why I should keep talking to them really quickly!

Oh yeah, and any book containing "for dummies" in the title is instant death <chuckle/>.

So, how would I respond to the question?

I might mention some recent read (ala "The Pragmatic Programmer.") or I might fall back on one of the very few books that have a profound impact on the way I program.

Looking back, there have been a lot of programming books, but very few that were life-changing. "Elements of Programming Style" counts (yes, that was a long time ago, but it's still worth reading.) Most programmers know about "Elements.." and it is actually used as a textbook in some college courses (which contradicts the "second-worst" judging criterion above. hmmm.)

Another book that had a major impact was "Writing Solid Code" by Steve Maguire. I'm not sure whether this was that good a book, or whether it just happened to be the right book at the right time for me. I should probably re-read it if I could find my copy.

One concept I acquired from "Writing Solid Code" is the idea of a compiler that checks semantics rather than (or in addition to) syntax. Wouldn't it be great if the compiler would tell you: "Yes, that's legal C++, but it's really not what you should have written." Actually, over time, compilers have gotten better at producing this type of warning messages. By flaging unused variables, statements with no effect, and such atrocities as:

if (a = b)

modern compilers bring your attention to possible semantic problems. This is a good thing.

But wouldn't it be nice if compilers could go further? If they could warn not only about obvious nonsense, but also questionable practices, bad algorithms, etc. we could write better programs faster.

One problem of course, is my "really cool technique" is your semantic abomination, and vice versa. In recent discussions here at work we haven't been able to agree on where the & should go in:

int & a;

Some say goes with a because you can say "int &a, b, *c;" to which I say -- not in MY semantic compiler you can't! Some say it goes with the int because it's "part of the type" to which I say, but how about const and static. Aren't they part of the type.

In case you haven't noticed, I think that & and * are first-class citizens and deserve to stand on their own rather than being piggybacked on another token -- but that's just my opinion and it is certainly subject to debate. It's also completely beside the point of this discussion.

Lack of agreement about what constitutes a good program makes it very difficult -- nay impossible -- to come up with a one-size-fits-all semantic compiler. So how about a compiler that "learns" your programming style, and flags departures? If you always indent by two, but happen to indent by four in one place -- well maybe that indicates the code is wrong. Better yet, if you always use braces (as you should (chuckle)) then an if statement with no braces should be flagged as an "error."

Hmmm. How well does this play on a team programming project?

Of course these are all "small scale" issues. The real benefit comes when the compiler can detect, for example, that you're doing a linear search of a (large enough) sorted list and suggest that a binary search would be a good idea here, or can look at an object full of get and set methods and advise you that you've really blown the encapsulization and should be writing domain-meaningful methods instead.

STL does makes some interesting strides in that area by declining to implement "unwise" methods on some containers. Java was also a step in this direction -- unfortunately a lot of the decisions that went into Java were one man's opinion so some valuable techinques were "tossed out with the bathwater." and some warts like uninitialized references made it into the language.

There's much more to be said on this topic, but this entry is getting too long. To be revisited...

The kind of person that keeps a parrot.

2005-03-04T13:20:00.000-08:00

Tina was looking at my blog and pointed out that not everyone was familar with the Mark Twain quote. Although anyone who reads parrot mailing lists surely knows it, for the rest of you, click here.

Pet Peeve n+1: Thinking outside the box

2005-03-04T12:39:00.000-08:00

The phrase "Think outside the box" ranks right up there with "Have a nice day :-)." and just barely below fingernails scraping on blackboard.

Most people use the phrase to mean "ignore the rules."

Trucker #1: Why are you stopping?
Trucker #2: Look at the sign on that overpass.
Trucker #1: Yeah, it says "Clearance 11 ft. 6 in." So what?
Trucker #2: The trailer we're pulling is 12 feet tall.
Trucker#1: (looks around) I don't see any cops. Let's go for it.

See. Trucker#1 is thinking outside the box the way most people use the phrase.

The origin of the phrase is a classic logic puzzle. Given nine points arranged in a 3x3 grid:


  X  X  X
  X  X  X
  X  X  X

Draw a continuous series of four line segments that passes through each point exactly once.

The solution (which you know, right? (if not, there's a hint below)) involves extending the lines beyond the "borders" of the array. Hence, "Thinking outside the box."

You don't solve this puzzle by thinking "outside" the box. You solve it by realizing that there is no box outside of which to think! [Look again, do you see any box?]

Understanding the true constraints on a problem and finding creative solutions within those constraints -- good. Ignoring the constraints that happen to be inconvenient -- bad.

All of which applies to programming, too!

Hint:


  X  X  X  x
  X  X  X
  X  X  X
  x

The Sins of Intel

2005-03-02T14:56:00.000-08:00

Another entry in my Hack series. This one's a threefer:

A lot of people complain about the Intel architecture. It must have been really easy for hardware designers to build systems around the early Intel chips, 'cause you'd never find a software developer praising their design. Early Intel chips (and some not-so-early chips) were much harder to program than they needed to be.

Sin #1: A + (-B) != A - B
One of my favorite Intel sins, is that the engineer(s) who designed the early chips did not understand binary arithmetic! The way the chip was designed 5 + (-1) [that's five plus negative 1] did not produce the same answer as 5 - 1 [five minus one]! That one deserves an extra exclamation mark!

To explain:
On a four bit machine 5 + (-1) looks like:


  0101
  1111
1 0100

That 1 hanging out there is a carry bit. It is normal for a subtraction to generate a carry (it means you did NOT have to borrow!)

Unfortunately on Intel the flag that ends up holding that 1 is called the carry/borrow flag. If you add, it holds the carry. If you subtract it holds the borrow.

That means 5 + (-1) is four with a carry, whereas 5 - 1 is four without a borrow, but borrow and carry are stored in the same flag, so to do-the-right-thing with the carry bit you have to know how you got here.

The result is a lot of really sweet binary arithmetic techniques were just a little bit harder and messier (and hence a little bit less sweet) on the Intel machines.

Sin #2: Segment granularity

When Intel discovered they needed to go beyond the 16 bit address space of their early processors they added segment registers. This was a good move because it preserved compatibility with older software -- or at least made it relatively easy to migrate to the new processors.

The sin comes when you considered how the segment registers were factored into the address calculations. The segment registers have 16 bits -- making them easy to manipulate on a machine that's built around a 16 bit architecture, but in order to achieve the goal of extending the address space, the segment registers have to address units of memory larger than a single byte. Intel choose a 16 byte addressable chunk for the segment registers. That means the segment register is shifted four bits to the left when it takes part in the addressing calculations. The result is the 20 bit (one megabyte) address space that hampered the Intel processors for years! (Of course IBM and Microsoft managed to hack that into the 640K limit, but that's a different transgression.)

Suppose Intel had shifted the segment register by 8 bits rather than 4 bits. Downside is a granularity of 256 bytes rather than 16 bytes (big deal--not)

Upsides:

First of all, calculating the values to go into segment registers would have been much easier because it's a lot easier to move things by 8 bits than by four bits on an Intel chip, but thats only a minor advantage compared to the real plus which is that the address space just became 24 bits (16 megabytes rather than 1 megabyte) Admittedly 16 megabytes seems small today, but it took almost 10 years before we achieved that state. Countless man-centuries (yes and woman-centuries) were poured down the bottomless pit of extended memory and expanded memory hacks trying to compensate for Intel's short sightness.

Sin #3: The 80286
Ok so they forgot to figure out how to get from user mode back to kernel mode (D'oh) This inspired the truly byzantine technique of booting the whole damn machine to do a context switch back to the OS. Kool, eh!

Stealth wins

2005-02-28T07:54:00.000-08:00

I finished weaving the "stealth scarf" (see previous dissussion) this weekend and just as I suspected the pattern is pretty much invisible. If you hold it at just the right angle in just the right light you can see it, but that's not what I was hoping for.

For my next bright idea.....

The AAM hack

2005-02-23T06:58:00.000-08:00

Backgound
I was working on a graphics editor for the Zenith Z100 computer. This was a shrink-wrap product intended to be distributed by the thousands (well millions actually but Zenith didn't sell enough Z100's (sigh))

The Z100 had 640 x 225 x 8 color graphics capability (or 640 x 450 if you used an undocumented video mode) (Compare and contrast to CGA.) The Z100's graphics were memory mapped, but the layout of the memory was somewhat arcane. Converting a (X,Y) pixel address to a byte and bit address involved some calculations including a divide by 9

The problem
In a word: speed. One of my test patterns took 40 seconds to render to the screen. This is painfully slow -- probably slow enough to kill the project.
Profiling the C program showed that writing pixels to the screen dominated performance of the program. Profiling the pixel writing code showed that the divide by nine was dog-slow. This was on an Intel 8086 processor (an 8 bit processor with delusions of 16 bitness)

The Hacker
Dale (that would be me) Wilson

The Hack
I can't claim exclusivity for this hack. Other people found it and later it became pretty common, but I can claim that I found it myself.

The DIV instruction on the early Intel processors was a real cycle burner. Not only that, but it took a lot of setup and tied up a lot of registers on a machine that is extremely register-poor. It had to go. The good news is that the DIV instruction was a 32bit/16bit divide which is way more than necessary for this problem. In fact an 8 bit/4 bit divide would be sufficient.

My first approach to solving the problem was to implement Divide-By-Nine as a series of shifts and subtracts. Since the divisor was hard-wired the division could be done in straight line code. No branches, no testing the carry bit (oops, this is Intel, I mean the borrow bit). The result was about ten times faster than the DIV based code. The test pattern now showed up in four seconds vs the original 40 seconds. Good, but four seconds is still a bit sluggish.

Studying the Intel instruction set revealed all sorts of oddities. One interesting one was the AAM gap. The AAM instruction itself was a somewhat dorky instruction intended to be used as one step in multiplying BCD numbers. The acronym stands for Arithmetic Adjust after Multiply. Once you get past the noise about BCD multiplies (who multiplies BCD numbers? Maybe COBOL programmers (grin)) and look at what it actually does to the bits, you discover that it's really a divide instruction. It divides the AL register by ten and puts the quotient in AH and the remainder in AL.

The opcode for AAM is D4 0A. But looking at the Intel instruction set docs reveals that AAM is the only instruction with D4 as the first byte. That seems wasteful. And it is interesting that the second byte happens to be an "A" (i.e. a ten) A little experimenting (can you say self-modifying code (with a straight face?)) reveals that AAM is really a 8 bit "divide immediate" instruction. If you put a 09 in the second byte it divides by 9. If you put a '0' there, you get a divide-by-zero fault!

Back to the write-the-pixel fast algorithm. Out comes the shift-and-subtract sequence. In goes a AAM9 and voila, the render time is significantly under a second. Life is good. Ship the product. Everyone sees what a marvelous machine the Z100 is; Zenith rules; and we all become rich-n-famous (oops--except for that last sentence (sigh.))

Ok, judges. What's the score for this one on the sleazy(0) to righteous(10) scale?

Extenuating circumstances

I left one point of information out of the discussion above. I left the shift and subtract code in the program. At startup the program tested to be sure AAM9 did the right thing. If the test failed, it fell back to shift and divide.

My Rating
Since this is my own hack it's hard for me to be objective but without the startup check, I'll give it about a 3. Using undocumented features of the processor in commercial software is bad news. With the check, however, I'd go as high as a 6. After all is success in the market requires speed and this is the only way to get the speed...

As it turns out, however, this wasn't the only way to get the speed. In a later version of the program I switched from thinking about the screen as a collection of pixels to thinking about it as a collection of horizontal lines (some of which were very short.) This gained almost as much of a speed increase as the switch from shift-subtract to AAM9, and it didn't involve any undocumented ops.

And one last point.
You may wonder why I didn't use the "normal" technique of rendering into an off-screen buffer then blitting to the actual video buffer. Good question, and the answer comes back to available memory. Zenith sold Z100's with as little as 128K bytes of RAM for programs + operating system. (The video buffer was separate.). A screen buffer takes 54K which means there just wasn't enough RAM available to do an off-screen buffer right.

The FNO Hack

2005-02-21T11:32:00.000-08:00

Background
Like the previous hack, this took place on a Honeywell 6000 computer running GCOS. We had an application that used a random access file for persistence in a high traffic environment (~50 allocations/second for sustained periods of time.)

To understand the hack you need to understand how floating point math was implemented on the Honeywell 6000 machine.

The H6000 worked with floating point numbers in the EAQ register where E is an eight bit exponent register and AQ is a double-word (72 bit) general purpose register used as a mantissa in this case. Floating point operations did not always produce normalized results, so a special instruction, FNO, normalized the current contents of the EAQ register.

Floating point normalization
Consider Avogadro's number = 6.022 × 10**23. Another way to express this is 0.602 x 10**24. The first version is normalized (base 10). The second is not. Notice the loss of precision. Binary normalization works the same way. To normalize a number you shift it left to get rid of leading zeroes and adjust the exponent appropriately.

The problem
The challenge was to control the allocation of blocks in the random file. Remember memory is tight, so a free list is not a good solution. Instead we used an allocation table with each bit corresponding to a block in the file.

How can you find an available block as fast as possible.

The hacker Bob ("If you need comments to understand my code, you shouldn't be reading it!") Miller

The hack
An important decision was to represent available blocks as one bits and used blocks as zero bits. This allowed testing 72 bits at a time when looking for an available block by loading the AQ register and branching if the result was non-zero. Thus the the algorithm was:


     loop:
         load AQ tablepointer (auto incremented by 2 words)
         jump if zero to loop
and now the hack:
         load the E register with zero
         FNO   (floating point normalize)
         copy the E register to a general purpose register.  
         Add 36 * the word offset in the allocation table

to get the available block number.

Rate this hack from 0 (slimey) to 10 (righteous).

Important factors in my rating of this hack are:

Although it uses an instruction for "the wrong purpose" if you read the description of the instruction in terms of how it maniuplates bits it does all the right things. In other words as long as Honewell doesn't decide to change how they represent floating point the hack should continue to work.

This is a high use function that has a direct and visible impact on performance.

Rating
I give it a 9 out of ten (If Bob had believed in comments it might actually be a 10).

The IOCW hack

2005-02-18T05:35:00.000-08:00

Setting the scene

The time is the early 1970's. The computer, a Honeywell 6000 running the GCOS operating system. Some characteristics of this system:

Addressing space was 18 bits, but fortunately the addressable unit was a four byte word so addressable space was one megabyte (where a byte has nine bits, but that's irrelevant). The OS had virtual memory but individual processes were still limited to the 1M space.

The system had a separate I/O processor (known as the IOC) that handled all input and output. The IOC was progammable using a very limited instruction set (I/O control words (IOCW)). To perform I/O you created one of these programs in your memory and asked the IOC to execute it. You could do scatter/gather I/O using IOCWs. You could also branch (but not conditionally) from one set of IOCWs to another.

When an application requested I/O the OS validated the IOCW's then started the I/O. The OS handled interrupts and status coming back from the IOC, then passed the results (and a limited form of interrupts) back to the application.

The Problem

Memory is at a premium, and dynamic memory allocation is tough in assembly language. Where do you put the IOCW's?

The Hacker
Jim Mettes (who happened to be my boss at the time.)

The Hack
Put an IOCW directly in the read buffer. The IOC fetches the instruction from the buffer first, then reads the data into the buffer -- overwriting the IOCW which is no longer needed. Four bytes (the size of an IOCW) saved!

At this point you should decide for yourself where this hack rates on the slimey to righteous scale. Zero is ultra-slime and 10 is mega-righteous.

The rest of the story.

Consider what happens when a recoverable I/O error happens. The IOC reports the error. The OS determines that it is retryable and asks that age-old question: "Abort, Retry, or Ignore?" In this case the question goes to the console operator, not the person running the program. "Retry" says the console operator because that's what his proceedure manual says to answer.

The OS tells the IOC to try again. The IOC refetches the IOCW -- but it's been overwritten by the data from the previous attempt. Remeber the point about the OS validating the IOCWs before issuing the I/O request? Guess what the designers of the OS forgot to do during the retry? If you were lucky you ended up with a core dump of your application. If you weren't quite so lucky the system administrators ended up with a core dump of the whole machine and came looking for your head!

The Score

I give it a 1. High danger, low payoff. And how do you tell your boss about it?

Thought #2 for the day

2005-02-16T12:44:00.000-08:00

Some code idioms are inherently bug-prone. High on my list of offenders:


    abc()->widget();

abc() presumably returns a pointer to an object that has a widget method. But what if it doesn't have a pointer available?

Programmer: Doctor, it hurts when I do this.
Doctor: So don't do that!

now if abc returned a reference rather than a pointer....

Dale

Fragile programming

2005-02-16T05:43:00.000-08:00

There was a time when I practiced defensive programming. The theory was that code should be able to handle anything thrown at it.

What a bad idea!

If you're writing a square root function and someone hands you a negative number, DON"T fix it for them. Abort, throw an exception, trigger an assert, whatever! Just be sure that they know as soon as possible that they've done you wrong. (A compile-time error would be ideal.)

This rant was triggered by code throughout ACE and TAO that looks like:


if (do_some_function () != 0)
 return -1; // this should not happen

(Yes, the comments are really there in the code.)

Adding an ACE_ASSERT (and the missing brackets which should have been there in the first place) to one instance of this "idiom" revealed a longstanding design error in ACE's handling of Thread Specific Storage.

I'd rather work with fragile code than helpful code!

Just to be thorough, the code should be:

if (do_some_function () != 0)
{
 ACE_ASSERT(false);
 return -1;
}

not:

ACE_ASSERT (do_some_function () == 0);

Relativity values

2005-02-15T06:30:00.000-08:00

In thinking about historical hacks I realized I needed to set the scene to make some of them understandable.

This started me thinking about the computing world and culture then vs. now. Everybody knows about the dramatic drop in price of electronics, but I'm not sure everyone has a gut feeling for the magnitude of the change. In fact, I often forget, and I lived thru it.

So: thought for today.

When I started working as a programmer, if I saved my entire salary (no food, no clothing, etc.) I could buy the computer I worked on in only 333 years.

Today I could buy a much more powerful machine every other day!

That helps to explain why we were willing to invest months and sometimes years of programmer time for relatively small gains in computer time. Thereby motivating hacks...

The Hack Spectrum

2005-02-11T08:32:00.000-08:00

Near the end of an otherwise excellent presentation on the boost shared pointers(boost::shared_ptr), Jonathan showed a slide with the title "Tricks." On this slide it explained how to create a smart pointer to a stack based or static object. This immediately raised by "hack"les.

Pointing a smart pointer at an auto variable violates the semantics of the pointer. The fact that it is syntacticly correct is not an excuse. In fact I consider this a defect in the design of the smart pointer -- a well designed smart pointer would not allow such nonsense. [Note what constitutes a well design smart pointer [IMO] is another topic that I might get into later...]

Jonathan defended the trick by saying "as long as you know what you are doing, it's ok." Alas, that's not correct. A more accurate statement would be: "As long as you and every programer who touches the system either before or after you is aware of all of the implications of this trick, then it's not quite so bad." What makes this hack so insideous is that it doesn't break your code; I breaks mine, months or years later. What's worse, once I find the true cause of the "bug" in my code I have lost confidence in the reliability of smart pointer. This means that every time I use smart pointer I have to consider and either eliminate or allow for the possibility that some programmer will have violated the semantics of the pointer somewhere in the system.

In Jonathan's defense, the technique he described comes straight from Smart Pointer Programming Techniques page on the boost web site. My quibble is not with Jonathan, but with the author(s) of boost::shared_ptr and that web page.

This has made me ruminate for the last few days on the various hacks I have encountered, or in some cases perpetrated over the years I have been developing software. Using the terminology from my early days as a programmer, I realized that there is a spectrum of hacks ranging from a "slimey hack" (one that works but makes you want to wash your mind out with lysol after you read it) to a "righteous hack" (one that makes you step back in awe at its beauty and clarity.)

So I thought I'd document some of these historic hacks and explain where I think they fit on the slime-to-righteous scale. Watch this space...

Swig vs C#

2005-02-10T07:26:00.000-08:00

I spent some time recently evaluating SWIG . It's a nice way to expose your C or C++ interfaces to perl or python (and possibly other languages) -- although it has some perfectly understandable limitation on what types you can use. These limitations are surmountable by writing some helper functions.

Unfortunately what the customer wanted was to access the interface "from .NET" (which I translated to: from C#. )

Swig has a -csharp option [Digression: Swig's argument are positional flags!!!!. That is "swig -csharp -c++ " doesnt work! You have to say swig -c++ -csharp. Not necessarily a confidence builder.] Unfortunately the entire documentation for the -csharp option consists of about 20 lines in the manual and these lines are not terribly helpful since they show how to access global C variables using Mono's version of C#.

"Google swig csharp" or "google swig c#" didn't produce anything more helpful. (actually this blog may now show up in that search and I've already explained more than any of the other hits did (chuckle))

There's a SWIG wiki page, but when I rummaged around on it the only relevant thing I found was a FAQ (with no answer) that turned out to be pretty useless.

Bottom line, I think it'll be easier to write a managed C++ bridge layer to expose the C++ interfaces to the .NET world. We'll see (if I ever get back to this issue.)

Linux on the Desktop

2005-02-07T09:19:00.000-08:00

Mitch Kapor as quoted in InfoWeek says:

A desktop version of Linux hasn't advanced as rapidly as the server version for a number of reasons. Microsoft's dominance in the desktop operating-system market is a big reason, but Kapor suggested another: the nature of desktop Linux development. Each component that comprises a desktop operating environment, whether the graphical interface, productivity applications, or browser, is being developed by different groups with little collaboration.

"It's not principally a technical issue," Kapor said. Rather, it's been a lack of motivation for these groups of developers to create a unified interface for users.

I say the reason Linux on the desktop isn't more widespread is the word processor in Open Office sucks (ahem, I mean has some fundamental flaws) -- even moreso than does Microsoft Word!

Real people (i.e. the rest of them) don't care from operating systems. They care about reading mail and writing documents and browsing the web. Two outta three aint good enuf.

Double Checked Lock Pattern reconsidered

2005-01-26T09:18:00.000-08:00

A recent Dr. Dobbs had an article pointing out the weaknesses of the Double Checked Lock Pattern(DCLP). For another presentation on this issue, see this article.

This pattern is most often used in the instance() method of a Singleton (nevermind that Singletons themselves tread mighty close to the dark side!) DCLP looks something like:


Filbert * Filbert::instance()

{

if (instance_ == 0)

{

   MutexGuard guard(instanceMutex_);

   if (instance == 0)

      instance_ = new Filbert();

 }

 return instance_;

}

The theory being that once you have your instance you never again need to lock the mutex.

The article raised two issues:
1) In a dual processor system with caching, the processor that doesn't create the Filbert could see the value of instance_ but still have cached, stale, information about the memory containing the new Filbert.

2) Even in a single processor system, the compiler is allowed to reorder statements as long as the result appears to be the same as one would see in a single processor, single threaded environment. Strange as it may seem, the compiler is allowed to store the address of the new Filbert into instance_ before calling the constructor of the new object.

#2 is easily resolvable. The root of the problem is that instance_ is overloaded -- serving both as a pointer to Filbert and as a bool indicating that Filbert has been created. Separating these two responsibilities produces the "triple checked locking pattern" (TCLP)


Filbert * Filbert::instance()

{

if(instance_is_valid_)

{

  MutexGuard guard(instanceMutex_);

  if(instance == 0)

    instance_ = new Filbert();

  else

    instance_is_valid_ = true;

}

return instance_;

}

Instance_is_valid_ is set only when thread one creates the Filbert and exits from the scope of the mutex, then thread 2 enters the scope of the mutex to find that the instance has already been created. I believe that this is safe on a single processor system for any legal reordering of the code. Alas, it still doesn't address the problem on a multi-processor system where each processor has its own cache.

It'll be interesting to see how cache is configured on the new multi-core processor chips that AMD & Intel are talking about.

The remaining problem with both DCLP and TCLP is that there is no way to delete the Filbert safely so resource leaks are gonna happen. Since the the need to delete usually comes at end-of-process time this is a non-issue on many (but not all) platforms (except for the purists and those running leak detection tools.) but still it would be nice to do it right.

Weavers' Guild meeting

2005-01-26T09:06:00.000-08:00

At the evening meeting of the Weavers' Guild of St. Louis Tina was giving a presentation on Complex Weaving. She used some of my network drafted work as one of her examples. I mentioned my current project -- the grey on grey scarf. Amy looked at me in disbelief and asked "Why?"

Sometimes I wonder. The weaving is going fine, but I may have invented the stealth pattern.

Subtle vs Invisible

2005-01-24T11:40:00.000-08:00

I've woven a couple of feet of this scarf. The new loom is working nicely (most of the time.)

On the other hand...

My goal was to produce a very subtle pattern in the cloth with the variation in the texture, not the color. I may have outdone myself on the subtle part. When does subtle become invisible, or even indetectable?

...maybe when I take it off the loom and finish the cloth the pattern will emerge. (hey, it could happen!) If not, well it'll be a nice, plain chenille scarf.

Pet peeve # (n+1) [ I lost count]

2005-01-11T06:54:00.000-08:00

Note to those who think in Linux: When someone asks you for help, please resist the urge to grab the keyboard and start typing. Instead dictate what needs to be typed. It has to do with giving fish vs teaching to fish. If nothing else it will make you aware of how truly arcane the "find" command is. ;-)

It's warped

2005-01-10T08:01:00.000-08:00

I tried to track my time dressing the loom for this project. Usually when someone looks at something I've woven and says "How long did it take you to weave that?" I stare at them blankly 'cause I really don't know. For this one, it's taken just over 8 hours to wind the warp, slay the reed, thread the heddles, and wind it on (I'm warping from front to back 'cause I always warp from front to back.) I guess I should also count the two hours Tina spent helping me wind it on. It wouldn't have been so bad but I made some mistakes winding the warp that led to some significant tangles that needed to be managed.

And then there's that unmistakable feeling when you finally open a shed and one thread -- right in the middle -- is not behaving properly. Aarrgghh... It was getting late and I was tired so I didn't even try to diagnose the problem -- I went to bed instead.

Of course that means I woke up in the middle of the night wondering whether I was going to have to rethread half the loom, hand tie a heddle or just cut out the bad thread and ignore the minor slaying glitch. It turned out to be the best possible outcome. The "missing heddle" was there, right beside the unattached thread. All I had to do was untie that thread from cloth beam, rethread, and reslay that single thread. Add another 1/2 hour to the "how long did it take?" answer, and it's ready to weave.

Weaving Project

2005-01-05T19:30:00.000-08:00

My current weaving project is a new (for me) experiment with network drafting and chenille. Chenille needs to be woven in a tight weave structure to prevent it from "worming." The most common form of network drafting is based on a four thread twill. (i.e. a mix of 1/3, 2/2, and 3/1 twill resulting in three thread floats -- however I realized that if you use a three thread twill (a mix of 1/2 and 2/1 twill) the longest float is only two threads. Alas, that means you have many fewer basic units to work with (think black and white rather than greyscale), but there are still some interesting possibilities.

For previous network drafting projects I have used different colors in the warp and the weft to make the pattern visible. For this project I'm using different textures. I have a 10-2 pearle cotton warp and a rayon chenille weft that are very close to the same color and weight (as close as I could find.) I'm hoping that the result will show areas of chenille velvet and areas of pearle cotton smoothness and luster. We'll see. At 24 epi x 12 inches I have a lot of threading to do before I get to see any results.

All of this is going to be woven on our 24 shaft Studio Dobby AVL loom with a compudobby 2. I'm only using 18 of the harnesses because there are only 6 "interesting" three thread twill units (001, 010, 100, 110, 101, 110.) I'm using an antique 386 computer with 16M of RAM and about 200M of hard drive to run the loom. Old computers never die...

Subversion on Debian

2005-01-05T07:00:00.000-08:00

I've spent the last week or so (spare time) setting up a debian linux system to support a subversion repository. Some notes to make it easier if I have to do it again. (I'll use "svn" to represent the directory in which repositories are created.)

Debian hint, not subversion related: Use the feta command rather than apt-get, et. al. Start with: apt-get install feta
feta install subversion
Pay close attention to user and group permission in the directory in which you wish to create the repository. Yes, you do need execute permission (?why--i donno?) I chose not to support direct file access except for repository maintenance. Hence: chmod 770 svn.
In addition to direct file access, there are two ways to provide remote access to the repository: svnserve, and DAV via apache. They coexist nicely.
The svnserv (svn://host/repostory) approach is easier to set up, but the apache (http://host/svn/repository) approach plays better with firewalls, etc. It also provides "free" web browsing of the repository which is cool!.
You configure svnserve permissions after creating the repository (via svnadmin create). To do so, edit the svn/repo/conf/svnserve.conf file which was automatically created when you created the repository (note: replace "repo" with the actual repository name.)
To install apache support, you need apache2: feta get apache2
You also need the module that supports svn via dav: feta get libapache2-svn
To configure permissions etc. for apache-based access, edit:
/etc/apache2/mods-available/dav_svn.conf
I added the default user under which apache runs -- www-data -- to the group that has access to the subversion directory.
I want to write some python utilities to help maintain the repository: feta install python2.3-subversion
I'm planning to take a look at pysvn: http://pysvn.tigris.org/

Note to myself: Start a blog today.

2005-01-04T08:08:00.000-08:00

Everybody's doin' it. There must be some reason.