home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume34 / flogger / part01 / OPTIMIZING < prev    next >
Text File  |  1992-12-18  |  4KB  |  93 lines
  1.  
  2. A brief word about optimizing code, in particular, code that
  3. calls a sorting function.
  4.  
  5. The qsort() that comes with most C implementations is fast enough for
  6. nearly all purposes.  The sort algorithms in this package are here
  7. mostly for intellectual curiousity.  The merge_sort algorithm is
  8. superior in some ways, mostly that it requires fewer callbacks to the
  9. comparison function, but that alone is no reason to sed -e s/qsort/merge_sort/
  10. over all your code.
  11.  
  12. Some general approaches to consider before borrowing one of these
  13. sort algorithms for use in your code, approximately in decreasing
  14. order of effectiveness:
  15.  
  16. 1. run prof or gprof to make sure the sorting is an actual
  17.    bottleneck; often, reading in the records to be sorted
  18.    takes more wall clock time than the sort itself and effort
  19.    spent optimizing the sort is completely pointless.
  20.  
  21. 2. Use your compiler's maximal optimization level when compiling
  22.    the comparison function.  This can result in a surprising 
  23.    improvement in performance.
  24.  
  25. 3. Hand optimize the comparison function.  Consider sorting on
  26.    a "predigested" key that requires less work to compare than 
  27.    the records themselves.  Make as few calls to other functions 
  28.    as necessary from within the comparison function.
  29.  
  30. 4. Reduce the size of the items being sorted.  Create an
  31.    array of pointers to records already existing elsewhere
  32.    in memory; the sort will then only have to shuffle the
  33.    pointers around rather than copy entire records.  Works
  34.    well in combination with #3.
  35.  
  36. 5. Consider maintaining a b-tree or other index which
  37.    lasts beyond program termination.  If the index is updated
  38.    infrequently and only one or two elements are added
  39.    to it at a time, the much-maligned bubble sort might
  40.    actually be of use.
  41.  
  42. 6. Plug in merge_sort from this package.  Expect only a slight
  43.    improvement.  But a degradation is possible as well: this merge
  44.    sort allocates a big chunk of memory, which can eat up swap 
  45.    space and slow things down.
  46.  
  47. 7. Make a copy of the merge_sort code and replace the calls
  48.    to the cmpr_func with the actual code of the compare.
  49.    Or if you have gcc, take advantage of inlining to achieve
  50.    the same thing.  Expect an even less noticeable improvement.
  51.  
  52. 8. If it's *still too slow*, write a sort that takes advantage
  53.    of the distribution of keys to calculate the position of a
  54.    record directly without having to compare it to other records.
  55.  
  56.  
  57. The comp.lang.c FAQ list has this to say about the subject of
  58. efficiency in general.  "Read it.  Learn it.  Live it."
  59.  
  60. ---------------------------------------------------------------------------
  61. 17.13:  How can I make this code more efficient?
  62.  
  63. A:      Efficiency, though a favorite comp.lang.c topic, is not
  64.         important nearly as often as people tend to think it is.  Most
  65.         of the code in most programs is not time-critical.  When code is
  66.         not time-critical, it is far more important that it be written
  67.         clearly and portably than that it be written maximally
  68.         efficiently.  (Remember that computers are very, very fast, and
  69.         that even "inefficient" code can run without apparent delay.)
  70.  
  71.         It is notoriously difficult to predict what the "hot spots" in a
  72.         program will be.  When efficiency is a concern, it is important
  73.         to use profiling software to determine which parts of the
  74.         program deserve attention.  Often, actual computation time is
  75.         swamped by peripheral tasks such as I/O and memory allocation,
  76.         which can be sped up by using buffering and cacheing techniques.
  77.  
  78.         For the small fraction of code that is time-critical, it is
  79.         vital to pick a good algorithm; it is less important to
  80.         "microoptimize" the coding details.  Many of the "efficient
  81.         coding tricks" which are frequently suggested (e.g. substituting
  82.         shift operators for multiplication by powers of two) are
  83.         performed automatically by even simpleminded compilers.
  84.         Heavyhanded "optimization" attempts can make code so bulky that
  85.         performance is degraded.
  86.  
  87.         For more discussion of efficiency tradeoffs, as well as good
  88.         advice on how to increase efficiency when it is important, see
  89.         chapter 7 of Kernighan and Plauger's The Elements of Programming
  90.         Style, and Jon Bentley's Writing Efficient Programs.
  91. ---------------------------------------------------------------------------
  92.  
  93.