Departments
Departments Letters to the editor may be sent via email to cujed@mfi.com, or via the postal service to Letters to the Editor, C/C++ Users Journal, 1601 W. 23rd St., Ste 200, Lawrence, KS 66046-2700.
Editor,
In his review of the book, Secrets of the C++ Masters, Marc Kilian pointed out that primitive variable types such as int have neither constructors nor destructors. This is not strictly true. It is possible to declare a primitive using a constructor, e.g.
int x(5);instead of
int x = 5;One can also use such statements in a constructor's member initialization list, to set the data members. Admittedly, this is not a very useful feature, since the assignment operator accomplishes the same task just as effectively.
Virgilio "Dean" B. Velasco Jr.
Case Western Reserve UniversityYes, the scalar types are neither fish nor fowl in C++. But the increased use of templates is applying pressure to make them look more like classes in most implementations. -- pjp
Dear Sir,
I want to write a simulation program which runs under Windows NT. Is there a possibility to use a timer which is more accurate than +-1sec? I would need an accuracy of about 1 msec. Is there a possibility to work with timers in a DLL? Is there any place where I can find what is allowed in a DLL?
Thank you for your help.
L.Zyka
PARALLEL_TASKI don't know NT, but I have to believe it has timer services like this. Anybody care to supply details? -- pjp
Dear CUJ,
I found James Bell's article on nested for statements (July 1996) to be an interesting technique. However, I found the implementation to be a somewhat inappropriate use of recursion, and also had some room for performance improvement. The rewritten program is shown in Listing 1, which also has a few tweaks to simplify calling the subroutine (the temporary counters are mallocd, rather than passed in).
In my experience, it usually only pays to use recursion in "tree-style'' problems, where two or more subproblems need to be taken at a recursive loop level. In this case, we have a straight linear problem that lends itself very well to an indexing technique. When we're talking nested loops, we're usually talking performance being important. The 2x performance loss Bell noted can probably be directly traced to the overhead of the recursive subroutine calls. Elimination of the recursion also allows us to use register variable pointers rather than direct indexing of the arrays, which can also provide a substantial improvement.
I performed the following tests under AIX on an RS/6000 C10 with an 80mhz 601 RISC processer. I suspect that the 601 is more efficient at subroutine calls than the processor architecture Bell was using. My performance penalty was not as severe as his. For my purposes, I changed the "work'' subroutine to be a simple count to maximize the overhead of the looping algorithms. I also included a "benchmark standard'' best-case time using register integer variables in three loops. These times are based on a 200x200x200 (8,000,000 loop) test.
For-loop with registers: 1.021 seconds
No-recursion method: 1.343 seconds
Bell's for-loop with arrays: 1.433 seconds
Bell's recursion method: 1.776 secondsI would expect, under Bell's architecture, the results would be even more dramatic.
Regards,
Tim Behrendsen
Air-Shields Information Systems
tim@airshields.comRecursion is indeed a powerful technique, but I'm all for eliminating it wherever possible, particularly if good performance is important. You weren't the only one who had improvements to suggest. See Robin Leatherbarrow's article elsewhere in this issue, offering a solution in C++ -- pjp
Editor,
In the July 1996 CUJ, there is a call for performance in the Editor's Forum. I attempted months ago to share a square root algorithm that has excellent performance. It may be called a Newton-Raphson method, even though it is not the same algorithm as the Newton-Raphson method for finding zeroes of a function. I first came across it in the book Companion to Concrete Mathematics, Z.A. Melzak, Wiley-Interscience, 1973. As Melzak notes, the method converges very rapidly. The method is also now found in Chapter 3 of C Mathematical Function Handbook, Louis Baker, McGraw-Hill, 1992.
Theoretically, for 32-bit integers, this algorithm converges in about four iterations. With a suitable choice of initial value for x, it converges more rapidly. With the domain of fx limited to non-negative numbers, a good choice is to shift fx right by half as many bits as the highest bit set. For 32-bit integers, the algorithm then converges in three iterations.
The pseudocode iterator is:
x = (x + fx/x)/2,Where fx is the squared number for which we wish to find the square root, x. The implementation in Baker's book, square_rt, is sub-optimal, particularly in his initial guess of 1.
Knowing that a set number of iterations can be used, we can unroll the iteration loop into three calls to the iterator (which also eliminates the test for convergence). By defining a macro for the iterator (or using an inline function), more performance is gained. Further optimizations are possible. The divide by 2 can be replaced with a right shift, since the domain of fx is non-negative.
All very interesting, you may be thinking, but how does this algorithm compare to others. Aside from fairly traditional methods, such as using Chebyshev, or rational polynomials, some more unusual methods have been published recently. The use of a Binomial theorem algorithm was covered in Peter Heinrich's A Fast Integer Square Root, March 1996 DDJ. There was also an article in the March 1996 CUJ that used a "folded lookup table."
Performance of the Triple Newton-Iteration (careful where you place the hyphens, we'll call it TNI) method is faster than either the binomial or folded-lookup methods. On a typical 486, TNI is twice as fast as the binomial method. TNI is also more than twice as fast as the folded-lookup method.
The one exception to TNI's performance superiority can be on a processor with a very slow (or no) divide instruction. As Peter Heinrich responded, some machines are "still excruciatingly slow at dividing and multiplying'' (the ARM is one such). In that case, the binomial method may be faster.
Is TNI accurate? For 32-bit integers, it is accurate within half a bit. TNI also has the virtue of being simpler than other methods. As Peter Heinrich responded, "another gem to add to my toolbox!''
sdmaley@tasc.com
You've described the classic divide-and-average method used in every serious square root function I've ever seen, or written. As far as I know, it is indeed just a special case of Newton Raphson, for square root. You can sometimes improve its performance slightly by a more accurate initial guess, but the algorithm is extremely robust. It more than doubles the number of significant bits with each iteration. -- pjp
Dear Mr. Plauger:
Is it me, or is technology moving faster than anyone can hope to keep up with? I am a successful software practitioner of over 15 years, and have endeavored to keep current with all of the latest advancements occurring in my industry. Lately, however, I have been overwhelmed with the amount of information that must be consumed in order to remain a "general practitioner'' in software development. An extremely small and insignificant sample of what I am talking about would be:
OLE COM ActiveX CORBA SEI and the CMM C++ RPC and DCE MFC OWL SOMnot including all of the latest technology dealing with the Internet:
TCP/IP HTML (all variants) Java CGI/Perl PPPMy lists above also do not include all of the development environments that one must be knowledgeable about these days:
Visual C/C++ Borland C/C++ IBM Visual AgeOr, the OSs:
OS/2 Win 3.x Win 95 Win NT UnixPlease help me Mr. Plauger! It appears to me that the day of the "general practitioner'' in software development is quickly coming to a close, and I don't know which way to jump. A wrong choice in this industry can be disastrous since the learning curve for new environments, languages, and OSs can be quite lengthy.
I cut my development teeth on C. C has been kind to me and seems to do everything that I would like it to. However, in nearly every circle C is quickly being considered as pass and dated. I am reading a half-dozen books on C++, but the transition is very painful for a procedural sort of person like myself.
Is it just me, or has the world suddenly gotten a lot more complex?
Feel free to edit, rearrange, and/or publish any of the above. Knowing you must be busy I don't expect a direct reply, but I am interested in your treatment of my topic in any of your articles or books. I suspect that there are many people in my same position (perhaps, the "silent majority''), but I have not read anything about them.
Chuck Patterson
No, it isn't just you. For what it's worth, I'm about as overwhelmed as you are with the accelerating proliferation of programming specialities. My wife, Tana, and I just hired a woman in Germany to design and implement the Web site for our fledgling little company, Dinkumware, Ltd. Sure, I know a little something about HTML, Java, CGI, Internet domains, etc., but not enough. And I don't have time to learn it. (By the way, we're pleased with the results to date. If you're in the market for a Web designer with good technical and artistic sense, I'll happily supply an offline reference.)
On another front, I'm wrestling with seemingly endless networking issues with the LAN we've set up in our house. Router boxes, mail servers, domain-name servers -- each presents a mini Pandora's box of complexities that periodically flood my life with horrors when briefly opened. I'm still looking for a steady source of advice and hand-holding, to avoid learning much more about network arcana.
My response to these multiple assaults is to specialize. I try to stay on top of the handful of areas where I have genuine expertise. In all the rest, I aim to be an intelligent consumer at best, ignorant and demanding at worst. Yes, it means the end of an era for us old GPs, but I do still make an occasional house call. -- pjp
CUJ,
In the August issue David C. Keith asks if you know where he can locate GUI.LIB. The LIB sounded familiar so I searched my computers and found it in DOS_GU.ZIP. Unfortunately I don't remember where I downloaded it from, probably the Borland forum on Compuserve.
He can get the shareware product for $29 from:
Plain Design Inc.
P.O. Box 135
Midland Park, NJ 07432Unless you know of a way for me to get my copy to him.
Frank Westlake
Thanks. -- pjp
Editor,
While on the subject of future enhancements to the C++ Standard, (re David Jameson's letter printed in the August '96 issue), there are several other C++ extensions I would love to see (forgive me for repeating something that has already been covered):
1) An option of some sort that allows the compiler to pre-initialize an object to all zeros upon construction. For instance, you might be able to say:
class autoinitialize foo { foo(); etc.... };This would instruct the compiler to set the memory of any foo object to all zeros immediately before the constructor is called. This would initialize only foo portions of the object, not any base class portions, and naturally any aggregated member objects would still be constructed normally after that point. I believe C programmers have appreciated this feature of Standard C for static data. It is likely that many real-world classes would actually receive a performance benefit from this, and it could reduce coding time and initialization errors.
2) Enumerations encourage type safety and are under-used -- I always wondered why we cannot enumerate other scalar data types, or specify the exact storage size for an enumeration, for example:
enum float foo {ONE_D = 1.4142, TWO_D = 1.1892, UNITY = 1.0}; enum char foo {ESC = 27, SPC = 32};Without being able to deliberately size an enumeration's storage in memory, the feature becomes much less useful to low-level code that maps data into memory for hardware, where it could be of great benefit.
3) Allow inheritance of some sort from an enumerated type. This might solve the problem as mentioned by Carroll/Ellis in the August issue. Perhaps something like this:
typedef enum {START, STOP} TPlayerState; typedef enum TPlayerState: {PAUSE, RESTART} TDerivedPlayerState;This would essentially generate a new enumerated type that contains all four enumeration values. The compiler would guarantee that all values would remain unique.
John LaPlante
I like to think that the era of adding small enhancements to Standard C++ is about over, but I've been wrong on this topic before. -- pjp
Editors,
This letter was in response to David Tribbles in the June '96 CUJ. It's good to know I'm not the only one out here that feels as I do. Over the years I have designed and written some pretty good software and never found it neccessary to be as obscure, complicated, and tricky as the C++ world seems to think is the way to go. To me KISS is the best possible advice: "Keep It Simple Stupid.'' If a month after writing it YOU have trouble figuring it out, imagine the poor slob a year from now who picks it up after you are gone. I hope you have been buried in attaboys from all us hard working programmers out here who don't have the time or the guts to write letters to the editor.
I recently headed up a team designing and writing a real-time display system for the US Navy in Puerto Rico. The mandate was for Windows NT and Visual C++. I note this only to document that I am out here in the real world doing real-world things. The system was more or less completed ahead of schedule and pleased the customer to no end. I say more or less because a prime/sub contractor dispute caused my relocation to Rhode Island before the final acceptance of the system.
Based on my experience, about 30 years worth, I felt that while by no means an expert, I at least was comfortable with C++ and OOP. That is, until I picked up a copy of The C/C++ Users Journal, the June '96 issue. After going cross-eyed trying to understand anything in the bulk of the magazine I came to the letters and felt at least a bit vindicated by several of the submissions. The very first letter, the "Don't do that'' letter, indicates to me the basic mind set of far too many of today's programmers. Let's take something easy and see if we can't make it as complicated as possible.
Your letter was great and very much expresses my feelings. I also live in terror of having "to decipher some hotshot's...'' You might have added to that paragraph the tendency of most of these hotshots to include a liberal sprinkling of typedef statements that alias everything familiar to something unknown. Not only do we need to search through the "overloaded operators within...'' junk, but when we do find what we think we are looking for it's not what it seems because of some typedef statements hidden somewhere else.
The letter following yours from Randy Astle made a lot of sense and so did the response from the editors. C++ may be great for the "experts,'' but only a subset (small) is viable for us in the trench folks in the real world.
Just one more small thought. As a sometime manager and longtime software developer, I have defined two criteria for judging the success or failure of a piece of software:
1. It does what it's designed to do and makes the customer happy.
2. The whole package can be maintained by modestly competent, everyday Joe programmers. I can't afford to pay "hotshot'' wages to maintenance programmers.
If either of these criteria are not met the software is a failure.
Thanks for speaking up for all of us.
Bob Ritter
cu11rjr@island.syscon.com