Dr. Dobb's Journal October 2000
Dear DDJ,
I ran the sort routine described in "The Fastest Sorting Algorithm?" by Stefan Nilsson (DDJ, April, 2000) and compared the results with those of some other common sorts. Stefan's routine was the clear loser. The routines I tested against were a Shell sort, a system quick sort, and a custom quick sort. I submitted a list of 10,000 random 32-bit integers to each routine and got the following results:
Stefan's sort: 0.8 seconds.
Shell sort: 0.5 seconds.
System quick sort: 0.2 seconds.
Custom quick sort: 0.1 seconds.
The machine I used is an old VAX 4000-300. To check the results on a more modern machine, I reran the test on an Alpha 300. The sorts were faster by a factor of about 5, but the proportions remained the same -- Stefan's sort brought up the rear at eight times slower than the fastest sort in the test. My conclusion: For general sorting, stick with quick sort, unless there is a compelling reason to do otherwise.
Dennis Wilkinson
dennis.wilkinson@hsc.com
Stefan responds: Dennis, I agree with your conclusion. Quicksort is typically the best algorithm for general sorting. However, in the article we play a different game. Time is measured by counting machine operations and the sorting algorithm has to compete in a very hostile environment: The numbers may be arbitrarily long and may be chosen so as to maximize the running time of the algorithm. Even under these harsh conditions it's possible to sort n numbers in time proportional to n log log n.
Just for the records, in my tests on a Sparc station 5, using 1 million randomly distributed 32-bit numbers, the new algorithm was faster than heapsort and mergesort but slower than quicksort.
Arrogant or Dumb?
Dear DDJ,
I have just finished reading Jonathan Erickson's "Editorial" on Microsoft stupidity (DDJ, August 2000) and I have a few comments.
In the over 50 years that I have been associated with automatic computing engines, I have noticed that common sense is a very uncommon attribute amongst computing aficionados (or amongst many others, for that matter). Neither IQ nor education level has anything to do with it. (I once had a fellow working for me who had two PhDs; his lack of common sense was legendary in the laboratory.)
Besides, none of those low-level high-IQ Microsoft employees that you have met have anything to do with Microsoft policy. MS policy and practices are dictated by Gates and Balmer, neither of whom is noted for a lack of arrogance.
I believe that the source of the MS stupidity Jonathan reports is the combination of lack of common sense and too highly developed arrogance on the part of MS management. MS arrogance began to be noticeable about 10 years ago. The most recent MS software I own is the Microsoft BASIC PDS v7.1 compiler (for DOS and OS/2 1.0) dated 6-24-90. The arrogant response I received to a fully documented bug report, submitted shortly after I received the update, made me decide never to buy another MS product.
Murray Lesser
mlesser@attglobal.net
Dear DDJ,
As much as I detest defending Microsoft's behavior in any regard, Jonathan Erickson's "Editorial" in the August 2000 DDJ is somewhat misleading and misses a key point in the matter of the Slashdot/Microsoft dispute.
While some of the posts Microsoft demanded be redacted under DMCA were in fact merely "derogatory comments about Microsoft's approach," the critical point omitted in his editorial was the fact that most of these messages contained in whole or via a link the entire text of the Kerberos documentation being claimed as a trade secret.
The reason this is notable is that once a "trade secret" is made publicly available through any means, it can no longer be considered a "trade secret" at all. At that point, the only redress available to the previous owner of the trade secret is to pursue civil action against the parties that leaked it.
Microsoft was attempting to prevent such a loss of trade secret protection by exercising the new rights available to copyright holders under DMCA. Thanks to the "whack-a-mole" effect of many posters and public uncensored forums like Slashdot, they failed.
Kerry L. Bonin
Jonathan responds: Kerry, thanks for your note. Yes, I'm aware of the trade secret laws, but the point to be made (and perhaps I should have made it stronger) is that the material Microsoft was claiming as trade secret was already public information. Clifford Neuman published the information -- or something close to it -- several years before. Somewhat like trying to put the genie back in the bottle -- but when it isn't your bottle or your genie. Incidentally, from what I understand, Microsoft has back pedaled and all of the information is now available I think without restriction. Finally, we have an in-depth article on the Kerberos protocol coming up in the November 2000 issue. Hope you enjoy it.
Myth versus Reality
Dear DDJ,
I have been reading the patent articles and letters to the editor in DDJ and have decided that most people -- including engineers, managers, CEOs, and investors -- have a basic misunderstanding about what a utility patent is and does. Remember, patents are legal devices and as such do not mean what you would think. (None of this is to be construed as legal advice.)
A patent only allows you to stop others from making, using, or selling what you have claimed in your patent application. Read that again. It does not allow you to make, use, or sell what you have claimed in your application; it does not allow others to make, use, or sell what you have claimed in your application. A patent is a disabling device. You use a patent to get your lawyers to stop others from making, using, or selling what you have claimed in the patent application. You license a patent to stop the patent owner from taking you to court and getting a slam-dunk judgment against you. That is it.
Myth: Being awarded a patent for X allows you to make, sell, or use X.
Reality: Your patent for X may include some other patented device Y. The owner of the patent for Y can (only) stop you from making, using, or selling X. The patent for Y is known as an enabling patent. This is why companies cross license patents.
Myth: Patents were designed to advance the state of the industry.
Reality: The only advancing and innovation done is to keep others from taking you to court and causing you to lose a lot of money. Patents become public so that you know what others are trying to keep you from doing. The reason that you try to "design around" a patent is so that you will have a reasonable assurance that some other patent owner cannot take you to court and get that slam-dunk ruling that you infringed on that patent. A byproduct of this is (possible) advancement of the state of the industry but it is not the reason for patents.
Myth: Other companies are licensing a patent X so that patent must be valid and nonbreakable.
Reality: If the cost of licensing is much less than the cost of fighting the patent, then the companies will pay rather than incur the legal fees needed to fight the patent. That is why only deep-pocket companies fight patents.
Myth: You must look for and show all prior art for a patent application.
Reality: You only need to include those that you know. Most corporations do not want you to search for any prior art and will tell you "Do not look for any prior art." (I have been told this myself.)
Myth: Patents are awarded only if it is novel and unobvious.
Reality: The items claimed may be well known to people who work in [the] industry but the examiner may have never worked in this industry and may not know that they are already well known. The novelty and unobviousness is only within the incestuous patent system and has nothing to do with the real world.
Jeff Davis
Dear DDJ,
I've read Al Stevens' column about mingw32, readers' comments, and Al's response and could not avoid the sense of déjà vu. It seems to me that there is a trend in the C++ world toward more bloated, more feature reach and -- shall we say -- more monstrous language. Well, throughout the last decade we witnessed all the pundits decrying the bloated software that was swamping us out of Redmond. I hoped that DDJ would promote the opposite, but lo and behold, the new Standard Library and compiler, which are more bloated by order of magnitude, are being promoted as something good and necessary. So why do I have the sense of déjà vu? "In the beginning the Lord created Cobol and Fortran. And they were lean and mean, but they were not all things for all people. So the Lord created PL/I. And in PL/I you did not need to define your variable types, so the run-time modules needed to run type conversions all the time. And the result was as bloated as you may imagine, and the run time was quadrupled, and IBM could sell bigger and stronger (and pricier) hardware to compensate for it." Allow me please to lament the deceased virtues of C that was supposed to be a small language and replace the assembler in the quest to produce a more readable code for operating systems. And allow me to lament the seemingly dead virtues of Cobol that was supposed to allow self documenting business code. And allow me to lament the virtues of Fortran that was supposed to ease the life of scientists. I do not lament the aforementioned languages themselves. Some of them are virtually dead and some are having a revival (Cobol is fully OO today, a surprising fact). What I lament is really the virtue of small and purpose minded languages versus the C++ and PL/I monsters. You may promote bloated software and find reasoning for its need, but it will stay unnecessarily bloated nevertheless.
Thank you very much.
Ze'ev Atlas
zatlas@juno.com
DDJ