xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (04/12/91)
Not about to wade through Mike Rizzo's whole 435 article again at 1200 baud to quote four lines, but the claim was made in an inclusion that "the quicksort programmer would have less need than an assembly games writer to make his program faster". This shows an incredible lack of knowledge of programming as a field of endeavor. Some of the most valuable products, with the most invested man-years, and at the highest prices (and profits) for sale in the business data processing market place are sort packages, and they sell based entirely on speed. This is easy to confirm; just go pick up the latest copy of ComputerWorld, look for the full page sort package ads, and note the prominent position and size of the histograms comparing speed against the competitors' products. Why, you may ask, is speed so important in this field? Because 75% of _all_ cpu cycles in business data processing are spent doing sorts. Shave off 1/15th of the time needed to run the sort, and you've added 1/5th to the time available to do the rest of the job, and made the hardware 1/5th more productive. Write a faster sort and the world will pave your pathway with cold, hard cash. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
rjc@geech.gnu.ai.mit.edu (Ray Cromwell) (04/13/91)
In article <1991Apr12.123455.24220@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >Not about to wade through Mike Rizzo's whole 435 article again at 1200 >baud to quote four lines, but the claim was made in an inclusion that >"the quicksort programmer would have less need than an assembly games >writer to make his program faster". > >This shows an incredible lack of knowledge of programming as a field of >endeavor. Some of the most valuable products, with the most invested >man-years, and at the highest prices (and profits) for sale in the >business data processing market place are sort packages, and they sell >based entirely on speed. This is easy to confirm; just go pick up the >latest copy of ComputerWorld, look for the full page sort package ads, >and note the prominent position and size of the histograms comparing >speed against the competitors' products. > >Why, you may ask, is speed so important in this field? Because 75% of >_all_ cpu cycles in business data processing are spent doing sorts. >Shave off 1/15th of the time needed to run the sort, and you've added >1/5th to the time available to do the rest of the job, and made the >hardware 1/5th more productive. > >Write a faster sort and the world will pave your pathway with cold, hard >cash. > >Kent, the man from xanth. ><xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us> I agree with your post Kent, except for one important point. If Miranda was ported to the Amiga, the library functions would be written in very quick assembler. For instance, most C libraries for the Amiga have the QSort fnction written in optimized Asm. The only overhead is the C function call. Still, _algorithms_ are still far more important than minimal assembler optimizations. Check out the April issue of BYTE. Dave Quick (Amigan) made a minor improvement to the old bubblesort algorithm which makes it faster than a QSort! Also, there comes a time of diminishing returns where a 10% optimization in speed doesn't speed up the application much. A major overhead in databases is the file system uses, and how to store records in the best configuration possible to make lookup and searching fast. Shaving off a few cycles in a QSort won't bring cold hard cash to your door. Invent a totally new algorithm that no one thought of before and they might. (Besides, you could patent it and make everyone else license it. Although I don't like Software patents.) -- +-----------------------------------------------------------------------------+ | rjc@gnu.ai.mit.edu | // The opinions expressed here do not in any way | | uunet!tnc!m0023 | \X/ reflect the views of my self. | +-----------------------------------------------------------------------------+
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (04/16/91)
rjc@geech.gnu.ai.mit.edu (Ray Cromwell) writes: > I agree with your post Kent, except for one important point. If > Miranda was ported to the Amiga, the library functions would be > written in very quick assembler. For instance, most C libraries for > the Amiga have the QSort fnction written in optimized Asm. The only > overhead is the C function call. Still, _algorithms_ are still far > more important than minimal assembler optimizations. Check out the > April issue of BYTE. Dave Quick (Amigan) made a minor improvement to > the old bubblesort algorithm which makes it faster than a QSort! And so could I, and so could you, since the worst case for quicksort and bubble sort are both n*n (different worst cases), and bubblesort has a simpler and therefore faster algorithm. Take a look at what the Miranda quicksort algorithm posted does with already sorted data; it is not a pretty sight, which is why quickersort picks the median of three randomly sampled points from the interval as the next pivot. Quicksort is popular because its _average_ case is so much faster than bubblesort's average case, but the ratings are more usually based on _worst_ case. See "How to Lie with Statistics" for more information on this fascinating area of human activity. ;-) As far as canned libraries, sure, but that wasn't the point of the thread. The Miranda example showed the tremendous expressive power of a functional language; _any_ language can look good calling a canned routine, but not every language can look good in a "get it coded in five minutes and get on with your life" environment. This is a very common one in the business world. (I helped purchase several 4GLs in a part of my 30 years of programming I don't usually emphasize a lot on my resume). That is why the 4th generation languages are making such big inroads there. "Write it, run it, throw it away" is a lot bigger part of the business programmer's life than most CS or engineering side folks realize, and it is often the case that the extra run time of a one shot 4th generation language program is more than compensated by the saved CPU cycles getting the code to run in the first place. And in a universe where time is money, getting the results fast is often a lot more important than getting them from the cheapest running program. All of us old fossils that "write FORTRAN in any language" look at the new functional languages with awe. I've had the delight of programming in METAFONT a bit, a hybred functional/imperative language that is a nice fit to my equational view of the world; like several folks posting here, I wish more of the new languages were available on the Amiga for beer budget hackers. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>