Duff's Device
Dear DDJ,
Reading Ralf Holly's article "A Reusable Duff Device" (DDJ, August 2005) brought back memories of doing much the same thing around 1981. I was working on a proprietary system that had a limited instruction set and functionality. It's been many years, but my solution for unrolling a loop was to use a series of reentrant calls with an instruction such was an output to an I/O device executed just before the primary return. Calls queued up like that allowed me to do 2, 4, 8, 16, and so on executions of the instruction that needed to be repeated. As I recall, we did not have an adder or increment instruction, so looping was a bit of a problem.
Gary G. Little
Optimal Queens
Dear DDJ,
I enjoyed the article "Optimal Queens" by Timothy Rolfe (DDJ, May 2005), but it seems like a good time for a food fight. I made a few mods to Timothy's Queens.c code to adapt it for a Macintosh CodeWarrior C console program that automates testing using each of the four optimizations listed below for 4-18 queens. Timothy must enjoy sitting around waiting for each test to finish so he can enter the next set of n-queens and optimization parameters [24 times for n-queens 12-18], then wait again. I globalized a few vars, paired allocs with frees inside nested for loops, and let the program handle the permutations. Because times start exceeding one second at 13-14 queens, my times can be directly compared with Timothy's without too much picking of nits or other amusements.
His Dell desktop computer with a 2-GHz Pentium 4, OS not specified: No Optimization, 20:59:51; Wirth's Validity Check, 08:51:50; Permutation Vector, 03:52:36; both optimizations, 01:54:54; Total Time 35:39:11 (128,351 seconds). My Macintosh 2003 MDD Dual 1.25-GHz G4, OS X 10.3.9: No Optimization, 22:34:59; Wirth's Validity Check, 08:06:42; Permutation Vector, 03:49:08; both optimizations, 01:53:54; Total Time 36:24:45 (131,085 seconds). The Mac at ~63 percent MHz gets ~98 percent of the performance.
F.C. Kuechmann
Editor's Note: F.C.'s modified Queens.c code is available electronically; see "Resource Center," page 4.
Licensing Again
Dear DDJ,
Thanks to Jim Wiggins for his detailed and interesting note ("Letters," DDJ, March 2005). I do not object to licensing software professionals in one area: embedded computing. Many of the cases that are cited below are exactly that kind of development, and Ed Nisley does a fine job every month of describing exactly how different a world that is. Licensing for "embedded space" would need to include EE training as well as computer science, and some mechanical engineering and materials science couldn't hurt. I think this kind of training and education is well beyond that of the typical software engineer.
In fact, while I don't know about automotive engineering, much of the rest of the embedded industry does have special requirements levied on the way they do software. Some of the strongest requirements are imposed upon nuclear power stations, and I have some experience with those. They cannot use C++, Ada, Java, and there are restrictions on the use of C. (I can provide references but don't have the time right now.) Why? Because to assure predictability of the software, dynamic storage allocation is disallowed. There are also strictly technical benefits, such as it being easier to burn code into PROMs and stuff, and know what box it is in. Software and its algorithms must fit into a structured reliability discipline, and the reliability engineer makes the call on whether a change of means or algorithm is acceptable.
Indeed, this kind of really rigorous structure is absent even in NASA's work, and is certainly missing in most defense and FAA aerospace development. They need to get things to work, yes, but the reliability element is often hit or miss because (at the systems level at prime) contractors, quality control folks, and testers have little clout—[they are] seen as impediments to the company getting paid. FAA's government people have a strong hand, but they can get burnt if the company has good political ties.
Nevertheless, NASA and FAA demand detailed, written specifications and formal test plans and procedures, all under ruthless change control. Defense is supposed to work that way, but it depends upon the program and the character of the SPO running it. A lot of this is criticized in Congress and in the trade press, lamenting how long it takes them to get anything done in comparison to their apparently fleet-footed commercial brethren, along with much lathered on opinion about the superiority of free-market versus government-run programs. I strongly suspect they are swift because they can afford to not be rigorous. Could things be done smarter? Of course, they can be: Consider the Shuttle program versus the Mars Rovers. Alas, that's pitting NASA mainstream against Caltech-JPL.
And don't mention SpaceShipOne: As admirable as that project is, and as supportive of that effort I am, its scope is far more limited than what NASA must do and it builds upon a lot of work originally paid for by government. When someone needs to launch a satellite as part of a tsunami-warning network for the Indian Ocean, Scaled Composites can't do it—not soon, anyway.
There may be other niches in software development that admit comparable discipline. I should think that software running securities trading and monetary exchange arbitrage must be of necessity right on, considering the amounts of money that can be lost in a mistake. In principle, there ought to be a high-reliability version of Windows or at least Windows NT out there. There's a question of how to pay for it, however. High-reliability Linux? There ought to be that, too, and perhaps there will be. It's being used in quasi-embedded situations more and more.
As negative as I might sound, there are successes to tout. Relational database systems sell themselves to their customers primarily because of their design for data safety, reliability, and ability to recover from all kinds of misfortune, man- and nature-made.
I hope I conveyed what I think to be a collective frustration on the part of software users of all kinds with how long it takes to do anything in software. Some of that is, as I tried to express, part of the nature of the beast because it demands being very precise about things people normally aren't and don't have to be. But some of it is limitations of our own technology and smarts, stuff that, apart from important hardware assists, really hasn't changed since 1980. I simply do not see how licensing will get us to fix that.
Jan Galkowski
DDJ
