Dear DDJ,
I was pleased to see the article about splay trees in your December 1992 issue. Because of their simplicity and ability to adapt to any pattern of usage, splay trees have been adopted in a number of important systems, including the Mach 3.0 kernel and the Microsoft Windows NT kernel.
Dean mentions the existence of a top-down variant of splaying, but does not give any details. Although slightly less general than bottom-up splaying, top down uses less memory and the code (see Example 1) is significantly simpler. The program is available via anonymous FTP from internet host 128.2.209.226 in /usr/sleator/public.
Daniel D. Sleator
Pittsburgh, Pennsylvania
/*
* An implementation of top-down splaying.
* D. Sleator
*
* This is adapted from simple top-down splay, at the bottom of page 669
* of "Self-adjusting Binary Search Trees" by Sleator and Tarjan, JACM 32,
* Volume No. 3, July 1985.
*
* The chief modification here is that the splay operation works even if
* the item being splayed is not in the tree, and even if the tree root
* of the tree is NULL. So the line:
* t + splay (i, t );
*
* causes it to search for item with key i in the tree rooted at t. If
* it's there, it is splayed to the root. If t=it isn't there, then the
* node put at the root is the last one before NULL that would have been
* reached in a normal binary tree search for I. (It's a symmetric order
* neighbor of i inthe tree.) This allows insertion, deletion, split and
* join to be easily implemented.
*/
typedef struct tree_node Tree;
struct tree_node {
Tree * left, * right;
int item;
};
Tree * splay (int i, Tree * t) {
Tree N, *1, *r, *y;
if (t == NULL) return t;
N. left = N. right = NULL;
l = r = &N;
for (;;) {
if (i < t->item) {
if (t->left != NULL && i <t->left->item) {
y = t->left; t->left =- y->right; y->right = t; t = y;
}
if (t->left == NULL) break;
r->left = t; r = t; t = t->left;
} else if (i > t->item) {
if (i < t->item) {
if (t->right != NULL && i < t->right->item) {
y = t->right; t->right =- y->left; y->left = t; t = y;
}
if (t->right == NULL) break;
l->right = t; l = t; t = t->right;
} else break;
}
l->right=t->left; r->left=t->right; t->left=N. right;
t->right=N.left; return t;
}
Dear DDJ,
In his October 1992 article, "Superdistribution and Electronic Objects," Brad Cox contends that superdistribution is a "silver bullet." I quite disagree.
First of all, you have the problem of when to call the charging routine: At program startup (an object's constructor)? When any method is called? When an important method is called? At regular intervals (time billing)? There is no solution that fits all programs, so a developer should think carefully about what portions of code will call the charging routine. (Can you imagine the ads? "Our program will cost you virtually nothing, while our competitor's program will cost you $1,000,000!")
Then there is the problem that I don't want to pay each time I use a program. One of the aspects of spreadsheets that made them popular was the fact that users could easily run what-if scenarios. You won't be as keen to experiment if each experiment (recalculation) costs you a dollar.
Developers will have an additional problem when using third-party libraries. These libraries will add cost to their program and they have no control over it. This will certainly influence programmers to call functions (create objects) in a nonoptimal way.
A fourth problem is the tamper-sensitivity of superdistribution. There will be a huge demand for hardware that charges a fraction of the real cost. Furthermore, there is no easy way to check if a program costs what its developer says it costs (and a new category of expensive software that does almost nothing: Phoneyware). And of course there is the threat of a virus costing you millions of dollars instead of just one hard disk full of information (and make no mistake: There will always be a virus threat, regardless of technological advances).
What advantages has superdistribution to offer? Mr. Cox mentioned software protection, information marketing, and free distribution. Software protection can be achieved with additional hardware (keys) and is as easy (or as difficult) as superdistribution hardware. When software protection is in place, information marketing is easy: Create information that can only be read by special programs. Free distribution must be limited to demonstration versions or versions that run for a limited amount of time. This will not be as easy as just distributing copies, but it certainly will not cost somebody money when they test a program that doesn't meet their expectations.
When you pay for usage you expect to reduce the availability of a resource (a very broad definition). When using a program, you are not actually costing a developer anything, so why should he get extra money? When I buy an alarm clock, I expect it to wake me up whenever I choose to use it. When I buy a compiler, I expect it to compile my programs whenever I ask it to. Have you ever seen an alarm clock that asks for a quarter each time it has to wake you?
Harald van Woerkom
Eindhoven, The Netherlands
Dear DDJ,
Joseph Newcomer's article, "Profiling for Performance," in the January 1993 issue was accurate, well written, and insightful. The simple distinction between knowing what a program is doing and why is very important.
I must point out, however, that profiling, subroutine timing, call counting, etc. are essentially heuristic methods of performance diagnosis. There is still a large element of educated guesswork involved, and this limits their effectiveness, especially in very large software. For example, in large programs the hot spot, if there is one, is often deep inside inaccessible subroutine libraries.
There is a nonheuristic but little-known method requiring no tool other than a decent debugger. Two major reasons programs are slow are that they: 1. do unnecessary calculation; and 2. call subroutines unnecessarily. Either way, they can be "caught in the act" by just examining the call stack at a few random points in time. To get a random sample of the call stack, just display it after hitting the manual interrupt key. You don't need many samples -- if something is taking 50 percent of your execution time, it will be glaringly obvious right away.
The call stack tells you both what the program is doing and why. You can see what subroutine is currently executing, and the line of source code that called it tells you why. And if you want to know why that was being done, just look at its caller, and so on. If the reason for a subroutine call isn't very good, maybe it can be eliminated. This will save time equal to the percentage of time that it was on the stack. This process can be repeated until the code is really tight.
This method is by far the most effective I have heard of. However, in asynchronous or event-driven software, it only does half of the job. It can locate hot spots and wasteful subroutine calls, but it can't identify needless event messages, unless they can somehow be backtraced.
Michael R. Dunlavey
Needham, Massachusetts
Dear DDJ,
Fortran execution times evidently do not compare as unfavorably to the execution times of C++ with Rogue Wave's Math.h++ library as Thomas Keffer claims in his article, "Why C++ Will Replace Fortran," in the December 1992 Special Supplement to Dr. Dobb's Journal. The graph in Figure 1 on page 44 of that issue shows that Microsoft Fortran, as tested, requires more than 35 percent more time for a long vector multiplication than Borland C++ 387 with Math.h++. Using a 16-MHz 80386 with an 80387 coprocessor, which the figure specifies, I compiled and ran the Fortran program cited there. However, I used Watcom Fortran 77/386, Version 8.5 instead of Microsoft Fortran. For a vector length of 4000, the multiplication required 40.5 milliseconds, only 13 percent more time than the approximately 35.8 milliseconds that Borland C++ 387 with Math.h++ required. In a Rogue Wave advertisement for Math.h++ in the November 1992 SIAM News, a nearly identical graph appears, but it shows that Borland C++ 387 with Math.h++ required approximately 38 milliseconds. Watcom Fortran needs less than 7 percent more time than that.
For this simple problem, a well-designed Fortran compiler with no special library produces a program that is almost as fast as that produced by a C++ compiler with such a library. Microsoft Fortran apparently does not provide a valid comparison. As for C++ alone being faster than Fortran, which seems to be the thrust of the article, no quantitative comparison is presented.
William J. Clover, Jr.
Chicago, Illinois
Tom responds: Alas, I have failed as a writer if Mr. Clover got the impression that my article was about how C++ is faster than Fortran. The point of the article was that C++ is far easier to manage, during both code development and maintenance, but just as fast. Indeed, real speed improvements come not with fiddling with compilers and languages, but with the ability to adopt whole new algorithms, perhaps too complicated to be managed safely and conveniently with Fortran. Because of its unique combination of manageability and efficiency, this is where C++ excels.
Dear DDJ,
Thanks for Greg Viot's article, "Fuzzy Logic in C," which appeared in the February 1993 issue. It was very informative and clear. However, a couple of things in the listings appear to need some adjustment.
First, the routine rule_evaluation() should include zeroing the values *(tp-> value) before it begins. If this is not done, the max() function ensures that the values keep increasing every cycle. Perhaps this is done somewhere else in the program, but I did not find it.
Second, the integer variables sum_of_ products and sum_of_areas, as well as compute_area_of_trapezoid(), can easily overflow. This can be overcome by changing the ints to floats.
James B. Calvert
Denver, Colorado
Greg responds: James uncovered two important oversights about the listings for the fuzzy-logic program. First, it is not clear from the listing that the initialization (zeroing) of the rule-evaluation outputs with each inference pass is necessary and where it takes place. It is assumed that this occurs in the get_system_inputs routine. Secondly, overflow of some of the integer data types could occur on computers with int size less than 32 bits. Both these issues should have been addressed somewhere in the listings. James's comments are greatly appreciated.
Dear DDJ,
In his fine article, "Cognitive Computing" (DDJ, February 1993), Colin Johnson discussed a number of real-world applications in which neural networks are used. I'd like to add to that list by mentioning Genesis (my company's PC-based neural-net development environment). In the past it has been used in applications from servo-control of a robot manipulator in real time to flight control for high-performance aircraft.
Presently, Genesis is being used to develop neural networks for such purposes as stand growth and yield prediction for the forestry industry. The network predictions provide a more efficient technique for forestry management, increasing forest productivity and protecting our forests. Genesis is also being used to develop nets for electric utilities by forecasting electrical capacity for long-term planning. This assists hydroelectric companies to successfully predict user demand, safeguarding against the threat of demand surpassing capacity.
Gary Josin
Neural Systems Inc.
Vancouver, British Columbia
Copyright © 1993, Dr. Dobb's Journal