home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Snippets / fastsort / READ ME < prev   
Encoding:
Internet Message Format  |  1994-05-10  |  4.9 KB  |  [TEXT/R*ch]
  1. From: tmdonahu@athena.mit.edu (Terence M Donahue)
  2. Subject: A faster sort
  3. Date: 7 Mar 89 19:36:58 GMT
  4.  
  5. I was curious about all of these "better faster stronger" sorting
  6. programs, so I decided to try them out myself using a Vaxstation 2000
  7. running Unix.
  8.  
  9. Functionality
  10. -------------
  11.  
  12. The man page for sort(1) says that it merges all the
  13. files together and sorts the entire mess.  Both fastsort and
  14. fastersort simply sort each file separately.
  15.  
  16. In addition, fastsort produced different output from sort and
  17. fastersort, as reported by diff.
  18.  
  19. Improvements
  20. ------------
  21.  
  22.     Use fputs() and putc() to output the sorted lines instead of fprintf()
  23.  
  24.     inline the strcmp function into compare().
  25.  
  26.     Ideally the compare() function should be built in to the qsort
  27.     routine, eliminating the significant amount of procedure call
  28.     overhead in the program.  This was not done in fastestsort
  29.     because my homemade quicksort is significantly slower than the
  30.     qsort in the C library here.  The qsort sources are not freely
  31.     distributable.  The inlining of the compare function would
  32.     result in a significant speed improvement.
  33.  
  34. Speed
  35. -----
  36.  
  37. All programs were compiled with gcc with optimization on. 
  38.  
  39. termcap is the first 1000 lines of /etc/termcap, a file with long lines
  40. dict is the first 10000 lines of /usr/dict/words in reverse order, a
  41. file with short lines.
  42. All times are in seconds
  43.  
  44. Method        termcap            dict
  45. ------        -------            ----
  46. sort         1.6u 0.5s 0:03        11.7u 0.4s 0:13
  47. fastsort    13.3u 1.2s 0:15     22.0u 1.9s 0:25
  48. fastersort     3.0u 0.2s 0:03        36.4u 0.4s 0:38
  49. fastestsort     1.2u 0.2s 0:01        13.1u 0.5s 0:14
  50.  
  51. So good old sort beats out fastsort and fastersort.  The latest version,
  52. fastestsort, does about as well as sort.
  53.  
  54.  
  55. Profiling
  56. ---------
  57.  
  58. fastsort on termcap
  59.   %   cumulative   self              self     total           
  60.  time   seconds   seconds    calls  ms/call  ms/call  name    
  61.  65.3       9.05     9.05        1  9050.00  9522.34  _qst [4]
  62.  10.3      10.48     1.43        1  1430.00 11010.00  _qsort [3]
  63.   7.6      11.54     1.06                             mcount (30)
  64.   5.8      12.34     0.80     2001     0.40     0.46  _fgets [5]
  65.   4.6      12.98     0.64     1007     0.64     0.68  __doprnt [7]
  66.   3.8      13.51     0.53    11095     0.05     0.05  _strcmp [8]
  67.  
  68. fastsort on dict
  69.   %   cumulative   self              self     total           
  70.  time   seconds   seconds    calls  ms/call  ms/call  name    
  71.  39.4      10.20    10.20                             mcount (25)
  72.  24.3      16.48     6.28   125441     0.05     0.05  _strcmp [5]
  73.  13.2      19.91     3.43        1  3430.00  9209.27  _qst [4]
  74.  10.2      22.54     2.63    10007     0.26     0.27  __doprnt [7]
  75.   4.8      23.77     1.23    20001     0.06     0.07  _fgets [8]
  76.   3.4      24.66     0.89        1   890.00 15690.00  _main [2]
  77.  
  78. fastersort on termcap
  79.   %   cumulative   self              self     total           
  80.  time   seconds   seconds    calls  ms/call  ms/call  name    
  81.  35.7       1.27     1.27                             mcount (21)
  82.  16.0       1.84     0.57     1000     0.57     0.62  __doprnt [7]
  83.  14.0       2.34     0.50    10900     0.05     0.05  _strcmp [8]
  84.   9.3       2.67     0.33    10900     0.03     0.08  _compare [5]
  85.   8.4       2.97     0.30        1   300.00  1037.79  _qst [4]
  86.   8.1       3.26     0.29        1   290.00  2290.00  _main [2]
  87.  
  88. fastersort on dict
  89.   %   cumulative   self              self     total           
  90.  time   seconds   seconds    calls  ms/call  ms/call  name    
  91.  47.6      23.96    23.96                             mcount (23)
  92.  21.0      34.54    10.58   218572     0.05     0.05  _strcmp [6]
  93.  12.5      40.83     6.29   218572     0.03     0.08  _compare [5]
  94.   9.9      45.82     4.99        1  4990.00 21027.27  _qst [4]
  95.  
  96. fastestsort on termcap
  97.   %   cumulative   self              self     total           
  98.  time   seconds   seconds    calls  ms/call  ms/call  name    
  99.  27.1       0.61     0.61                             mcount (22)
  100.  19.1       1.04     0.43    10900     0.04     0.04  _compare [5]
  101.  18.7       1.46     0.42        1   420.00   802.23  _qst [4]
  102.  10.7       1.70     0.24        1   240.00  1640.00  _main [2]
  103.   8.9       1.90     0.20        1   200.00   200.00  _read [6]
  104.   4.9       2.01     0.11     1000     0.11     0.17  _fputs [7]
  105.   4.0       2.10     0.09        6    15.00    15.00  _write [9]
  106.   2.2       2.15     0.05        2    25.00    25.00  _open [10]
  107.   2.2       2.20     0.05        1    50.00   900.00  _qsort [3]
  108.  
  109. fastestsort on dict
  110.   %   cumulative   self              self     total           
  111.  time   seconds   seconds    calls  ms/call  ms/call  name    
  112.  44.9      12.34    12.34                             mcount (21)
  113.  29.2      20.38     8.04   218572     0.04     0.04  _compare [5]
  114.  17.8      25.26     4.88        1  4880.00 12523.14  _qst [4]
  115.   2.8      26.02     0.76        1   760.00 15150.00  _main [2]
  116.   2.2      26.62     0.60    10000     0.06     0.07  _fputs [6]
  117.   1.0      26.89     0.27        1   270.00 13190.00  _qsort [3]
  118.